Efficiency Adjustments Break the Logarithmic Rank Barrier

Abstract

We study the expected average rank achieved by the Efficiency-Adjusted Deferred Acceptance (EADA) mechanism in i.i.d.\ matching markets. While student-proposing Deferred Acceptance gives students an expected average rank of logarithmic order, we prove that EADA's expected average rank is at most $4\log \log n+O(1)$. Therefore, EADA improves the asymptotic order of students' assignments. At the cost of a weaker bound, $O((\log \log n{)}^2)$, we extend this conclusion to a much larger class of mechanisms. Namely, every Pareto-efficient mechanism that weakly Pareto-dominates DA breaks DA's logarithmic barrier. These are the first asymptotic guarantees for the expected average rank of EADA and of the broader class of Pareto-efficient improvements of DA. The conclusions extend to many-to-one markets with bounded quotas and random markets with correlated preferences.