Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 37 ยท Projects and Practice

Practice Problems: Sequential, Repeated and Auction Games

Ten worked game theory exercises on backward induction, subgame perfection, repeated games, evolutionary stability, auctions and matching, with Python checks for each answer.

The best way to learn game theory is to solve games yourself. This page gives ten problems that cover the chapters on sequential games, repeated and evolutionary games, auctions and applications. Try each one on paper first, then run the code to check yourself. Each answer is verified numerically, so a mismatch means you should look again at either your reasoning or your arithmetic.

Problem 1: A three-stage bargaining tree

Player 1 chooses Left or Right. After Left, player 2 chooses between payoffs (4, 1) and (2, 3). After Right, player 2 chooses between (3, 2) and (1, 4). Find the subgame-perfect outcome.

Python Check problem 1

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Player 2 picks b after Left (3 > 1) and d after Right (4 > 2). Player 1 then compares 2 (Left) with 1 (Right) and chooses Left. The outcome is (2, 3). Notice that the best-looking payoff for player 1, 4, is never reached.

Problem 2: The value of commitment

In the Stackelberg game with price P = 120 - Q and unit cost 20, find both firms' profits when firm 1 leads.

Python Check problem 2

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The leader produces 50, the follower 25, the price is 45, and profits are 1250 and 625, against 1111 each in Cournot. Think about why the follower loses compared with the simultaneous game.

Problem 3: When does cooperation survive?

In a repeated prisoner's dilemma with T = 6, R = 4, P = 2, S = 0, what is the minimum discount factor for grim-trigger cooperation? Verify by testing values of delta.

Python Check problem 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The threshold is (6 - 4) / (6 - 2) = 0.5.

Problem 4: Tit-for-tat against a noisy copy

Two tit-for-tat players each play 100 rounds. With a 5 percent chance that any intended move is flipped, estimate the average payoff per round. Compare with the noise-free value 3.

Python Check problem 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The noise-free average is exactly 3. With noise it falls well below 3, since mistakes trigger echoes of retaliation. How would you change the strategy to recover?

Problem 5: Evolutionary stability

For the symmetric game with payoff matrix [[a, b], [c, d]] = [[3, 0], [5, 1]] (the prisoner's dilemma), which pure strategy is an ESS? Check the conditions for each pure strategy against the other.

Python Check problem 5

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only D is an ESS. A single defector in a cooperative population earns 5 > 3. Evolution picks defection here, even though everyone would be better off cooperating.

Problem 6: Hawk-Dove with a different prize

Find the mixed ESS fraction of Hawks when V = 6 and C = 10, and verify with replicator dynamics from 20 percent Hawks.

Python Check problem 6

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer is V / C = 0.6.

Problem 7: Auction bidding

Four bidders have values uniform on [0, 1] in a first-price auction. Your value is 0.6. What is your equilibrium bid, and what is your expected profit given that everyone else uses the equilibrium rule? Estimate the profit by simulation, and compare with a bid of 0.6 (truthful).

Python Check problem 7

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The equilibrium bid is 0.45 and the profit is roughly 0.6 * 0.6^3 / 4 = 0.032 (theory: v^n / n = 0.6^4 / 4 = 0.0324). The truthful bid earns exactly 0.

Problem 8: VCG payment by hand

Two identical items, three bidders with unit demand and values 9, 7 and 4 for either item. Find the winners and each winner's VCG payment.

Python Check problem 8

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both winners (A and B) pay 4, the highest losing value. With identical items and unit demand, VCG is the uniform (k+1)-price auction.

Problem 9: Shapley value of a glove game

Players 1 and 2 each have a left glove; player 3 has a right glove. A coalition gets 1 for every matching pair it contains. Find the Shapley value.

Python Check problem 9

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Player 3 gets 2/3 and each left-glove owner gets 1/6. The scarce resource captures most of the value.

Problem 10: Stable matching by hand

Three students (s1, s2, s3) rank schools (X, Y, Z) as s1: X, Y, Z; s2: X, Z, Y; s3: Y, X, Z. The schools rank students as X: s2, s1, s3; Y: s1, s3, s2; Z: s1, s2, s3. Each school has one seat. Find the student-optimal stable matching.

Python Check problem 10

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Work through the proposals by hand: s1 and s2 both apply to X, which keeps s2, so s1 moves to Y, and s3 also wants Y, which prefers s1 and rejects s3. Then s3 tries X, which prefers s2 and s1 to s3, so s3 ends up at Z.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In Problem 1, why does player 1 not get the payoff 4?

    After Left, player 2 prefers (2, 3) to (4, 1), so the outcome with 4 is never reached.
  2. 2. In the glove game, why does the owner of the right glove earn the largest Shapley share?

    Scarcity gives the right-glove owner a larger marginal contribution in many arrival orders.
  3. 3. In Problem 8, what price do the two winners pay?

    Each winner's externality is the value of the bidder who would win in their absence: 4.
  4. 4. In Problem 4, what weakens tit-for-tat pairs under noise?

    An error makes each player punish the other in turn, so cooperation breaks down for a while.

Summary

  • Backward induction, commitment and subgame perfection can be checked with a few lines of code.
  • Repeated-game cooperation depends on a threshold discount factor; noise erodes it.
  • ESS and replicator dynamics agree on where populations settle.
  • Auctions, VCG, the Shapley value and stable matching can all be verified by simulation or by brute force.
  • When your hand answer and the code disagree, trust neither until you find the reason.

Next: Game Theory