Cutting cake and matching pennies

Do you ever remember having to split a piece of cake with a friend or sibling when you were a child?  How did you do it?  I'd be willing to bet that one person cut the cake, and then the other person decided who got which piece of the cake.  It's probably one of the fairest ways to divide up a cake between two individuals.  Think about it for a moment.  If I am splitting a piece of cake with you, I know that if I cut one piece larger than the other, you will choose that piece (and I will get the smaller piece of the two).  My best option is to cut the piece of cake into two equal pieces (or as equal as I can make it).

As it turns out, this simple "game" is a perfect explanation of the so-called minimax theorem, developed by the Hungarian-American mathematician John von Neumann, one of the early game theorists.  Without getting too technical, the minimax theorem essentially states that the best strategy for any player in a non-cooperative, two-person, zero-sum game (the total winnings are fixed, so that whatever amount I win, you lose and vice versa) is to minimze the maximum possible loss.  In the cake game above, my best strategy is to minimize the maximum size of the piece of cake for you by cutting the two pieces as equally as possible.

There's another simple game that further illustrates the minmax theorem, called "matching pennies".  The game is fairly simple (maybe even as simple as the cake game above).  Two players simultaneously place a penny on the table in front of them - either heads up or tails up.  When the pennies match (both are heads or both are tails), player A gets to keep both pennies.  However, if the pennies do not match, player B gets to keep both pennies.  A simple 2x2 matrix of the strategies and pay-offs is shown below:

As you can see, if Player A plays "Heads" and Player B plays "Heads" (top/left quadrant of the matrix), Player A gets to keep Player B's penny.  How would you play this game?  As it turns out, there is not a pure strategy here.  The best strategy (according to the minimax theorem) is for each player to play heads and tails randomly, i.e. use a mixed strategy (sometimes Player A plays "Heads" and other times "Tails").  

One more variant of the "matching pennies" will hopefully drive home the point (credit for this one goes to William Poundstone in his book Prisoner's Dilemma).  Let's change the pay-off for a "Heads"/"Heads" match (for Player A) to $1 million:

If you analyze this particular version of the game, you can see (I hope) that Player B's best strategy is to play "Tails" (at the worst, Player A will lose a penny and in the best case, he or she will win a penny).  By playing "Tails", Player B never has to lose $1 million.  Okay, so with that in mind, your best strategy is to always pick "Tails" too, then at least you are guaranteed to win one penny.  But wait a minute.  If Player B knows that you are always going to play "Tails", he or she may be tempted to occasionally play "Heads" (otherwise, Player B always loses one penny).  

Game theory concludes that the best strategy (again, according to the minimax theorem) is to use a mixed strategy.  Player A should almost always play "Tails", but every once in a while he or she should play "Heads" just to keep Player B honest!  Similarly, Player B should almost always play "Tails" too, but every once in a while, he or she should play "Heads".

We will use the minimax theorem and the concept of "mixed strategies" to try to determine the best strategy for kicking penalty kicks in football (soccer)!