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"?
Game Theory. Repeated Games. Strategy set.
-
0Yeah, i got it now!Thanks – 2012-04-24
2 Answers
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$.