# Bogglers

By Scott Kim|Thursday, August 1, 2002

A Beautiful Equilibrium
The mathematics of John Forbes Nash

He who goes first . . .

Ticktacktoe is easy to analyze. If both players play perfectly, then the game ends in a draw. Chess is harder. But if we could play through every possible game, we could figure out which player can force a win or at least a draw. Every competitive situation has a best strategy, a statement that is borne out by the game of Hex, which was invented by Nobel Prize-winner John Forbes Nash. (Nash's theories deal with players who are fully rational; for theories about players who are imperfect reasoners, check out "The Mathematics of . . . Auctions.")

Hex is a two-person game played on a diamond-shaped, hexagonal tiled board. The board can be any size, so long as all sides are equal. In the four-by-four board shown above, two opposite edges of the board are colored blue, and the other two edges are orange. At the beginning of the game, all the hexagonal tiles are empty. Players pick sides (blue or orange) and then take turns coloring in the empty cells; the "blue" player colors cells blue, and the "orange" player, orange. The first player to color a chain of cells connecting his two sides of the board wins. In the example above, whoever colors the cell marked X wins. Nash proved that the first player can always win. His elegant proof is described in The Essential John Nash (Princeton University Press, 2001), a collection of Nash's mathematical papers edited by Harold Kuhn and Sylvia Nasar, author of A Beautiful Mind.

1. [Hard]   Can the game end in a draw? Can you demonstrate why this is so? Hint: Pretend blue is water and orange is land, then walk along the shoreline.

2. [Medium]   Why does the first player have a winning strategy? Hint: Use your answer from question 1. Suppose player 2 makes a move that could lead him to a victory. How should the first player respond?

The Nash Equilibrium

Game theory gets more interesting when players seek not merely to win but also to maximize their scores. Nash proved that assuming a game is played by completely rational competitors, it will reach a predictable conclusion, a point at which neither player can do better by changing his strategy while the other player's strategy remains unchanged. This point is now known as a Nash equilibrium.

A simple game shows the equilibrium in action. Two players are competing for dollar amounts (the figures shown in the three-by-three matrix above). Player 1's payoffs are shown in red; player 2's payoffs are shown in blue. Payoff amounts are determined in the following way: Player 1 selects any one row and player 2 selects any one column. The amounts in the box at the intersection of the selected row and column are the payoffs. When play begins, player 1 picks a row that contains the payoff amount she wants (for example, row 3, which includes a \$9 payoff). Player 2 then selects the column that includes her desired payoff (say, column C, with a \$9 payoff in the bottom square). Because the payoff is the intersection of the row and column, if play stopped at this point, player 1 would get \$2 and player 2 would get \$9. But now player 1 gets a chance to switch rows, and then player 2 can switch columns. Each player continues to switch until both players settle on a single row and column. If both players are fully rational, this point is a Nash equilibrium.

1. [Medium]   Which square above is a Nash equilibrium?

2. [Medium]   How can you modify the dollar amounts in the green square to create an additional Nash equilibrium?

3. [Medium]   What is the maximum number of equilibriums that can occur in a three-by-three matrix? What is the maximum if each amount can appear just once in a row or column?

4. [Hard]   Can you make a three-by-three matrix with no equilibrium?

Decisions, Decisions

A simple matrix can describe classic competitive situations as well as some complex human behaviors. Four scenarios and four payoff matrices appear at right. The matrices illustrate games in which two players choose between two alternatives. As in the previous problem, player 1 chooses a row, then player 2 chooses a column. The players continue switching until they reach an equilibrium. Can you match the pattern of play for each payoff matrix with the corresponding scenarios?

1. [Easy]   The game never ends (no equilibrium).

2. [Easy]   There are two or more possible endings (multiple equilibriums).

3. [Medium]   Two prisoners are questioned separately. If neither talks, both go free. If one talks, he goes free and is rewarded, and the other is severely punished. If both talk, both are punished. Each prisoner is motivated to talk, yet if both talk, they fare worse than they would have if they had kept silent. (This is the classic prisoner's dilemma.)

4.   Two cars race toward each other. If neither swerves, they crash. If one swerves, the other wins big. (This is the game of chicken.)

Solution

Want to see the solution to this puzzle?

Got new solutions for the puzzle? Want to see other people's solutions? Talk to the puzzle master in his discussion forum at www.scottkim.com.