1-to-N or N simultaneous Zero sum games

233 Views Asked by At

Consider a zero-sum game between a row player $R$ and a column player $C$. Finding the NE is quite straightforward. Now consider the row player is going to play the same game with $N$ different column players $C_1$ to $C_N$ (i.e., $N$ two-player zero-sum games) under the following assumptions:

  1. Every single game between $R$ and $C_i$ has its own payoffs table. That is, under the same strategy, the payoff gained by $C_i$ is different from that of $C_j$ (and consequently by $R$). Thus, there will be $N$ different payoff tables for $N$ different games.
  2. The row player's strategy is applied to all $N$ games. That is, the row player should select a single strategy for all $N$ games.

To make this more clear, let's consider a simple game between $R$ as the row player with two strategies (A and B), and $C_1$ and $C_2$ as the column players. Each column player $C_i$ plays with two strategies $A_i$ and $B_i$, respectively. The first and the second column are the $C_1$'s possible strategies and the third and the fourth columns are the $C_2$ strategies. The table shows the payoff of the rows player. So, the payoff of the column player is the negative of the payoff of the row player.

The question is, can we say this is still a zero-sum game? If yes (which I don't think it is because the definition of zero-sum games does not apply here), what is the NE? If no, under what categories of the games should I consider it? Any more discussion would be appreciated.

$$\begin{array}{c|c|c|c|c|} & A_1 & B_1 & A_2 & B_2 \\ \hline \text{A} & 1 & -1 & 2 & -2 \\ \hline \text{B} & -1 & 1 & -1 & 1 \\ \hline \end{array}$$

2

There are 2 best solutions below

1
On

You can consider it as a game between the row player and the whole group of column players if you don't care which of the column players wins and which loses. Then it is clearly a zero-sum game with the column player having $2^N$ strategies. For $N=3$ the strategies could be numbered in binary from $000$ to $111$ representing which strategy of each pair the column player uses. Each column would be the sum of the applicable three columns in your original matrix.

If you don't group the column people, it is not a two person game, but is still zero sum. The total gain of all the players is zero. The row player then might play for best advantage, which would give the same strategy as above. The row player might also try to benefit one column player at the expense of another.

0
On

A generalization of this concept is described here: "Zero-sum Polymatrix Games: A Generalization of Minmax". Think of each player as a node in a graph, each node has a set of strategies to choose from, and an edge between nodes means a zero-sum game between the two players. If the payoffs for each strategy profiles add up to zero, then it is still ultimately a zero sum game. The Nash equilibria can be found using linear programming as detailed in the paper.