3
$\begingroup$

I am now reading Nash's 1951 paper Non-cooperative games and I have a question about the definition of symmetry of a game.

Symmetries of Games(Nash 1951)

If two strategies belong to a single player they must go into two strategies belonging to a single player. Thus if $\phi$ is the permutation of the pure strategies, it induces a permutation $\psi$ of the players.

Each $n$-tuple of pure strategies is therefore permuted into another $n$-tuple of pure strategies. We may call $\lambda$ the induced permutation of these $n$-tuples. Let $\xi$ denote an $n$-tuple of pure strategies and $p_{i}(\xi)$ the payoff to player $i$ when the $n$-tuple $\xi$ is employed. We require that if $j=i^{\psi}$, then $p_{j}(\xi^{\lambda})=p_{i}(\xi)$.

The permutation $\phi$ has a unique linear extension to the mixed strategies. If $$s_{i}=\sum_{\alpha}c_{i\alpha}\pi_{i\alpha}$$We define $(s_{i})^{\phi}=\sum_{\alpha}c_{i\alpha}(\pi_{i\alpha})^{\phi}$

The extension of $\phi$ to the mixed strategies clearly generates an extension of $\lambda$ to the $n$-tuples of mixed strategies. We shall also denote this by $\lambda$.

We define a symmetric $n$-tuple $\mathcal S$ of a game by $\mathcal S^{\lambda}=\mathcal S$ for all $\lambda$.

In Nash's notation, $c_{i\alpha}$ is the probability weight put on action $\pi_{i\alpha}$. i.e $\sum_{\alpha}c_{i\alpha}=1$ and $c_{i\alpha}\geq 0$. $\pi_{i\alpha}$ is the $\alpha$-th strategy in the pure-strategy space of player $i$. i.e $S_{i}=\{\pi_{i\alpha}\}_{\alpha=1}^{N_{i}}$ where $N_{i}$ is finite.

I don't quite understand the definition of a permutation of strategies. To me it seems that there are two interpretations for this.

The first interpretation is that it is a permutation of strategies within player $i$'s strategy space. For example, if a player's strategy space is $S=\{U,D\}$, then a permutation is $S'=\{D,U\}$. But if this is the case, how can it induce a permutation on players?

The second interpretation is that it is a permutation of a strategy profile. To be more specific, suppose in a game with players $1$ and $2$, with $S_{1}=\{L,R\}$ and $S_{2}=\{U,D\}$, and a strategy profile $\xi=(L,U)$. Then $(U,L)$ a permutation of $(L,U)$ as defined above and the induced $\psi$ permutes the players from $\{1,2\}$ to $\{2,1\}$.

However, if the second interpretation is correct, suppose the strategy profile is $(\frac{1}{3}L+\frac{2}{3}R,\frac{1}{4}U+\frac{3}{4}D)$, then a possible permutation of the mixed strategy profile is $(\frac{1}{3}U+\frac{2}{3}D,\frac{1}{4}L+\frac{3}{4}R)$, does it mean that a symmetric tuple of a game only exists when the pure-strategy spaces are the same for all players?

Thanks in advance!

$\endgroup$

1 Answer 1

3
$\begingroup$

I split my answer in two parts, one about how symmetries are defined and the other what the meaning of a symmetric tuple is.

  1. In principle, a symmetry is a permutation of the disjoint union of all pure-strategy spaces of all players. One can then derive symmetries on the tuples of pure strategies. If a symmetry $\phi$ maps a (pure) strategy of one player, let's call her Ann to a strategy of another player, Bob, then Ann and Bob must have the same number of strategies. To see this, note that $\phi$ maps by assumption any two strategies of Ann to strategies of Bob. Since $\phi$ is injective, Bob must have at least as many strategies as Ann. But $\phi^{-1}$ maps some, and hence all, strategies of Bob to strategies of Ann. Since $\phi^{-1}$ is injective, Ann must have at least as many strategies as Bob. Together, they must have the same number of strategies. The strategies need not have the same label. Also, a symmetry can also switch strategies of a single player.

  2. A tuple is symmetric if it is mapped to itself by every induced symmetry on tuples. Now, the more "symmetric" a game is, the more symmetries it has. But a game can be so asymmetric that the only symmetry is the trivial one that maps every strategy to itself. In such a game, every tuple is mapped by all symmetries (really, the only one) to itself. So every tuple in such a game is symmetric. If a symmetry in your example permutes $U$ and $L$, then it must also permute $R$ and $D$. Let's assume that these symmetries together with their inverses and the identity are the only symmetries. The profile $(\frac{1}{3}L+\frac{2}{3}R,\frac{1}{4}U+\frac{3}{4}D)$ is not a symmetric tuple, because it is not mapped to itself. However, the tuple $(\frac{1}{3}L+\frac{2}{3}R,\frac{1}{3}U+\frac{2}{3}D)$ would be symmetric.

$\endgroup$
3
  • $\begingroup$ Can you elaborate a bit more on the statement that $(\frac{1}{3}L+\frac{2}{3}R,\frac{1}{3}U+\frac{2}{3}D)$ is a symmetric tuple? It's mapped to $(\frac{1}{3}U+\frac{2}{3}D,\frac{1}{3}L+\frac{2}{3}R)$ right? So the order of the entries doesn't matter? To my understanding, a symmetric tuple implicitly assumes that all pure-strategy spaces are the same for all players. $\endgroup$
    – John
    May 18, 2022 at 19:29
  • $\begingroup$ Because in the Nash's definition, a tuple $S$ is called symmetric if $$S=S^{\lambda}$$ for all permutation $\lambda$. This seems to require that all strategy spaces to be the same. If we want to accommodate the case you mentioned in which the labels can be different, then we should say that a tuple is symmetric if $j=i^{\psi}$, then $p_{j}(S^{\lambda})=p_{i}(S)$ where $\psi$ is the induced permutation on players. Intuitively, this means that a tuple is symmetric if the payoff only depends on the strategy profile rather than who plays it. (An explanation from Wikipedia) $\endgroup$
    – John
    May 18, 2022 at 19:49
  • 1
    $\begingroup$ Nash is not very explicit, but I think it is natural to take the strategy spaces (that Nash does not introduce notation for) to be disjoint. Then, the order becomes irrelevant, one can recover the player from the strategy. Indeed, Nash introduces symmetries as being permutations of strategies, not $n$-tuples. There is no explicit statement that they should be applied coordinate by coordinate. I think my reading of "induced permutation" of a tuple is more natural. $\endgroup$ May 18, 2022 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.