We now formalize simultaneous-move games and develop the most conservative solution concepts: those that rely only on rationality and common knowledge of rationality.

The normal (strategic) form

Normal-form gamenormalform A normal-form (or strategic-form) game is a triple \(G = \langle N, (A_i)_{i \in N}, (u_i)_{i \in N} \rangle\) where

  • \(N = \{1, \dots, n\}\) is a finite set of players;

  • \(A_i\) is the set of actions (pure strategies) available to player \(i\); an action profile is \(a = (a_1, \dots, a_n) \in A = A_1 \times \dots \times A_n\);

  • \(u_i : A \to \R\) is player \(i\)’s payoff function (a vNM utility).

We write \(a_{-i}\) for the profile of actions of everyone except \(i\), and \(a = (a_i, a_{-i})\).

Everything about the game—the sets \(N\), \(A_i\), and functions \(u_i\)—is assumed common knowledge among the players (this is what complete information means).

Two-player finite games are displayed as payoff matrices: rows are player 1’s actions, columns player 2’s, and each cell shows \((u_1, u_2)\).

Classic \(2\times 2\) games

Four canonical games recur throughout the book. Internalize them—they are the fruit flies of game theory.

Prisoner’s Dilemmapd

\(C\) \(D\)
\(C\) \(3,3\) \(0,4\)
\(D\) \(4,0\) \(1,1\)

(Payoffs rescaled from Chapter [ch:intro]; only the ordering matters.) Defection (\(D\)) strictly dominates cooperation; the unique prediction \((D,D)\) is Pareto-dominated by \((C,C)\). Theme: conflict between individual and group rationality.

Coordination / Stag Huntstaghunt Two hunters can jointly hunt a stag (needs both) or individually hunt hares:

Stag Hare
Stag \(4,4\) \(0,2\)
Hare \(2,0\) \(2,2\)

Both (Stag, Stag) and (Hare, Hare) are stable (each is a Nash equilibrium, as we’ll see): the first is payoff-dominant, the second risk-dominant (safer if you doubt your partner). Theme: trust and equilibrium selection.

Battle of the Sexesbos A couple wants to spend the evening together but one prefers the Ballet, the other the Football match:

\(B\) \(F\)
\(B\) \(3,1\) \(0,0\)
\(F\) \(0,0\) \(1,3\)

Coordination is good but the players disagree about where to coordinate. Theme: coordination with distributional conflict.

Matching Penniesmatchingpennies Each player shows Heads or Tails; player 1 wins if they match, player 2 if they differ:

\(H\) \(T\)
\(H\) \(1,-1\) \(-1,1\)
\(T\) \(-1,1\) \(1,-1\)

Pure conflict (zero-sum): whatever one wins the other loses. No pair of pure actions is stable—each player wants to outguess the other. Theme: the need for randomization (Chapter [ch:mixed]).

Dominant and dominated strategies

Dominancedominance Action \(a_i\) strictly dominates \(a_i'\) if \[u_i(a_i, a_{-i}) > u_i(a_i', a_{-i}) \quad \text{for every } a_{-i} \in A_{-i}.\] It weakly dominates \(a_i'\) if the inequality is weak for all \(a_{-i}\) and strict for at least one. An action is strictly (weakly) dominant if it strictly (weakly) dominates every other action; it is strictly dominated if some other action (pure or mixed—see Section 1.5) strictly dominates it.

A rational player never plays a strictly dominated action, whatever her beliefs. When every player has a strictly dominant action, the game is solved by rationality alone—no strategic reasoning about others is even needed. The Prisoner’s Dilemma is the leading case.

Second-price auction (a preview)spapreview A seller auctions one object. Each bidder \(i\) values it at \(v_i\) and submits a sealed bid \(b_i\); the highest bidder wins and pays the second-highest bid. Then bidding truthfully, \(b_i = v_i\), weakly dominates every other bid: overbidding only matters when it wins at a price above \(v_i\) (a loss), underbidding only matters when it loses an object priced below \(v_i\) (a forgone gain). This remarkable dominance argument (Vickrey, 1961) needs no assumptions about opponents at all, and is the seed of mechanism design (Chapter [ch:mechanism]).

Iterated elimination of dominated strategies

Rationality removes dominated actions. Common knowledge of rationality lets us iterate: I know you won’t play dominated actions, so I can delete them from my analysis of your play, which may make some of my actions dominated in the reduced game, and so on.

IESDSiesds Iterated elimination of strictly dominated strategies (IESDS) is the process of repeatedly deleting, for every player, all strictly dominated actions in the current reduced game, until no more deletions are possible. A game is dominance solvable if IESDS leaves exactly one action profile.

Order independenceorderindep In a finite game, the set of action profiles surviving IESDS does not depend on the order or speed of elimination.

(For weak dominance, order matters—one reason strict dominance is the preferred notion for iteration.)

A dominance-solvable gameiesdsexample

\(L\) \(M\) \(R\)
\(T\) \(4,3\) \(2,7\) \(0,4\)
\(B\) \(5,5\) \(5,-1\) \(-4,-2\)

Step 1: for player 2, \(R\) is strictly dominated by \(M\) (\(7>4\) against \(T\); \(-1>-2\) against \(B\)). Delete \(R\). Step 2: in the reduced game, no pure action of player 1 dominates the other (\(4<5\) against \(L\) but \(2<5\) against \(M\): in fact \(B\) dominates \(T\) here since \(5>4\) and \(5>2\)). Delete \(T\). Step 3: against \(B\), player 2 prefers \(L\) (\(5 > -1\)). Delete \(M\). The unique survivor is \((B, L)\) with payoffs \((5,5)\).

The beauty contest (guessing game)beautycontest \(n\) students each pick a number in \([0, 100]\); the winner is whoever is closest to \(\tfrac{2}{3}\) of the class average. Any guess above \(\tfrac{2}{3} \cdot 100 = 66.7\) is dominated (the target can never exceed it). Once those are removed, any guess above \(\tfrac{2}{3} \cdot 66.7 = 44.4\) is dominated, and so on: IESDS spirals down to 0, the unique rationalizable guess. In experiments the winning guess is typically around 20–35: real people iterate only a few steps. Keynes used this game as a metaphor for stock markets (“anticipating what average opinion expects average opinion to be”).

Dominance by mixed strategies

An action can be strictly dominated by a randomization even when no pure action dominates it.

Mixed dominationmixeddom

\(L\) \(R\)
\(T\) \(4,1\) \(0,2\)
\(M\) \(1,1\) \(1,0\)
\(B\) \(0,3\) \(4,1\)

Neither \(T\) nor \(B\) dominates \(M\). But the mixture \(\tfrac12 T + \tfrac12 B\) yields expected payoff \(2\) against both \(L\) and \(R\), strictly beating \(M\)’s payoff of \(1\). So \(M\) is strictly dominated and a rational player 1 never plays it.

From now on, “strictly dominated” always means dominated by some pure or mixed strategy.

Rationalizability

What exactly does common knowledge of rationality imply? An action is justifiable if it is a best response to some belief about opponents’ play; it survives deeper scrutiny only if that belief itself assigns positive probability only to justifiable actions; and so on.

Rationalizability (informal)rationalizability An action is rationalizable if it is a best response to a belief that puts weight only on opponents’ actions that are themselves best responses to such beliefs, recursively ad infinitum.

Rationalizability and IESDS (Bernheim 1984; Pearce 1984)ratiesds In finite two-player games, the set of rationalizable actions coincides exactly with the set of actions surviving iterated elimination of strictly dominated strategies. (With three or more players the equivalence holds if beliefs may be correlated across opponents.)

Rationality \(\Rightarrow\) no strictly dominated actions. Rationality + knowledge of others’ rationality \(\Rightarrow\) survives two rounds of IESDS. Common knowledge of rationality \(\Rightarrow\) rationalizable actions. Nash equilibrium (next chapter) requires something more: correct beliefs, not merely coherent ones.

Exercises

Dominance huntingdomhunt

\(L\) \(C\) \(R\)
\(T\) \(2,0\) \(1,1\) \(4,2\)
\(M\) \(3,4\) \(1,2\) \(2,3\)
\(B\) \(1,3\) \(0,2\) \(3,0\)

Solve by IESDS, stating at each step which action is eliminated and by what it is dominated.

Weak dominance and order dependenceweakorder

\(L\) \(R\)
\(T\) \(1,1\) \(0,0\)
\(M\) \(1,1\) \(2,1\)
\(B\) \(0,0\) \(2,1\)

Show that different orders of eliminating weakly dominated strategies can lead to different final predictions.

Cournot by dominancecournotdom Two firms choose quantities \(q_1, q_2 \ge 0\); market price is \(P = \max\{12 - q_1 - q_2, 0\}\) and production is costless, so \(u_i = q_i P\). Show that any \(q_i > 6\) is strictly dominated. In the reduced game with \(q_i \in [0,6]\), show any \(q_i < 3\) is strictly dominated. Iterate and show the process converges to \(q_1 = q_2 = 4\). (Compare Chapter [ch:applications].)

Traveler’s dilemmatraveler Two travelers independently claim an integer amount in \(\{2, \dots, 100\}\) for lost luggage. Both are paid the lower claim; additionally the lower claimant gets a bonus of 2 and the higher pays a penalty of 2. Show that IESDS (using weak dominance at the top, then strict) leads to both claiming 2, and comment on whether you find the prediction plausible.