# Game Theory. Repeated Games. Strategy set.

I'm reading the book "Strategic games" by Krzysztof R. Apt. I have a question about the strategies in Prisoner Dilemma repeated game. On page 63 there is expression: "In the first round each player has two strategies. However, in the second round each player’s strategy is a function f : {C,D} × {C,D} → {C,D}. So in the second round each player has 2^4 = 16 strategies and consequently in the repeated game each player has 2 × 16 = 32 strategies. Each such strategy has two components, one of each round." I understood like 32 strategies each player has after second round, but there is 2^16 (quantity of function strategies of each player after second round), I think. What is the meaning of "32 strategies"?

• Can you explain a little bit why on the second round, the player has 16 different strategies? Aren't those affected only by the decisions made on the 1st round? If so shouldn't they be only 8?$(C_1,C_1)\rightarrow C_2,(C_1,D_1)\rightarrow C_2,(D_1,C_1)\rightarrow C_2,(D_1,D_1)\rightarrow C_2$ and $(C_1,C_1)\rightarrow D_2,(C_1,D_1)\rightarrow D_2,(D_1,C_1)\rightarrow D_2,(D_1,D_1)\rightarrow D_2$. Apr 24, 2012 at 15:51
• @chemeng: Strange coincidence; it looks like you got the correct count of $8$ strategies by an incorrect argument. The decisions are all independent; i.e. whether to play $C_2$ or $D_2$ after $(C_1,C_1)$ is a separate decision from whether to play $C_2$ or $D_2$ after $(C_1,D_1)$, so the number of strategies is $2^n$, not $2\cdot n$ as you counted. The reason the count is nevertheless only $8$ is that the player's own move in the first round isn't something to be responded to (see my answer). Apr 24, 2012 at 17:20
• @joriki: Though your answer is detailed, I'm a bit confused about the term $strategy$. The strategy of a player is the combination of only HIS choices no matter if choices by other players might affect thiose?For example in 2 rounds the choices a prisoner has are only 4 right?: {C,C};{C,D};{D,C};{D,D} Apr 24, 2012 at 17:27
• @chemeng: No. A strategy is an entire prescription for how to play the game, which includes a response to every possible move of the opponent. I suspect that you're confusing this with a game in which moves are played simultaneously; in that case a strategy is indeed only a choice for one player. However, a fully specified strategy for a game where decisions are made after other players' decisions have become known requires a response to each possible decision by the other players. Apr 24, 2012 at 17:32
• Yeah, i got it now!Thanks Apr 24, 2012 at 17:55

Unfortunately I'm not sure whether I follow the intended grammar of your last few sentences. If by "I understood like" you mean "I understood this as follows:", then I think you're misunderstanding the text. It's not saying that the player has $32$ strategies after the second round, but in a game with two rounds, that is, up to and including the second round.

However, this is actually wrong, because the player's own strategy in the first round shouldn't be considered as something unknown to be responded to, since it's part of the strategy itself. The correct way to count the number of strategies for the two-round game is one decision for the first round, and two decisions for the second round, one for each possible move of the opponent in the first round, for a total of three decisions, and thus $2^3=8$ different strategies.

Some investigations of the prisoner's dilemma assume that you can't implement your own strategy perfectly and there's a certain chance that you accidentally play the option you didn't intend to play. In case you forgot to state that this is how the book treats the game, then $32$ would be the correct count of the number of strategies in the two-round game, because then the player's own move in the first round would indeed be something to be responded to, or rather, the random choice that determines whether the player's first move is executed as intended needs to be responded to.

To specify a strategy for the entire game, I have to:

• Choose an element of $\{C,D\}$ for the first round.
• Choose, for each possible way the first round can be played, an element of $\{C,D\}$ for the second round.
• Choose, for each possible way the first two rounds could have been played, an element of $\{C,D\}$ for the third round.
• etc.

In general, if $A$ is the set of things I can do on any given round, and $B$ is the set of things my opponent can do, then, my strategy set is:

$$A \times [A \times B,A] \times [A^2 \times B^2,A] \times \cdots = \prod_{i=0}^\infty [A^i \times B^i,A],$$

where the notation $[X,Y]$ means the set of functions $X \rightarrow Y$.

That's assuming we choose pure strategies. If you want to allow mixed stratgies, then the strategy set is $$\prod_{i \in I}^\infty\langle A^i \times B^i,A\rangle,$$ where $A$ and $B$ are measureable spaces, and the notation $\langle X,Y\rangle$ means the set of Markov kernels from $X$ to $Y$.