Two cafés, run by Arno and Bea, face each other across a square and sell the same espresso. Each Monday the owners set a price for the week, High or Low, without knowing what the other has chosen. If both charge High, each clears a weekly profit of 6 (in hundreds of euros). If both charge Low, each clears 3. If one charges Low and the other High, the low-price café takes most of the trade and clears 8, while the other clears 1. What will the owners do?
A first guess is that they will both charge High, since that is the best outcome for the pair. A second look at Arno’s position gives a different answer. If Bea charges High, Arno earns 6 from High and 8 from Low. If Bea charges Low, Arno earns 1 from High and 3 from Low. Whatever Bea does, Low earns Arno exactly 2 more. Bea’s position is the mirror image. So two owners who each reason correctly about their own profit end up at Low and Low with 3 each, although High and High with 6 each was available. Nothing in this argument required either owner to guess what the other would do.
The argument is short, but it used every ingredient of a game: a list of decision makers, a list of what each may choose, and a rule that turns every combination of choices into a result for each of them. This chapter makes those ingredients precise, introduces the two elementary tools of the subject, best responses and dominance, and finds out how far they can go without any further idea.
1.1 Players, strategies, payoffs
Definition 1.1 (game in strategic form). A game in strategic form consists of a finite set of players \(N=\{1,\dots,n\}\) ; for each player \(i\) a nonempty set \(S_i\) of strategies; and for each player \(i\) a payoff function
An element \(s=(s_1,\dots,s_n)\) of \(S=S_1\times\dots\times S_n\) is a strategy profile. The game is finite if every \(S_i\) is finite. We write the game as \(G=(N,(S_i),(u_i))\) .
The definition describes a single simultaneous choice. Each player picks one element of \(S_i\) ; nobody observes anyone else’s pick before making their own; the resulting profile \(s\) determines the number \(u_i(s)\) for every player; and each player prefers larger values of their own \(u_i\) . The description of the game, including everyone’s payoff function, is known to all players. Games in which moves are made in sequence or in which some information is private need more structure, and Chapters 5 and 7 supply it, but both are eventually analysed by reducing them to the object just defined.
For a profile \(s\) and a player \(i\) , the list of everyone else’s strategies is written \(s_{-i}\in S_{-i}=\prod_{j\ne i}S_j\) , and \((t_i,s_{-i})\) denotes the profile in which player \(i\) uses \(t_i\) and the others use what \(s\) prescribes. This notation is used on every page that follows. It expresses the one thought experiment that noncooperative game theory performs over and over: hold the others fixed and let one player change.
Example 1.1: The cafés as a game
The players are \(N=\{1,2\}\) , with Arno as player 1 and Bea as player 2. Each has the strategy set \(S_i=\{\text{High},\text{Low}\}\) , so there are \(2\cdot 2=4\) profiles. The payoff functions are read off the story, for instance \(u_1(\text{Low},\text{High})=8\) and \(u_2(\text{Low},\text{High})=1\) . A two-player finite game is displayed as a table in which player 1 chooses the row, player 2 the column, and each cell holds the pair \((u_1,u_2)\) :
The opening argument is now a statement about this table. For player 1, compare the first coordinates down each column: \(8>6\) in the column High and \(3>1\) in the column Low. For player 2, compare the second coordinates along each row: \(8>6\) in the row High and \(3>1\) in the row Low. Reading the wrong coordinate, or comparing along a row when it is the row player who is choosing, is the most common slip in the subject, and it helps to say aloud “player 1 moves vertically, player 2 moves horizontally” until it is automatic.
A payoff is not a sum of money. It is a number that represents the player’s ranking of the possible results: \(u_i(s)>u_i(s')\) means that player \(i\) prefers what happens under \(s\) to what happens under \(s'\) . Money, market share, years in prison, and concern for other people all enter only through that ranking. For everything in this chapter and the next, only the order of each player’s payoffs matters, so replacing \(u_i\) by any strictly increasing function of \(u_i\) leaves the analysis unchanged. From Chapter 3 on, players will face lotteries over profiles and payoffs will be averaged; then the numbers must be von Neumann–Morgenstern utilities, whose expected value represents preference over lotteries, and they are determined only up to a positive affine change \(au_i+b\) with \(a>0\) .
The distinction between results and payoffs is not pedantry. The same physical outcomes produce different games when the players care about different things.
Example 1.2: Same profits, different game
Suppose Arno and Bea are old friends, and each evaluates a week by their own profit plus half of the other’s. The profits are those of Example 1.1, but the payoffs are now different numbers. At (High, High) each gets \(6+\tfrac12\cdot 6=9\) . At (Low, Low) each gets \(3+\tfrac12\cdot 3=4.5\) . At (Low, High) the low-price owner gets \(8+\tfrac12\cdot 1=8.5\) and the other gets \(1+\tfrac12\cdot 8=5\) . The table is
Now compare player 1’s payoffs down each column: \(9>8.5\) against High and \(5>4.5\) against Low. High is better for player 1 whatever player 2 does, and by symmetry the same holds for player 2. The friends charge High. The profit table did not change; the game did. Before analysing any situation, one must settle what each player is trying to achieve, and the payoff function is where that decision is recorded.
1.2 Best responses
Definition 1.2 (best response). Let \(s_{-i}\in S_{-i}\) . A strategy \(s_i\in S_i\) is a best response of player \(i\) to \(s_{-i}\) if
The set of all best responses to \(s_{-i}\) is written \(\operatorname{BR}_i(s_{-i})\) .
A best response answers a conditional question: if the others were to play \(s_{-i}\) , what should I play? It is a set, not a single strategy, because ties are possible, and in a finite game it is never empty because a finite set of numbers has a largest element. The map \(s_{-i}\mapsto\operatorname{BR}_i(s_{-i})\) is the best-response correspondence of player \(i\) . Computing it is an optimization problem with one decision maker, solved once for each possible behaviour of the others. A game with two players and a payoff table is therefore two families of optimization problems written on one sheet: player 1 solves one problem per column and player 2 solves one problem per row.
Example 1.3: Marking best responses in a table
Consider the game
For player 1, look down each column at first coordinates. In column \(L\) they are \(3,3,1\) , so the largest value \(3\) is reached twice and \(\operatorname{BR}_1(L)=\{T,M\}\) . In column \(C\) they are \(1,4,2\) , so \(\operatorname{BR}_1(C)=\{M\}\) . In column \(R\) they are \(2,0,5\) , so \(\operatorname{BR}_1(R)=\{B\}\) .
For player 2, look along each row at second coordinates. In row \(T\) they are \(2,4,1\) , so \(\operatorname{BR}_2(T)=\{C\}\) . In row \(M\) they are \(0,1,3\) , so \(\operatorname{BR}_2(M)=\{R\}\) . In row \(B\) they are \(3,2,4\) , so \(\operatorname{BR}_2(B)=\{R\}\) .
It is good practice to underline in the table each payoff that is a best response. Here four first coordinates are underlined (two in column \(L\) , one each in columns \(C\) and \(R\) ) and three second coordinates (one per row). Exactly one cell has both coordinates underlined: the cell \((B,R)\) with payoffs \((5,4)\) . In that cell each player’s strategy is a best response to the other’s. Chapter 2 is about cells with this property. For the moment, notice two things the marking does not show. Player 1 has no strategy that is a best response to everything: each of \(T\) , \(M\) , \(B\) is underlined in some column and not in another. And no strategy is useless either: each is a best response to something.
1.3 Dominance
In the café game one strategy was a best response to everything. That situation deserves a name, and so does its opposite, a strategy that is beaten by one fixed alternative no matter what the others do.
Definition 1.3 (dominance). Let \(s_i,t_i\in S_i\) . The strategy \(t_i\) strictly dominates \(s_i\) if
It weakly dominates \(s_i\) if \(u_i(t_i,s_{-i})\ge u_i(s_i,s_{-i})\) for every \(s_{-i}\in S_{-i}\) , with strict inequality for at least one \(s_{-i}\) . A strategy is strictly dominated (weakly dominated) if some other strategy of the same player strictly (weakly) dominates it. A strategy is strictly dominant if it strictly dominates every other strategy of that player, and weakly dominant if it weakly dominates every other strategy of that player.
The quantifier is the whole content of the definition. Dominance compares two strategies of one player against every possible profile of the others, one profile at a time. It does not compare the largest entry in one row with the largest entry in another, and it does not compare a player’s payoff with anyone else’s.
Proposition 1.4 (dominated strategies and best responses). (a) A strictly dominated strategy is not a best response to any \(s_{-i}\in S_{-i}\) . (b) If \(t_i\) is strictly dominant, then \(\operatorname{BR}_i(s_{-i})=\{t_i\}\) for every \(s_{-i}\) ; in particular a player has at most one strictly dominant strategy.
Proof. (a) Let \(t_i\) strictly dominate \(s_i\) and fix \(s_{-i}\) . Then \(u_i(t_i,s_{-i})>u_i(s_i,s_{-i})\) , so \(s_i\) does not attain the maximum of \(u_i(\cdot,s_{-i})\) and is not a best response to \(s_{-i}\) . (b) Fix \(s_{-i}\) . For every \(s_i\ne t_i\) we have \(u_i(t_i,s_{-i})>u_i(s_i,s_{-i})\) , so \(t_i\) is the unique maximizer of \(u_i(\cdot,s_{-i})\) . If \(t_i\) and \(t_i'\) were two different strictly dominant strategies, each would be the unique best response to a given \(s_{-i}\) , which is impossible.
Part (a) fails for weak dominance. A weakly dominated strategy can tie with its dominator against some \(s_{-i}\) and so be a best response there; Example 1.6 below contains one. This small gap between the strict and the weak notion has large consequences in Section 1.5.
When every player has a strictly dominant strategy, the prediction is as firm as game theory ever gets: each player’s choice is optimal regardless of what the others do, know, or believe. The café game is of this kind. Its fame comes from what the prediction looks like to an outside observer.
Definition 1.5 (Pareto comparison). A profile \(s\) Pareto dominates a profile \(s'\) if \(u_i(s)\ge u_i(s')\) for every player \(i\) and \(u_j(s)>u_j(s')\) for at least one player \(j\) . A profile is Pareto efficient if no profile Pareto dominates it.
In the café game, (High, High) Pareto dominates (Low, Low): \(6>3\) for both owners. The other three profiles are all Pareto efficient, since moving away from any of them lowers somebody’s payoff. So the unique dominant-strategy outcome is the only inefficient profile in the table. A game with this structure, two strategies each, a strictly dominant strategy for each player, and a dominant-strategy profile that is Pareto dominated, is called a prisoner’s dilemma, after the story usually told about it. The lesson is that individual optimality and collective efficiency are different properties, tested by different comparisons. Dominance compares two cells that differ in one player’s strategy and looks at that player’s payoff. Pareto dominance compares two arbitrary cells and looks at everyone’s payoff. Neither implies the other.
Example 1.4: A dilemma with many players
Each of \(n\ge 2\) villagers decides whether to contribute one day of labour to a drainage ditch. Write \(c_i=1\) if villager \(i\) contributes and \(c_i=0\) otherwise. Every day of labour contributed, by anyone, is worth \(m\) to each villager, where \(1/n<m<1\) , and contributing costs the contributor \(1\) . So
There is no table to draw when \(n\) is large, but the definition of dominance needs none. Fix any choices \(c_{-i}\) of the others and let \(k\) be the number of them who contribute. Contributing gives villager \(i\) the payoff \(m(k+1)-1\) and not contributing gives \(mk\) . The difference is \(m-1<0\) , whatever \(k\) is. So not contributing strictly dominates contributing, for every villager. If nobody contributes, each gets \(0\) . If everybody contributes, each gets \(mn-1>0\) . The dominant-strategy profile is Pareto dominated by universal contribution.
With \(n=4\) and \(m=0.4\) : if all four contribute each gets \(0.4\cdot 4-1=0.6\) ; if three contribute, each contributor gets \(0.4\cdot 3-1=0.2\) and the villager who stays home gets \(1.2\) ; if nobody contributes each gets \(0\) . The two conditions on \(m\) do different jobs. The inequality \(m<1\) makes staying home individually better, and the inequality \(m>1/n\) makes universal contribution collectively better. If \(m>1\) contributing would be dominant and there would be no dilemma; if \(m<1/n\) the ditch would not be worth digging.
1.4 Iterated elimination of strictly dominated strategies
Few games have dominant strategies. Many more have some strictly dominated strategy, and removing it can change the picture for the other players. The reasoning is layered. A rational player never plays a strictly dominated strategy, by Proposition 1.4(a). A player who knows that the opponents are rational can therefore ignore their strictly dominated strategies, and against the smaller set of opponent behaviours some of the player’s own strategies may have become strictly dominated. A player who knows that the opponents know this can go one step further, and so on.
Definition 1.6 (iterated elimination). Let \(G\) be a finite game. A reduction of \(G\) is a game obtained by restricting each player \(i\) to a nonempty subset \(R_i\subseteq S_i\) , with the payoff functions restricted accordingly. An elimination sequence is a sequence of reductions \(G=G^0,G^1,\dots,G^K\) in which each \(G^{k+1}\) is obtained from \(G^k\) by removing one or more strategies that are strictly dominated in \(G^k\) , and in which no strategy is strictly dominated in \(G^K\) . The strategies of \(G^K\) are said to survive iterated elimination of strictly dominated strategies.
Dominance at stage \(k\) is tested inside \(G^k\) : the dominating strategy must still be present, and the comparison runs only over opponent profiles that are still present. Because the game is finite and each step removes at least one strategy, every elimination sequence stops.
Example 1.5: Four rounds of elimination
Consider
Round 1. For player 1, \(T\) strictly dominates \(M\) : comparing first coordinates column by column, \(3>2\) , \(4>0\) , and \(6>2\) . No other strategy is strictly dominated in the full game. In particular \(C\) is not: against \(M\) it gives player 2 the payoff \(6\) , more than \(L\) or \(R\) . Remove \(M\) .
Round 2. With rows \(T\) and \(B\) left, player 2’s payoffs are \((2,4)\) from \(L\) , \((1,3)\) from \(C\) , and \((5,3)\) from \(R\) . Now \(L\) strictly dominates \(C\) , since \(2>1\) and \(4>3\) . The strategy \(C\) was protected only by the row \(M\) , which a rational player 1 never uses. Remove \(C\) .
Round 3. With columns \(L\) and \(R\) left, player 1’s payoffs are \((3,6)\) from \(T\) and \((1,3)\) from \(B\) . So \(T\) strictly dominates \(B\) . Remove \(B\) .
Round 4. Only row \(T\) is left, and player 2 gets \(2\) from \(L\) and \(5\) from \(R\) . Remove \(L\) .
The single surviving profile is \((T,R)\) , with payoffs \((6,5)\) . Each round used a longer chain of knowledge than the last. Round 1 needs player 1 to be rational. Round 2 needs player 2 to be rational and to know that player 1 is. Round 3 needs player 1 to know that player 2 knows that player 1 is rational. The prediction \((T,R)\) therefore rests on four levels of this hierarchy, and it is weaker evidence than a dominant-strategy prediction in proportion.
In Example 1.5 there was only one strictly dominated strategy available at each round, so the order of removal was forced. In general several strategies may be removable at once, and one may remove them all, or one at a time in any order. It matters that the answer does not depend on such choices.
Theorem 1.7 (order independence). In a finite game, every elimination sequence ends with the same reduction. That is, the set of strategies surviving iterated elimination of strictly dominated strategies does not depend on the order in which strictly dominated strategies are removed, or on how many are removed at each step.
Proof. Let two elimination sequences end in reductions with strategy sets \((R_i)\) and \((R_i')\) . By symmetry it suffices to show \(R_i\subseteq R_i'\) for every \(i\) . Suppose not. Then the second sequence removes some strategy that belongs to the first final reduction; consider the first step at which this happens, and let \(s_i\in R_i\) be a strategy removed at that step, from a reduction with strategy sets \((Q_j)\) . Because no strategy of any \(R_j\) was removed earlier, \(R_j\subseteq Q_j\) for every player \(j\) .
The strategy \(s_i\) is strictly dominated in the reduction \((Q_j)\) by some \(t^0\in Q_i\) , so \(u_i(t^0,s_{-i})>u_i(s_i,s_{-i})\) for all \(s_{-i}\in Q_{-i}\) , and in particular for all \(s_{-i}\in R_{-i}\) . If \(t^0\in R_i\) , then \(s_i\) is strictly dominated in the final reduction \((R_j)\) of the first sequence, contradicting the definition of an elimination sequence. So \(t^0\notin R_i\) : the first sequence removed \(t^0\) at some step, from a reduction whose opponent profiles include \(R_{-i}\) , because some \(t^1\) present at that step strictly dominated it there. Then for all \(s_{-i}\in R_{-i}\) ,
If \(t^1\in R_i\) we again have a contradiction. Otherwise the first sequence removed \(t^1\) as well, at the same step as \(t^0\) or a later one, from a reduction whose opponent profiles again include \(R_{-i}\) , because some \(t^2\) present in that reduction strictly dominated it there. Continuing, we obtain strategies \(t^0,t^1,t^2,\dots\) , each removed by the first sequence and each strictly better than its predecessor, and hence strictly better than \(s_i\) , against every \(s_{-i}\in R_{-i}\) . Because each is strictly better than all the earlier ones against the same profiles, no strategy occurs twice in the chain. Player \(i\) has finitely many strategies, so the chain must stop, and it can stop only at a strategy \(t^m\in R_i\) , since every strategy outside \(R_i\) has a successor. That strategy strictly dominates \(s_i\) in the reduction \((R_j)\) , which is the contradiction that proves \(R_i\subseteq R_i'\) .
The chain cannot be ordered by the steps at which its members were removed, because Definition 1.6 lets one step remove several strategies, and a strategy and its dominator may leave together; what makes the chain end is that its members are distinct. Two features of the proof are worth isolating. Strict inequalities chain together: if \(t^1\) beats \(t^0\) and \(t^0\) beats \(s_i\) against the same opponent profiles, then \(t^1\) beats \(s_i\) . And strict dominance is inherited by smaller games: an inequality that holds against every profile in \(Q_{-i}\) holds against every profile in a subset of \(Q_{-i}\) . The first feature also holds for weak dominance. The second does not, because the one profile at which the weak inequality was strict may be among those removed.
A game in which iterated elimination leaves exactly one profile is called dominance solvable. Most games are not. In many, some strategies are removed and a smaller game with no dominated strategies remains, which then has to be analysed by other means. In others, such as the game of Example 1.3, nothing can be removed at all.
1.5 Why weak dominance is treated differently
It is tempting to eliminate weakly dominated strategies too. A weakly dominated strategy is never better than its dominator and sometimes worse, so why would anyone use it? The trouble is that the iterated procedure built on weak dominance has no analogue of Theorem 1.7.
Example 1.6: The order of weak eliminations changes the answer
Consider
Nothing is strictly dominated. For player 1, \(M\) weakly dominates \(T\) (the payoffs are \(2=2\) against \(L\) and \(3>0\) against \(R\) ) and \(M\) weakly dominates \(B\) (\(2>0\) against \(L\) and \(3=3\) against \(R\) ). For player 2, neither column weakly dominates the other in the full game: \(L\) is better against \(T\) and \(R\) is better against \(B\) .
Order A. Remove \(T\) . In the remaining game with rows \(M\) and \(B\) , player 2 gets \((1,0)\) from \(L\) and \((1,1)\) from \(R\) , so \(R\) weakly dominates \(L\) . Remove \(L\) . Player 1 is then indifferent between \(M\) and \(B\) , and the surviving profiles are \((M,R)\) and \((B,R)\) , both with payoffs \((3,1)\) .
Order B. Remove \(B\) . In the remaining game with rows \(T\) and \(M\) , player 2 gets \((1,1)\) from \(L\) and \((0,1)\) from \(R\) , so \(L\) weakly dominates \(R\) . Remove \(R\) . The surviving profiles are \((T,L)\) and \((M,L)\) , both with payoffs \((2,1)\) .
A third order, removing \(T\) and \(B\) together at the first step, leaves the row \(M\) with both columns, because player 2 gets \(1\) from either column against \(M\) . The orders A and B leave disjoint sets of profiles, and player 1’s surviving payoff is \(3\) in one and \(2\) in the other. The argument for removing \(R\) in order B was that \(R\) does worse than \(L\) against \(T\) ; but \(T\) is itself a strategy that order A discards at once. The justification for a weak elimination can thus be destroyed by another weak elimination. Notice also that \(T\) , although weakly dominated, is a best response to \(L\) , in agreement with the remark after Proposition 1.4.
Common mistake. Deleting weakly dominated strategies round after round and reporting “the” surviving set. For strict dominance the survivors are well defined by Theorem 1.7. For weak dominance they depend on the order of deletion, so an answer must either state the order used or avoid the procedure. A related slip is to call a strategy dominated after checking only some columns. To test whether \(t_i\) strictly dominates \(s_i\) , write one inequality for every opponent profile still in the game and check that each is strict. In Example 1.6 the comparison of \(M\) with \(T\) produces \(2\ge 2\) and \(3>0\) , which is weak dominance and nothing more.
Weak dominance is still informative when used once, without iteration. A weakly dominant strategy is a best response to every \(s_{-i}\) , so a player who has one can use it without forming any view about the others. The most important example in this book is the second-price auction of Chapter 9, in which bidding one’s true value is weakly dominant.
1.6 What dominance leaves open
Dominance arguments ask almost nothing of the players. A strictly dominant strategy is optimal whatever the others do; iterated elimination needs only that the players are rational and know, to some finite depth, that the others are. The price of such weak assumptions is that in most games they decide little.
Two drivers approach each other on a narrow lane and each must swerve to their own left or their own right. If both choose left they pass safely, and likewise if both choose right; otherwise they collide. Give each driver payoff \(1\) for passing and \(0\) for a collision. For either driver, left is the unique best response to left and right is the unique best response to right. No strategy is dominated, weakly or strictly, and iterated elimination removes nothing. Yet the situation is not shapeless: there are two cells in which each driver is doing the best possible given the other’s choice, and two in which each would rather have chosen differently. Dominance cannot tell these apart, because dominance never asks what the other player is in fact doing.
The best-response marking of Example 1.3 already pointed at the missing idea. A cell in which every player’s strategy is a best response to the others’ strategies is stable in a way that needs no dominance: nobody can gain by changing alone. Such cells are the subject of Chapter 2. They exist in the drivers’ game, they exist in Example 1.3, and Chapter 2 proves that they are compatible with everything done here: no profile of that kind is ever removed by iterated elimination of strictly dominated strategies, and when elimination leaves a single profile, that profile is the only one.
Exercises
-
Two neighbours each decide whether to Clear or Leave the snow on a shared path. Each ranks the outcomes, from best to worst: the other clears alone; both clear; neither clears; I clear alone. Write this as a game in strategic form, naming \(N\) , each \(S_i\) , and a payoff table that uses the numbers \(4,3,2,1\) for the ranks, and decide whether either player has a strictly dominant strategy.
Answer
\(N=\{1,2\}\) and \(S_i=\{\text{Clear},\text{Leave}\}\) . With rows and columns in the order Clear, Leave, the cells are \((3,3)\) and \((1,4)\) in the first row and \((4,1)\) and \((2,2)\) in the second. Leave is strictly dominant for each neighbour (\(4>3\) and \(2>1\) ), and the dominant-strategy profile (Leave, Leave) is Pareto dominated by (Clear, Clear): the game is a prisoner’s dilemma.
-
For the game \(\begin{array}{c|ccc}& L & C & R\\\hline T&(2,5)&(4,1)&(0,3)\\ M&(3,3)&(1,2)&(4,4)\\ B&(3,0)&(0,6)&(2,2)\end{array}\) find \(\operatorname{BR}_1\) of each column and \(\operatorname{BR}_2\) of each row, and list every cell in which both players are best responding.
Answer
\(\operatorname{BR}_1(L)=\{M,B\}\) , \(\operatorname{BR}_1(C)=\{T\}\) , \(\operatorname{BR}_1(R)=\{M\}\) ; \(\operatorname{BR}_2(T)=\{L\}\) , \(\operatorname{BR}_2(M)=\{R\}\) , \(\operatorname{BR}_2(B)=\{C\}\) . The only cell in which both players are best responding is \((M,R)\) , with payoffs \((4,4)\) .
-
In the game \(\begin{array}{c|ccc}& L & C & R\\\hline T&(1,4)&(5,2)&(3,3)\\ B&(2,1)&(6,0)&(0,2)\end{array}\) decide for each player whether any strategy is strictly dominated, writing out every inequality you use, and say which strategies survive iterated elimination.
Answer
Player 1 has no strictly dominated strategy: \(T\) is better against \(R\) (\(3>0\) ) and \(B\) is better against \(L\) (\(2>1\) ). For player 2, \(C\) is strictly dominated by \(L\) (\(4>2\) and \(1>0\) ), and also by \(R\) (\(3>2\) and \(2>0\) ). After \(C\) is removed nothing else is strictly dominated: \(L\) beats \(R\) against \(T\) and loses against \(B\) , and player 1 still prefers \(B\) against \(L\) and \(T\) against \(R\) . The survivors are \(\{T,B\}\) and \(\{L,R\}\) .
-
Apply iterated elimination of strictly dominated strategies to \(\begin{array}{c|ccc}& L & C & R\\\hline T&(4,2)&(2,6)&(5,1)\\ M&(2,1)&(0,7)&(3,5)\\ B&(5,3)&(5,5)&(1,7)\end{array}\) in two different orders, record the dominating strategy and the inequalities at each step, and confirm that both orders leave the same reduced game. Is this game dominance solvable?
Solution
In the full game two strategies are strictly dominated. For player 1, \(T\) strictly dominates \(M\) , because the first coordinates satisfy \(4>2\) , \(2>0\) , and \(5>3\) . For player 2, \(C\) strictly dominates \(L\) , because the second coordinates satisfy \(6>2\) , \(7>1\) , and \(5>3\) . No other strategy is strictly dominated: \(B\) is player 1’s best response to \(L\) and to \(C\) , \(T\) is the best response to \(R\) , and for player 2 the strategy \(R\) is the best response to \(B\) while \(C\) is the best response to \(T\) and to \(M\) .
Order 1. Remove \(M\) , then \(L\) . After \(M\) is gone, the comparison of \(C\) with \(L\) uses only the rows \(T\) and \(B\) , where \(6>2\) and \(5>3\) , so \(L\) is still strictly dominated.
Order 2. Remove \(L\) , then \(M\) . After \(L\) is gone, the comparison of \(T\) with \(M\) uses only the columns \(C\) and \(R\) , where \(2>0\) and \(5>3\) , so \(M\) is still strictly dominated.
Both orders leave the reduced game
\[ \begin{array}{c|cc} & C & R\\ \hline T & (2,6) & (5,1)\\ B & (5,5) & (1,7) \end{array} \]In it, player 1 prefers \(B\) against \(C\) and \(T\) against \(R\) , and player 2 prefers \(C\) against \(T\) and \(R\) against \(B\) , so nothing is strictly dominated and elimination stops. The game is not dominance solvable: four profiles survive. The agreement of the two orders is an instance of Theorem 1.7.
-
Prove that if every player in a finite game has a strictly dominant strategy, then the profile of those strategies is the only profile that survives iterated elimination of strictly dominated strategies.
Solution
Let \(t_i\) be the strictly dominant strategy of player \(i\) and let \(t=(t_1,\dots,t_n)\) . In the full game every strategy \(s_i\ne t_i\) is strictly dominated, namely by \(t_i\) . The strategy \(t_i\) is not strictly dominated: by Proposition 1.4(b) it is a best response to every \(s_{-i}\) , and by Proposition 1.4(a) a strictly dominated strategy is a best response to nothing. Consider the elimination sequence that removes, in a single step, every strategy other than \(t_i\) for every player \(i\) . That is allowed by Definition 1.6, since all of them are strictly dominated in the full game. The resulting reduction has the single profile \(t\) , and in a game where each player has one strategy nothing can be dominated, so the sequence ends there. By Theorem 1.7 every elimination sequence ends with the same reduction. Hence \(t\) is the only surviving profile, whatever order is used.
-
Prove that weak dominance is transitive: if \(r_i\) weakly dominates \(t_i\) and \(t_i\) weakly dominates \(s_i\) , then \(r_i\) weakly dominates \(s_i\) . Then give a \(2\times 2\) game in which a weakly dominated strategy is a best response to one of the opponent’s strategies.
Solution
Suppose \(r_i\) weakly dominates \(t_i\) and \(t_i\) weakly dominates \(s_i\) . For every \(s_{-i}\) we have \(u_i(r_i,s_{-i})\ge u_i(t_i,s_{-i})\ge u_i(s_i,s_{-i})\) , which gives the weak inequalities between \(r_i\) and \(s_i\) . There is some \(\hat s_{-i}\) with \(u_i(t_i,\hat s_{-i})>u_i(s_i,\hat s_{-i})\) , and at that profile \(u_i(r_i,\hat s_{-i})\ge u_i(t_i,\hat s_{-i})>u_i(s_i,\hat s_{-i})\) . So the inequality between \(r_i\) and \(s_i\) is strict at least once, and \(r_i\) weakly dominates \(s_i\) .
For the example, let player 1’s payoffs be \(1\) and \(0\) in row \(T\) and \(1\) and \(1\) in row \(B\) , against columns \(L\) and \(R\) , with player 2’s payoffs all equal to \(0\) . Then \(B\) weakly dominates \(T\) , since \(1\ge 1\) and \(1>0\) . Yet \(T\) attains the maximal payoff \(1\) against \(L\) , so \(T\in\operatorname{BR}_1(L)\) . A weakly dominated strategy can be a best response; only a strictly dominated one cannot.
-
A student examines \(\begin{array}{c|cc}& L & R\\\hline T&(9,0)&(1,1)\\ B&(4,2)&(3,0)\end{array}\) and writes “\(T\) dominates \(B\) because the best payoff in row \(T\) is \(9\) and the best payoff in row \(B\) is only \(4\) .” Explain precisely what is wrong with this argument, give the correct dominance analysis for both players, and say what survives iterated elimination.
Hint
Dominance compares the two rows column by column, not their largest entries. Against \(L\) compare \(9\) with \(4\) ; against \(R\) compare \(1\) with \(3\) . What does the second comparison say about the claim? Then compare player 2’s columns row by row: \(0\) with \(1\) in row \(T\) and \(2\) with \(0\) in row \(B\) . You should find that nothing is dominated for either player, so all four profiles survive.
-
In the game \(\begin{array}{c|ccc}& L & C & R\\\hline T&(1,3)&(1,3)&(0,0)\\ B&(0,0)&(1,4)&(1,4)\end{array}\) show that no strategy is strictly dominated, find every weak dominance relation in the full game, and exhibit two orders of iterated elimination of weakly dominated strategies that end with different sets of surviving profiles, giving player 2’s payoff in each.
Solution
No strict dominance. Player 1’s payoffs are \((1,1,0)\) in row \(T\) and \((0,1,1)\) in row \(B\) ; \(T\) is better against \(L\) and \(B\) is better against \(R\) , so neither dominates the other in any sense. Player 2’s payoffs are \((3,0)\) in column \(L\) , \((3,4)\) in column \(C\) , and \((0,4)\) in column \(R\) . Comparing \(C\) with \(L\) gives \(3=3\) and \(4>0\) ; comparing \(C\) with \(R\) gives \(3>0\) and \(4=4\) . Each comparison contains an equality, so there is no strict dominance, and \(L\) and \(R\) do not dominate each other because each is better in one row.
Weak dominance in the full game. \(C\) weakly dominates \(L\) and \(C\) weakly dominates \(R\) . There are no other relations.
Order A. Remove \(L\) . With columns \(C\) and \(R\) , player 1 gets \((1,0)\) from \(T\) and \((1,1)\) from \(B\) , so \(B\) weakly dominates \(T\) . Remove \(T\) . Player 2 is then indifferent between \(C\) and \(R\) . The survivors are \((B,C)\) and \((B,R)\) , and player 2’s payoff is \(4\) .
Order B. Remove \(R\) . With columns \(L\) and \(C\) , player 1 gets \((1,1)\) from \(T\) and \((0,1)\) from \(B\) , so \(T\) weakly dominates \(B\) . Remove \(B\) . The survivors are \((T,L)\) and \((T,C)\) , and player 2’s payoff is \(3\) .
The two orders leave disjoint sets of profiles, so iterated elimination of weakly dominated strategies gives no well-defined answer here.
-
In the café game of Example 1.1, suppose each owner’s payoff is their own profit plus \(\alpha\) times the other’s profit, where \(\alpha\ge 0\) . Write the payoff table in terms of \(\alpha\) and find all \(\alpha\) for which High is strictly dominant, all \(\alpha\) for which Low is strictly dominant, and what happens at the boundary value.
Solution
With concern \(\alpha\) for the other owner, the payoffs are \(6+6\alpha\) for each at (High, High), \(3+3\alpha\) for each at (Low, Low), and at (Low, High) the low-price owner gets \(8+\alpha\) while the other gets \(1+8\alpha\) . By symmetry it is enough to examine player 1.
Against High: High gives \(6+6\alpha\) and Low gives \(8+\alpha\) . High is strictly better exactly when \(6+6\alpha>8+\alpha\) , that is, when \(\alpha>2/5\) .
Against Low: High gives \(1+8\alpha\) and Low gives \(3+3\alpha\) . High is strictly better exactly when \(1+8\alpha>3+3\alpha\) , that is, again when \(\alpha>2/5\) .
So High is strictly dominant for \(\alpha>2/5\) and Low is strictly dominant for \(0\le\alpha<2/5\) . At \(\alpha=2/5\) both comparisons are equalities (\(8.4=8.4\) and \(4.2=4.2\) ): each owner is indifferent between the two prices whatever the other does, every strategy is a best response to everything, and nothing is dominated even weakly. Example 1.1 is the case \(\alpha=0\) and Example 1.2 the case \(\alpha=1/2\) .
-
In the ditch game of Example 1.4 with \(n=5\) villagers, find the range of \(m\) for which the game is a dilemma, and for \(m=0.3\) compute each villager’s payoff when all contribute, when exactly two contribute, and when none contribute.
Answer
The game is a dilemma for \(1/5<m<1\) . With \(m=0.3\) : all contribute, each gets \(0.3\cdot 5-1=0.5\) ; exactly two contribute, each contributor gets \(0.6-1=-0.4\) and each of the other three gets \(0.6\) ; none contribute, each gets \(0\) .
-
Let \(G\) be a finite game and let \(G'\) be obtained by replacing each \(u_i\) by \(a_iu_i+b_i\) with \(a_i>0\) . Prove that \(G\) and \(G'\) have the same best-response correspondences and the same strict dominance relations. Then show by a \(2\times 2\) example that adding a constant to player 1’s payoffs in one row only can change which of player 1’s strategies is dominant.
Solution
Fix a player \(i\) and a profile \(s_{-i}\) . For any two strategies \(s_i,t_i\) ,
\[ a_iu_i(t_i,s_{-i})+b_i\ \ge\ a_iu_i(s_i,s_{-i})+b_i\iff u_i(t_i,s_{-i})\ge u_i(s_i,s_{-i}), \]because subtracting \(b_i\) and dividing by the positive number \(a_i\) preserves the direction of an inequality; the same equivalence holds with strict inequalities. Hence a strategy maximizes \(a_iu_i(\cdot,s_{-i})+b_i\) if and only if it maximizes \(u_i(\cdot,s_{-i})\) , so the best-response sets agree for every \(s_{-i}\) . And \(t_i\) strictly dominates \(s_i\) in \(G'\) if and only if the strict inequality holds for every \(s_{-i}\) in \(G'\) , which by the equivalence happens if and only if it holds for every \(s_{-i}\) in \(G\) .
For the example, let player 1 get \(2\) in both cells of row \(T\) and \(1\) in both cells of row \(B\) . Then \(T\) is strictly dominant. Add \(3\) to row \(B\) only: now row \(B\) pays \(4\) in both cells and \(B\) is strictly dominant. The change is not of the form \(a_1u_1+b_1\) , because the constant added depends on player 1’s own strategy, and comparisons between a player’s own strategies are exactly what a payoff function encodes.
-
Two partners each choose an effort level in \(\{0,1,2\}\) , and \(u_i(s_i,s_j)=3s_j+2s_i-s_i^2\) . Without drawing the table, show that effort \(1\) is strictly dominant for each partner; then draw the table and find a profile that Pareto dominates the dominant-strategy profile.
Answer
The part of \(u_i\) that depends on \(s_i\) is \(2s_i-s_i^2\) , which equals \(0,1,0\) at \(s_i=0,1,2\) ; the term \(3s_j\) is the same whatever \(s_i\) is. So effort \(1\) gives exactly \(1\) more than either alternative against every \(s_j\) and is strictly dominant. At \((1,1)\) each partner gets \(4\) . At \((2,2)\) each gets \(6\) , so \((2,2)\) Pareto dominates \((1,1)\) .
-
Three players each choose \(A\) or \(B\) . A player who chooses \(A\) gets \(2\) if at least one other player also chooses \(A\) and \(0\) otherwise; a player who chooses \(B\) gets \(1\) regardless. Write player 1’s payoff for each of the four profiles of the other two players, and decide whether any strategy is strictly or weakly dominated.
Hint
List the profiles of the other two players as \((A,A)\) , \((A,B)\) , \((B,A)\) , \((B,B)\) . Against the first three, \(A\) pays \(2\) and \(B\) pays \(1\) ; against the last, \(A\) pays \(0\) and \(B\) pays \(1\) . A strategy that is strictly better in one column and strictly worse in another is not dominated in either sense.
-
Two travellers each claim \(2\) , \(3\) , or \(4\) . Both are paid the smaller claim; in addition, if the claims differ, the one who claimed less receives a bonus of \(2\) and the other pays a penalty of \(2\) . Write the \(3\times 3\) table, show that no strategy is strictly dominated, and carry out iterated elimination of weakly dominated strategies, stating at each round which strategy is removed and why.
Answer
With rows and columns in the order \(2,3,4\) , the rows of the table are \((2,2),(4,0),(4,0)\) ; then \((0,4),(3,3),(5,1)\) ; then \((0,4),(1,5),(4,4)\) . No claim is strictly dominated: \(2\) loses to \(3\) against a claim of \(4\) (\(4<5\) ), \(3\) ties with \(4\) against a claim of \(2\) , and \(2\) ties with \(4\) against a claim of \(4\) . In the full game the claim \(4\) is weakly dominated, by \(3\) (\(0=0\) , \(3>1\) , \(5>4\) ) and by \(2\) . Remove it for both travellers. In the remaining \(2\times 2\) game the claim \(2\) strictly dominates \(3\) (\(2>0\) and \(4>3\) ). The survivor is \((2,2)\) with payoffs \((2,2)\) , although \((4,4)\) would give each traveller \(4\) .
-
For the game of Example 1.5, list every Pareto-efficient profile, and decide whether the profile that survives iterated elimination is Pareto efficient.
Answer
The payoff pair \((6,5)\) at \((T,R)\) Pareto dominates every other cell except \((M,C)\) , whose pair \((0,6)\) gives player 2 the highest payoff in the table. The Pareto-efficient profiles are \((T,R)\) and \((M,C)\) , and the surviving profile \((T,R)\) is efficient.
-
A game has \(n\) players, each with \(k\) strategies. How many strategy profiles are there, how many real numbers are needed to specify the game, and how many inequalities must be checked to verify that one given strategy of player 1 strictly dominates another? Evaluate all three for \(n=3\) and \(k=4\) .
Answer
There are \(k^n\) profiles and the game is specified by \(nk^n\) numbers. Dominance of one strategy of player 1 by another requires one inequality for each profile of the other players, \(k^{n-1}\) in all. For \(n=3\) and \(k=4\) these are \(64\) , \(192\) , and \(16\) .
-
For Example 1.5, change the single payoff \(u_2(M,C)\) from \(6\) to \(0\) . Redo the elimination, say how many strategies are now strictly dominated in the full game, and explain why the surviving profile is the same although the knowledge needed to reach it has changed.
Hint
With \(u_2(M,C)=0\) , compare \(C\) with \(L\) in all three rows. You should find two strictly dominated strategies in the full game, one for each player. By Theorem 1.7 the order does not matter, so the survivor is unchanged; what changes is that the removal of \(C\) no longer needs player 2 to know anything about player 1.
-
Two partners choose efforts \(e_1,e_2\in[0,4]\) and \(u_i(e_i,e_j)=e_i(1+e_j)-e_i^2\) . Using the fact that a concave quadratic in \(e_i\) decreases to the right of its vertex and increases to the left of it, show that every \(e_i>2.5\) is strictly dominated by \(2.5\) and every \(e_i<0.5\) is strictly dominated by \(0.5\) . Repeat the argument in the reduced game, find the interval of efforts that survives \(k\) rounds, and identify the unique effort that survives every round.
Solution
For fixed \(e_j\) , the payoff \(u_i(e_i,e_j)=e_i(1+e_j)-e_i^2\) is a concave quadratic in \(e_i\) with vertex at \(e_i=(1+e_j)/2\) . As \(e_j\) ranges over \([0,4]\) the vertex ranges over \([0.5,2.5]\) .
Let \(e_i>2.5\) . For every \(e_j\in[0,4]\) the vertex is at most \(2.5\) , so both \(2.5\) and \(e_i\) lie to the right of the vertex, where the quadratic is strictly decreasing. Hence \(u_i(2.5,e_j)>u_i(e_i,e_j)\) for every \(e_j\) : the effort \(2.5\) strictly dominates \(e_i\) . Symmetrically, if \(e_i<0.5\) both \(e_i\) and \(0.5\) lie to the left of every possible vertex, where the quadratic is strictly increasing, so \(0.5\) strictly dominates \(e_i\) .
No effort in \([0.5,2.5]\) is strictly dominated, because each such \(e_i\) is the best response to \(e_j=2e_i-1\in[0,4]\) , and a strictly dominated strategy is never a best response. So one round leaves exactly \([0.5,2.5]\) .
Now repeat with \(e_j\) confined to an interval \([a,b]\) : the vertices range over \([(1+a)/2,(1+b)/2]\) , and the same argument leaves exactly that interval. Starting from \(a_0=0\) and \(b_0=4\) , the recursions \(a_{k+1}=(1+a_k)/2\) and \(b_{k+1}=(1+b_k)/2\) give
\[ a_k=1-2^{-k},\qquad b_k=1+3\cdot 2^{-k}, \]as one checks by induction: \((1+1-2^{-k})/2=1-2^{-k-1}\) and \((1+1+3\cdot 2^{-k})/2=1+3\cdot 2^{-k-1}\) . After two rounds the interval is \([0.75,1.75]\) . Both endpoints converge to \(1\) , and \(1\) belongs to every interval, so the unique effort that survives every round is \(e_i=1\) .