To Sam: On Mixed Strategies in the Repeated Coin Game
What follows is an analysis of the possible use of mixed strategies in creating a subgame perfect Nash equilibrium in the repeated coin game, which is defined in the next paragraph.
[elitist] If you don't understand the last sentence, this post probably isn't for you. [/elitist]
Suppose you have a large, finite pile of coins sitting on the table in front of you, and the owner of those coins poses you and the guy standing next to you a proposition: each of you may take 1 coin per turn, which allows the game to go on, OR you may choose to take 2 coins, which ends the game at that point, leaving the remaining coins unclaimed. The turns are sequential, not simultaneous, and the pile of coins is visible, so you could conceivably count how many coins remain. The goal of the game is to maximize your own coin total at the end of the game. What set of complete strategies represents a subgame perfect Nash equilibrium in this game?
Mixed Strategy discussion:
Suppose we employ a mixed strategy of a linearly declining probability of taking 1 coin in a 12 coin game. On the first turn, we assign a 100% probability of taking 1 coin. On the next turn (10 coins remaining if we reach it), we assign an 80% probability of taking 1 coin, and a 20% probability of taking 2 coins. On the third turn (8 coins remaining), a 60% probability of taking 1 coin. On the fourth turn (6 coins remaining), a 40% probability of taking 1 coin. On the fifth turn (4 coins remaining) a 20% probability of taking 1 coin. On the sixth turn (2 coins remaining), we always take 2 coins, naturally.
Our opponent sees our strategy profile (since Nash equilibria require that we assume perfect information about strategy profiles), and creates the following strategy profile: 80% probability of taking 1 coin on turn 1 (11 coins left), 60% probability of taking 1 coin on turn 2 (9 coins left), 40% probability of taking 1 coin on turn 3 (7 coins left), 20% probability of taking 1 coin on turn 3 (5 coins left), certain to take 2 coins on turn 4(3 coins left).
A Nash equilibrium requires that no player be able to switch strategies unilaterally and improve his outcome. Unfortunately, this collection of strategy profiles does not meet that requirement. Player 1 can improve his outcome by employing a more steeply declining probability distribution, or by simply taking 2 coins for certain on turn 4, one step ahead of player 2. The problem with mixed strategy Nash equilibria in this game stems from the fact that whichever player finds himself in the situation of having 2 coins remaining MUST choose to take 2 coins 100% of the time in that situation. Any other play there is clearly suboptimal, and that player's outcome could be improved by unilaterally changing his strategy to always take 2 coins there. Unfortunately, that means that the other player knows that the optimal strategy in that position is to always take 2 coins, and that he will thusly be best off if he takes 2 coins at a 100% rate the turn before.
Thus, even in a mixed strategy setting, the unraveling we see in calculating the subgame perfect Nash equilibrium in the coin game still occurs, and the only subgame perfect Nash equilibrium exists at (Take 2 coins first turn, Take 2 coins first turn).
[elitist] If you don't understand the last sentence, this post probably isn't for you. [/elitist]
Suppose you have a large, finite pile of coins sitting on the table in front of you, and the owner of those coins poses you and the guy standing next to you a proposition: each of you may take 1 coin per turn, which allows the game to go on, OR you may choose to take 2 coins, which ends the game at that point, leaving the remaining coins unclaimed. The turns are sequential, not simultaneous, and the pile of coins is visible, so you could conceivably count how many coins remain. The goal of the game is to maximize your own coin total at the end of the game. What set of complete strategies represents a subgame perfect Nash equilibrium in this game?
Mixed Strategy discussion:
Suppose we employ a mixed strategy of a linearly declining probability of taking 1 coin in a 12 coin game. On the first turn, we assign a 100% probability of taking 1 coin. On the next turn (10 coins remaining if we reach it), we assign an 80% probability of taking 1 coin, and a 20% probability of taking 2 coins. On the third turn (8 coins remaining), a 60% probability of taking 1 coin. On the fourth turn (6 coins remaining), a 40% probability of taking 1 coin. On the fifth turn (4 coins remaining) a 20% probability of taking 1 coin. On the sixth turn (2 coins remaining), we always take 2 coins, naturally.
Our opponent sees our strategy profile (since Nash equilibria require that we assume perfect information about strategy profiles), and creates the following strategy profile: 80% probability of taking 1 coin on turn 1 (11 coins left), 60% probability of taking 1 coin on turn 2 (9 coins left), 40% probability of taking 1 coin on turn 3 (7 coins left), 20% probability of taking 1 coin on turn 3 (5 coins left), certain to take 2 coins on turn 4(3 coins left).
A Nash equilibrium requires that no player be able to switch strategies unilaterally and improve his outcome. Unfortunately, this collection of strategy profiles does not meet that requirement. Player 1 can improve his outcome by employing a more steeply declining probability distribution, or by simply taking 2 coins for certain on turn 4, one step ahead of player 2. The problem with mixed strategy Nash equilibria in this game stems from the fact that whichever player finds himself in the situation of having 2 coins remaining MUST choose to take 2 coins 100% of the time in that situation. Any other play there is clearly suboptimal, and that player's outcome could be improved by unilaterally changing his strategy to always take 2 coins there. Unfortunately, that means that the other player knows that the optimal strategy in that position is to always take 2 coins, and that he will thusly be best off if he takes 2 coins at a 100% rate the turn before.
Thus, even in a mixed strategy setting, the unraveling we see in calculating the subgame perfect Nash equilibrium in the coin game still occurs, and the only subgame perfect Nash equilibrium exists at (Take 2 coins first turn, Take 2 coins first turn).