Asymptotic Equivalence of Immediate and Deferred Acceptance

Imagine you are the mayor of a bustling city where every child needs a spot in a school, but there are exactly as many seats as there are students. The problem isn't just finding a seat; it's finding the right seat. Every family has a list of schools they love, from "My Dream School" down to "The One I'd Go To If I Had To." The city has rules, too: maybe a school gives priority to kids who live nearby or have siblings already there. The big question for the people in charge is: How do we match kids to schools so that everyone is as happy as possible?

For decades, experts have debated two main ways to do this. The first is called Deferred Acceptance (DA). Think of this like a slow, careful dance. Students apply to their top choice. Schools hold onto their favorite applicants but don't say "yes" forever; they just say "maybe." If a better student shows up later, the school can swap them out. This process repeats until everyone is settled. It's famous for being fair and impossible to cheat, but it can be a bit messy and inefficient.

The second method is Immediate Acceptance (IA), often known as the "Boston mechanism." This is more like a frantic race. Students line up and apply to their top choice. Schools look at the line, pick their favorite based on priority, and say "You're in!" immediately. If you get rejected, you instantly run to your second choice. The catch? If you apply to your top choice late, you might lose your spot to someone with higher priority who applied earlier, even if you really wanted that school more. Because of this, IA is often criticized for being unfair or easy to manipulate. However, it has one big superpower: if everyone tells the truth about what they want, IA guarantees a result where no one can be made happier without making someone else unhappy. This is called "Pareto efficiency."

So, here is the million-dollar question: Does IA's superpower actually make a huge difference in real life? Does it get kids into schools they like much better than the slower DA method? Or is the difference just a tiny, invisible speck? This is the puzzle Josué Ortega tackles in his paper.

---

The Great School Race: A Tale of Two Mechanisms

Josué Ortega, a researcher from Queen's University Belfast, decided to settle this debate by running a massive thought experiment. He didn't look at real cities with their messy history and politics. Instead, he imagined a "random market"—a world where every student's list of favorite schools is drawn completely at random, like pulling names out of a hat. In this world, there are $n$ students and $n$ schools.

Ortega wanted to measure the "average rank." Imagine if every student got a score based on how high up their list their assigned school was. If you got your #1 choice, your rank is 1. If you got your #100 choice, your rank is 100. The goal is to keep this number as low as possible.

For a long time, we knew the answer for the slow, careful dance (DA). Back in the 1970s, mathematicians figured out that in a random market, the average student ends up at a school ranked about $\log n$ (logarithm of $n$). If you have 1,000 students, the average rank is roughly 7. If you have 100,000 students, it's roughly 11. It grows, but very slowly.

But what about the frantic race (IA)? Because IA works differently—where the order of application matters and students can get rejected just for being "late"—mathematicians thought it might be much more complex. Some computer scientists had tried to solve it, but they could only figure out the odds of getting a specific rank, not the average rank for everyone. They guessed it might be logarithmic too, but no one could prove it.

The "Coupon Collector" Secret

Ortega's breakthrough was realizing that both mechanisms, despite looking totally different, are secretly playing the same game. He used a classic puzzle called the Coupon Collector Problem to explain it.

Imagine you are trying to collect a complete set of $n$ different trading cards. Every time you buy a box of cereal, you get one random card. How many boxes do you need to buy to get every single card at least once?
The answer is roughly $n \times \log n$. You spend a lot of time buying boxes just to find the last few rare cards you're missing.

Ortega showed that Deferred Acceptance is exactly like this. Students keep applying to schools until every school has received at least one application. The total number of applications made by everyone is roughly the same as the number of cereal boxes you'd need to buy to collect all the coupons. Since the average student makes about $\log n$ applications, their final school rank is also about $\log n$.

Then, Ortega turned his gaze to Immediate Acceptance. At first, it seemed different because students can't just keep applying immediately; they have to wait for a "round" to finish before trying again. But Ortega realized that if you look at the process in a specific way, it's also a coupon collector.

He imagined a slightly "amnesiac" version of the game. Suppose a student keeps picking schools at random, even if they've already tried that school. If they pick a school they've already tried, they just ignore it (that's a "wasted" draw). Ortega proved that even with these wasted draws, the number of real applications needed to fill every school is still roughly the same as the coupon collector problem.

The Big Reveal

Here is the punchline: The difference between the two methods is surprisingly small.

Ortega proved mathematically that as the market gets huge (as $n$ gets very large), the average rank for students in the Immediate Acceptance (IA) system is also roughly $\log n$.

This means that even though IA is "Pareto efficient" (meaning it's theoretically perfect if everyone tells the truth), it does not give students a massive advantage in terms of getting their top choices compared to the slower DA method. The "first-order" improvement—the big, noticeable gain—simply doesn't exist.

Ortega's paper explicitly rules out the idea that IA is a magic bullet that drastically improves student outcomes in large, random markets. While IA might be slightly better in specific, tiny scenarios or with specific priority rules, the paper shows that in the general case, the two mechanisms are asymptotically equivalent. They both land students in schools ranked roughly logarithmically in the size of the market.

Why This Matters

This finding is a bit of a bummer for fans of the "Immediate Acceptance" system, but it's a relief for the math. It tells us that the "Pareto efficiency" of IA is a bit of a mirage when it comes to average happiness. The mechanism that is often criticized for being unfair and manipulable doesn't actually deliver a significantly better average result than the one that is fair and hard to cheat.

Ortega's work extends this finding to other variations, too. Whether schools have multiple seats (many-to-one matching) or whether students are allowed to skip over full schools (a variation called "IA with skips"), the result holds: the average rank stays around $\log n$.

So, the next time you hear someone argue that we must use the "Boston mechanism" because it's more efficient, you can smile and say, "Well, maybe it's efficient, but it doesn't actually get kids into better schools on average than the other way." In the grand race of school choice, both runners are crossing the finish line at almost the exact same time.