PHIL 109 · Introduction to Formal Reasoning and Decision Making

10 Games

10.1 Games as interactive decisions

So far, every decision we have considered has been made against a partition of states of nature: possibilities that, for the most part, obtain or fail to obtain independently of what the agent decides to do. Whether it rains has nothing to do with whether you go to the park or to the movies; whether a given company’s stock rises has nothing to do with which stocks you bought. This independence is what let us treat the probability of a state as fixed, no matter which option we were evaluating.

We did, however, come across an exception to this pattern. Recall the lazy student: whether he studies is not independent of whether he passes, since studying raises the probability of passing. Even there, though, something important was still missing that will now become central. The state—passing or not passing the class—was not itself anyone’s choice. It was just a fact about the world that happened to be sensitive, probabilistically, to what the student did. Nobody was choosing to fail the lazy student in order to satisfy their own preferences.

Games are what you get when you take that last step: when the “state” that determines how well your choice turns out is not a brute fact about the world, nor even a fact that is merely sensitive to your choice, but is itself the deliberate choice of another agent—an agent who, exactly like you, has preferences over the possible outcomes and is choosing with an eye to satisfying them. This is what makes games distinctive, and it is why we call them interactive decisions.

Because a game has more than one decision-maker, we need more than one utility function: one per player. For now we restrict ourselves to games with exactly two players, whom we will call Row and Column—names that will make sense once we get to the matrix representation below. For the sake of ease of exposition, we will also assume that Row is a man and Column is a woman. Row’s utility function will be written $u_{R}$, and Column’s $u_{C}$. Both take as arguments a pair consisting of a choice by Row and a choice by Column: $u_{R}(R_{i}, C_{j})$ is how good the outcome is for Row, by Row’s own lights, when Row picks $R_{i}$ and Column picks $C_{j}$; and $u_{C}(R_{i}, C_{j})$ is how good that very same outcome is for Column, by Column’s lights.

The rest of this chapter will make heavy use of two ways of depicting a game: as a matrix, and as a tree. We introduce the general schema for each before putting both to work on a simple example.

10.1.1 Matrices

The most compact way of representing a two-player game is as a matrix. Row’s available choices, $R_{1}, R_{2}, \ldots, R_{m}$, label the rows; Column’s available choices, $C_{1}, C_{2}, \ldots, C_{n}$, label the columns. Each cell of the resulting payoff matrix corresponds to one possible outcome—one for each combination of a choice by Row and a choice by Column—and so it must contain two utilities rather than one. We will adopt the following convention throughout: Column’s utility goes in the upper-right corner of the cell, and Row’s utility goes in the lower-left corner. Table 10.1 displays the general schema.

Reading across a row tells you how well Row does against each of Column’s possible choices; reading down a column tells you how well Column does against each of Row’s possible choices. This is exactly the kind of information a single agent’s decision matrix gave us in earlier chapters; the only novelty is that we now have two such matrices at once, layered into a single grid of cells.

10.1.2 Trees

Matrices are compact, but they hide the order, if any, in which the players choose, and they picture both players as choosing simultaneously and independently of one another. A second way of representing a game, its extensive form or game tree, makes the order of choice explicit. In a game tree, each point at which a player must choose is drawn as a circle, labeled with whichever player chooses there—$R$ for Row, $C$ for Column; the branches leading out of a node, each labeled with the choice it represents, are the options available to that player; and the tips of the branches are the possible outcomes, each labeled with a pair of utilities $\big(u_{R}(R_{i},C_{j}), u_{C}(R_{i},C_{j})\big)$, in that order. Figure 10.1 gives the schema for a two-player game in which Row chooses first, among $R_{1}, \ldots, R_{m}$, and Column then chooses, among $C_{1}, \ldots, C_{n}$, already knowing what Row chose.

Notice the qualification at the end of the last paragraph: in Figure 10.1, Column chooses after Row, branching out separately beneath each of Row’s choices, and so is implicitly pictured as knowing what Row chose before choosing herself. That is a fine way of depicting a genuinely sequential game. But many of the games that interest us—including the one we turn to next—are not sequential: both players choose at the same time, each in ignorance of what the other is doing. A tree can still represent such a game, but only if we add a device for marking that several nodes are, from the point of view of the player choosing at them, indistinguishable. We do this by joining those nodes with a dotted line; the resulting cluster is called an information set. A player choosing at an information set must choose the same way at every node in it, since she cannot tell which one she is actually at. We will have more to say about information sets later on; for now, the dotted line is just a reminder that a choice is being made in ignorance of another player’s choice.

10.1.3 Example: Rock-Paper-Scissors

Let us put both representations to work on a simple, familiar game. In Rock-Paper-Scissors, Row and Column simultaneously choose one of Rock, Paper, or Scissors. Rock beats Scissors, Scissors beats Paper, and Paper beats Rock; if both players make the same choice, the game is a tie. The winner receives a utility of $1$, the loser a utility of $-1$, and both players receive $0$ in the event of a tie.

Table 10.2 gives the matrix representation of the game.

Figure 10.2 gives the tree representation of the very same game. Since Rock-Paper-Scissors is a simultaneous game, Column’s three choice nodes—one beneath each of Row’s choices—are joined by a dotted line, marking them as a single information set: Column must choose among Rock, Paper, and Scissors without having seen what Row chose.

The two representations agree, as they must, on every outcome: if Row plays Scissors and Column plays Paper, both the matrix and the tree tell us that Row gets a payoff of $1$ and Column a payoff of $-1$. Which representation is more convenient depends on the game and on what we want to do with it; we will use both freely throughout this chapter.

10.1.4 From trees to matrices, and back

Before we show how to translate one representation into the other, it helps to make explicit something that has so far been true without needing a name. In both Figure 10.1 and Figure 10.2, each player moves exactly once, so a row or a column of a matrix, and a first- or second-level branch of a tree, already amounts to a complete plan of action for that player. Once players may move more than once, this stops being true, and we need the more general notion of a strategy.

In every game we have considered so far, each player has exactly one decision node (or one information set), so a strategy for Row just is one of $R_{1}, \ldots, R_{m}$, and a strategy for Column just is one of $C_{1}, \ldots, C_{n}$. The rows and columns of our matrices, and the branches of our trees, already are strategies. This is what lets the translation between the two representations be a matter of bookkeeping rather than something requiring us to introduce anything new. The bookkeeping goes as follows.

From a tree to a matrix. List Row’s strategies along the rows and Column’s strategies along the columns. For each pair of strategies—one for Row, one for Column—follow the tree from the root, letting each player move exactly as her strategy specifies; this traces a unique path down to a single leaf. Copy that leaf’s pair of utilities into the corresponding cell of the matrix. This is exactly how Table 10.2 was read off Figure 10.2: the strategy pair (Scissors, Paper), for instance, traces a path down the branch labeled Scissors and then the branch labeled Paper, landing on the leaf labeled $(1,-1)$—which is exactly the entry in the Scissors row and Paper column of Table 10.2.

From a matrix to a tree. A matrix does not, by itself, say in what order, if any, the players moved; a tree, by contrast, always shows branches emerging from a root in some order. Turning a matrix into a tree therefore requires an arbitrary choice: pick one player to draw as moving “first” (it does not matter which), draw her strategies as the branches out of the root, and then, beneath each of those branches, draw a node for the other player, with her own strategies as its branches. If, as is usually the case, the matrix represents a genuinely simultaneous choice, join all of the second mover’s nodes into a single information set with a dotted line, exactly as we did for Column in Figure 10.2: this cancels out the false impression, created by the tree’s left-to-right layout, that the second mover already knows what the first one did. The leaves are then labeled directly from the matrix: the leaf at the end of the path through $R_{i}$ and $C_{j}$ gets whichever pair of utilities sits in row $R_{i}$, column $C_{j}$ of the matrix.

Since Table 10.2 and Figure 10.2 depict the very same game, running either procedure on one of them should return (up to the arbitrary choice of who is drawn as moving first) the other. We encourage you to check this for yourself.

10.2 The assumptions of game theory

Before going any further, it is worth making explicit several assumptions that classical game theory takes for granted. None of them is beyond dispute—each has been challenged, by philosophers and economists alike—but we will adopt all four for the remainder of this chapter, since doing so is what lets us use matrices, trees, and the solution concepts to come in their standard form.

1. Utilities are measured on interval scales. Recall that an ordinal utility function only records a ranking of outcomes, whereas a cardinal, or interval-scale, utility function also records facts about the magnitude of the differences between them—and that this is exactly what maximizing expected utility requires (Norm 8.4). We will assume throughout that each player’s utility function is at least interval-scale: $u_{R}$ and $u_{C}$ are each fixed only up to a positive linear transformation (Definition 8.1), so nothing follows from the bare fact that, say, $u_{R}(R_{1},C_{1}) = 4$ while $u_{C}(R_{1},C_{1}) = 2$. Comparisons of magnitude are licensed only within a single player’s own scale—Row’s $4$ against one of Row’s other numbers—never across players: classical game theory does not assume any way of comparing how much Row wants something to how much Column wants something.

2. Players maximize expected utility. Row and Column are both assumed to be maximizing expected utility (Norm 8.4), exactly as the single agents of earlier chapters did. It is worth being careful about what this assumption does, and does not, say. It does not say that a player always wants to win, in whatever sense her opponent would recognize as winning. A mother playing chess against her young son may well prefer that he win, and so assign a higher utility to that outcome than to her own victory. Game theory has no trouble representing this: it simply means that the mother and son are not playing the game that two rival grandmasters would be playing, even though the legal moves of chess are exactly the same in both cases. A game, recall, is individuated by the players’ utilities over outcomes, not by the nominal activity they happen to be engaged in (Definition 10.1); change the utilities and, officially, you have changed the game, whatever the rules on the box say.

3. All of this is common knowledge. It is not enough that the rules, the payoffs, and each player’s rationality merely happen to be known by both players; game theory assumes something considerably stronger.

   Definition 10.3. Common knowledge: A proposition $p$ is common knowledge among a group of agents if and only if every agent in the group knows $p$, every agent knows that every agent knows $p$, every agent knows that every agent knows that every agent knows $p$, and so on, without end.

   This is a much stronger condition than what is called mutual knowledge: the mere fact that each member of a group individually knows $p$. Suppose I tell Row, in private, that Column is rational, and I separately tell Column, in private, that Row is rational. Then it is true that both know that the other is rational—the fact is mutually known. But neither of them knows that I told the other: for all Row knows, Column may think Row is irrational, and so Row cannot safely reason about what a rational Column will do on the assumption that Column is reasoning about a rational Row. Had I announced the very same fact publicly, with both of them present and aware of each other’s presence, it would have become common knowledge instead: each would know it, each would know that the other knows it, each would know that the other knows that they know it, and so on—because each can see that the other was there to hear the announcement, and can see that the other can see this too. It is this whole infinite hierarchy, not the mere fact that everyone happens to know, that licenses each player’s confidence in reasoning about what the other player, reasoning in turn about her, will do.

4. We limit ourselves to two-person games. For the rest of this chapter, every game we consider will have exactly two players, Row and Column, and no more. This is a substantive restriction—many interesting games have three or more players—but it keeps our matrices and trees to a manageable size, and the theory of games with more than two players is, in any case, considerably more complicated.

10.3 Strictly competitive two-player games

Look back at Table 10.2. Every one of its nine cells has the same curious feature: whatever number appears as Row’s utility, Column’s utility is exactly that number’s negative. A win for Row ($u_{R}=1$) is paired with a loss for Column ($u_{C}=-1$); a loss for Row ($u_{R}=-1$) is paired with a win for Column ($u_{C}=1$); a tie ($u_{R}=0$) leaves them both exactly where they started ($u_{C}=0$). Rock-Paper-Scissors is the simplest possible case of a wider phenomenon: games in which the players’ preferences are in exact opposition, so that to whatever extent one of them gains from an outcome, the other loses.

Since each player’s utility function is fixed only up to a positive linear transformation (our first assumption above), it makes no sense to ask whether Column’s utility is “really” the negative of Row’s. But in a strictly competitive game we are free to choose Column’s utility function so that it is: letting $u(R_i,C_j)$ be Row’s utility for a given outcome, we can take Column’s utility for that same outcome to be $-u(R_i,C_j)$, so that $u_{R}(R_i,C_j) + u_{C}(R_i,C_j) = 0$ for every $i$ and $j$. A game whose utilities are written in this way is called zero-sum. Every strictly competitive game can be written as a zero-sum game, and so we will use the two terms interchangeably from now on.

Since Column’s utility is never independent information in a strictly competitive game—once we know Row’s utility for an outcome, we know Column’s for free, as its negative—we will simplify our matrices from here on by writing only Row’s utility in each cell and leaving Column’s implicit. Table 10.3 gives Rock-Paper-Scissors in this simplified notation. Compare it with Table 10.2 to confirm that no information has been lost: Column’s utility in any cell can always be recovered just by flipping the sign of the number written there.

10.4 Nonzero-sum games

Not all two-player games are zero-sum. Suppose, for instance, that Row and Column want to meet during this weekend, but cannot communicate. The options, which they arranged beforehand, are to go to the park or to the movies. They both prefer meeting each other to not meeting, but Row prefers meeting at the park and Column meeting at the movies:

10.5 Iterated deletion of dominated strategies

What are the norms for rational game players? One uncontroversial norm is that rational players do not play strongly dominated strategies. Remember our definition of a strongly dominated strategy from Chapter 7: option $\varphi$ strongly dominates option $\psi$ if and only if $\varphi$ does better than $\psi$ no matter which state obtains (Definition 7.8), that is, if and only if, for every state $S_{i}$, $$u(\varphi \land S_{i}) > u(\psi \land S_{i}).$$ In a game, the role of the states is played by the other player’s strategies. From Row’s point of view, what he does not control, and what together with his own choice settles the outcome, is which strategy Column plays; and the same goes, the other way around, for Column. So Row’s strategy $R_{k}$ strongly dominates his strategy $R_{i}$ if and only if, for every strategy $C_{j}$ of Column’s, $$u_{R}(R_{k}, C_{j}) > u_{R}(R_{i}, C_{j}),$$ and Column’s strategy $C_{k}$ strongly dominates her strategy $C_{j}$ if and only if, for every strategy $R_{i}$ of Row’s, $$u_{C}(R_{i}, C_{k}) > u_{C}(R_{i}, C_{j}).$$ In a zero-sum game written, as we have agreed, with Row’s utilities only, the second condition has to be read with care. Since Column’s utility is the negative of Row’s, Column’s strategy $C_{k}$ strongly dominates $C_{j}$ if and only if, for every $R_{i}$, $$u_{R}(R_{i}, C_{k}) < u_{R}(R_{i}, C_{j}).$$ That is, every number in column $C_{k}$ is lower than the corresponding number in column $C_{j}$. Column, remember, wants the numbers in the matrix to be as low as possible.

The dominance norm (Norm 7.10) tells us that a rational player never plays a strongly dominated strategy. Consider, then, the following zero-sum game:

None of Row’s strategies is strongly dominated: $R_{1}$ does better than $R_{2}$ if Column plays $C_{3}$ ($6 > 5$), but worse if she plays $C_{1}$ ($0 < 4$); $R_{3}$ does better than both of the others against $C_{1}$, but worse than both against $C_{2}$. Column, however, has a strongly dominated strategy: every number in column $C_{3}$ is higher than the corresponding number in column $C_{2}$ ($6 > 2$, $5 > 3$, and $7 > 1$), so $C_{2}$ strongly dominates $C_{3}$. A rational Column, therefore, will not play $C_{3}$.

If the dominance norm were all we had to go on, that is where our analysis would stop. But recall our third assumption: the players’ rationality, and the payoffs of the game, are common knowledge (Definition 10.3). Since Row knows that Column is rational, he knows that Column will not play $C_{3}$, and so he can reason as if $C_{3}$ had been deleted from the game. And in the smaller game that results, $R_{1}$ is strongly dominated, by $R_{2}$ ($4 > 0$ and $3 > 2$). The only thing that protected $R_{1}$ was its good showing against $C_{3}$, and $C_{3}$ is no longer a live possibility. So a rational Row who knows that Column is rational will not play $R_{1}$.

The process does not stop there. Column knows that Row is rational and that Row knows that Column is rational, so she, too, can work out that Row will not play $R_{1}$, and can reason as if both $C_{3}$ and $R_{1}$ had been deleted. In the game that is left, $C_{1}$ is strongly dominated by $C_{2}$ ($3 < 4$ and $1 < 9$): $C_{1}$ was protected only by the $0$ that Row would get by playing $R_{1}$, and Row will not play $R_{1}$. So Column deletes $C_{1}$ as well.

Finally, Row can follow all of this reasoning, so he knows that Column will play $C_{2}$; and against $C_{2}$, $R_{2}$ does better than $R_{3}$ ($3 > 1$). So Row deletes $R_{3}$. The only strategies left standing are $R_{2}$ and $C_{2}$, and the outcome of the game is that Row receives $3$ (and Column, therefore, $-3$).

Try it in the Games Lab Step through iterated deletion of strongly dominated strategies in this game.

Notice how each step of this reasoning requires one more layer of knowledge than the one before. The first deletion requires only that Column be rational. The second requires, in addition, that Row know that Column is rational. The third requires that Column know that Row knows that Column is rational. And the fourth requires that Row know that Column knows that Row knows that Column is rational. In bigger games, the chain can get as long as you like, which is why game theory does not stop at any particular layer and simply assumes common knowledge, which delivers all of the layers at once.

Iterated deletion works in exactly the same way in games that are not zero-sum. The only difference is that we can no longer write just one number per cell, so we have to be careful to read each player’s own utilities: Row’s strategies are compared using the numbers in the lower-left corners, and Column’s using the numbers in the upper-right corners. And since those upper-right numbers are now Column’s own utilities, Column wants them to be as high as possible. Consider the game in Table 10.10.

This time it is Row who has a strongly dominated strategy to begin with: $R_{3}$ is strongly dominated by $R_{1}$ ($4 > 1$, $1 > 0$, and $3 > 2$), and also by $R_{2}$ ($2 > 1$, $2 > 0$, and $5 > 2$). None of Column’s strategies is dominated yet: $C_{2}$ does better for Column than $C_{1}$ against $R_{1}$ and $R_{2}$, but worse against $R_{3}$ ($2 < 3$). Once Column knows that Row will not play $R_{3}$, however, $C_{1}$ is strongly dominated by $C_{2}$ ($3 > 1$ and $4 > 1$), so she deletes it. With $C_{1}$ gone, Row loses the one thing that made $R_{1}$ worth considering, its $4$ against $C_{1}$, and $R_{1}$ is now strongly dominated by $R_{2}$ ($2 > 1$ and $5 > 3$). Finally, with only $R_{2}$ left for Row, $C_{3}$ is strongly dominated by $C_{2}$ ($4 > 0$). The game is dominance solvable: Row plays $R_{2}$, Column plays $C_{2}$, and they receive $2$ and $4$ respectively. Figure 10.3 summarizes the process.

Try it in the Games Lab Step through iterated deletion of strongly dominated strategies in this game.

Something happens in this game that could never happen in a zero-sum game. Look at the outcome of $R_{1}$ and $C_{3}$: Row would get $3$ and Column would get $5$, so both players would be better off there than at the solution of the game. Why, then, can they not get there? Because $(R_{1}, C_{3})$ is not stable. If Column plays $C_{3}$, Row does better by switching to $R_{2}$ ($5$ rather than $3$), which would leave Column with $0$; and Column, who can see this coming, will not expose herself to that risk by playing $C_{3}$. In a zero-sum game the question cannot even arise, since there whatever is better for one player is worse for the other, so no outcome can be better for both players than another. Once we leave zero-sum games behind, by contrast, perfectly rational players, with common knowledge of each other’s rationality, can end up at an outcome that both of them would gladly trade for another one. We will see a starker version of this phenomenon when we come to the Prisoner’s Dilemma.

If, at the end of this process, each player is left with a single strategy, as happens in the two cases we examined in this section, we say that the game is dominance solvable, and we take the surviving pair of strategies to be its solution. Because we only ever delete strongly dominated strategies, the order in which we carry out the deletions makes no difference: whichever strongly dominated strategy we delete first, we always end up with the same strategies at the end. The same is not true, as we will see, if we also delete weakly dominated strategies, where the order of deletion can affect the result.

Not every game is dominance solvable, however. In Rock-Paper-Scissors (Table 10.3), no strategy of either player is strongly dominated, or even weakly dominated: each of Row’s strategies is the best possible against one of Column’s strategies and the worst possible against another, and likewise for Column. So iterated deletion does not even get started, and we would need other tools to say anything about how such games should be played.

10.6 Nash equilibrium

Iterated deletion of dominated strategies is a powerful tool, but it only gets started if some player has a dominated strategy. Consider the zero-sum game in Table 10.11, written, as usual, with only Row’s utilities.

Try it in the Games Lab Star the best responses and find the Nash equilibria step by step.

No strategy here is dominated, not even weakly. Each of Row’s strategies is his best option against one of Column’s ($R_{1}$ against $C_{2}$, $R_{2}$ against $C_{1}$, and $R_{3}$ against $C_{3}$), and each of Column’s strategies is her best option against one of Row’s ($C_{1}$ against $R_{2}$, $C_{2}$ against $R_{3}$, and $C_{3}$ against $R_{1}$). So iterated deletion is of no help. Can the players nevertheless figure out what to do?

Since what is best for each player depends on what the other one does, it is natural for each of them to start by asking what the other will do. Suppose, for instance, that Row expects Column to play $C_{2}$. Then his best reply is $R_{1}$, which would get him $8$. But Column knows that Row is rational, and she knows the payoffs, so she can work out that if Row expected her to play $C_{2}$ he would play $R_{1}$; and against $R_{1}$, her best reply is not $C_{2}$ but $C_{3}$, which holds Row down to $0$. The expectation that Column will play $C_{2}$ undermines itself: if Row acted on it, Column, anticipating this, would not play $C_{2}$ after all. The same thing happens if Row expects Column to play $C_{3}$: his best reply is $R_{3}$, which would get him $7$, but Column’s best reply to $R_{3}$ is $C_{2}$, which holds him down to $1$. In fact, these expectations chase each other round in a circle: $C_{2}$ leads to $R_{1}$, which leads to $C_{3}$, which leads to $R_{3}$, which leads back to $C_{2}$.

Things are different if Row expects Column to play $C_{1}$. His best reply to $C_{1}$ is $R_{2}$, and Column’s best reply to $R_{2}$ is $C_{1}$ itself, since $4$ is the lowest number in row $R_{2}$. Here, and only here, the expectation confirms itself: if Row expects $C_{1}$ and therefore plays $R_{2}$, then Column, who can anticipate this, has every reason to play $C_{1}$, which is just what Row expected her to do. Running the same reasoning from Column’s side singles out the very same pair. Once the players are at $(R_{2}, C_{1})$, neither has any reason to move: Row gets $4$, and switching would get him only $2$ or $3$; Column holds Row down to $4$, and switching would let him have $6$ or $5$.

Notice that this solution is not particularly glamorous for Row. $R_{1}$ holds out the prospect of $8$ and $R_{3}$ the prospect of $7$, whereas the best $R_{2}$ can do is $6$. But Row cannot count on getting $8$ or $7$: those outcomes require Column to play into his hands, and she has no reason to do so.

The same kind of reasoning works in games that are not zero-sum. In the game of Table 10.12, again, no strategy of either player is dominated.

Try it in the Games Lab Star the best responses and find the Nash equilibria step by step.

Suppose that Column expects Row to play $R_{1}$. Her best reply would then be $C_{1}$, which gets her $5$ (rather than $3$ or $0$). But Row, anticipating this, would play $R_{2}$ against $C_{1}$, since that gets him $4$ (rather than $2$ or $1$). Against $R_{2}$, however, Column would rather play $C_{2}$ ($2$ rather than $0$ or $1$); against $C_{2}$, Row would rather play $R_{3}$ ($4$ rather than $2$ or $1$); and against $R_{3}$, Column would rather play $C_{3}$ ($3$ rather than $0$ or $1$). At this point the chain of reasoning comes to rest, since Row’s best reply to $C_{3}$ is $R_{3}$ itself ($3$ rather than $0$ or $2$). The pair $(R_{3}, C_{3})$ is the only one at which each player’s strategy is a best reply to the other’s, and wherever we start the chain of reasoning, it ends there. Each player gets $3$.

Sometimes, however, this kind of reasoning does not single out a unique pair of strategies. Go back to the Park or Movies game (Table 10.4):

Try it in the Games Lab Star the best responses and find the Nash equilibria step by step.

If Row expects Column to go to the park, his best reply is to go to the park too ($2$ rather than $0$); and if Column expects Row to go to the park, her best reply is to go there as well ($1$ rather than $0$). So (Park, Park) confirms itself. But so does (Movies, Movies): if each expects the other at the movies, each does best by going there too (Row gets $1$ rather than $0$, and Column $2$ rather than $0$). The two remaining pairs do not confirm themselves: whoever expects the other at the park does best by going to the park, and whoever expects the other at the movies does best by going to the movies, so neither player has any reason to stick to a pair in which they miss each other. The reasoning that served the players so well in the previous two games thus leaves them, in this one, with two candidate solutions, and nothing in the game itself tells them which one to aim for. Worse, Row prefers one of them and Column the other. If each heads for his or her own favorite, they end up at (Park, Movies) and miss each other; and if each gallantly defers to the other, they end up at (Movies, Park) and miss each other again.

The self-confirming pairs of strategies we have been looking for are named after the mathematician John Nash, who introduced the idea in 1950. To state the definition precisely, we first need the notion of a best response.

Equivalently, a pair of strategies is a Nash equilibrium just in case neither player could do better by switching to another strategy while the other player sticks to hers. $(R_{2}, C_{1})$ is the only Nash equilibrium of Table 10.11, and $(R_{3}, C_{3})$ the only one of Table 10.12; Park or Movies has two, (Park, Park) and (Movies, Movies). You can also check that the solutions we found by iterated deletion in Table 10.5 and Table 10.10 (both of which happen to be $(R_{2}, C_{2})$) are Nash equilibria. This is no accident: whenever iterated deletion of strongly dominated strategies leaves each player with a single strategy, the resulting pair is a Nash equilibrium, and it is the game’s only one.

Things are different if we also delete weakly dominated strategies. Consider the game in Table 10.14.

Try it in the Games Lab Star the best responses and find the Nash equilibria step by step.

This game has two Nash equilibria. At $(R_{1}, C_{1})$, Row’s best response to $C_{1}$ is $R_{1}$ ($2$ rather than $0$), and Column’s best response to $R_{1}$ is $C_{1}$ ($2$ rather than $0$). At $(R_{2}, C_{2})$, Row’s best response to $C_{2}$ is $R_{2}$, since it gets him $3$ and $R_{1}$ would get him no more than that, and Column’s best response to $R_{2}$ is $C_{2}$ ($3$ rather than $0$). Notice, moreover, that $(R_{2}, C_{2})$ is better for both players than $(R_{1}, C_{1})$. But $R_{2}$ is weakly dominated by $R_{1}$: against $C_{1}$, $R_{1}$ does better ($2 > 0$), and against $C_{2}$ the two do equally well ($3 = 3$). If we delete $R_{2}$ on that basis, Column is left choosing between $C_{1}$ and $C_{2}$ against $R_{1}$ alone, and now $C_{2}$ is strongly dominated by $C_{1}$ ($2 > 0$). The procedure thus leaves us with $(R_{1}, C_{1})$, and the equilibrium that both players prefer has been deleted along the way.

What has gone wrong? Deleting $R_{2}$ because it is weakly dominated makes sense only if Row takes seriously the possibility that Column will play $C_{1}$, since that is the only case in which $R_{1}$ does better than $R_{2}$. But if Row is confident that Column will play $C_{2}$, as he is entitled to be at the equilibrium $(R_{2}, C_{2})$, then he loses nothing by playing $R_{2}$. Strongly dominated strategies never raise this problem. A strongly dominated strategy does worse than some alternative against everything the other player might do, so it is never a best response to anything, and so it can never be part of a Nash equilibrium. Deleting strongly dominated strategies, however many times we do it, therefore never deletes an equilibrium. This is a second reason, in addition to the fact that the order of deletion can matter, to restrict iterated deletion (Definition 10.5) to strongly dominated strategies.

Not every game has a Nash equilibrium if we consider just the strategies depicted in the matrix corresponding to the game, however. Consider Rock-Paper-Scissors once more (Table 10.3), and go through each of the nine pairs of strategies:

In every one of them, at least one of the players would do better by switching. At (Rock, Rock), Row would rather switch to Paper ($1$ rather than $0$); at (Rock, Paper), Row would rather switch to Scissors ($1$ rather than $-1$); at (Rock, Scissors), Column would rather switch to Paper (getting $1$ rather than $-1$); and so on for the remaining six pairs. Whatever pair the players expect, one of them has a reason to depart from it, and the reasoning goes round in circles forever, just as it did for the strategies other than $R_{2}$ and $C_{1}$ in Table 10.11.

This is not quite the end of the story. Instead of simply choosing one of their strategies, players can also randomize: Row could, for instance, roll a die and play Rock if it lands $1$ or $2$, Paper if it lands $3$ or $4$, and Scissors if it lands $5$ or $6$. A way of choosing among one’s strategies with given probabilities is called a mixed strategy; by contrast, the strategies we have been dealing with so far are called pure strategies, and what we have defined is, strictly speaking, a Nash equilibrium in pure strategies. Nash proved that every game with finitely many players and strategies has at least one Nash equilibrium once mixed strategies are allowed. In Rock-Paper-Scissors, for instance, the only equilibrium is the one in which each player plays each strategy with probability $\sfrac{1}{3}$: if Column does this, every strategy of Row’s has the same expected utility, $0$, so Row has nothing to gain by doing anything else, and the same goes for Column. We will not deal with mixed strategies in this book, however. From now on, “Nash equilibrium” will always mean Nash equilibrium in pure strategies.

10.6.1 Saddle points

In zero-sum games, there is a simple, mechanical way of finding Nash equilibria. Recall that, in a zero-sum matrix written with Row’s utilities only, Row wants the numbers to be as high as possible and Column wants them to be as low as possible. So Row’s best response to a column is whichever row has the largest number in that column, and Column’s best response to a row is whichever column has the smallest number in that row. A pair $(R_{i}, C_{j})$ is therefore a Nash equilibrium just in case the number in its cell is at once the largest in its column and the smallest in its row.

The name comes from the shape of a horse’s saddle: the middle of the seat is the lowest point as you move from the horse’s head to its tail, but the highest point as you move from one of its sides to the other. In a zero-sum game, then, the Nash equilibria are exactly the saddle points.

To find the saddle points of a zero-sum game, write down the minimum of each row and the maximum of each column, as in Table 10.16. The minimum of a row is what Row can guarantee himself by playing it, whatever Column does; the largest of these row minima, which is called the maximin of the game, is therefore the most Row can guarantee himself. Choosing a row whose minimum is the maximin is just following the maximin norm of Norm 7.13, with Column’s strategies playing the role of the states. Similarly, the maximum of a column is the most Row can get if Column plays it; the smallest of these column maxima, which is called the minimax of the game, is therefore the least that Column can guarantee to hold Row down to. (Since Column’s utilities are the negatives of Row’s, choosing a column whose maximum is the minimax is just Column following the maximin norm from her own point of view.)

Try it in the Games Lab Step through the row minima, the column maxima and the saddle points.

In Table 10.16, the maximin and the minimax are both $4$, and the cell where the maximin row and the minimax column meet, $(R_{2}, C_{1})$, is a saddle point: $4$ is the smallest number in row $R_{2}$ and the largest in column $C_{1}$. It is, of course, the equilibrium we reasoned our way to earlier. (You can check that the solution of Table 10.5, whose value is $3$, is a saddle point as well.)

The maximin can never be larger than the minimax. Take any row $R_{i}$ and any column $C_{j}$: the minimum of $R_{i}$ is at most the number in their shared cell, which is in turn at most the maximum of $C_{j}$. So every row minimum is less than or equal to every column maximum, and in particular the largest row minimum is less than or equal to the smallest column maximum. When the two are equal, the game has a saddle point, at the intersection of any row that achieves the maximin with any column that achieves the minimax. When the maximin is strictly smaller than the minimax, the game has no saddle point, and so no Nash equilibrium. Rock-Paper-Scissors is a case in point: every row minimum is $-1$ and every column maximum is $1$, so the maximin, $-1$, falls short of the minimax, $1$.

There is something striking about all this. When we first met the maximin norm, in decisions under ignorance, it could look excessively pessimistic: why assume that the worst state will obtain? In a zero-sum game, however, the “states” are chosen by an opponent whose interests are exactly opposed to yours and who can anticipate what you will do, so expecting the worst is just being realistic. And whenever a zero-sum game has a saddle point, each player’s cautious maximin choice is exactly an equilibrium choice: neither of them could do better by being less cautious.

Finally, zero-sum games never confront the players with the problem we saw in the Park or Movies case. A zero-sum game may have more than one saddle point, but all of them have the same value (namely, the maximin, which equals the minimax); and if $(R_{i}, C_{j})$ and $(R_{k}, C_{l})$ are both saddle points, then so are $(R_{i}, C_{l})$ and $(R_{k}, C_{j})$. So each player can simply pick any of his or her equilibrium strategies, without any need to coordinate with the other.

10.6.2 Finding pure equilibria by starring best responses

The saddle-point method only works for zero-sum games. Fortunately, there is an equally mechanical method that works for every game, zero-sum or not, and that follows the definition of a Nash equilibrium very closely. To see how it works, consider the game in Table 10.17, in which each player has five strategies.

We could, of course, go through all twenty-five cells one at a time, asking of each whether either player would do better by switching. But there is a quicker way, which consists of two passes through the matrix.

In the first pass, we go through the matrix column by column, and in each column we put a star next to Row’s highest number, that is, next to the highest of the numbers in the lower-left corners. A star on Row’s number in the cell of $R_{i}$ and $C_{j}$ thus records that $R_{i}$ is a best response to $C_{j}$: against $C_{j}$, no other strategy of Row’s does better. In column $C_{1}$, for instance, Row’s numbers are $5$, $1$, $5$, $6$, and $0$, so we star the $6$ in row $R_{4}$. If several of Row’s numbers are tied for highest in a column, we star all of them, since each of the corresponding strategies is a best response to that column. This happens in column $C_{2}$, where Row’s $7$ in row $R_{2}$ and his $7$ in row $R_{4}$ both get a star. The result of the first pass is shown in Table 10.18.