Recognizing that a Nash equilibrium must exist in mixed-strategy games

The pure strategy version of Rock, Paper, Scissors has no Nash equilibrium. But if the strategies were used with a given probability — for example, Karen played rock with probability 1/3 — then you’d see a very different outcome. What does it mean to play a strategy with probability 1/3? It’s as if Karen had a pie chart divided into thirds: one third for rock, one third for scissors, and one third for paper. Before choosing, she spins a pointer on the pie chart, and where it lands is the move or action that she makes. When players mix their strategies, we can show that at least one Nash equilibrium must exist in any finite game. The equilibrium strategies in this case are probability mixes that no player has an incentive to change.

Finding a Nash equilibrium by elimination

The typical way of finding a Nash equilibrium in the strategic form of a game is by eliminating any strategies that can’t be optimal to play. This method relies on the concept of a dominant strategy.

A strategy is dominant if, regardless of what any other player does, playing that strategy results in a higher payoff. A strategy can be dominant in two ways:

• Weakly dominant: If it’s always at least as good as any other given strategy in terms of payoff the player gets
• Strongly dominant: If it always gives a higher payoff than any other possible strategy the player could choose

A good way to solve a game is to look at its strategic form and eliminate any strategies that are dominated. This approach involves looking at the reverse of a dominant strategy, that is, eliminating any strategy that you know a rational player won’t play, because it is dominated irrespective of the moves of another player by another strategy.

Figure 17-2 shows an example of a strategic form of game. The method just described is called the iterated elimination of dominated strategies. It means, very simply, that you go eliminate one by one any strategy that wouldn’t be chosen by a player, because playing another strategy would lead to higher payoffs no matter what the other player does. If you arrive to a point where no player has any incentive to change strategy, then you’ve “solved” the game. You found the Nash equilibrium. In the game in Figure 17-2, start by eliminating Right for the Colm player (she always does better playing Middle than Right). Once Right is eliminated for Colm, then we can eliminate Down for Rowe. Once Down is eliminated, then we can eliminate Left for Colm, and voila we have found the Nash Equilibrium (Up, Middle) and you can award yourself a gold star.

Solving a repeated game by backward induction

A repeated game, such as a repeated version of the Prisoner’s Dilemma (described in detail in Chapter 16) takes place over many rounds, and the overall payoffs are computed at the end of the game. The matrix you get by looking at the payoffs for one round is the strategic form of the game from the last chapter.

The best way to find out which of the payoffs for the repeated game corresponds to a Nash equilibrium is to solve by backward induction. This technique means starting at the payoffs for the last round of the game and looking for the Nash equilibrium for that final round. Then you work backwards and see what players would do at the second-to-last round, knowing what will happen in the final round. Keep rolling back to the beginning or first round of the game. As you roll back through the game, you eliminate paths that don’t lead to an outcome that would have been chosen.

As an example, consider the trust game, which has been applied to the relationship between managers and workers or to the “trust but verify” strategies in disarmament. In the trust game, two participants have to decide whether or not to trust each other. In the first round, the first player, Yvonne, has to decide between trusting the second player, Zak, or not trusting him. After Yvonne makes her choice, Zak has to choose in the second round between honoring Yvonne’s trust or betraying it. We set up the game and see how to solve it.

Start with Yvonne:

• If Yvonne decides not to trust Zak, the relationship is over, and both parties gain zero.
• If Yvonne does trust Zak, he makes the next choice:
  • If Zak chooses to honor this trust, he gets 1 and Yvonne gets 1.
  • If Zak cheats, he gets 2 and Yvonne gets –1.
• If Yvonne knows this, what should she do?

To solve the game using backward induction, you start by writing the game down in extensive form as a tree. (Or take a look at Figure 17-3, which does this for you.)

The payoff numbers can be equally well represented on a strategic form matrix, and so you can use the method in the preceding section to find the Nash equilibrium — and if you don’t trust us, you can verify the results by doing so!

Working backwards from the very end, Zak’s round, note that Zak has a dominant strategy: Starting from this part of the tree, Zak does better, getting 2 (as opposed to 1) when he betrays Yvonne. Thus Zak will betray Yvonne.

Now go roll back to Yvonne’s move. If she knows what Zak’s payoffs to cheating are, then she can anticipate that he’s going to cheat, and so she chooses not to trust. Thus, the business relationship terminates before it has a chance to be poisoned.

You can say that solving this game for a Nash equilibrium finds that Yvonne and Zak do their best given each other’s payoffs by staying well away from each other.

Check out the nearby sidebar “Scoundrels don’t profit in the long run” for a timely financial example.

Deterring entry: A monopolist’s last resort

If a company has been successful enough to gain a dominant share of a market, it often wants to prevent a rival from coming in and stealing that market away.

Entry deterrence is a key concept in antitrust policy. The main antitrust statute in the United States, the Sherman Act, makes it clear that exploiting monopoly power to impede competition is illegal. So, for example, it is illegal to temporarily price below cost to prevent a competing firm from surviving in the market. If the competing firm is a would-be entrant, it would not be able to afford to enter the industry.

In Figure 17-4 we set up the situation as a game between a monopolist and an entrant. The entrant chooses to enter or not, and the monopolist chooses to retaliate (fight the entrant) or not. The monopolist wants to make the payoffs turn out so that the Nash equilibrium has the entrant choosing “Don’t enter.” When you analyze the game, you will see that it is a variant of the trust game in the earlier section “Solving a repeated game by backward induction.”

Analyzing society with economic reasoning

Economists have come a long way from merely studying markets and often look for ways of applying economic reasoning to difficult problems in other areas. One of these is the evolution of social institutions. Economists are able to use the insights of game theory to consider how cooperation and competition shape the strategies people use to punish those who cross them.

In society people have two ways of dealing with those who act against others: forgiving them or punishing them. If you think of society as a set of repeated Prisoner’s Dilemma games (see Chapter 16), you can develop a model that looks at punishing and forgiving as two different strategies. If the repeated games have different Nash equilibria, you can then think about how to characterize the different ways of behaving and compare the equilibria, telling you over the long run which strategy would be preferred from society’s point of view.

Typically, economists compare and contrast three strategies for playing a repeated Prisoner’s Dilemma (if you’re unfamiliar with the roles of Hawks and Doves, check out Chapter 16):

• Tit for Tat: Players start by playing the Dove. When one plays a Hawk, the other players default to Hawk too until the first player to play Hawk returns to playing Dove. Then, everyone else reverts to Dove.
• Grim Trigger: After a player has defaulted, the other players punish her by playing Hawk and never return to playing Dove, whatever the original defaulter’s subsequent moves.
• Firm but Fair: A bit like tit for tat, but the first default to Hawk is forgiven, and only the second one punished.

The evidence is that strategies like Firm but Fair tend to do better in simulations than Grim Triggers — providing evidence that though nice guys may finish last, nice societies tend to be better in the long run.