So what is the Matching Pennies Problem anyway (MPP)?
Matching Pennies is a simple game but has very interesting properties that can be applied to many other types of complex games.
There are two players, and each select either Head or Tail. Here are the rules of the game:
– if the choices differ (one player chooses Head while the other Tail), Player 1 pays Player 2 $1
– if the choices are the same (both players select Head or both select Tail), Player 2 pays Player 1 $1
| Head | Tail | |
| Head | 1,-1 | -1,1 |
| Tail | -1,1 | 1,-1 |
This is a Zero-sum game in that one player’s win would mean a loss for the second player. In another words, the choices are diametrically opposed to one another. This game is a strictly competitive game and no amount of collaboration will help the situation.
Recap: To be in Nash’s Equilibrium, no player has an action yielding an outcome that he prefers to that of the current action, given that every other player chooses his equilibrium action. In other words, no player can profitably deviate, given the actions of the other players. In the MPP, if Player 2 and Player 1 have chosen Head, Player 2 end up paying Player 1. If now Player 2 chooses to change his choice to Tail, so can Player 1 and the results are the still the same. You can see what happens from Player 1’s perspective if the users’ selections were not the same to start.
But there is not a single solution that “stands” out in that there is no solution (or strategy) that has a better outcome for one player over the current action.
Art Sedighi