Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You've overcounted X's strategies. They don't need to have a second move prepared for situations their first move makes impossible. –  Chris Eagle Sep 7 '11 at 15:44
    
@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? –  Stijn Sep 7 '11 at 17:34
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for your answer. But why is the generalized statement I wrote in my question? That statement came out of another exercise which I tried to prove. Am I misinterpretting it wrong? Also, am I still correct in saying that player Y has 3 possible moves in round 2 and 1 possible moves in round 4, and therefore has $3^4\cdot 1^{24}$ possible pure strategies? –  Stijn Sep 11 '11 at 11:03
    
@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. –  Brian M. Scott Sep 11 '11 at 21:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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