Game Theory · Chapter 12
Mechanism Design and Matching
So far we’ve taken the rules of a game as given and asked how people play. Mechanism design turns the question around: if you could write the rules, which rules would make self-interested people produce a good outcome, even when only they know what they want? Here you’ll run the algorithm that matches new doctors to hospitals and students to schools, try to cheat it and find out who can, then use a clever tax that makes honesty the best policy for everyone.
Markets
Who proposes
Mode
Lying
Live numbers
Missions
These are everyone’s true preferences. Press a name to move it up one place in that list; the algorithm restarts. Lies set in the panel change only what is reported.
What you’re seeing
The market. Each student ranks the schools and each school ranks the students; each school has one seat. A matching pairs students with schools. It’s stable if there is no blocking pair: a student and a school who both prefer each other to the partners they were given. A blocking pair would simply walk away from the official match and make their own deal, which is exactly how centralized markets have unraveled in the past.
The algorithm. In David Gale and Lloyd Shapley’s deferred acceptance, each free student proposes to the best school that hasn’t yet rejected them. A school holds on to the best proposal it has received so far and rejects the rest. Holding is not accepting: if a better student proposes later, the school lets the held one go, and that student moves down their list. When nobody is free with a school left to try, the held proposals become final.
Lying. Pick anyone in the panel and how they misreport. Their reported list is what the algorithm sees; their true list, in the editor, is what decides whether the lie helped. The live numbers tell you their true rank of what they got, with and without the lie.
Stable matching
Why stable? Suppose a student s prefers school t to the school she ended up with. Then she proposed to t earlier, and t rejected her, at that moment or later, for someone t liked better. Schools only ever trade up, so t ends with someone it prefers to s. So s and t can’t be a blocking pair. The algorithm also always ends: each student proposes to each school at most once.
A market can have many stable matchings. Gale and Shapley showed that when students propose, every student gets the best school they could get in any stable matching, and every school gets its worst. Swapping who proposes flips this. That’s why the choice of proposing side was a real policy question for the medical match.
Students propose. Ana tries Oak, which holds her. Ben tries Oak; Oak prefers Ben, so Ana is let go and tries Elm, which holds her. Cai tries Elm, which prefers Ana and rejects him; Cai tries Oak, which prefers Cai to Ben and lets Ben go. Ben tries Pine, which holds him. Dee tries Oak (rejected, Oak prefers Cai), then Elm (rejected, Elm prefers Ana), then Bay, which holds her. Nobody is free: Ana–Elm, Ben–Pine, Cai–Oak, Dee–Bay, after 9 proposals. Step through it in the simulation and watch the chips get crossed out.
Ana likes Oak best, Ben likes Elm, Cai likes Pine. But Oak likes Ben best, Elm likes Cai, and Pine likes Ana. When students propose, each gets their first choice at once, and each school gets its last. When schools propose, each school gets its first choice, and each student gets their last. There is a third stable matching in between, where everyone gets their second choice. Find it by hand to complete a mission.
Who can game it?
Lester Dubins and David Freedman (1981) and Alvin Roth (1982) proved that in deferred acceptance, no proposer can ever gain by misreporting: telling the truth is a dominant strategy for the proposing side. Roth also proved the bad news: no stable matching mechanism is strategy-proof for both sides. Receivers can sometimes gain by pretending to be pickier than they are. In “Three’s company”, Oak gets Ana, its last choice, when students propose. If Oak claims that only Ben is acceptable, Ana is rejected, the rejections cascade, and Oak ends up with Ben, its first choice.
Mechanism design: writing the rules
A designer wants an outcome that depends on information only the participants have: who values the item most, which schools students prefer, whether a park is worth its cost. A mechanism asks participants for messages and maps messages to an outcome and payments. The designer can’t force anyone to tell the truth, so the mechanism has to make the truth worth telling.
- A mechanism is incentive compatible if truthful reporting is an equilibrium. It’s dominant-strategy incentive compatible (strategy-proof) if truth is best whatever others do, as in a second-price auction or for proposers in deferred acceptance; Bayesian incentive compatible if truth is best on average given beliefs about others.
- It’s individually rational if nobody is worse off for taking part.
The idea is simple: take any mechanism and its equilibrium, and build a new one that asks you for your type and then plays your equilibrium strategy for you. Lying to the new mechanism is like deviating in the old one, which didn’t pay. So the designer can search among truthful direct mechanisms only, which turns a hopeless search into an optimization problem.
There are limits. The Gibbard–Satterthwaite theorem (1973, 1975) says that with three or more possible outcomes, any voting rule in which every outcome can win and nobody can gain by lying is a dictatorship. Money is what lets mechanisms like the next one escape it.
VCG: pay for the harm you cause
Three neighbors could build a $300 park and split the cost, $100 each. Who values it how much is private. Ask them and build if the total is at least $300? Then anyone who wants the park should exaggerate, and anyone who doesn’t should understate. The Vickrey–Clarke–Groves idea fixes this: build if the reported values cover the cost, and charge each person the harm their report does to everyone else.
Your payoff is then your own value plus the others’ values, minus something you can’t affect. Since the mechanism picks the decision that maximizes the sum of reported values, the best you can do is make it maximize the sum of true values, by telling the truth. William Vickrey’s second-price auction (Chapter 9) is the special case of selling one item: the winner pays the second-highest bid, which is exactly the value the others lose by not getting it. Edward Clarke (1971) and Theodore Groves (1973) developed the public-project version.
True values: you $150, Bo $120, Cy $60, so net of the $100 shares: +50, +20, −40. The total is +30, so the park is built. Without you, the others total 20 − 40 = −20 and the park wouldn’t be built: you are pivotal. Your report costs the others 20 in net value, so your Clarke tax is $20. Bo and Cy aren’t pivotal (without either of them, the park is still built), so they pay no tax. Your payoff is 50 − 20 = $30. Report $250 instead and the park is still built and your tax is still $20, so nothing changes. Report $110 and the total falls to −10: no park, no tax, payoff $0. You can’t do better than the truth.
VCG has real flaws. The taxes can’t be handed back to the participants without spoiling the incentives, so money is wasted (Jerry Green and Jean-Jacques Laffont showed in 1977 that no efficient, strategy-proof mechanism balances the budget in general). Groups can collude, and the payments can look arbitrary. That’s one reason VCG is more admired than used, though the logic behind it shapes many real designs.
Myerson’s optimal auction, in brief
VCG aims at efficiency. A seller wants revenue. Roger Myerson (1981) showed how to find the revenue-maximizing auction for bidders with independent private values. For a value v drawn from a distribution F with density f, define the virtual value
The optimal auction gives the item to the bidder with the highest virtual value, if it is positive, and to no one otherwise. With symmetric bidders and a regular distribution, that’s a second-price auction with a reserve price r where φ(r) = 0. For values uniform from $0 to $200, φ(v) = 2v − 200, so the reserve is $100, whatever the number of bidders. That’s the reserve-price result you met in Chapter 9.
Mechanism design assumes the opposite: everyone pursues their own interest, and the rules are built so that self-interest produces the desired result. Deferred acceptance doesn’t ask proposers to be honest; it makes honesty their best strategy. When a mechanism relies on people not gaming it, as the old Boston school assignment system did, careful players game it and the honest ones lose out.
Market design in the real world
- The medical match. In the United States, the National Resident Matching Program has matched graduating medical students to hospital residencies since 1952. Alvin Roth showed in 1984 that its algorithm was equivalent to deferred acceptance with hospitals proposing, which helps explain why the match survived when earlier systems had collapsed. Starting with the 1998 match, it switched to a design by Roth and Elliott Peranson in which applicants propose and couples can apply together.
- School choice. New York City’s high school match was redesigned around deferred acceptance starting in 2003, with Atila Abdulkadiroğlu, Parag Pathak and Roth. Boston adopted deferred acceptance in 2005, replacing a system that rewarded families for ranking schools strategically.
- Kidney exchange. A patient with a willing but incompatible donor can swap with another such pair. Roth, Tayfun Sönmez and Utku Ünver (2004) designed exchanges that find these swaps, including longer cycles and chains, and their work helped found the New England Program for Kidney Exchange in 2004.
- Nobel prizes. In 2007, Leonid Hurwicz, Eric Maskin and Roger Myerson shared the Nobel Memorial Prize in Economic Sciences “for having laid the foundations of mechanism design theory”. In 2012, Lloyd Shapley and Alvin Roth shared it “for the theory of stable allocations and the practice of market design”. David Gale had died in 2008; the prize is not awarded after death.
Practice
1. Two students and two schools. Ana: Oak > Elm. Ben: Oak > Elm. Oak: Ben > Ana. Elm: Ana > Ben. Run deferred acceptance with students proposing.
Show the answer
Ana proposes to Oak, held. Ben proposes to Oak; Oak prefers Ben and lets Ana go. Ana proposes to Elm, held. Result: Ana–Elm, Ben–Oak, after 3 proposals. It is stable: Ana would rather have Oak, but Oak prefers Ben.
2. In “Three’s company”, is the matching Ana–Elm, Ben–Oak, Cai–Pine stable? If not, name a blocking pair.
Show the answer
Not stable. Check each student who would like to move up. Ana prefers Oak to Elm, but Oak has Ben, its first choice. Ben has Oak, his last choice, so he’d prefer Elm or Pine. Elm has Ana and ranks Ben below her, so no. Pine has Cai, its last choice, and ranks Ben above Cai, so Ben–Pine is a blocking pair. Cai already has his first choice. Build this matching by hand in the simulation and it draws the Ben–Pine pair in red.
3. Explain in two sentences why no student can gain by lying when students propose, but a school sometimes can.
Show the answer
Proposing students already get the best partner available to them in any stable matching, and a misreport can only get them a partner who would have rejected them for someone better. A receiving school, by rejecting proposals it would really accept, sets off a chain of new proposals that can bring it a student it prefers.
4. Three neighbors value a $300 park at $250, $80 and $40. Who pays a Clarke tax, and how much?
Show the answer
Net values: +150, −20, −60; total +70, so it is built. Without neighbor 1, the others total −80 and it wouldn’t be built, so neighbor 1 is pivotal and pays $80, the net loss the park imposes on the others. Without neighbor 2, the total is +90: still built, no tax. Same for neighbor 3. Neighbor 1’s payoff: 150 − 80 = $70.
5. Show that a second-price auction is a VCG mechanism.
Show the answer
VCG gives the item to the highest bidder (the efficient choice for the reported values). Losers impose no harm on others, so they pay 0. If the winner weren’t there, the item would go to the second-highest bidder, who would get value b(2); with the winner present, the others get 0. So the winner pays b(2), the second-highest bid.
6. Values are uniform from $0 to $200. What reserve price maximizes a seller’s expected revenue in a second-price auction, and why doesn’t it depend on the number of bidders?
Show the answer
F(v) = v/200 and f(v) = 1/200, so φ(v) = v − (200 − v) = 2v − 200, zero at v = $100. The reserve screens out bidders whose virtual values are negative, and whether a single bidder’s virtual value is negative depends only on their own value, not on how many others there are.
7. (Harder) Prove that in the Clarke mechanism with N people, reporting your true value is a dominant strategy.
Show the answer
Let ni be your true net value and m the sum of the others’ reported net values. If your report makes the decision “build”, your payoff is ni − max(0, −m); if “don’t build”, it is 0 − max(0, m). In both cases that equals (value of the decision to you plus the others) − max(0, m), and max(0, m) doesn’t depend on your report. So you want the decision that maximizes ni + m if built versus 0 if not, which is exactly what the mechanism picks when you report ni truthfully. Our test checked 3,000 random cases against 121 possible reports each: the truth was never beaten.
How the interactive works
Deferred acceptance runs one proposal at a time: the free proposer with the lowest number makes the next proposal. (The final matching doesn’t depend on the order of proposals.) Each school has one seat. Blocking pairs are always checked against the true preferences in the editor. The count of stable matchings is found by checking every possible matching, which is quick for five a side.
The park costs $300, split equally. Under VCG, the park is built if the reported net values add up to zero or more, and a pivotal neighbor pays the absolute value of the others’ total. Under the proportional rule, it’s built if reports add up to $300, and each pays $300 times their share of the reports.
What’s simplified. One seat per school, complete preference lists (unless someone lies by truncating), and no couples or ties. Real school-choice systems break ties in schools’ priorities with lotteries, and the medical match handles couples.
How it was checked (Node.js tests, run before the page was built):
- “Three’s company”: students proposing give everyone their first choice in 3 proposals; schools proposing give the reverse; exactly 3 stable matchings exist. “Four and four”: Ana–Elm, Ben–Pine, Cai–Oak, Dee–Bay in 9 proposals, stable.
- 400 random markets with 2 to 5 a side (592 stable matchings in all): deferred acceptance was always stable, best for every proposer and worst for every receiver among all stable matchings.
- All 41,200 possible misreports (every reordering and truncation) by a proposing student: none ever got the student a better match. A receiving school gained by truncating in 99 of the 400 markets. Oak’s truncation in “Three’s company” gets it Ben.
- Clarke: taxes [20, 0, 0] for values 150, 120, 60 and [80, 0, 0] for 250, 80, 40; truth never beaten in 3,000 random cases; the park is built exactly when true values cover the cost. Under the proportional rule with values 150, 120, 60, underreporting gains $16.36 over the truth.
Check yourself
What makes a matching unstable?
Show the answer
That’s a blocking pair. Not getting your first choice is normal and doesn’t make a matching unstable.
When students propose in deferred acceptance, which statement is true?
Show the answer
The proposing side gets its best stable outcome and can’t gain by lying; the receiving side gets its worst stable outcome.
What does the revelation principle say?
Show the answer
A direct mechanism can “play your equilibrium strategy for you”, so the designer may look only at truthful direct mechanisms.
Under the Clarke tax, when do you pay?
Show the answer
You pay the harm your report imposes on everyone else, which is zero unless you’re pivotal.
Which famous mechanism is a special case of VCG?
Show the answer
The winner pays the value the others lose because of their presence: the second-highest bid.
Sources
- D. Gale and L. S. Shapley, “College Admissions and the Stability of Marriage”, American Mathematical Monthly 69(1), 9–15 (1962).
- L. E. Dubins and D. A. Freedman, “Machiavelli and the Gale–Shapley Algorithm”, American Mathematical Monthly 88(7), 485–494 (1981); A. E. Roth, “The Economics of Matching: Stability and Incentives”, Mathematics of Operations Research 7(4), 617–628 (1982).
- A. E. Roth, “The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory”, Journal of Political Economy 92(6), 991–1016 (1984); A. E. Roth and E. Peranson, “The Redesign of the Matching Market for American Physicians”, American Economic Review 89(4), 748–780 (1999).
- A. E. Roth, T. Sönmez and M. U. Ünver, “Kidney Exchange”, Quarterly Journal of Economics 119(2), 457–488 (2004).
- A. Abdulkadiroğlu, P. A. Pathak and A. E. Roth, “The New York City High School Match”, and A. Abdulkadiroğlu, P. A. Pathak, A. E. Roth and T. Sönmez, “The Boston Public School Match”, American Economic Review 95(2), 364–371 (2005).
- A. Gibbard, “Manipulation of Voting Schemes”, Econometrica 41(4), 587–601 (1973); M. A. Satterthwaite, Journal of Economic Theory 10(2), 187–217 (1975); R. B. Myerson, “Incentive Compatibility and the Bargaining Problem”, Econometrica 47(1), 61–73 (1979); P. Dasgupta, P. Hammond and E. Maskin, Review of Economic Studies 46(2), 185–216 (1979).
- E. H. Clarke, “Multipart Pricing of Public Goods”, Public Choice 11, 17–33 (1971); T. Groves, “Incentives in Teams”, Econometrica 41(4), 617–631 (1973); J. Green and J.-J. Laffont, Econometrica 45(2), 427–438 (1977).
- R. B. Myerson, “Optimal Auction Design”, Mathematics of Operations Research 6(1), 58–73 (1981).
- Textbooks: D. Fudenberg and J. Tirole, Game Theory (MIT Press, 1991), chapter 7; A. Mas-Colell, M. D. Whinston and J. R. Green, Microeconomic Theory (Oxford University Press, 1995), chapter 23; A. E. Roth and M. Sotomayor, Two-Sided Matching (Cambridge University Press, 1990).
- The Nobel Prize, The Prize in Economic Sciences 2012 and 2007.
- MIT OpenCourseWare, 14.12 Economic Applications of Game Theory.
- Wikipedia (secondary): Stable marriage problem, Revelation principle, Vickrey–Clarke–Groves mechanism, National Resident Matching Program.