Efficiency Adjustments Break the Logarithmic Rank Barrier

Technical Summary: Efficiency Adjustments Break the Logarithmic Rank Barrier

Problem Statement
In random matching markets with independent and identically distributed (i.i.d.) preferences, the student-proposing Deferred Acceptance (DA) mechanism is known for its stability and strategy-proofness but suffers from inefficiency. Classical results by Wilson [1972] and Knuth [1976] establish that under DA, the expected average rank of students (the position of their assigned school in their preference list) is of logarithmic order, $O(\log n)$. This stands in sharp contrast to the rank-minimizing assignment, which achieves an expected average rank bounded by a constant (below 2).

While the Efficiency-Adjusted Deferred Acceptance (EADA) mechanism, proposed by Kesten [2010], is known to Pareto-dominate DA and improve assignments for almost all students in large markets, the magnitude of this improvement remained an open question. Specifically, it was unknown whether EADA's efficiency adjustments could break the logarithmic barrier. Furthermore, no asymptotic rates for the expected average rank were known for EADA or for the broader class of Pareto-efficient mechanisms that weakly Pareto-dominate DA.

Methodology
The authors analyze the expected average rank in balanced one-to-one markets and extend their findings to many-to-one markets with bounded quotas and markets with correlated preferences (Plackett-Luce models). The core of their analysis relies on the sequential implementation of EADA introduced by Tang and Yu [2014].

1. Sequential Implementation: Instead of settling all "under-demanded" schools (those that rejected no student) simultaneously, the authors implement EADA by settling one under-demanded school at a time, rerunning DA on the residual market after each settlement. They prove this sequential process yields the same final matching as the batch process.
2. Deterministic Rank Accounting: Using the sequential view, the authors decompose the total rank into two components:
   • Students settled before a cut point $q$: Their ranks are bounded by the worst rank in the initial DA matching ($M_{DA}$), as EADA never assigns a student a school worse than their DA assignment.
   • Students settled after the cut point: Their ranks are bounded by the total number of applications made in the residual DA run at that stage.
3. Probabilistic Bounds via Union Bounds: The primary challenge is that the residual market is selected endogenously by the mechanism, not drawn as a fresh i.i.d. sample. The authors overcome this by:
   • Defining a "student-closed" market: A residual market where every surviving student prefers their current assignment to every school removed earlier.
   • Proving that for a residual market to be closed and simultaneously have a high number of applications is a rare event.
   • Applying a union bound over all possible sets of surviving students and schools. The probability of a specific set being closed decays exponentially with the number of applications, allowing the authors to control the expected application count despite the endogenous selection.
4. Generalization to Pareto-Efficient Mechanisms: For the broader class of Pareto-efficient mechanisms that weakly Pareto-dominate DA, the authors replace the "closure" condition with an "acyclicity" condition on the envy graph. They show that random preferences admit no large acyclic induced subgraphs in the top-$k$ envy graph, leading to a similar sublogarithmic bound, albeit with a weaker rate.

Key Contributions and Results

• Theorem 1 (EADA Bound): In i.i.d. one-to-one markets, the expected average rank of EADA is bounded by:
  $$E[R(\mu_{EADA})] \le 4 \log \log n + O(1)$$
  This result proves that EADA breaks the logarithmic rank barrier of DA, improving the asymptotic order from $O(\log n)$ to $O(\log \log n)$.

• Theorem 2 (General Pareto-Efficient Bound): For any Pareto-efficient matching that weakly Pareto-dominates DA (including those selected adversarially after observing preferences), the expected average rank is:
  $$E[R(\nu)] = O((\log \log n)^2)$$
  This is the first asymptotic guarantee for the entire class of Pareto-efficient improvements of DA, showing they all achieve sublogarithmic average ranks.

• Extensions:

  • Many-to-One Markets: The results extend to balanced many-to-one markets with bounded quotas $\bar{q}$. EADA achieves $O(\log \log m)$, and general efficient improvements achieve $O((\log \log m)^2)$.
  • Correlated Preferences: Under bounded Plackett-Luce popularity (where the ratio of max to min school weights is $\kappa$), EADA achieves $O(\kappa \log \log n)$, and general improvements achieve $O((\log \log n)^2)$. The paper notes that unrestricted correlation (e.g., tiered markets) can restore linear rank barriers, necessitating these boundedness assumptions.

Significance and Claims
The paper claims to provide the first asymptotic guarantees for the expected average rank of EADA and the broader class of Pareto-efficient improvements of DA.

• Breaking the Barrier: The central claim is that efficiency adjustments do not merely improve assignments by a constant factor but fundamentally change the asymptotic order of student assignments, moving from logarithmic to doubly logarithmic (or squared doubly logarithmic for the general class).
• Robustness: The order break is robust to market capacities and moderate preference correlations.
• Modesty on Tightness: The authors explicitly state that they do not claim the derived coefficients (e.g., 4) or the exact rates ($\log \log n$ vs. $(\log \log n)^2$) are tight. Simulations suggest the average rank grows very slowly, consistent with both bounded growth and slow divergence. The paper positions these results as "first asymptotic guarantees rather than exact characterizations," emphasizing that the primary contribution is ruling out logarithmic average ranks for these mechanisms.
• Methodological Insight: The paper introduces "closure" and "acyclicity" arguments as tools to handle endogenous selection in random matching markets, providing a potential route for future research to obtain tighter bounds.

In summary, the work demonstrates that while DA is inefficient in terms of average rank, the class of mechanisms that Pareto-improve upon DA (including EADA) successfully circumvents the logarithmic inefficiency inherent in stable matching, achieving significantly better average outcomes for students in large random markets.