When the Welfare Ranking and the Incentive Ranking Disagree

mennle_seuken_2014_da_vs_boston.md · 1,627 words · 7 min read

When the Welfare Ranking and the Incentive Ranking Disagree

Mennle and Seuken (2014) compare three centralized school-choice mechanisms — Deferred Acceptance, Classic Boston, and Adaptive Boston — and show that the ordering that maximizes student welfare is the exact reverse of the ordering that resists strategic manipulation. The paper formalizes the trade-off, places the Adaptive Boston Mechanism on the Pareto frontier between the two objectives, and validates the claim on the Mexico City high-school match. For a decentralized model like college-sim, the moral is less "which mechanism should you adopt" and more "where in your sequential round structure are students rewarded for misreporting, and by how much."

The mechanism design problem

When a city school district assigns tens of thousands of students to a few hundred schools, it has to choose a rule. The rule turns each student's stated preference list and each school's priority ordering into a single matching. Three rules dominate the literature: Deferred Acceptance (DA), the Classic Boston Mechanism (BM), and the Adaptive Boston Mechanism (ABM). The companion essay College Admissions as a Matching Market develops the DA primer in depth and traces it from Gale and Shapley's 1962 paper through Roth's NRMP work to the Boston schools reform. The K-12 companion School Choice Mechanisms walks through the Boston-mechanism failure that motivated the switch.

Mennle and Seuken's contribution is to prove a clean, general, and uncomfortable result: the welfare ranking of these three mechanisms is the exact reverse of their incentive-compatibility ranking. Under truthful play BM produces the best welfare, ABM the second-best, DA the worst. Under strategic play DA is incorruptible, BM is the most corruptible, and ABM lies cleanly between them. The paper shows ABM is on the Pareto frontier of welfare-versus-strategy-proofness — you cannot improve one without sacrificing the other. The simulation evidence is built on top of this theory rather than as a substitute for it.

DA, BM, and ABM in 90 seconds

Deferred Acceptance (student-proposing). Round k: each unmatched student proposes to their k-th-listed school. Each school tentatively holds the highest-priority proposers up to capacity and rejects the rest. Tentative holds can be displaced in later rounds when a higher-priority student arrives. Terminate when nobody is rejected. DA is strategy-proof for students: truth-telling is a dominant strategy, and the result is the student-optimal stable matching.

Classic Boston Mechanism (immediate acceptance). Round k: each unmatched student applies to their k-th-listed school. Each school admits up to its remaining capacity by priority among new applicants only. Admissions are final the moment they are made. A round-1 admit cannot be displaced even by a higher-priority round-2 applicant. The mechanism is not strategy-proof: a sophisticated family that knows a popular school will fill in round 1 has a strict incentive to skip listing it altogether — any rejection at the head of the list forfeits priority at every later school for which other students named that school first.

Adaptive Boston Mechanism. ABM is the simplest possible patch on BM. Before each round begins, every student's preference pointer is automatically advanced past schools that are already full. The student then applies to the next available school on their list rather than wasting an application on a school that has no remaining seats. Mechanically the change is tiny. Strategically it is enormous: the most damaging form of manipulation under BM is "skip the popular school you actually like best, because applying to it costs you the schools you would have ranked below it." ABM does that skipping for you, free of charge. The payoff for misreporting your top choice falls dramatically.

Headline results: the welfare-vs-incentives Pareto frontier

The paper's two formal claims, in plain language:

1. Welfare ranking under truthful play. For sufficiently large markets, BM rank-dominates ABM, which rank-dominates DA. "Rank-dominates" means the distribution of student match-ranks under BM stochastically dominates ABM's, which dominates DA's. More students get their first choice under BM than under ABM than under DA, more students get their top three, and so on at every cutoff.

2. Incentive ranking. DA is fully strategy-proof. ABM is partially strategy-proof — Mennle and Seuken define a quantitative epsilon-bound on the worst-case manipulation gain that ABM achieves but BM does not. BM is fully manipulable, with no nontrivial bound.

The two rankings are exact reverses. Stated together: the better a mechanism does on welfare under the assumption of honest reporting, the worse it does at protecting honest reporters from being exploited by sophisticated ones.

The Mexico City computational experiments — roughly 270,000 students applying to roughly 700 high schools, on real preference data — quantify the gap. ABM delivers welfare numbers that sit very close to BM's while reducing the average best-response manipulation gain by roughly 50% relative to BM. ABM is not the welfare-maximizer and not the strategy-proof option; it is the in-between point that empirically dominates everything off the frontier.

The reproduction in /research2/cas-abm-references/reproductions/04-mennle-seuken-da-vs-boston/ recovers the welfare ordering at small market scale (200 students, 10 schools, 100 seeds). At that scale BM and ABM both show clear manipulation gains and DA shows zero, but the BM-vs-ABM 50%-reduction gap that the paper documents on Mexico City does not cleanly separate — that quantitative claim sharpens as the market grows, exactly as the asymptotic theory predicts.

What college-sim already does

College-sim is not a centralized school-choice mechanism. There is no rule we are evaluating against alternatives — there is no DA mode, no BM mode, no ABM mode. The US college admissions system the simulator models is fundamentally decentralized: each college runs its own admission process, students send applications independently, and there is no clearinghouse that takes preference lists in and emits a matching out. So the cleanest mapping from Mennle-Seuken's machinery to ours is structural rather than mechanistic.

The closest analog college-sim has to a sequential proposal mechanism is the six-round structure: ED → EA/REA → EDII → RD → student decisions → waitlist. Round assignment is computed once per student in assignRounds() (sim.js:2764); each round is then processed in turn through processRound() (sim.js:4511), which dispatches to routeApplicants() (sim.js:4338) to bin applicants into the various pools (athlete, legacy, first-gen, URM, general, and so on) and admitFromPool() (sim.js:4416) to issue admits within each pool. After the four admit rounds, students see their full set of admits and pick one in studentFinalDecisions() (sim.js:4919). Colleges that ended up under-enrolled then resolve their waitlists in resolveWaitlist() (sim.js:5013).

The Early Decision multipliers are the closest thing in the model to a Boston-style preference signal. ED_MULT_DATA (sim.js:1318) supplies a per-college boost to the admission logit for ED, EDII, REA, and EA applicants. ED's binding commitment is, structurally, the same lever Boston uses: a college rewards you with higher admit probability in exchange for revealing it as your first choice. The reward is large — up to 4-6× the regular-decision rate at some Ivies — and like the Boston mechanism it disproportionately benefits sophisticated applicants who understand the trade-off and have the financial flexibility to commit before seeing aid offers.

Crucially, college-sim does not enforce stability by construction. There is no Gale-Shapley-style displacement of tentative holds, and the model does not guarantee that the realized matching is free of blocking pairs. We treat stability as an empirical property of the output rather than a structural property of the mechanism, and a stability check would test for blocking pairs after the fact rather than design them out a priori.

What Mennle-Seuken does that we don't (yet)

Mennle and Seuken's central diagnostic is the manipulation gain: for each student, fix every other student's report at truth, then search a candidate strategy set for that student's best-responding misreport, and measure how many ranks of personal welfare the misreport buys them. The score is well-defined for any matching mechanism, including a decentralized one. The most directly publishable extension of college-sim is to compute it.

Concretely: for each (archetype × tier) cell — say, humanities-spike applicants targeting Tier-2 schools, or well-rounded students with a Pell flag targeting Tier-4 publics — generate a representative student, build a "truthful" application portfolio that follows the model's default utility ordering, and compare the realized match-rank against three strategic alternatives: an ED-aggressive portfolio that spends the binding commitment on the most ambitious reach, a RD-safeties-only portfolio that skips ED entirely to preserve aid leverage, and an oracle portfolio that knows the realized random draws and picks the optimal application set ex post. The gap between truthful and oracle is the manipulation ceiling; the gap between truthful and the realistic strategic variants is the manipulation gain a sophisticated student could actually capture.

The output is a simple table — archetype rows, tier columns, manipulation-gain cells — that answers the question "where in the system do honest applicants pay the largest tax for being honest?" Mennle and Seuken show that the answer in centralized systems is concentrated in a few well-understood structural places. In a decentralized system with binding ED, the answer is open and is exactly the kind of narrative the marketing site is built to surface. We forward-link the implementation roadmap in cas_abm_extensions_roadmap.html.

Run the reproduction yourself

A pure-Node.js reproduction of the welfare and manipulation-gain comparison lives at /research2/cas-abm-references/reproductions/04-mennle-seuken-da-vs-boston/README.md. The reproduction implements DA, BM, and ABM directly and reports mean rank, median rank, and manipulation gain across 100 seeds. The welfare ordering reproduces cleanly at 200 students and 10 schools; the BM-vs-ABM manipulation-gain gap that the paper highlights sharpens at the larger market scales the asymptotic theory targets.

Citation

Mennle, T., & Seuken, S. (2014). Trade-offs in School Choice: Comparing Deferred Acceptance, the Naive and the Classic Boston Mechanism. arXiv:1406.3327. Revised 2017. University of Zurich.