Game theory -  A Tutorial

Jean Walrand

Static: Matching Pennies

Alice and Bob each show one of the faces of a penny. If they show the same face, Bob gives Alice $1.00; otherwise, Alice gives Bob $1:00.  This game is summarized by the following reward matrix (left):

How should Alice and Bob play , possibly in a randomized way, to maximize their expected reward?

Not surprisingly, they should each choose H or T randomly with probability 1/2.

To see this, assume that Bob chooses H with probability b and Alice chooses H with probability a.

It is easy to see that if a > 0.5, then the best choice for b is b*(a) = 0, since Bob tries to present a face that does not match Alice’s.  The function b*(a), called the best response, is shown in the right-hand part of the figure, and so is a*(b).  These best response functions have only one intersection: (0.5, 0.5). What this means is that there is only one pair of choices for (a, b) where no player has an incentive to deviate unilaterally. Thus, if (a, b) = (0.4, 0.5), then Bob has an incentive to deviate from 0.5 because b*(0.4) is not equal to 0.5.  Only the intersection of the two best response functions is such that no player wants to deviate unilaterally: this point is called a Nash Equilibrium.

Thus, the game of Matching Pennies has a unique Nash Equilibrium, and it is randomized. One says that the strategies are mixed (for non-deterministic).