Metraipolis › archive › dc_52220aa28bd2

Efficiency Adjustments Break the Logarithmic Rank Barrier — arXiv:2608.09984

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.09984
License (as archived): CC0-1.0
Archived: 2026-10-19T06:15:06.560Z
SHA-256 of the archived text: 28a1df1052d8196404edfb53652d7cc78cb05e8fc9684888c5ccd1ad1cc3a440
Stable URL of this page: https://metraipolis.com/documento/dc_52220aa28bd2

How to cite

Efficiency Adjustments Break the Logarithmic Rank Barrier — arXiv:2608.09984 — arXiv (en), https://arxiv.org/abs/2608.09984 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_52220aa28bd2 (Metraipolis archive dc_52220aa28bd2, sha256 28a1df1052d8196404edfb53652d7cc78cb05e8fc9684888c5ccd1ad1cc3a440)

BibTeX

@misc{dc52220aa28bd2,
  title = {Efficiency Adjustments Break the Logarithmic Rank Barrier — arXiv:2608.09984},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.09984},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_52220aa28bd2; sha256 28a1df1052d8196404edfb53652d7cc78cb05e8fc9684888c5ccd1ad1cc3a440},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09984. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-12 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Theoretical Economics (econ.TH).
Pagina del lavoro: https://arxiv.org/abs/2608.09984 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T06:10:07.743Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).