1
$\begingroup$

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.

  • 0
    @Chris, the way I've constructed the game tree of this game, that shouldn't be a problem. However I do feel that $2^{14}$ is way too high... Where do you think the problem lies?2011-09-07

3 Answers 3

3

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.

  • 0
    @Stijn: I’m not comfortable commenting on the general statement, because I’m not sure how the author is defining *information set*. Y does have $3^4$ pure strategies: each one specifies what move he would make in response to each of X’s $4$ possible first moves, and of course he needn’t specify anything for his 2nd move, since it’s forced.2011-09-11
0

I'm a beginner myself, but I think the difference boils down to the fact that the generalized statement mentioned (and information sets concept) apply to imperfect information games, while the example given is one with perfect information because the players know the complete history of the game.

This means that the number of information sets at each move is a singleton. And thus, the number of pure strategies is the product of the number of moves at various points of the game, which for X is $4 \times 8 = 32$ (which is actually $4(1) \times 8(1) = 32$)(OP, the fault in your argument is that the $12$ in the exponent of $2^{12}$ comes from $4\times3$ in round 1 and 2, but here you're recounting the $4$).

For Y, the number of singleton information sets is 4(each corresponding to round 1 of X) and for each set, has 3 moves of his own and thus the total number of strategies he can choose from is $3^4$(Think of each strategy as 4 consequent digits, the $i^{th}$ digit representing the move Y makes should X mark the cell $i$. Now see that there are 3 choices for each digit).

This link will describe the information sets better: http://lcm.csa.iisc.ernet.in/gametheory/ln/web-ncp2-efg.pdf