📈 economics

A Note on the Strategic Vulnerability of the Boston Mechanism in Random Markets

This paper presents the first asymptotic analysis of the Boston Mechanism in random markets, demonstrating that while truthful reporting initially yields high satisfaction, the mechanism becomes strategically vulnerable in equilibrium as market size grows, causing average student assignment quality to collapse from logarithmic to nearly linear rank.

Original authors: Josue Ortega

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Josue Ortega

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "First-Choice" Trap

Imagine a high school where every student gets to pick their favorite school. There is a popular rule called the Boston Mechanism. It works like this:

Round 1: Everyone applies to their #1 choice.
The Cut: If a school is full, it instantly accepts the students with the highest "priority" (like having a sibling there or living nearby) and rejects everyone else.
Round 2: The rejected students immediately apply to their #2 choice.
Repeat: This continues until everyone is placed.

For years, policymakers loved this system. Why? Because when everyone plays honestly (telling the truth about what they want), about 63% of students get their absolute favorite school. That sounds amazing! It beats almost every other system.

But here is the catch: This paper argues that this "63% success rate" is a mirage. It only exists if students are naive and don't think ahead. As soon as students start playing strategically (trying to game the system to avoid rejection), the system collapses.

Analogy 1: The "Rush Hour" Traffic Jam

Think of the school assignment process like a massive traffic jam at a popular intersection.

The Honest Scenario (The 63% Miracle):
Imagine everyone just drives straight to their dream destination without checking traffic. Because there are so many drivers, almost every road gets at least one car. The "Boston Mechanism" acts like a cop who lets the first car through immediately. Since everyone is driving randomly, about 63% of people happen to get lucky and get their dream spot on the first try. It looks like a miracle.

The Strategic Scenario (The Collapse):
Now, imagine everyone has a GPS that tells them, "Hey, that road is too crowded; you'll get stuck."

Smart drivers stop aiming for the most popular school because they know they will get rejected.
Instead, they aim for the second or third best school to be safe.
The Domino Effect: Because everyone avoids the top schools, the top schools suddenly get empty! But wait, the students who did aim for the top schools (the ones who didn't change their strategy) now get rejected because the "safe" schools are full.
The Result: The whole system unravels. The "lucky" 63% disappears. In fact, as the city (market) gets bigger, the number of people getting their #1 choice drops to zero.

The Two Main Findings

The paper uses math to prove two shocking things about what happens when students play smart:

1. The "First Choice" Rate Vanishes

Truthful Play: 63% of students get their #1 pick.
Strategic Play: 0% of students get their #1 pick (in the long run).
The Metaphor: It's like a game of musical chairs where everyone realizes the music is about to stop. Instead of running for the nearest chair, everyone tries to sit in the "best" chair. But because everyone is so smart, they all end up standing in the middle of the room, and no one gets the chair they wanted. The "First Choice" rate doesn't just go down; it evaporates.

2. The "Average Rank" Disaster

This is the second, even more dramatic finding.

Truthful Play: On average, a student gets their 7th choice. (This is actually pretty good!)
Strategic Play: Depending on how the "game" is played, the average student might end up with their 145th choice.
The Metaphor: Imagine you are ordering a meal.
- Honesty: You order your favorite dish. If it's sold out, you get your 7th favorite. You leave happy.
- Strategy: You try to be clever. You think, "I'll order the 2nd best dish because the 1st is too popular." But everyone else thinks the same thing. The 2nd best dish gets sold out instantly. You try the 3rd, then the 4th... until you are forced to eat the 145th item on the menu, which is basically a raw potato.
- The paper shows that strategic thinking can turn a "pretty good" meal into a "disaster" meal.

Why Does This Happen? (The "Cascade" Effect)

The author explains that the Boston Mechanism has a built-in "cascade" (a chain reaction).

In the honest world: The cascade is short. You get rejected from #1, you take #2, and you're done.
In the strategic world: The cascade becomes a runaway train. Because everyone is trying to avoid the "popular" schools, they all pile onto the "medium" schools. Those get full. Then everyone piles onto the "okay" schools.
The result is that students are pushed further and further down their list of choices.

The Takeaway for Policymakers

This paper is a warning label for school districts.

Don't trust the "63%" statistic: If a school district says, "Our system gives 63% of kids their first choice," they are only measuring what happens if kids are naive.
Strategy hurts everyone: When kids try to outsmart the system, the system breaks. It doesn't just help the smart kids; it hurts the average kid, pushing them from their 7th choice to their 145th.
The Boston Mechanism is fragile: It works well only if everyone is honest. But in the real world, people are rarely honest when their future is on the line.

In short: The Boston Mechanism is like a house of cards. It looks beautiful and tall when the wind is calm (everyone is honest). But the moment the wind blows (students start strategizing), the whole thing collapses, leaving everyone with a worse outcome than if they had just played it safe.

1. Problem Statement

The paper investigates the performance of the Boston Mechanism (BM), also known as Immediate Acceptance, in large random markets. While BM is widely used in school choice systems, it is known to be manipulable (not strategy-proof).

The Gap: Previous literature (specifically Pritchard and Wilson, 2023) demonstrated that under truthful preference revelation, BM achieves a remarkably high "first preference rate" (approx. 63%) and a low "average rank" (logarithmic order) in random markets, outperforming other efficient mechanisms like Serial Dictatorship (SD) and Top Trading Cycles (TTC).
The Question: Does this superior performance hold when students act strategically (i.e., in Nash Equilibrium)? The paper aims to quantify the asymptotic performance of BM in every Nash equilibrium of the preference revelation game as the market size $n \to \infty$ .

2. Methodology

The author employs the Random Markets framework, a standard theoretical benchmark in mechanism design.

Model Setup:
- A one-to-one matching problem with $n$ students and $n$ schools (each with capacity 1).
- Preferences and Priorities: Both student preferences over schools and school priorities over students are drawn independently and uniformly at random.
- Information Structure: The analysis assumes complete information. Students know the true preferences of all other students and all school priorities before submitting their lists.
Mechanism: The Boston Mechanism operates in rounds. In round $k$ , remaining students apply to their $k$ -th choice. Schools immediately and permanently accept the highest-priority applicant among those applying in that round.
Equilibrium Concept: The study analyzes the set of Nash Equilibria (NE) of the induced preference revelation game.
- A key theoretical tool used is the result by Ergin and Sönmez (2006), which establishes that the set of Nash equilibrium outcomes of the Boston Mechanism coincides exactly with the set of stable matchings under true preferences.
Performance Metrics:
1. First Preference Rate ( $f$ ): The fraction of students assigned to their top choice.
2. Average Rank ( $r$ ): The mean position of the assigned school in the student's preference list.
Equilibrium Selection: Since multiple equilibria exist, the paper defines an equilibrium selection rule $\sigma$ that picks one stable matching for any given realization of the market. The results characterize the performance across all possible selection rules.

3. Key Contributions

This paper provides the first asymptotic analysis of the Boston Mechanism under equilibrium play in random markets. Its primary contributions are:

Refuting the "Truthful Advantage": It demonstrates that the high first preference rate (63%) observed under truthful reporting is an artifact of naive behavior and vanishes completely under strategic play.
Quantifying Strategic Vulnerability: It proves that strategic behavior can lead to catastrophic efficiency losses, shifting the average rank from logarithmic (efficient) to nearly linear (highly inefficient), depending on the equilibrium selected.
Bridging Theory and Practice: It connects the theoretical property of BM (equivalence to stable matchings) with asymptotic performance metrics, explaining why the mechanism fails in large strategic markets.

4. Key Results

A. First Preference Rate ( $f$ )

Truthful Behavior: As established by Pritchard and Wilson (2023), under truthful reporting, $f(BM_n) \to 1 - e^{-1} \approx 0.63$ .
Strategic Behavior (The Main Result):
- Proposition 2: For any equilibrium selection rule $\sigma$ , the expected first preference rate converges to zero as the market size grows:
  $\lim_{n \to \infty} f(BM^\sigma_n) = 0$
- Rate of Convergence: The rate is $O(1/\log n)$ .
- Mechanism: In equilibrium, students anticipate rejection at popular schools and avoid "wasting" their first-round application there. This triggers a cascading effect where students shift applications to lower-ranked schools. Since the number of applications per school in a random market is $\Theta(\log n)$ , the probability of a student having the highest priority at their true top choice drops to $1/\log n$ . Consequently, the "lucky" 63% first-round matches disappear.

B. Average Rank ( $r$ )

Truthful Behavior: The average rank grows as $\Theta(\log n)$ , which is better than Serial Dictatorship but worse than the Rank-Minimizing mechanism.
Strategic Behavior: The outcome depends heavily on the specific equilibrium selected:
- Best Case (Student-Optimal Stable Matching): There exists an equilibrium where the average rank remains $\Theta(\log n)$ . This occurs if strategic adjustments are mild, preserving the student-optimal outcome.
- Worst Case (School-Optimal Stable Matching): There exists an equilibrium where the average rank degrades to $\Theta(n / \log n)$ .
- Proposition 3:
  $\inf_{\sigma} r(BM^\sigma_n) = \Theta(\log n)$
  $\sup_{\sigma} r(BM^\sigma_n) = \Theta\left(\frac{n}{\log n}\right)$
- Implication: In a market of $n=1,000$ , the average student moves from their 7th choice (truthful) to their 145th choice (worst-case equilibrium).

5. Significance and Discussion

Policy Relevance: The findings challenge the use of the Boston Mechanism in real-world school choice. While policymakers often cite the high "first preference rate" as a success metric, this paper shows that metric is illusory in a strategic environment. The mechanism is extremely fragile; once agents stop being naive, the mechanism collapses to a state where almost no one gets their first choice.
Efficiency vs. Stability: The paper highlights that while the set of NE outcomes are stable matchings, the quality of these matchings varies wildly. The mechanism allows for equilibria that are highly inefficient (School-Optimal), which are significantly worse than the truthful outcome.
Robustness:
- The results hold under complete information. The author notes that incomplete information (where students don't know others' preferences) is an open question, as the equivalence to stable matchings may break down.
- The results assume a balanced market ( $n$ students, $n$ schools). In "thick" markets (more students than seats), the first preference rate would likely vanish even under truthful play, potentially reducing the relative gap between truthful and strategic behavior, though absolute welfare would still be low.

Conclusion: The Boston Mechanism's apparent efficiency in random markets is entirely dependent on the assumption of truthful reporting. Under strategic play, its performance degrades to the point where it offers no advantage over other mechanisms in terms of first-choice assignments and can lead to severe inefficiencies in average placement. This underscores the critical importance of accounting for incentives when evaluating allocation mechanisms.