Chapter 11: Mechanism Design and Market Design

Chapter 10 asked: given preferences and endowments, do competitive markets produce efficient outcomes? The answer — yes, under the welfare theorem conditions — takes the market mechanism as given. This chapter inverts the question: given a desired outcome, can we design a mechanism to achieve it?

Mechanism design is often called "reverse game theory." Instead of predicting the outcome of a game, we design the game to produce a desired outcome. Market design applies these ideas to real institutions — auctions, matching markets, spectrum allocation, kidney exchange.

Prerequisites: Chapters 7 (game theory basics, Nash equilibrium) and 10 (welfare theorems, general equilibrium).

Named literature: Myerson (1981); Vickrey (1961); Clarke (1971); Groves (1973); Gale & Shapley (1962); Roth (2002); Milgrom (2004).

11.1 Social Choice and the Revelation Principle

Social Choice Functions

The challenge: agents' types are private. How do we get them to reveal their types truthfully?

Mechanisms

The mechanism designer chooses the rules (message space and outcome function) to achieve a desired social choice function.

The Revelation Principle

A direct mechanism asks each agent to simply report their type (their private information). It is incentive compatible (IC) if truthful reporting is an equilibrium strategy — no agent benefits from lying.

This is the most powerful simplification in mechanism design — arguably the most powerful simplification in all of economic theory. In principle, the space of possible mechanisms is infinitely large. An auction could have any number of rounds, any bidding rules, any payment formula. A matching algorithm could work in any conceivable way. Searching over all possible mechanisms for the best one seems hopeless.

The revelation principle says: you don't have to search. Whatever outcome any mechanism can achieve, a direct mechanism (just ask everyone to report truthfully) can achieve the same outcome. So the mechanism design problem reduces to: find the best allocation rule and payment rule as functions of reported types, subject to the constraint that truth-telling is optimal. This transforms an impossibly broad search into a well-defined optimization problem.

DSIC is stronger but harder to achieve. BIC is weaker but allows more mechanisms.

11.2 The Gibbard-Satterthwaite Theorem

This is the mechanism design analog of Arrow's impossibility theorem. It says that in general social choice settings, no non-dictatorial mechanism can elicit truthful preferences in dominant strategies.

The escape: restrict the domain. With quasi-linear preferences ($U_i = v_i(a) + t_i$, where $t_i$ is a monetary transfer), the Gibbard-Satterthwaite barrier falls. The VCG mechanism achieves efficiency and DSIC with transfers.

11.3 The VCG Mechanism

The Vickrey-Clarke-Groves (VCG) mechanism achieves efficient allocation with truth-telling as a dominant strategy, using monetary transfers.

Efficient allocation: $a^*(\theta) = \arg\max_a \sum_i v_i(a, \theta_i)$ — maximize total value.

Agent $i$ pays the externality she imposes on others — the difference between others' welfare with and without $i$.

Why is truth-telling dominant? Under truthful reporting, agent $i$'s payoff is:

$$v_i(a^*(\theta)) + t_i = v_i(a^*(\theta)) + \sum_{j \neq i} v_j(a^*(\theta_{-i})) - \sum_{j \neq i} v_j(a^*(\theta))$$

This simplifies to $\sum_j v_j(a^*(\theta)) - \sum_{j \neq i} v_j(a^*(\theta_{-i}))$. The second term doesn't depend on $i$'s report. So $i$ maximizes her payoff by choosing her report to maximize $\sum_j v_j(a^*(\theta))$ — which happens when she reports truthfully, since $a^*$ already maximizes total value.

Interactive: VCG Payment Calculator

Enter agent values for a single indivisible object. The calculator computes VCG payments (equivalent to a second-price auction for a single item).

Agent 1 value:

Agent 2 value:

Agent 3 value:

Click "Compute" to see results.

Figure 11.2. Agent values and VCG payments. Each agent pays the externality they impose on others. The winner pays the second-highest value (in a single-item auction, VCG reduces to the Vickrey auction).

Example 11.1 — VCG for a Public Good

Three citizens value a bridge at $v_1 = 30$, $v_2 = 25$, $v_3 = 15$. The cost is $C = 60$.

Build if $\sum v_i > C$: \$10 > 60$ → yes.

Clarke tax payments:

$t_1 = C - (v_2 + v_3) = 60 - 40 = 20$ (agent 1 must cover the gap)
$t_2 = C - (v_1 + v_3) = 60 - 45 = 15$
$t_3 = C - (v_1 + v_2) = 60 - 55 = 5$

Total collected: \$10 + 15 + 5 = 40 < 60$. There's a budget deficit of 20 — VCG does not generally achieve budget balance. Each agent pays their "pivotal" contribution.

11.4 Optimal Auctions and Revenue Equivalence

Auction Formats

Format	Rules	Winner pays
English (ascending)	Bidders raise bids; last bidder wins	Second-highest value (approx.)
Dutch (descending)	Price drops until someone claims	Their bid
First-price sealed-bid	Highest bid wins	Their bid
Second-price sealed-bid (Vickrey)	Highest bid wins	Second-highest bid

The Vickrey auction (second-price sealed-bid) is DSIC: each bidder's dominant strategy is to bid their true value $v_i$. Bidding above $v_i$ risks winning at a price above value; bidding below risks losing when the second-highest bid is below $v_i$.

Revenue Equivalence

This is a stunning result. It says that the seemingly vast differences between auction formats — open vs sealed bid, ascending vs descending, first-price vs second-price — are irrelevant for expected revenue under these conditions.

Interactive: Auction Simulator

Set the number of bidders and their value distribution. Run single auctions to see individual outcomes, or run 100 rounds to observe revenue equivalence (average revenues converge across formats). Adjust the risk aversion slider to break equivalence.

Number of bidders:

Max value (Uniform[0, max]):

Risk aversion (CRRA $\rho$): 0.00 (risk-neutral — revenue equivalence holds)

Risk-neutral (0) Moderate (0.4) High (0.8)

Click a button to run the auction simulator.

Figure 11.3. Auction outcomes. In single runs, revenues differ across formats due to randomness. Over 100 runs, average revenues converge — demonstrating revenue equivalence. Increase risk aversion ($\rho > 0$) to break equivalence: first-price revenue rises above second-price.

Myerson's Optimal Auction

When the seller wants to maximize revenue (not efficiency), Myerson showed the optimal mechanism uses the virtual value:

The optimal auction allocates to the bidder with the highest virtual value, provided it is positive. If all virtual values are negative, the seller retains the object. This implies a reserve price — the seller sets a minimum bid equal to $\psi^{-1}(0)$.

Example 11.2 — Optimal Reserve Price

Values uniformly distributed on $[0, 1]$: $F(\theta) = \theta$, $f(\theta) = 1$.

$\psi(\theta) = \theta - (1-\theta)/1 = 2\theta - 1$

$\psi(\theta) = 0 \implies \theta = 1/2$. Optimal reserve price = \$1/2$.

A second-price auction with reserve \$1/2$ is optimal: the item is sold only if at least one bidder values it above \$1/2$.

Interactive: Myerson Optimal Auction

For values drawn from Uniform$[0, V_{\max}]$, the virtual value is $\psi(\theta) = 2\theta - V_{\max}$. Drag the reserve price slider. The revenue curve shows expected revenue as a function of the reserve. The optimal reserve (maximizing expected revenue) is highlighted.

Number of bidders ($n$): 2

Reserve price ($r$): 0.50

No reserve (0) Optimal ($r^*$) Maximum (1)

Figure 11.4a. Virtual value function $\psi(\theta) = 2\theta - 1$ (for $U[0,1]$). The reserve price is set where $\psi(r) = 0$. Bidders with $\theta < r$ are excluded (shaded red).

Figure 11.4b. Expected revenue as a function of reserve price. The green dot marks the optimal reserve that maximizes expected revenue. Your chosen reserve is shown as a blue dot.

Example 11.4 — Incentive Compatibility Check

A government allocates a license to one of two firms. Firm $i$ has private value $\theta_i \in \{L, H\} = \{10, 50\}$, each equally likely.

Proposed mechanism: Allocate to the firm reporting higher value; in case of a tie, allocate to firm 1. Payment: the winner pays 30.

Check IC for a high-value firm ($\theta = 50$):

Report truthfully ($H$): Win with probability 3/4 (win if rival is $L$ or tie). Payoff = \$1/4 \times (50 - 30) = 15$.
Report $L$: Win only if rival also reports $L$ and you are firm 1, otherwise lose. Expected payoff $\leq 1/4 \times 20 = 5$.

Truthful is better. IC holds for type $H$.

Check IC for a low-value firm ($\theta = 10$):

Report truthfully ($L$): Likely lose. Expected payoff $\approx 0$.
Report $H$: Win with probability 3/4 but pay 30 > 10. Payoff = \$1/4 \times (10 - 30) = -15$.

Truthful is better. IC holds for type $L$. The mechanism is incentive compatible.

Example 11.5 — Revenue Equivalence Verification

Two bidders with values drawn independently from $U[0, 100]$.

Second-price auction: Expected revenue = $E[\text{2nd highest value}] = 100/3 \approx 33.33$.

First-price auction: Optimal bid with 2 bidders: $b(\theta) = \theta/2$. Expected revenue = $E[\max(b_1, b_2)] = E[\max(\theta_1/2, \theta_2/2)] = E[\max(\theta_1, \theta_2)]/2 = (200/3)/2 = 100/3 \approx 33.33$.

Both formats yield expected revenue of \$100/3$, confirming revenue equivalence. The first-price auction generates less variable revenue (each winner pays exactly half their value) while the second-price auction has higher variance (the payment depends on the second-highest value, which can vary widely).

Myerson-Satterthwaite Impossibility

Myerson-Satterthwaite Theorem (1983). In bilateral trade with private information — one buyer and one seller, each knowing only their own valuation — there is no mechanism that simultaneously achieves all four of:

Individual rationality (IR): Both parties voluntarily participate
Incentive compatibility (IC): Both parties report truthfully
Budget balance (BB): No outside subsidies needed
Efficiency: Trade occurs if and only if $v_B > c_S$

Intuition: The seller wants to overstate her cost (to extract a higher price). The buyer wants to understate his value (to pay less). Incentive compatibility requires leaving "information rents" to both parties. These rents are costly, and with budget balance, there isn't enough surplus to pay both rents and ensure all efficient trades occur.

Real-world bargaining under private information — salary negotiations, used car purchases, M&A deals — always involves some inefficiency. Institutions like posted prices, reputation systems, and standardized contracts mitigate the problem but cannot fully eliminate it.

11.5 Matching Markets

Some goods cannot be allocated by prices — we don't (or shouldn't) sell school admissions, organ transplants, or residency positions. Matching markets use algorithms instead.

Gale-Shapley Deferred Acceptance Algorithm

Theorem (Gale & Shapley, 1962). The algorithm terminates in at most $n^2$ rounds and produces a stable matching — no unmatched pair both prefer each other to their current match.

Example 11.3 — Gale-Shapley with Four Students

Four students (A, B, C, D) and four schools (W, X, Y, Z). Students propose.

Student	Preferences	School	Preferences
A	W > X > Y > Z	W	B > A > D > C
B	X > W > Y > Z	X	A > B > C > D
C	W > Y > X > Z	Y	C > D > A > B
D	Y > W > X > Z	Z	D > C > B > A

Final matching: A-W, B-X, C-Y, D-Z. This is stable: no pair wants to deviate. Use the interactive above to verify step by step.

Real-World Market Design

Alvin Roth (Nobel 2012, shared with Lloyd Shapley) describes this as "the economist as engineer" — using economic theory not just to explain the world but to design real institutions that improve people's lives.

The broader lesson: Markets are not natural objects that arise spontaneously. They are designed institutions — rules, algorithms, and enforcement mechanisms that determine who gets what, at what price, and through what process. The design matters enormously.

Thread Example: Maya's Enterprise

The city decides to auction the exclusive right to operate a lemonade stand at the prime downtown corner. Three potential vendors: Maya ($v_M = 50$/day), Nate ($v_N = 35$/day), Olivia ($v_O = 20$/day). Values drawn from $U[0, 60]$.

Second-price auction (Vickrey): Dominant strategy is to bid truthfully. Maya bids 50, Nate bids 35, Olivia bids 20. Maya wins, pays 35.

Optimal auction (Myerson): Virtual values with $F(\theta) = \theta/60$, $f(\theta) = 1/60$:

$\psi(\theta) = \theta - (60 - \theta) = 2\theta - 60$

Reserve price: $\psi(\theta) = 0 \implies \theta = 30$.

Maya's virtual value: \$1(50) - 60 = 40$. Nate's: \$10$. Olivia's: $-20$ (excluded by optimal auction).

In a second-price auction with reserve 30: Maya wins, pays $\max(35, 30) = 35$.

The Historical Lens

Roth as "Economist as Engineer." Alvin Roth (Nobel Prize 2012) transformed mechanism design from pure theory into a practical discipline that redesigns real markets. His work demonstrates that markets are designed institutions, not natural phenomena.

The National Residency Matching Program (NRMP): Roth diagnosed why the original medical residency match was failing (instability, strategic manipulation) and redesigned it using deferred acceptance. The new system matches ~40,000 medical residents annually.

Kidney exchange: Roth, Sonmez, and Unver designed exchange protocols allowing incompatible donor-patient pairs to swap donors through chains of transplants, saving thousands of lives. This was pure market design — creating a market where none existed, without using prices.

School choice: Roth and colleagues replaced Boston's manipulable school assignment mechanism with a strategy-proof system. Under the old system, parents who reported their true preferences were punished; under the new system, honesty is always optimal.

Spectrum auctions: Milgrom and Wilson (Nobel Prize 2020) designed combinatorial auctions for the FCC, raising billions of dollars while efficiently allocating spectrum licenses. The 2017 incentive auction alone raised \$19.8 billion.

The common thread: economic theory provides the blueprint, but implementation requires understanding the specific institutional context — the "details" that pure theory abstracts away.

Summary

Mechanism design inverts game theory: instead of predicting outcomes, we design games to achieve desired outcomes.
The revelation principle says any implementable outcome can be achieved by a direct mechanism where agents report truthfully. This massively simplifies the design problem.
Gibbard-Satterthwaite: without transfers, only dictatorships are DSIC in general. With quasi-linear preferences, the VCG mechanism achieves efficiency with dominant-strategy truth-telling.
Revenue equivalence: standard auctions with the same allocation rule yield the same expected revenue. Myerson's optimal auction uses virtual values and a reserve price to maximize seller revenue.
Myerson-Satterthwaite impossibility: bilateral trade with private information cannot simultaneously be efficient, IC, IR, and budget-balanced.
Matching markets (Gale-Shapley) produce stable matchings without prices. The algorithm is strategy-proof for proposers and terminates in polynomial time.
Market design applies these ideas to real institutions: medical residencies, school choice, kidney exchange, spectrum auctions.

Label	Equation	Description
Eq. 11.1	$U_i(\theta_i, \theta_i) \geq U_i(\hat{\theta}_i, \theta_i)$ for all $\hat{\theta}_i, \theta_{-i}$	DSIC
Eq. 11.2	$E[U_i(\theta_i, \theta_i)] \geq E[U_i(\hat{\theta}_i, \theta_i)]$	BIC
Eq. 11.3	$t_i = \sum_{j \neq i} v_j(a^(\theta_{-i})) - \sum_{j \neq i} v_j(a^(\theta))$	VCG payment
Eq. 11.4	$\psi(\theta) = \theta - (1-F(\theta))/f(\theta)$	Myerson virtual value

Exercises

Practice

A single indivisible object is auctioned to two bidders with values $v_1 = 10$, $v_2 = 7$. Compute the winner and payment under: (a) first-price sealed-bid (assume each bidder shades bid by half), (b) second-price sealed-bid, (c) English auction.
Three voters rank three alternatives {A, B, C}. Construct preference profiles where: (a) majority rule produces a cycle (Condorcet paradox), (b) a dictatorial rule avoids the cycle.
Run Gale-Shapley (students propose) on: Students {1,2,3}, Schools {X,Y,Z}. Preferences: 1: X>Y>Z, 2: Y>X>Z, 3: X>Y>Z. Schools: X: 1>2>3, Y: 2>3>1, Z: 3>1>2.

Apply

A government wants to allocate carbon emission permits efficiently. Compare: (a) a VCG mechanism (firms report abatement costs), (b) a standard auction, (c) a cap-and-trade market. Under what conditions do they produce the same allocation?
Explain why eBay uses a second-price auction (proxy bidding) rather than a first-price auction. How does the Vickrey result relate to eBay's design?
The Boston school choice mechanism (pre-reform) penalized parents who listed popular schools if they weren't high-priority. Explain why this is not strategy-proof and how deferred acceptance fixes it.
The Myerson-Satterthwaite theorem says efficient bilateral trade is impossible with private information. Yet eBay, Craigslist, and used car markets facilitate millions of trades daily. How do these institutions mitigate the impossibility result?

Challenge

Derive the optimal reserve price for a second-price auction with $n$ bidders whose values are drawn i.i.d. from $U[0, 1]$. Show that the reserve is \$1/2$ regardless of $n$. What is the expected revenue as a function of $n$?
Prove that the Gale-Shapley algorithm produces a stable matching. (Hint: suppose there exists a blocking pair. Show this leads to a contradiction with the algorithm's rejection logic.)
A seller has two identical items and three bidders with values $v_1 > v_2 > v_3$. Design a VCG mechanism for this multi-unit auction. What does each winner pay?
Consider a matching market where one side has strict preferences but the other side is indifferent among some matches (ties). Does Gale-Shapley still produce a stable matching? If ties are broken randomly, is the result unique?

Chapter 11Mechanism Design and Market Design

Introduction