I've just started following a game theory course. I'm still getting used to the concepts so I hope I can get some comment on my thoughts. This is a homework exercise.
Consider a four square board. There are two players, players X and O. The game consists of four rounds. In round 1 and 3 player X writes a 'X' in one of the squares. In rounds 2 and 4 player Y writes a 'Y' in one of the squares. It is not allowed to write something in a square in which something has been written.
Determine the total number of possible pure strategies for each player.
I think I can calculate the answer by using a more general statement.
Suppose player $i$ has $N$ information sets. Denote by $M_n$ the number of possible actions player $i$ can take at information set $n$, $n = 1,\ldots,N$. Then the total number of possible pure strategies of player $i$ is $\prod_{n=1}^{N} M_n$.
My attempt at a proof: creating a pure strategy boils down to picking from each information set a possible action. Therefore the number of possible pure strategies is equal to the number of ways you can pick an action from information set 1 times the number of ways you can pick an action from information set 2, etcetera, up to information set N. In otherwords, it is equal to $\prod_{n=1}^{N} M_n$.
If this is correct, then the number of possible pure strategies for player X are $4\cdot 2^{12}$. For player Y, this would then be $3^4\cdot 1^{24}$.
Is this right? If not, where do I go wrong? Thanks in advance.
Consider what a pure strategy for X will actually look like. It must have two components: it must specify X’s Round 1 move, and it must specify what X is to do in Round 3 for every possible response by Y in Round 2. The Round 1 component can obviously be chosen in $4$ ways. Suppose that it’s been chosen. Then Y’s $3$ possible responses are known, and a countermove must be specified for each of them. There are $2$ choices for each countermove, so the entire set of countermoves can be chosen in $2^3 = 8$ ways. In other words, for each choice of Round 1 move, X has $8$ possible strategies for Round 3, each covering every possible response by Y in Round 2. Since there are $4$ possible round 1 moves, X has altogether $4 \cdot 8 = 32$ pure strategies.
Here’s another way to see it. Number the cells of the board $1$ through $4$. A strategy for X can be specified as follows. First give the number of the cell in which X plays in Round 1. Then list remaining cells in numerical order. Finally, replace each of the three numbers in that list by $0$ or $1$; replacing number $c$ by $0$ means that if Y plays $c$ in Round 2, X will play in the lower-number of the remaining cells in Round 3, while replacing it by $1$ means that X will instead play in the higher-numbered of the two remaining cells. The strategy $3010$, for instance, means that X will play in cell $3$ in Round 1. If Y then plays in cell $1$, leaving cells $2$ and $4$ open, X will play in cell $2$, the lower-numbered one. If Y plays in cell $2$ in Round 2, leaving $1$ and $4$ open, X will play in $4$. And if Y plays in cell $4$ in Round 2, X will answer with cell $1$. Clearly every strategy for X can be uniquely specified in this way, and clearly there are $4 \cdot 2^3$ such specifications.