0
$\begingroup$

A two-player two-action simultaneous move game is represented by the following matrix:

┌───┬───┬───┐
│1\2│ C │ D │
├───┼───┼───┤
│ A │a\b│c\d│
├───┼───┼───┤
│ B │e\f│g\h│
└───┴───┴───┘

Player 1 has two actions, $A$ and $B$. Player 2 has two actions, $C$ and $D$. If player 1 plays action $A$ and player 2 plays action $C$ then player 1 gets utility $a$ and player 2 gets utility $b$. Similarly, for every other combination of actions. The objective of each player is to maximize their expected utility.

An example of such a game is Prisoner's dilemma for which $d = e < a = b < g = h < c = f$ given that $A$ and $C$ are betray and $B$ and $D$ are silent. From this it can be seen that the best action for player 1 is $A$ since $e < a$ and $g < c$. Similarly, the best action for player 2 is $C$. Hence, $AC$ is a state of Nash equilibrium.

One way to represent such games is to use the notation $a \leq b \leq c \leq d \leq e \leq f \leq g \leq h$ where the variables $a, \ldots, g$ may be arranged in any permutation and the intermediate $\leq$ operators may either be $<$ or $=$ since when instantiated the values of the varaibles $a, \ldots, g$ are known. Hence, the upper bound on the number of possible games is $8! \times 2^7 = 5,160,960$.

Unfortunately, this notation is not unique since equality is symmetric. Furthermore, the same game can be represented in upto 4 different ways depending upon what actions we assign to $A$ and $C$.

Another representation of such games is to assign to each state (i.e. $AC$, $AD$, $BC$ or $BD$) the values $0$, $1$, $2$ and $3$ representing which players would like to switch their action. Hence, $0$ denotes Nash equilibrium and $3$ denotes that both players would like to switch. Hence, the upper bound on the number of possible games is $4^4 = 256$.

Again, a lot of games might be repeated because the same game can be represented in upto 4 different ways depending upon what actions we assign to $A$ and $C$. However, this representation has the advantage of being unique with respect to notation. That being said, the difference between $5,160,960$ and $256$ makes me wonder whether there are some games that I'm missing.

So, my question is how do you calculate the number of unique two-player two-action simultaneous move games? Two games are considered the same iff the only difference between them is the choice of actions assigned to $A$ and $C$.

$\endgroup$
1
$\begingroup$

There are several classification of $2 \times 2$ games in the literature. I believe that the ones most useful to you are the following two.

1) Rapoport, A. and M. J. Guyer: 1966, ‘A taxonomy of 2 × 2 games’, General Systems 11, 203–214. (This classification assumes no ties in players' payoffs and derives 78 classes.)

2) Kilgour, D.M. & Fraser, N.M.: 1988, 'A taxonomy of all ordinal 2 × 2 games". Theor Decis 24: 99-117. (This classification extends the former one by allowing for ties and derives 726 classes.)

$\endgroup$
  • $\begingroup$ Would you be kind enough to provide links to the aforementioned articles or at least restate the ideas described in these articles? I'd really like to learn more about them. $\endgroup$ – Aadit M Shah Feb 25 '17 at 22:56
  • $\begingroup$ The two papers above are published but they are not open access. As far as I know, only the second one can be found on internet. For related material in open access, see mdpi.com/2073-4336/6/4/495 $\endgroup$ – mlc Feb 26 '17 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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