EADA algorithm breaks DA's logarithmic rank barrier in matching markets

In a new paper on arXiv, researchers Josue Ortega, Geng Zhao, and Gabriel Ziegler solve a long-standing question about matching market efficiency. The student-proposing Deferred Acceptance (DA) algorithm, widely used in school choice systems, is known to produce stable matches but leaves students with an expected average rank that grows logarithmically with market size. The authors prove that the Efficiency-Adjusted Deferred Acceptance (EADA) mechanism—a Pareto-efficient improvement of DA—cuts this to at most 4 log log n + O(1), breaking the logarithmic order. This is the first asymptotic guarantee for EADA, and the team extends the result to any Pareto-efficient mechanism that weakly Pareto-dominates DA, achieving a bound of O((log log n)^2).

The results hold for many-to-one markets with bounded quotas and for random markets with correlated preferences, broadening real-world applicability. For professionals working on matching platforms—from public school assignment to residency placement—this means that carefully designed efficiency adjustments can dramatically improve student welfare without sacrificing stability. The proof also opens the door for further research into the trade-off between efficiency and strategic properties in matching mechanisms. As the authors note, these are the first asymptotic guarantees for this broader class of improvements, establishing a new benchmark for evaluating alternative matching algorithms in both theory and practice.