Game Theory — Module 2

Games with Perfect Information

Instructor Lecture Notes & Student Handout — 7 Lecture Sessions

Note for the Instructor

These notes are written to be delivered as-is to a large class (100 students) and also double as your own lecture
script, since this is being taught for the first time. Each lecture opens with a boxed header stating its learning
objectives and closes with an in-class exercise you can run on the spot (cold-call or think-pair-share both work
well for a 100-student room). Every model that needs mathematics (Cournot, Bertrand, mixed strategy, repeated
games) is derived step by step — nothing is asserted without showing where it comes from, so you can
reconstruct any derivation live on the board with confidence.
Table of Contents
TOC \h \o "1-3"
 LECTURE 1 of 7 — Strategic Games — Formal Setup, Prisoner's Dilemma,
Matching Pennies
Learning Objectives:
• Write down the formal definition of a strategic (normal-form) game with general notation.
• Recall and generalize the Prisoner's Dilemma and Matching Pennies from Module 1.
• Define the Best Response function — the single most important tool for the rest of this module.

1.1 Recap: What We Already Know (from Module 1)

In Module 1 we defined a game informally as Players + Strategies + Payoffs, and looked at the Prisoner's Dilemma and
Matching Pennies using specific numbers. In Module 2, we make this fully general and rigorous, so that the SAME
framework can describe an oligopoly, an auction, or a repeated interaction — not just a 2x2 toy example.

1.2 Formal Definition of a Strategic Game

A strategic game (also called a normal-form game or game in strategic form) consists of:
1. A finite set of players N = {1, 2, ..., n}.
2. For each player i, a non-empty set of actions Aᵢ (also written Sᵢ for "strategy set" — in a strategic/one-shot game,
action and strategy mean the same thing).
3. For each player i, a payoff function uᵢ : A → ℝ, where A = A₁ × A₂ × ... × Aₙ is the set of all possible action profiles
(one action chosen by each player).
We write this compactly as G = ⟨N, (Aᵢ), (uᵢ)⟩. An action profile is written a = (a₁, a₂, ..., a ₙ); we will very often write a = (aᵢ,
a₋ᵢ), separating out player i's own action aᵢ from everyone else's actions a₋ᵢ = (a₁,...,aᵢ ₋₁, aᵢ ₊₁,...,a ₙ). This notation is used
constantly from here on — make sure students can read a₋ᵢ comfortably before moving on.

Instructor Tip
On the board, physically circle aᵢ and box a₋ᵢ in an example action profile the first time you write it. Students
consistently confuse "a sub minus i" with a negative number — spend thirty seconds killing that misreading
early.

1.3 Prisoner's Dilemma — The General Version

Module 1 used specific numbers. Now consider the general Prisoner's Dilemma payoff structure, where every entry is a
named payoff satisfying one ordering condition:
• T = Temptation payoff (I defect while you cooperate) — the best individual outcome.
• R = Reward payoff (both cooperate) — the best joint outcome.
• P = Punishment payoff (both defect).
• S = Sucker's payoff (I cooperate while you defect) — the worst individual outcome.
The defining condition of ANY Prisoner's Dilemma is the ordering: T > R > P > S, together with the requirement 2R > T + S
(this second condition ensures mutual cooperation is jointly better than "taking turns" exploiting each other — it will matter
again in Lecture 7 on repeated games).
Player 1 \ Player 2 Cooperate Defect
Cooperate R, R S, T
Defect T, S P, P

Exactly as in Module 1, Defect strictly dominates Cooperate for both players (because T > R and P > S), so (Defect, Defect)
is the unique Nash Equilibrium — regardless of the SPECIFIC numbers, as long as the T > R > P > S ordering holds. This is
the power of working with the general structure instead of one numeric example: the conclusion is now proven for an entire
FAMILY of games at once.

1.4 Matching Pennies — Revisited as a Zero-Sum Game

Recall from Module 1: two players each show Heads or Tails; Player 1 wins if they match, Player 2 wins if they differ. We
now formally classify this:

Definition: Zero-Sum Game

A two-player game is zero-sum if, in every action profile, u₁(a) + u₂(a) = 0 (or more generally, sums to some
fixed constant k). One player's gain is always exactly the other player's loss — there is no way for both players
to be better off together, unlike the Prisoner's Dilemma.

Matching Pennies is the canonical zero-sum game and, as we saw in Module 1, it has NO Nash Equilibrium in pure strategies
— every cell leaves someone wanting to switch. We will return to this game twice more in this module: once with the Best-
Response underlining method (Lecture 2) and once to formally compute its mixed strategy equilibrium (Lecture 5).

1.5 The Best Response Function — The Most Important Tool in This Module
This single idea will be reused in every remaining lecture — Nash equilibrium, Cournot, Bertrand, auctions, and subgame
perfection are all, underneath, applications of "best response".

Definition: Best Response

Player i's best response to the other players' actions a₋ᵢ is the action (or set of actions) that maximizes player i's
own payoff, given a₋ᵢ:
BRᵢ(a₋ᵢ) = { aᵢ ∈ Aᵢ : uᵢ(aᵢ, a₋ᵢ) ≥ uᵢ(aᵢ′, a₋ᵢ) for all aᵢ′ ∈ Aᵢ }
In plain English: "given what everyone else is doing, what is the best thing I can do?" This is exactly the
underlining step you already used informally in Module 1's Best Response Method (Section B.7.1) — we are
now giving it a formal name and notation.

In-Class Exercise 1
Write the Battle of the Sexes payoff matrix on the board (from Module 1) and cold-call students to state BR₁(Football) and
BR₁(Ballet) out loud, then BR₂(Football) and BR₂(Ballet). This primes them perfectly for the formal Nash Equilibrium
definition in Lecture 2, which is built directly out of these four best-response statements.
 LECTURE 2 of 7 — Nash Equilibrium — Formal Theory and Illustrations;
Zero-Sum Games
Learning Objectives:
• State the formal definition of Nash Equilibrium using the Best Response function.
• Understand (without proof) why Nash Equilibrium always exists in finite games.
• Apply the definition to several new illustrative games beyond Prisoner's Dilemma.

2.1 The Formal Definition of Nash Equilibrium

Definition: Nash Equilibrium

An action profile a* = (a₁*, a₂*, ..., aₙ*) is a Nash Equilibrium if, for every player i, aᵢ* ∈ BRᵢ(a ₋ᵢ*) — i.e.,
every single player's action is a best response to everyone else's equilibrium action, SIMULTANEOUSLY, for
all players at once.
Equivalently: no player can gain by unilaterally deviating, given everyone else's action stays fixed at a*.

This is exactly the plain-English idea from Module 1 ("I'm doing the best I can given what you're doing, and vice versa") —
we have simply written it using the Best Response notation from Lecture 1, which makes it directly usable in the Cournot,
Bertrand and auction models later in this module.

2.2 Existence of Nash Equilibrium (Nash's Theorem — Statement Only)

Nash's Existence Theorem (1950)

Every strategic game with a FINITE number of players, each having a FINITE set of actions, has AT LEAST
ONE Nash Equilibrium — possibly requiring mixed strategies (Lecture 5).
We state this without proof (the proof uses Kakutani's fixed-point theorem, which is outside the scope of this
course) — but the CONSEQUENCE is important and testable: if you check every pure-strategy profile and find
none work, the game is NOT equilibrium-free — you simply have not looked at mixed strategies yet (see
Matching Pennies).

2.3 Illustrations: Working Through More Games

Illustration A: The Stag Hunt (A Coordination Game)
Two hunters can each choose to hunt Stag (requires both hunters cooperating, high reward) or Hare (safe, can be done alone,
lower reward):
Hunter 1 \ Hunter 2 Stag Hare
Stag 4, 4 0, 3
Hare 3, 0 3, 3

Using the Best Response method: (Stag, Stag) is a Nash Equilibrium (4 ≥ 3 for both, given the other stays at Stag), AND
(Hare, Hare) is ALSO a Nash Equilibrium (3 ≥ 0 for both, given the other stays at Hare). This introduces an important new
idea: (Stag, Stag) Pareto-dominates (Hare, Hare) (both do strictly better), yet (Hare, Hare) is "safer" — it doesn't depend on
trusting the other hunter. This tension between the payoff-dominant and the risk-dominant equilibrium is a classic discussion
point worth pausing on in class.

Illustration B: Chicken / Hawk-Dove Game

Two drivers speed toward each other; each can Swerve or go Straight. Going Straight while the other Swerves is the best
outcome; both going Straight is disastrous:
 Driver 1 \ Driver 2 Swerve Straight
Swerve 3, 3 1, 5
Straight 5, 1 0, 0

Two pure Nash Equilibria exist: (Swerve, Straight) and (Straight, Swerve) — each player wants to be the one who does NOT
swerve, but SOMEONE has to swerve in equilibrium. Notice the structural similarity to Battle of the Sexes (Module 1): both
are "anti-coordination"-flavoured games with two asymmetric pure equilibria, but here the players' interests are more starkly
opposed than in Battle of the Sexes.

2.4 Zero-Sum Games and the Idea of a "Value"

Return to Matching Pennies (Lecture 1). Since it is zero-sum with no pure Nash Equilibrium, game theorists ask a different
question: is there a payoff level that Player 1 can GUARANTEE regardless of Player 2's action, and that Player 2 can prevent
Player 1 from EXCEEDING? This guaranteed level is called the value of the game.

Minimax Idea (Preview — fully solved in Lecture 5)

maximin: the best worst-case payoff Player 1 can guarantee by picking their best action against the worst
possible response.
minimax: the best worst-case payoff Player 2 can guarantee by limiting Player 1's best possible outcome.
Von Neumann's Minimax Theorem: in any FINITE two-player zero-sum game, allowing mixed strategies,
maximin = minimax = the unique VALUE of the game. We will compute this exact number for Matching
Pennies in Lecture 5 once mixed strategies are formally defined.

In-Class Exercise 2
Split the 100-student room into pairs. Give half the pairs the Stag Hunt matrix and half the Chicken matrix (both already on
the slide). Ask each pair to find ALL pure Nash Equilibria using the Best Response definition from Section 2.1, and cold-call
3–4 pairs for each game. This is a good moment to informally poll: "who would actually play Hare/Swerve?" — it motivates
the mixed-strategy discussion to come.
 LECTURE 3 of 7 — Cournot's Model of Oligopoly (Quantity Competition)
Learning Objectives:
• Set up the Cournot duopoly as a strategic game with continuous action spaces (quantities).
• Derive each firm's best response (reaction) function from profit maximization.
• Solve for the Cournot-Nash Equilibrium quantities, price, and profits, and generalize to n firms.

3.1 Why Cournot Matters Here

Every game so far had a small, discrete action set (Cooperate/Defect, Heads/Tails). Cournot's model (1838) — actually older
than modern game theory itself — is our first example where a firm's "action" is a CONTINUOUS number (how much to
produce), and Nash Equilibrium is found using calculus (first-order conditions) instead of a payoff table. This is a major
conceptual jump for students; go slowly.

3.2 Model Setup

Two firms (a duopoly), Firm 1 and Firm 2, simultaneously and independently choose quantities q₁ ≥ 0 and q₂ ≥ 0 of an
identical (homogeneous) product. The total quantity supplied to the market is Q = q₁ + q₂.
Market (inverse) demand function: P(Q) = a − bQ = a − b(q₁ + q₂), where a, b > 0 are constants (a is the choke price where
demand hits zero; b is how steeply price falls as quantity rises).
Assume both firms have the same constant marginal cost c per unit (0 ≤ c < a), and no fixed cost, for simplicity.
Firm i's profit function (this IS firm i's payoff function uᵢ in our strategic-game language):

πᵢ(qᵢ, qⱼ) = qᵢ · P(Q) − c·qᵢ = qᵢ [a − b(qᵢ + qⱼ) − c]

3.3 Deriving the Best Response (Reaction) Function

Firm 1 chooses q₁ to maximize π₁, TREATING q₂ as given (fixed) — this is exactly the Best Response idea from Lecture 1,
applied to a continuous action.
π₁(q₁, q₂) = q₁[a − b(q₁ + q₂) − c]
= a·q₁ − b·q₁² − b·q₁·q₂ − c·q₁

First-order condition — differentiate w.r.t. q₁ and set to zero:

∂π₁/∂q₁ = a − 2b·q₁ − b·q₂ − c = 0

Solve for q₁:

a − c − b·q₂
q₁ = ───────────────── = BR₁(q₂)
2b
This is Firm 1's Best Response / Reaction Function: it tells Firm 1 the profit-maximizing quantity to produce, FOR ANY
quantity q₂ that Firm 2 might choose. Notice it is DOWNWARD SLOPING in q₂ — the more Firm 2 produces, the less Firm
1 wants to produce (quantities are "strategic substitutes"). By perfect symmetry, Firm 2's reaction function is q₂ = BR₂(q₁) =
(a − c − b·q₁) / 2b.

3.4 Solving for the Cournot-Nash Equilibrium

A Nash Equilibrium here is a pair (q₁*, q₂*) where BOTH reaction functions hold simultaneously — exactly the Nash
Equilibrium definition from Lecture 2 (Section 2.1), just with continuous best responses instead of a table. By symmetry of
the two firms, we expect q₁* = q₂* = q*. Substitute q₂ = q* into Firm 1's reaction function:
a − c − b·q*
q* = ────────────────
 2b

2b·q* = a − c − b·q*
3b·q* = a − c

a − c
q₁* = q₂* = ───── = q* (Cournot-Nash quantity, each firm)
3b
Substitute back to find total quantity, market price, and profit:
• Total industry output: Q* = q₁* + q₂* = 2(a − c) / 3b
• Equilibrium price: P* = a − bQ* = a − (2/3)(a − c) = (a + 2c) / 3
• Each firm's equilibrium profit: π* = q*(P* − c) = (a − c)² / 9b

Instructor Tip — Board Diagram

Draw q₁ on the horizontal axis and q₂ on the vertical axis. Plot BOTH reaction functions as straight downward-
sloping lines. Their intersection point IS the Cournot-Nash Equilibrium (q₁*, q₂*) — this single picture is the
most memorable takeaway of the lecture; students who forget the algebra usually still remember "equilibrium =
where the two reaction lines cross".

3.5 Generalizing to n Firms

With the same demand and cost setup but n identical firms, the same first-order-condition method (now for firm i, treating the
sum of all OTHER firms' quantities as given) yields, by symmetry, each firm producing:

qᵢ* = (a − c) / [(n+1)b] so that total output Q* = n(a − c) /

[(n+1)b]
As n → ∞, total output Q* approaches (a − c)/b, which is exactly the perfectly competitive output level (price = marginal
cost). This is a key insight: Cournot competition smoothly interpolates between monopoly (n = 1) and perfect competition (n
→ ∞) as the number of competing firms grows.

In-Class Exercise 3
Give the room specific numbers: a = 100, b = 1, c = 10. Ask students (individually, 5 minutes, then reveal) to compute q*,
P*, and π* for the duopoly case using the boxed formulas above. (Answer: q* = 30 each, Q* = 60, P* = 40, π* = 900 each.)
This numerical check is important — 100 students copying symbolic algebra off a slide often make sign errors; a clean
numeric example catches this immediately.
 LECTURE 4 of 7 — Bertrand's Model of Oligopoly (Price Competition) and
Comparison with Cournot
Learning Objectives:
• Set up the Bertrand duopoly where firms compete in PRICE rather than quantity.
• Derive the Bertrand Paradox: equilibrium price collapses to marginal cost.
• Compare and contrast the Cournot and Bertrand predictions, and see how each can be resolved/extended.

4.1 Model Setup

Same industry as Lecture 3 (homogeneous product, constant marginal cost c for both firms) — but NOW firms
simultaneously choose PRICES p₁ and p₂ instead of quantities. Consumers are assumed to have perfect information and zero
switching cost, so ALL consumers buy from whichever firm charges the LOWER price (if prices are equal, demand is split
equally, typically 50-50).
Firm i's demand (how much it actually sells) therefore depends discontinuously on BOTH prices:
• If pᵢ < pⱼ : Firm i gets the ENTIRE market demand D(pᵢ).
• If pᵢ = pⱼ : Firm i gets HALF the market demand, D(pᵢ)/2.
• If pᵢ > pⱼ : Firm i gets ZERO demand — all customers go to the cheaper rival.

4.2 The Undercutting Argument (Reasoning Toward Equilibrium)

Rather than a smooth first-order condition (Section 3.3), Bertrand's logic is a direct argument by contradiction — walk
through it slowly on the board, as this is the part students find most surprising:
4. Claim: any price pair with pᵢ > c for both firms CANNOT be a Nash Equilibrium. Suppose both firms charge some
price p > c. Firm 1 could instead charge a price just slightly below p (say p − ε) — it would capture the ENTIRE
market instead of half, at an almost-unchanged margin. This is a strictly profitable deviation, so p > c for both firms is
never an equilibrium.
5. Claim: any price pair with pᵢ < c for either firm cannot be an equilibrium either — that firm would be selling at a loss
on every unit, and could profitably raise its price (or exit the low-price competition) instead.
6. The only price surviving both arguments is p₁ = p₂ = c — at this point, neither firm can profitably undercut (price
cannot go below marginal cost without a loss), and neither wants to raise its price alone (it would lose all its customers
to the rival, who is still at c).

4.3 The Bertrand Paradox

The Bertrand Paradox

With just TWO firms, homogeneous products, and simultaneous price competition, the Nash Equilibrium price
falls all the way to marginal cost (p* = c), exactly matching the PERFECTLY COMPETITIVE outcome — and
both firms earn ZERO economic profit.
This is called a "paradox" because it seems to say that competition among just two firms is already as fierce as
competition among infinitely many firms (compare to Cournot's n → ∞ result in Lecture 3, Section 3.5, which
needed MANY firms to reach the same competitive outcome) — a single extra competitor should not usually
cause such a dramatic collapse in real markets, which is exactly why economists went looking for ways to
resolve the paradox (Section 4.5).

4.4 Cournot vs Bertrand: Side-by-Side Comparison

Feature Cournot Model Bertrand Model
Strategic variable Quantity (qᵢ) Price (pᵢ)
 Nature of best response Downward-sloping (substitutes) Undercutting (discontinuous)
Equilibrium price (duopoly, P* = (a + 2c)/3 (above cost) p* = c (equals marginal cost)
n=2)
Equilibrium profit Strictly positive: (a−c)²/9b Zero economic profit
Approaches competitive Number of firms n → ∞ Already with just n = 2 firms
outcome when...
Real-world fit Markets with capacity/production Markets with easy quantity adjustment,
limits (e.g., steel, oil) homogeneous goods

4.5 Resolving the Bertrand Paradox (Brief Extensions)

• Capacity Constraints (Edgeworth/Kreps-Scheinkman) — if firms cannot produce unlimited quantities even after
undercutting, the fierce undercutting incentive breaks down, and equilibrium prices rise above marginal cost again.
• Product Differentiation — if the two firms' products are not perfectly identical (branding, quality, location), consumers
do not switch entirely for a tiny price difference, softening price competition.
• Repeated Interaction — if firms interact over many periods (previewed here, developed fully in Lecture 7), tacit
collusion sustained by the threat of future price wars can support prices above marginal cost.

In-Class Exercise 4
Pose this question to the full room and take a quick show-of-hands vote before revealing the answer: "If a market has only
TWO airlines flying an identical route, does Bertrand's model predict ticket prices equal to cost?" Use the vote to launch
straight into the capacity-constraint resolution (Section 4.5, first bullet) — airline seats are exactly a capacity-constrained
good.
 LECTURE 5 of 7 — Auctions; Mixed Strategy Equilibrium; Zero-Sum Games
(Formal Solution)
Learning Objectives:
• Classify the standard auction formats and analyze the second-price (Vickrey) auction rigorously.
• Define mixed strategies formally and compute the mixed-strategy Nash Equilibrium of Matching Pennies.
• Return to zero-sum games and compute the exact value of a game using the minimax idea from Lecture 2.

5.1 Auction Formats

• English Auction (open ascending-bid) — auctioneer raises the price; bidders drop out; last remaining bidder wins at the
final price. Common for art, antiques.
• Dutch Auction (open descending-bid) — auctioneer starts high and lowers the price until a bidder accepts. Used
historically for flowers (hence the name) and some IPO mechanisms.
• First-Price Sealed-Bid Auction — every bidder submits one secret bid; highest bidder wins and pays THEIR OWN bid.
• Second-Price Sealed-Bid / Vickrey Auction — every bidder submits one secret bid; highest bidder wins but pays the
SECOND-highest bid (this is the mechanism behind Module 1's eBay example, and a simplified relative of Google's
GSP auction).

5.2 Second-Price (Vickrey) Auction — Truthful Bidding is Dominant

Claim: in a second-price sealed-bid auction, bidding your TRUE valuation vᵢ is a (weakly) dominant strategy — exactly the
dominant-strategy idea from Module 1, Section B.6.1.
Proof sketch (walk through both directions on the board):
7. Suppose you bid ABOVE your true value (bᵢ > vᵢ). The only case this changes the outcome is when the second-highest
bid is between vᵢ and bᵢ — in that case, overbidding makes YOU win at a price ABOVE your own valuation, which is a
loss you would have avoided by bidding truthfully. Overbidding never helps and can hurt.
8. Suppose you bid BELOW your true value (bᵢ < vᵢ). The only case this changes the outcome is when the second-highest
bid is between bᵢ and vᵢ — in that case, underbidding makes you LOSE an auction you would have profitably won
(paid less than your value) by bidding truthfully. Underbidding never helps and can hurt.
9. Therefore bidding exactly bᵢ = vᵢ is always at least as good as any other bid, regardless of what other bidders do — the
definition of a dominant strategy.

5.3 First-Price Sealed-Bid Auction — Why Bidders "Shade" Their Bids

Here you pay YOUR OWN bid if you win, so bidding your true value vᵢ would win but give you ZERO surplus (profit = vᵢ −
vᵢ = 0) — clearly not optimal. Rational bidders shade their bid below their true value, trading off a lower chance of winning
against a higher profit if they do win. For the symmetric case of n bidders with valuations drawn independently and
uniformly from [0, v̄ ], the symmetric Nash Equilibrium bidding function can be shown to be:

b(vᵢ) = [(n − 1) / n] × vᵢ
Notice: as the number of bidders n grows, (n−1)/n → 1, so bidders shade LESS and bid closer to their true value — more
competition pushes first-price bidding behavior toward the truthful behavior we get automatically in a second-price auction.
(Full derivation of this formula uses calculus of variations / differential equations and is left for a more advanced auction
theory course — state the RESULT and its intuition here.)

5.4 Mixed Strategies — Formal Definition

Definition: Mixed Strategy

 A mixed strategy for player i is a probability distribution over player i's (pure) action set Aᵢ. If Aᵢ = {aᵢ¹, aᵢ²}, a
mixed strategy is simply a number σᵢ ∈ [0,1] representing the probability of playing aᵢ¹ (and 1−σᵢ of playing aᵢ²).
A pure strategy is just the special case σᵢ = 0 or σᵢ = 1.

Worked Example: Mixed Strategy Equilibrium of Matching Pennies

Recall the payoffs from Lecture 1 (Player 1 wants to match, Player 2 wants to mismatch). Let Player 1 play Heads with
probability p (Tails with probability 1−p), and Player 2 play Heads with probability q (Tails with probability 1−q).
Key Principle — the Indifference Condition: in a mixed-strategy Nash Equilibrium, EVERY pure action that a player mixes
over with positive probability must give that player EXACTLY THE SAME expected payoff (otherwise the player would put
all probability on the better one, and it would not really be "mixing"). We use this to solve for the opponent's mixing
probability.
Player 2 must be indifferent between Heads and Tails, GIVEN Player 1 plays Heads
with prob. p:

Expected payoff to Player 2 from Heads = p(−1) + (1−p)(+1) = 1 − 2p

Expected payoff to Player 2 from Tails = p(+1) + (1−p)(−1) = 2p − 1

Set equal: 1 − 2p = 2p − 1 → 2 = 4p → p = 1/2

By the identical argument applied to Player 1 (indifferent given Player 2's mix q):
q = 1/2
So the unique mixed-strategy Nash Equilibrium is: both players randomize 50/50 between Heads and Tails. This matches
intuition perfectly — any predictable pattern (any p or q ≠ 1/2) could be exploited by the opponent, so pure unpredictability is
the only stable outcome.

5.5 Zero-Sum Games: Computing the Value

Using the equilibrium mixing probabilities (p = q = 1/2) found above, we can now compute the VALUE of Matching Pennies
previewed in Lecture 2 (Section 2.4):
Expected payoff to Player 1 at (p=1/2, q=1/2):
= (1/2)(1/2)(+1) + (1/2)(1/2)(−1) + (1/2)(1/2)(−1) + (1/2)(1/2)(+1)
= 1/4 − 1/4 − 1/4 + 1/4 = 0
The value of Matching Pennies is exactly 0 — a perfectly "fair" zero-sum game, confirming the minimax theorem from
Lecture 2: maximin = minimax = 0 here, achieved precisely at the mixed strategy equilibrium we just solved for.

In-Class Exercise 5
Ask students to redo the exact same indifference-condition calculation for the Battle of the Sexes matrix (Module 1) to find
its mixed-strategy equilibrium (Answer: Player 1 plays Football with probability 2/3, Player 2 plays Football with probability
1/3 — give them the payoff numbers and let them derive it themselves as homework/tutorial, since it is a direct copy of the
method just demonstrated).
 LECTURE 6 of 7 — Extensive Games with Perfect Information; Subgame
Perfect Nash Equilibrium
Learning Objectives:
• Represent a sequential decision situation as a game tree with perfect information.
• Apply backward induction to solve extensive games.
• Define a subgame and Subgame Perfect Nash Equilibrium (SPNE), and see why some Nash Equilibria are
NOT credible.

6.1 Why We Need a New Representation

Every game up to now (strategic/normal form) assumed players choose SIMULTANEOUSLY, with no player observing
another's move before deciding. Many real situations are SEQUENTIAL — one player moves, the next player OBSERVES
that move and then responds. The Extensive Form (game tree), introduced briefly in Module 1 (Section B.3.5), is built
exactly for this.

6.2 Extensive Game with Perfect Information — Formal Ingredients

• A game tree: a set of nodes connected by branches, starting from a single root (initial) node.
• Decision nodes: each belongs to exactly one player, who chooses among the branches leading out of it.
• Terminal nodes: the ends of the tree, each labeled with a payoff for every player.
• Perfect Information means every decision node is its own singleton "information set" — in plain language, whoever is
moving can see the ENTIRE history of the game so far (every earlier move by every player) before choosing. This
rules out simultaneous moves and hidden information within the tree.

6.3 Worked Example: The Market Entry Game

An Entrant is deciding whether to enter a market currently monopolized by an Incumbent. If the Entrant enters, the
Incumbent then chooses to Fight (start a price war) or Accommodate (share the market peacefully). If the Entrant stays out,
the game ends immediately.
Entrant
/ \
Enter Stay Out
| |
Incumbent (1, 5)
/ \
Fight Accommodate
| |
(0, 0) (2, 3)

[Payoffs written as (Entrant, Incumbent)]

This tree has TWO decision nodes (Entrant's initial choice, and the Incumbent's choice reached only if Entrant plays Enter)
and THREE terminal nodes, each with a payoff pair.

6.4 Backward Induction

Definition: Backward Induction

An algorithm for solving finite extensive games with perfect information: start at the LAST decision nodes in
the tree (closest to the terminal nodes), determine the optimal choice there, replace that entire sub-tree with its
resulting payoff, and repeat this process moving BACKWARD toward the root, one layer at a time, until the
whole tree is solved.
Applying it to the Entry Game:
10. Step 1 (last decision node): At the Incumbent's node, compare Fight (payoff 0 to Incumbent) vs Accommodate (payoff
3 to Incumbent). Accommodate is better for the Incumbent — so a rational Incumbent, IF this node is ever reached,
will Accommodate.
11. Step 2 (fold back): Replace the Incumbent's decision node with its predicted outcome, Accommodate, giving payoffs
(2, 3). The tree now effectively becomes: Entrant chooses between Enter → (2, 3) and Stay Out → (1, 5).
12. Step 3 (root node): Compare Enter (payoff 2 to Entrant) vs Stay Out (payoff 1 to Entrant). Enter is better — the Entrant
enters.
The backward-induction solution (and, as we will now see, the Subgame Perfect Nash Equilibrium) is: Entrant plays Enter;
Incumbent plays Accommodate (if reached) — final outcome (2, 3).

6.5 Subgames and Subgame Perfect Nash Equilibrium (SPNE)

Definition: Subgame
A subgame is any part of the extensive game that starts at a single decision node and includes every node/branch
that follows from it — it is a complete, self-contained game in its own right. In the Entry Game, the Incumbent's
decision node (with its two branches Fight/Accommodate) is a valid subgame; so is the WHOLE tree from the
root.

Definition: Subgame Perfect Nash Equilibrium

A strategy profile is a Subgame Perfect Nash Equilibrium (SPNE) if it induces a Nash Equilibrium in EVERY
SINGLE subgame of the original game — not just in the game as a whole. Equivalently (and this is the practical,
usable version): the SPNE is exactly the outcome found by Backward Induction.

6.6 Why Not Every Nash Equilibrium Is Subgame Perfect (Non-Credible Threats)
Consider the strategy profile: Entrant plays Stay Out; Incumbent plays Fight (if ever reached). Check: is this a Nash
Equilibrium of the WHOLE game? Given the Incumbent threatens to Fight, the Entrant's payoff from Enter would be 0
(worse than Stay Out's payoff of 1) — so Stay Out IS the Entrant's best response to this threat, and the Incumbent has nothing
to reconsider since the Enter branch is never actually played. This IS technically a Nash Equilibrium of the full game!

But It Is NOT Subgame Perfect

Look at the SUBGAME starting at the Incumbent's node alone. IF that node were ever reached, would the
Incumbent actually choose to Fight? No — Accommodate (payoff 3) beats Fight (payoff 0) for the Incumbent.
The threat to Fight is a NON-CREDIBLE THREAT: it only "works" to deter entry because we never test
whether the Incumbent would actually carry it out. SPNE eliminates exactly this kind of empty threat by
requiring optimal play in EVERY subgame, including ones that end up never being reached along the
equilibrium path.

This is arguably the single most important idea in this lecture: Nash Equilibrium alone can support outcomes that only
survive because of an incredible promise or threat; Subgame Perfection is the refinement that rules these out, using nothing
more than the Backward Induction algorithm you already know how to execute.

In-Class Exercise 6
Draw a new, slightly different tree on the board: same structure, but change the Incumbent's Fight payoff from (0,0) to (0, 4)
instead. Ask the class (2 minutes, then reveal): does backward induction still give Accommodate? (Answer: No — now Fight
(4) beats Accommodate (3) for the Incumbent, so the SPNE flips to Enter met with Fight, giving (0,4); reworking this by
hand is the best way to confirm students can actually PERFORM backward induction rather than just recognizing the
previous answer.)
 LECTURE 7 of 7 — Repeated Games (Prisoner's Dilemma); Computational
Issues; Module Review
Learning Objectives:
• Distinguish finitely and infinitely repeated games, and see why finite repetition of the Prisoner's Dilemma
unravels to permanent defection.
• Show how cooperation CAN be sustained as a Subgame Perfect Nash Equilibrium in an infinitely repeated
Prisoner's Dilemma using the Grim Trigger strategy.
• Understand the computational issues associated with each solution concept covered in this module.

7.1 What Is a Repeated Game?

A repeated game takes a single strategic game (the STAGE game — e.g., the Prisoner's Dilemma from Lecture 1) and has the
SAME players play it over and over, observing all past outcomes before each new round. A player's overall strategy must
now specify an action for every possible ROUND, given every possible HISTORY of past play so far — this is a direct
extension of the "strategy = complete plan" idea from Module 1, Section B.3.2.
• Finitely Repeated Game — the stage game is played a fixed, commonly known number of times, T.
• Infinitely Repeated Game — the stage game is (in principle) played forever; because an infinite sum of payoffs needs
care, players' payoffs are usually measured as a discounted sum using a discount factor δ ∈ (0,1), where δ represents
how much a player values next round's payoff relative to this round's (patience).

7.2 Finitely Repeated Prisoner's Dilemma: The Unraveling Argument

Suppose the Prisoner's Dilemma stage game is repeated a FIXED, known T times. We solve this using Backward Induction
(Lecture 6) — exactly the same algorithm, just applied to a much bigger (but still finite) tree.
13. Consider the LAST round, round T. There is no future left to protect — so this is identical to a single, one-shot
Prisoner's Dilemma. Since Defect strictly dominates (Lecture 1, Section 1.3), BOTH players Defect in round T, no
matter what happened before.
14. Now consider round T−1. Since round T's outcome (mutual defection) is ALREADY fixed regardless of what happens
in round T−1, there is nothing to gain by cooperating in round T−1 either — there is no way to "reward" future
cooperation, since round T is already decided. So both players Defect in round T−1 too.
15. Repeating this backward-induction logic all the way to round 1: both players Defect in EVERY single round. The
unique Subgame Perfect Nash Equilibrium of the finitely repeated Prisoner's Dilemma is Always Defect, in every
round, regardless of how large T is.

This Result Often Surprises Students

It seems intuitive that repeating an interaction many times should encourage cooperation ("I'll be nice now so
you're nice to me next time") — but with a FIXED, KNOWN final round, backward induction unravels this all
the way back to round 1. This is sometimes called the "chain-store paradox". The key missing ingredient,
restored in the next section, is an UNKNOWN or INFINITE horizon, so there is never a "last round" from which
unraveling can start.

7.3 Infinitely Repeated Prisoner's Dilemma: Sustaining Cooperation

Now suppose the game is repeated infinitely (or, equivalently, ends each round only with some fixed small probability, so
there is never a KNOWN final round). Consider the Grim Trigger strategy for each player:

Grim Trigger Strategy

Cooperate in round 1. In every later round, continue to Cooperate AS LONG AS both players have cooperated
in every round so far. If EITHER player ever Defects even once, switch to Defect FOREVER after that, as
 punishment.

We check whether BOTH players playing Grim Trigger is a Subgame Perfect Nash Equilibrium, by comparing the payoff
from continuing to cooperate versus deviating (defecting) once, using the general T, R, P, S notation from Lecture 1 (Section
1.3):
Payoff from cooperating forever (discounted sum, using δ ∈ (0,1)):
V_cooperate = R + δR + δ²R + ... = R / (1 − δ)

Payoff from deviating ONCE (defect this round, get caught, punished forever after):
V_deviate = T + δP + δ²P + ... = T + δP/(1 − δ)

Cooperation is sustainable (i.e. nobody wants to deviate) exactly when V_cooperate

≥ V_deviate:

R/(1−δ) ≥ T + δP/(1−δ)
R ≥ (1−δ)T + δP
R ≥ T − δT + δP
δT − δP ≥ T − R
δ(T − P) ≥ T − R

T − R
δ ≥ ─────── (the critical discount-factor threshold)
T − P
So Grim Trigger sustains full cooperation as an SPNE if and only if players are sufficiently patient: δ ≥ (T − R)/(T − P).
Intuition: if players care enough about the future (δ close to 1), the threat of permanent punishment outweighs the one-time
temptation payoff T, and rational, self-interested players cooperate indefinitely — the exact opposite conclusion from the
finitely repeated case in Section 7.2, purely because there is no known final round to unravel from.

7.4 The Folk Theorem (Informal Statement)

Folk Theorem (Informal)

In an infinitely repeated game, if players are sufficiently patient (δ close enough to 1), ALMOST ANY payoff
outcome that gives each player at least their "minmax" (worst guaranteed) payoff from the stage game can be
sustained as a Subgame Perfect Nash Equilibrium of the repeated game — not just the one-shot Nash
Equilibrium outcome. This is called a "Folk Theorem" because early versions circulated informally among game
theorists before being formally written up and proven.

The practical takeaway for students: repetition dramatically EXPANDS the set of outcomes that can be rationally sustained,
compared to the single-shot game — this is precisely why long-term business relationships, repeated international trade
agreements, and reputational concerns can sustain cooperative behavior that a one-shot analysis would never predict.

7.5 Computational Issues Across This Module

Task Computational Difficulty
Finding pure Nash Equilibria in a Easy — direct inspection / best-response underlining, polynomial time.
small payoff matrix (Lectures 1–2)
Solving Cournot / Bertrand equilibria Easy — closed-form algebraic solution from first-order conditions.
(Lectures 3–4)
Computing a mixed-strategy Easy for 2 players/2 strategies (solve linear indifference equations);
equilibrium (Lecture 5) becomes substantially harder as the number of strategies/players grows.
Finding a general Nash Equilibrium PPAD-complete in general (recall Module 1, Section B.7.2) — no
(arbitrary size game) known efficient algorithm for all cases.
Backward Induction on a finite Efficient — linear in the number of nodes in the tree; the main practical
extensive game (Lecture 6) issue is that real game trees (e.g., chess) can be astronomically LARGE,
not that the algorithm itself is slow per node.
Finding equilibria of repeated/infinite- Substantially harder — the number of possible history-dependent
horizon games (Lecture 7) strategies (like Grim Trigger) grows explosively; the Folk Theorem
shows MANY equilibria can exist, which itself makes selecting among
them a non-trivial computational and conceptual problem.

Module 2 Revision Summary

• A strategic game is formally G = ⟨N, (Aᵢ), (uᵢ)⟩; Best Response BRᵢ(a₋ᵢ) is the foundation for every solution concept in
this module.
• Nash Equilibrium: every player's action is a best response to everyone else's, simultaneously; Nash's Theorem
guarantees existence (possibly in mixed strategies) for any finite game.
• Cournot (quantity competition): reaction functions from first-order conditions; equilibrium price stays above marginal
cost, approaching the competitive outcome only as n → ∞.
• Bertrand (price competition): the undercutting argument drives price down to marginal cost even with just two firms —
the Bertrand Paradox, resolved by capacity constraints or product differentiation.
• Auctions: truthful bidding is dominant in second-price (Vickrey) auctions; first-price auctions require strategic bid-
shading.
• Mixed strategies use the Indifference Condition to solve for equilibrium randomization probabilities (e.g., 50/50 in
Matching Pennies); zero-sum games have a well-defined VALUE via the minimax theorem.
• Extensive games with perfect information are solved via Backward Induction, which is EXACTLY equivalent to
finding the Subgame Perfect Nash Equilibrium (SPNE) — SPNE rules out non-credible threats that plain Nash
Equilibrium can wrongly support.
• Finitely repeated Prisoner's Dilemma unravels to Always Defect (backward induction from the known last round);
infinitely repeated versions can sustain cooperation via strategies like Grim Trigger, provided players are sufficiently
patient (δ above a derived threshold) — formalized broadly by the Folk Theorem.
• Computational difficulty varies sharply across these tasks: small matrices and Cournot/Bertrand are easy and closed-
form; general Nash Equilibrium and repeated-game equilibrium selection are substantially harder problems.