Reference · Cheat Sheet 11 · Capstone
Mechanism Design
Core idea: don't just play the game — design its rules so that self-interest produces the outcome you want. The central property is incentive compatibility: the right thing is also the self-interested thing.
The four design questions
- What outcome do I want? Name it precisely: stable matching, honest bids, quality referrals, aligned agents. If you can't state the desired outcome clearly, you can't design toward it.
- What do players privately know or want? Their true valuations, preferences, types — the information asymmetry you're working around.
- What rule makes desired behavior their best move? Engineer the equilibrium. You're choosing which Nash equilibrium (or dominant strategy equilibrium) players land on.
- Can they game it? Walk through the incentive. If a rational player can benefit by lying or gaming — fix the mechanism, not the people.
The second-price auction result
Bid your true value — it's a dominant strategy.
The price you pay is set by the second-highest bid (someone else's), not your own. Shading your bid lower can't reduce that price — it only risks losing an auction you'd have profited from. Bidding above your value risks winning at a loss. Therefore: true value is optimal whatever others do. Mechanism is incentive-compatible by design.
Why shading fails in a second-price auction
| You try to… | Effect on price you pay | Effect on outcome |
|---|
| Shade bid below true value | None — price is set by other bid | Risk losing a profitable win |
| Inflate bid above true value | None — price is set by other bid | Risk winning at a loss |
| Bid true value | N/A | Win if and only if you value it most — optimal |
Contrast: in a first-price auction you pay your own bid — shading makes sense there and truth-telling is gone. Not incentive-compatible.
Stable matching and kidney exchange (the medical proof)
Gale-Shapley deferred-acceptance (1962): when prices can't operate, rank preferences and run iterative proposals. The result is a stable matching — no two agents would both prefer to abandon their current assignment for each other. Designed so truth-telling about preferences is safe.
Alvin Roth — kidney exchange: incompatible donor-patient pairs are chained together so each pair's incompatible donor gives to a stranger whose donor gives back. Pure mechanism design saving lives — cooperation is rational because the mechanism makes it each pair's best move.
Glossary (new terms this lesson)
- Mechanism design
- Designing game rules so rational self-interested players produce the outcome the designer wants. "Reverse game theory."
- Incentive compatibility
- The desired behavior is each player's own best strategy — no policing needed.
- Second-price (Vickrey) auction
- Highest bidder wins, pays second-highest bid. Bidding true value is dominant strategy. William Vickrey (1961).
- Dominant-strategy truthfulness
- Truth-telling is best regardless of what others do — stronger than Nash-level truthfulness.
- Stable matching
- No unmatched pair would both prefer each other to their current assignment. Gale-Shapley algorithm (1962).
- Revelation principle
- Any outcome achievable by any mechanism can be achieved by a direct, incentive-compatible one. You only ever need to search for truth-telling mechanisms.
The one rule
If people are gaming your system, the mechanism is wrong — not the people. Diagnose the incentive structure before blaming behavior.