Comment on 'What's the Matter with Tie-Breaking: Improving Efficiency in School Choice'

This paper identifies and corrects a bug in the code used by Erdil & Ergin (2008) to compute stable improvement cycles, revealing that while their theoretical findings remain valid, the actual fraction of students benefiting from tie-breaking is slightly lower and their average rank improvement is slightly higher than originally reported.

The Gist

Imagine a high-stakes game of musical chairs, but instead of chairs, the prizes are spots in popular schools. Everyone has a list of which schools they want most, and every school has a list of which students they prefer most.

In 2008, two researchers named Erdil and Ergin wrote a famous paper about how to fix this game when there are ties (when two students are equally good for a school). They created a "magic algorithm" to shuffle students around so that everyone ends up happier without anyone being unfairly bumped out. They even wrote computer code to prove how well this magic worked.

The Plot Twist: A Tiny Bug in the Magic Wand

Fast forward to 2026. A researcher named Tom Demeulemeester decided to check the math behind that magic wand. He found a tiny, almost invisible glitch in the code Erdil and Ergin used.

Think of the algorithm like a referee in a game. When a student gets a better seat, the referee is supposed to say, "Okay, you're happy with this new seat, so stop looking at the other seats you wanted."

The Bug:
In the original code, the referee was a bit lazy. If a student moved from School A to their dream School B, the referee told them to stop looking at School B. But the referee forgot to tell them to stop looking at School C, which was in between A and B.

The Result:
Because the student was still "looking" at School C (even though they already had a better seat at B), the computer got confused. It thought, "Oh, this student still wants School C!" and swapped them again. This time, they got moved from their dream School B to the "okay" School C.

In the worst case, this caused a student to end up in a seat they liked less than the one they started with, breaking the rules of fairness (stability) that the whole system was supposed to protect.

The Fix
Tom found the bug and wrote a patch. It's like giving the referee a better checklist. Now, when a student moves up to a better school, the referee immediately crosses off every school on their list that is worse than the new one but better than the old one. No more confusion.

Did the Original Research Fail?
Here is the good news: No. The big ideas in the original 2008 paper are still 100% true. The "magic" still works; it just wasn't quite as powerful as the original computer simulation suggested.

When Tom ran the numbers with the fixed code:

• Fewer people got a "lucky break" than the original paper claimed (the number of happy campers dropped slightly).
• But, for the people who did get a better spot, the improvement was bigger than originally thought. They didn't just get a slightly better school; they got a much better one.

The Bottom Line
It's like finding out that a recipe for a cake was slightly off. The cake still tastes delicious (the theory is sound), and the general idea of the cake is correct. But now, with the corrected recipe, we know exactly how much sugar to use to get the perfect result. The original authors didn't lose their reputation; they just got a little help from a new generation of researchers to make their math perfect.

Technical Summary

Here is a detailed technical summary of the paper "What's the Matter with Tie-Breaking: Improving Efficiency in School Choice" by Tom Demeulemeester.

1. Problem Statement

The paper addresses a critical implementation error in the code used by Erdil and Ergin (2008) to compute Stable Improvement Cycles (SIC).

• Context: In school choice mechanisms, the Deferred Acceptance (DA) algorithm produces a stable matching but is not necessarily efficient (Pareto optimal) when student priorities contain ties. Erdil and Ergin proposed an algorithm to resolve these ties by identifying and executing "stable improvement cycles" to improve student welfare without violating stability.
• The Issue: The specific code implementation provided by Erdil and Ergin (2019) to execute these cycles contains a bug. Under certain conditions, this bug causes the algorithm to generate unstable matchings, violating the fundamental requirement of the mechanism.

2. Methodology

The author employs a combination of theoretical counterexample construction and large-scale computational re-evaluation.

• Counterexample Construction:

  • The author constructs a specific instance with four agents (students) and four unit-capacity objects (schools).
  • Preferences and priorities are defined such that the original code, starting from a DA matching, resolves one cycle (between agents 2 and 4) and then erroneously resolves a second cycle (between agents 2 and 3).
  • This sequence results in a final matching ($\mu'$) where a blocking pair exists (specifically, student 2 and school $b$), proving the output is unstable.

• Code Analysis and Correction:

  • Root Cause: The bug lies in the improve_allocations function. When a student $i$ moves from school $x$ to a preferred school $y$ via a cycle, the original code correctly removes the student from the priority list of $y$ ($D_y$). However, it fails to remove the student's proposals to schools ranked between $x$ and $y$ in their preference list.
  • Consequence: This oversight allows the student to remain in the candidate sets ($D_z$) for schools $z$ that are less preferred than the new school $y$ but more preferred than the old school $x$. This leads to the student being included in subsequent, invalid cycles.
  • Fix: The author proposes a code modification that iterates through all schools ranked between the old and new assignments and explicitly removes the student's proposals from those schools' priority lists.

• Computational Re-evaluation:

  • The author re-ran the computational experiments from Erdil and Ergin (2008) using both the original (buggy) code and the corrected code.
  • Parameters: 1,000 students, 20 schools, 200 instances per parameter set.
  • Variables: $\alpha$ (correlation in student preferences) and $\beta$ (sensitivity to locational proximity).

3. Key Contributions

1. Identification of the Bug: The paper pinpoints the exact logical flaw in the SIC algorithm's implementation regarding the updating of student proposals to intermediate schools.
2. Corrected Implementation: A verified, corrected version of the code is provided (hosted on GitHub), ensuring that future research using SIC algorithms produces stable matchings.
3. Quantitative Impact Analysis: The paper quantifies how the bug distorted the empirical findings of the seminal 2008 study.

4. Results

The re-evaluation yielded the following findings:

• Stability: In the specific counterexample, the original code produced an unstable matching. In the large-scale simulation (25,200 instances), the original code resulted in unstable matchings in only 2 instances, suggesting the bug is rare but theoretically possible.
• Matching Divergence: In 90.6% of the instances where the SIC algorithm successfully improved upon the DA matching, the corrected code produced a different matching than the original code.
• Efficiency Metrics:
  • Fraction of Improving Students: The corrected code shows a slightly smaller fraction of students who benefit from the tie-breaking compared to the original report.
  • Average Rank Improvement: The average improvement in rank for those who do benefit is larger than originally reported.
  • Overall Welfare: The corrected code results in matchings with a lower average rank (better overall welfare) than the original code. The improvement in average rank due to the fix can reach up to 5%, depending on the parameters $\alpha$ and $\beta$.

5. Significance

• Validation of Theoretical Foundations: The paper confirms that all theoretical findings in Erdil and Ergin (2008) remain unaffected. The existence of stable improvement cycles and the theoretical properties of the mechanism hold true.
• Refinement of Empirical Insights: While the general insights of the 2008 study persist (that tie-breaking can significantly improve efficiency), the magnitude of these gains was slightly misestimated due to the bug. The corrected data suggests that while fewer students might be involved in improvements, the improvements for those involved are more substantial.
• Reproducibility and Reliability: This work highlights the importance of verifying code implementations in mechanism design. It ensures that future policy analyses and academic research relying on the SIC algorithm are based on stable and accurate computational results.