CP. The Prisoners Dilemma
After discussing last week’s Mismatched Pennies Game, Kyle and Chaim are hauled off to jail!
First, here are some of the details of the calculation for mismatched pennies.
The expected payouts (from Kyle’s point of view) are
HH -> -3
HT or TH -> 2
TT -> -1
1) Is it really true, if Kyle steadily plays 3/8ths Heads and 5/8ths Tails, that Chaim can’t adjust his own strategy to take advantage of Kyle? Suppose Chaim plays some fraction p Heads and then (1-p) Tails. Then we expect to see
HH exactly 3/8 * p of the time, for an expected payout of 3/8 * p * (-3)
TH exactly 5/8 * p of the time, for exp. payout of 5/8 *p *2
HT exactly 3/8 * (1-p) of the time, for exp. payout of 3/8 * (1-p) * 2
TT exactly 5/8 * (1-p) of the time for an expected payout of 5/8 * (1-p)*(-1)
The total expected payout is thus
3/8 * p * (-3) + 5/8 *p *2+3/8 * (1-p) * 2+5/8 * (1-p)*(-1) =
-9/8 p + 10/8 p – 6/8 p + 5/8 p – 5/8 + 6/8 = 1/8
No matter what p is chosen, Kyle will come out 1/8th of a penny ahead, per game, on average, in the long run.
Similarly, if Chaim chooses to play 3/8ths H and 5/8ths T, Kyle cannot exploit this and do any better.
As discussed in the podcast, there is a quick trick for calculating this, at least for simple games like this one.
2) What’s really going on? Why is von Neumann’s theorem true, for more complicated games?
Really, one can think of the expected payout as a function of the various probabilities assigned to each outcome. If you think about it, this function is quadratic– each term will have degree at most two– and the von Neumann minimax is a search for a saddle point. The existence of such saddle points– unless the game is always tilted to one inevitable outcome– is straightforward enough, but is beyond what we can discuss here.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Shawn said,
November 21, 2011 at 10:28 pm
The way to find a mixed-strategy that “cannot be exploited” is to find your mixture of strategies that will make your opponent indifferent between his or her pure strategies. In symmetric games such as rock-paper-scissors, it’s easy to see that the mixed-strategy Nash equilibrium occurs when each player chooses to play each pure strategy with 1/3 probability. However, since both players have the symmetric payoffs, it’s not obvious that this is because Player A is choosing a mixture that would make Player B “break even” (at least in expectation) regardless of what strategy he or she chooses. If a game starts out symmetric but then becomes lopsided, as in the mismatched pennies game, it is the player whose payoffs did not change who should adjust their mixture in order to fall back into equilibrium. Mixed-strategies are definitely one of the most difficult concepts in game theory, but I think this particular principle at least can be thought of relatively intuitively. If I know that my opponent has the same expected payoff from both of his or her strategies, he or she will likely choose to play the pure strategy that gives the highest expected payoff from the strategy that I play more often. For example, if Player n gets 2 when he chooses left and I choose up, 2 when he chooses right and I choose down, and 0 otherwise, he’s going to always play left if I choose up more than half the time and he will always play right if I play down more than half the time. To get him not to have a pure strategy be a strict best response, I have to mix evenly between up and down. In other words, the expected payoff from playing either pure strategy against my mixture should be equal. That is what allows a mixture to be a best response (albeit only weakly).