SI 563 Tutorial 2

Problem 1: Information Sets and Multiple SPNE (20 points)

Consider the following extensive-form game with imperfect information:

Game Description:

Player 1 moves first and chooses either M or N
If Player 1 chooses N, the game ends with payoffs (1, 1)
If Player 1 chooses M, Player 1 moves again and chooses either L or R
After Player 1's second move (L or R), Player 2 chooses either U or D
Player 2 has imperfect information - they don't know whether Player 1 chose L or R
Payoffs are written as (Player 1, Player 2)

Tasks:

(a) Identify all subgames in this game tree. (3 points)

(b) Find the Nash equilibrium of the subgame that starts after Player 1 chooses M. Show the normal form representation. (6 points)

(c) Use backward induction to find all Subgame Perfect Nash Equilibria (SPNE). Show your reasoning. (8 points)

(d) State the complete SPNE strategy profiles. (3 points)

Solution to Problem 1:

(a) Subgames:

There are 2 subgames (1 proper subgame):

The entire game (starting at Player 1's initial node)
The proper subgame starting after Player 1 chooses M (the simultaneous-move subgame between Player 1's second move and Player 2's move)

(b) Normal Form Representation of the Subgame:

The subgame that starts after Player 1 chooses M is a simultaneous-move game between Player 1 (choosing L or R) and Player 2 (choosing U or D).

	Player 2: U	Player 2: D
Player 1: L	(1, 2)	(3, 0)
Player 1: R	(1, 0)	(2, 2)

Finding Nash Equilibrium in the Subgame:

Player 2's best responses:

If Player 1 chooses L: Player 2 compares U (payoff 2) vs D (payoff 0) → Player 2 chooses U
If Player 1 chooses R: Player 2 compares U (payoff 0) vs D (payoff 2) → Player 2 chooses D

Player 1's best responses:

If Player 2 chooses U: Player 1 compares L (payoff 1) vs R (payoff 1) → Player 1 is indifferent, both give payoff 1
If Player 2 chooses D: Player 1 compares L (payoff 3) vs R (payoff 2) → Player 1 chooses L

Subgame Nash Equilibrium: (L, U) with payoffs (1, 2)

This is the unique pure strategy Nash equilibrium in the subgame.

(c) Backward Induction for SPNE:

Now that we know the subgame equilibrium is (L, U) with payoffs (1, 2), we work backwards:

Player 1's initial choice:

Player 1 compares:

Choosing M: leads to subgame with payoffs (1, 2) → Player 1 gets 1
Choosing N: leads directly to (1, 1) → Player 1 gets 1

Since Player 1 gets the same payoff (1) from both choices, Player 1 is indifferent between M and N.

Two SPNE exist:

SPNE 1: Player 1 chooses M, then L; Player 2 chooses U
SPNE 2: Player 1 chooses N; Player 2 chooses U (off-equilibrium path)

(d) Complete SPNE Strategy Profiles:

SPNE 1: (M;L, U)

Player 1: Choose M, then choose L
Player 2: Choose U
Equilibrium path: M → L → U
Equilibrium payoffs: (1, 2)

SPNE 2: (N;L,U)

Player 1: Choose N
Player 2: Choose L if P1 chose L, choose U if P1 chose R (if subgame were reached)
Equilibrium path: N
Equilibrium payoffs: (1, 1)

Key Insight: The existence of two SPNE arises because Player 1 receives the same payoff (1) from both initial choices, making Player 1 indifferent between M and N. This indifference creates multiple equilibrium outcomes.

Problem 2: Multiple Subgames Case (25 points)

Consider the sequential game represented by the game tree below (exactly as in the shared hand-drawn figure):

Game Description (matches the image):

Player 1 moves first and chooses either Z or W.
If Z: Player 2 chooses C or D.
- (Z,C) → (6, 4)
- (Z,D) → (3, 2)
If W: Player 2 first chooses A or B; then Player 1 moves but does not observe A vs B (both P1 nodes are in the same information set). Player 1 chooses X or Y.
- (A,X) → (3, 0)
- (A,Y) → (8, 5)
- (B,X) → (4, 6)
- (B,Y) → (2, 1)
Payoffs are (Player 1, Player 2).

Tasks:

(a) Identify all subgames. (5 points)

(b) For each proper subgame, find the Nash equilibrium. Show best-response reasoning. (8 points)

(c) Use backward induction to find the SPNE(s) of the entire game. (7 points)

(d) State complete SPNE strategy profiles in the form: (P1 initial; P2 after Z; P2 after W; P1’s action at the W-information-set). (3 points)

Solution to Problem 2:

(a) 3 Subgames:

The entire game (root).
Proper Subgame 1 (after Z): P2 chooses C or D.
Proper Subgame 2 (after W): P2 chooses A/B, then P1 (without observing A/B) chooses X/Y. P1’s two nodes are connected by an information set.

(b) Nash equilibrium in each proper subgame:

Subgame 1 (after Z): P2 compares payoffs: C gives 4 vs D gives 2 ⇒ C is strictly better.

Subgame-1 NE: C ⇒ outcome (6, 4).

Subgame 2 (after W): Best-response arrows from the 2×2 payoff table:

If P1 plays X, P2 prefers B (6 > 0).
If P1 plays Y, P2 prefers A (5 > 1).
If P2 plays A, P1 prefers Y (8 > 3).
If P2 plays B, P1 prefers X (4 > 2).

⇒ Two pure-strategy NE: (A,Y) with payoffs (8,5), and (B,X) with payoffs (4,6).

(c) Backward induction (visual cases):

Case 1 — Subgame 2 continues at (B,X): continuation payoff under W is (4,6). Compare with Z→C = (6,4). Player 1 prefers Z (6 > 4).

Case 2 — Subgame 2 continues at (A,Y): continuation payoff under W is (8,5). Player 1 prefers W (8 > 6).

(d) Complete SPNE strategy profiles:

SPNE-A (when Subgame 2 selects (B,X)):
(Z;X, C;B) → Equilibrium path: Z → C; payoffs (6,4).
SPNE-B (when Subgame 2 selects (A,Y)):
(W;Y, C;A) → Equilibrium path: W → A → Y; payoffs (8,5).

Problem 3: No Pure Nash Equilibrium in Subgame (25 points)

Consider the following sequential game where Player 1 first decides whether to enter a market or fight:

Game Description:

Player 1 moves first and chooses either E (Enter) or F (Fight)
If Player 1 chooses F, the game ends immediately with payoffs (2, 1.5)
If Player 1 chooses E, both players simultaneously play the following subgame:

Subgame Payoff Matrix (after E is chosen):

	Player 2: X	Player 2: Y
Player 1: A	(3, 0)	(0, 3)
Player 1: B	(0, 3)	(3, 0)

Note: This subgame has NO pure strategy Nash equilibrium.

Tasks:

(a) Verify that the subgame (after E is chosen) has no pure strategy Nash equilibrium by checking all four strategy profiles. (4 points)

(b) Find the mixed strategy Nash equilibrium of the subgame. Let p = probability that Player 1 plays A, and q = probability that Player 2 plays X. Show all work including indifference conditions. (8 points)

(c) Calculate the expected payoffs for both players in the mixed strategy Nash equilibrium of the subgame. (4 points)

(d) Using backward induction, determine whether Player 1 will choose E or F in the SPNE. Compare the expected payoff from E with the payoff from F. (5 points)

(e) State the complete SPNE strategy profile, including the mixed strategies in the subgame. (4 points)

Solution to Problem 3:

(a) Verify No Pure Strategy Nash Equilibrium:

Check all four possible pure strategy profiles:

1. (A, X) → (3, 0):

Player 1: If Player 2 plays X, should Player 1 play A (payoff 3) or B (payoff 0)? A is better. ✓
Player 2: If Player 1 plays A, should Player 2 play X (payoff 0) or Y (payoff 3)? Y is better. ✗
Not a Nash equilibrium (Player 2 wants to deviate)

2. (A, Y) → (0, 3):

Player 1: If Player 2 plays Y, should Player 1 play A (payoff 0) or B (payoff 3)? B is better. ✗
Not a Nash equilibrium (Player 1 wants to deviate)

3. (B, X) → (0, 3):

Player 1: If Player 2 plays X, should Player 1 play B (payoff 0) or A (payoff 3)? A is better. ✗
Not a Nash equilibrium (Player 1 wants to deviate)

4. (B, Y) → (3, 0):

Player 1: If Player 2 plays Y, should Player 1 play B (payoff 3) or A (payoff 0)? B is better. ✓
Player 2: If Player 1 plays B, should Player 2 play Y (payoff 0) or X (payoff 3)? X is better. ✗
Not a Nash equilibrium (Player 2 wants to deviate)

Conclusion: No pure strategy Nash equilibrium exists.

(b) Mixed Strategy Nash Equilibrium:

Let p = probability Player 1 plays A (and 1-p for B)

Let q = probability Player 2 plays X (and 1-q for Y)

For Player 2 to mix, Player 2 must be indifferent between X and Y:

Expected payoff from X: E₂(X) = p(0) + (1-p)(3) = 3 - 3p

Expected payoff from Y: E₂(Y) = p(3) + (1-p)(0) = 3p

Set equal: 3 - 3p = 3p

Solving: 3 = 6p → p = 1/2

For Player 1 to mix, Player 1 must be indifferent between A and B:

Expected payoff from A: E₁(A) = q(3) + (1-q)(0) = 3q

Expected payoff from B: E₁(B) = q(0) + (1-q)(3) = 3 - 3q

Set equal: 3q = 3 - 3q

Solving: 6q = 3 → q = 1/2

Mixed Strategy Nash Equilibrium: (p*, q*) = (1/2, 1/2)

Each player plays each of their strategies with probability 1/2.

(c) Expected Payoffs in Mixed Strategy Equilibrium:

Player 1's expected payoff:

E₁ = 3q = 3(1/2) = 3/2 = 1.5

(Or equivalently: E₁ = 3 - 3q = 3(1/2) = 1.5)

Player 2's expected payoff:

E₂ = 3p = 3(1/2) = 3/2 = 1.5

(Or equivalently: E₂ = 3 - 3p = 3(1/2) = 1.5)

Both players get expected payoff of 1.5 in the mixed strategy equilibrium.

(d) Backward Induction - Will Player 1 Choose E or F?

Compare expected payoffs:

Choosing F: Player 1 gets 2
Choosing E: Player 1 expects 1.5 (from the mixed strategy equilibrium)

Since 2 > 1.5, Player 1 prefers to choose F.

(e) Complete SPNE Strategy Profile:

Player 1 chooses F at the initial node.

Off-equilibrium behavior (if E were chosen): Both players would play the mixed strategy (1/2, 1/2) in the subgame.

Complete SPNE:

(F; play A with probability 1/2 and B with probability 1/2 if E is chosen; play X with probability 1/2 and Y with probability 1/2 if E is chosen)

Equilibrium outcome: F is chosen, game ends with payoffs (2, 1.5)

Problem 4: Information Sets and Subgame Perfect Nash Equilibrium (30 points)

Consider the following extensive-form game with imperfect information:

Game Description:

Player 1 moves first and chooses either A or B
Player 2 chooses either C or D
If Player 2 chooses C, the game ends with payoffs depending on Player 1's initial choice:
- If P1 chose A: payoffs are (1, 2)
- If P1 chose B: payoffs are (7, 8)
If Player 2 chooses D, Player 1 gets to move again and chooses either E or F:
- If P1 chose A initially and then E: payoffs are (3, 4)
- If P1 chose A initially and then F: payoffs are (5, 6)
- If P1 chose B initially and then E: payoffs are (9, 10)
- If P1 chose B initially and then F: payoffs are (11, 12)
Payoffs are written as (Player 1, Player 2)

Tasks:

(a) Identify all subgames in this game tree. (5 points)

(b) For each subgame, find the Nash equilibrium using backward induction. Show your reasoning clearly. (10 points)

(c) Find all Subgame Perfect Nash Equilibria (SPNE) of the entire game. (8 points)

(d) State the complete SPNE strategy profiles in the form: (Player 1's initial choice; Player 2's choice after A, Player 2's choice after B; Player 1's choice after (A,D), Player 1's choice after (B,D)). (4 points)

(e) What are the equilibrium payoffs for each SPNE? (3 points)

Solution to Problem 4:

(a) Subgames:

There are 3 subgames (2 proper subgames):

The entire game (starting at Player 1's initial node)
Proper Subgame 1: Starting at Player 1's decision node after (A, D)
Proper Subgame 2: Starting at Player 1's decision node after (B, D)

(b) Nash Equilibrium in Each Subgame:

Subgame 1 (after A, D):

Player 1 compares:

Choosing E: payoff = 3
Choosing F: payoff = 5

Since 5 > 3, Player 1's best response is F.

Nash equilibrium in Subgame 1: F

Subgame 2 (after B, D):

Player 1 compares:

Choosing E: payoff = 9
Choosing F: payoff = 11

Since 11 > 9, Player 1's best response is F.

Nash equilibrium in Subgame 2: F

(c) Finding SPNE of the Entire Game:

Now we work backwards to find Player 2's optimal choices, knowing Player 1 will choose F in both subgames:

Player 2's decision after A:

Player 2 compares:

Choosing C: payoff = 2
Choosing D: leads to Player 1 choosing F → payoff = 6

Since 6 > 2, Player 2's best response after A is D.

Player 2's decision after B:

Player 2 compares:

Choosing C: payoff = 8
Choosing D: leads to Player 1 choosing F → payoff = 12

Since 12 > 8, Player 2's best response after B is D.

Player 1's initial decision:

Knowing that Player 2 will choose D after both A and B, and that Player 1 will choose F in both resulting subgames, Player 1 compares:

Choosing A: leads to (A, D, F) → payoff = 5
Choosing B: leads to (B, D, F) → payoff = 11

Since 11 > 5, Player 1's optimal initial choice is B.

There is exactly ONE SPNE:

(B;F;F, D)

(d) Complete SPNE Strategy Profile:

(B;F;F, D)

This means:

Player 1 initially chooses B
Player 2 chooses D after A (off-equilibrium path)
Player 2 chooses D after B (on-equilibrium path)
Player 1 chooses F after (A, D) (off-equilibrium path)
Player 1 chooses F after (B, D) (on-equilibrium path)

(e) Equilibrium Payoffs:

Following the equilibrium path (B → D → F):

Payoffs: (11, 12)

Key Insights:

Player 1 prefers B over A because it leads to higher payoffs in the continuation game
Player 2 always prefers D over C because the continuation game gives higher payoffs
Player 1 always chooses F in the final subgames because it maximizes their payoff
The equilibrium path is B → D → F with payoffs (11, 12)

Problem 5: The Hungry Lions Game (35 points)

Consider a hierarchical group of n hungry lions facing a prey. The game proceeds as follows:

If Lion 1 does not eat the prey, the prey escapes and the game ends
If Lion 1 eats the prey, it becomes fat and slow, and Lion 2 can eat Lion 1
If Lion 2 does not eat Lion 1, the game ends
If Lion 2 eats Lion 1, then Lion 3 can eat Lion 2, and so on...
This continues until either a lion chooses not to eat, or we reach the last lion

Preferences:

Each lion prefers to eat than to be hungry
Each lion prefers to be hungry than to be eaten

Payoff Structure:

Eat (E) = +1
Not Eat (NE) = 0
Be Eaten = -1

Game Description:

This is a sequential game where lions move in hierarchical order. Each lion can choose to eat the previous lion (if any) or not eat. The game ends when a lion chooses not to eat, or when we reach the last lion.

Tasks:

(a) Analyze the game for n = 2 lions. Draw the game tree and find the Subgame Perfect Equilibrium (SPE). (8 points)

(b) Analyze the game for n = 3 lions. Draw the game tree and find the SPE. (10 points)

(c) Analyze the game for n = 4 lions. Find the SPE without drawing the full tree. (7 points)

(d) Generalize your findings: What is the SPE for any number n of lions? Provide a clear rule. (6 points)

(e) Explain the intuition behind your general result. Why does the pattern depend on whether n is odd or even? (4 points)

Solution to Problem 5:

(a) Analysis for n = 2 Lions:

Game Tree:

Lion 1 chooses: Eat (E) or Not Eat (NE)
If Lion 1 chooses NE: Game ends, payoffs (0, 0)
If Lion 1 chooses E: Lion 2 chooses E or NE
If Lion 2 chooses E: Lion 2 eats Lion 1, payoffs (-1, 1)
If Lion 2 chooses NE: Game ends, payoffs (1, 0)

Backward Induction:

At Lion 2's decision: Lion 2 compares eating (payoff 1) vs not eating (payoff 0). Since 1 > 0, Lion 2 chooses E.

At Lion 1's decision: Lion 1 compares not eating (payoff 0) vs eating (which leads to Lion 2 eating Lion 1, payoff -1). Since 0 > -1, Lion 1 chooses NE.

SPE for n = 2: Lion 1 chooses NE, Lion 2 chooses E (if reached)

Equilibrium outcome: Lion 1 does not eat, game ends with payoffs (0, 0)

(b) Analysis for n = 3 Lions:

Game Tree:

Lion 1 chooses: E or NE
If Lion 1 chooses NE: Game ends, payoffs (0, 0, 0)
If Lion 1 chooses E: Lion 2 chooses E or NE
If Lion 2 chooses NE: Game ends, payoffs (1, 0, 0)
If Lion 2 chooses E: Lion 3 chooses E or NE
If Lion 3 chooses E: Lion 3 eats Lion 2, payoffs (-1, -1, 1)
If Lion 3 chooses NE: Game ends, payoffs (-1, 1, 0)

Backward Induction:

Stage 3 (Lion 3): Lion 3 compares eating (payoff 1) vs not eating (payoff 0). Since 1 > 0, Lion 3 chooses E.

Stage 2 (Lion 2): Lion 2 compares not eating (payoff 0) vs eating (which leads to Lion 3 eating Lion 2, payoff -1). Since 0 > -1, Lion 2 chooses NE.

Stage 1 (Lion 1): Lion 1 compares not eating (payoff 0) vs eating (which leads to Lion 2 not eating Lion 1, payoff 1). Since 1 > 0, Lion 1 chooses E.

SPE for n = 3: (E, NE, E)

Equilibrium outcome: Lion 1 eats, Lion 2 does not eat Lion 1, game ends with payoffs (1, 0, 0)

(c) Analysis for n = 4 Lions:

Using the same backward induction logic:

Stage 4 (Lion 4): Lion 4 chooses E (payoff 1 > 0)

Stage 3 (Lion 3): Lion 3 chooses NE (payoff 0 > -1)

Stage 2 (Lion 2): Lion 2 chooses E (payoff 1 > 0)

Stage 1 (Lion 1): Lion 1 chooses NE (payoff 0 > -1)

SPE for n = 4: (NE, E, NE, E)

Equilibrium outcome: Lion 1 does not eat, game ends with payoffs (0, 0, 0, 0)

(d) General Rule for Any n Lions:

For n odd: The first lion eats, the second lion does not eat, and the game ends.

For n even: The first lion does not eat, and the game ends immediately.

Pattern:

n = 1: Lion 1 eats (no one to eat him)
n = 2: Lion 1 does not eat
n = 3: Lion 1 eats, Lion 2 does not eat
n = 4: Lion 1 does not eat
n = 5: Lion 1 eats, Lion 2 does not eat
And so on...

(e) Intuition Behind the Pattern:

The key insight is that each lion wants to avoid being eaten by the next lion. This creates a "chain of fear" that works backwards from the last lion.

For odd n: The last lion (nth) will always eat the previous lion because no one can eat him. This means the (n-1)th lion will not eat because he would be eaten. This pattern continues, so the 1st lion can safely eat because the 2nd lion will not eat him.

For even n: The last lion will eat the previous lion, so the (n-1)th lion will not eat, and so on. This means the 2nd lion will eat the 1st lion if the 1st lion eats. Therefore, the 1st lion prefers not to eat to avoid being eaten.

Key Insight: The equilibrium depends on whether the "chain of fear" ends with the first lion being safe (odd n) or vulnerable (even n).

Problem 6: Farmers and Markets (15 points)

There are 25 farmers who must choose which of two markets to sell their produce at. At Market A, the total profit is given by g₁(M₁) = 14M₁ - M₁²/2 where M₁ is the number of farmers who select Market A. For Market B, the total profit is g₂(M₂) = 7M₂ where M₂ is the number of farmers who choose Market B. Assume that the total profit at a market is equally divided between all farmers who sell at that market. What is the Nash equilibrium?

Problem Details:

Total farmers: 25
Market A profit function: g₁(M₁) = 14M₁ - M₁²/2
Market B profit function: g₂(M₂) = 7M₂
Profit sharing: Total profit at each market is equally divided among farmers at that market
Constraint: M₁ + M₂ = 25

Tasks:

(a) Derive the profit per farmer at each market as a function of the number of farmers. (5 points)

(b) Find the Nash equilibrium by setting the profits equal. Show your work. (8 points)

(c) Verify your answer by checking that no farmer wants to switch markets. (2 points)

Solution to Problem 6:

(a) Profit per Farmer at Each Market:

Market A:

Total profit: g₁(M₁) = 14M₁ - M₁²/2

Profit per farmer: g₁(M₁)/M₁ = (14M₁ - M₁²/2)/M₁ = 14 - M₁/2

Market B:

Total profit: g₂(M₂) = 7M₂

Profit per farmer: g₂(M₂)/M₂ = 7M₂/M₂ = 7

(b) Finding the Nash Equilibrium:

The system will be in Nash equilibrium if no farmer wants to switch markets. This occurs when the profit per farmer is equal at both markets.

Set the profits equal:

14 - M₁/2 = 7

14 - 7 = M₁/2

7 = M₁/2

M₁ = 14

Since there are 25 farmers total:

M₂ = 25 - M₁ = 25 - 14 = 11

(c) Verification:

Profit per farmer at Market A:

14 - M₁/2 = 14 - 14/2 = 14 - 7 = 7

Profit per farmer at Market B:

Since the profits are equal (7 = 7), no farmer wants to switch markets.

Answer: M₁ = 14 and M₂ = 11 is the Nash equilibrium.

Economic Interpretation:

At equilibrium, 14 farmers choose Market A and 11 farmers choose Market B. Each farmer earns a profit of 7, regardless of which market they choose. This equalization of profits ensures that no individual farmer has an incentive to switch markets, making this allocation a Nash equilibrium.