Metraipolis › archive › dc_e83ebd0648f0

Settling the Complexity of Hylland--Zeckhauser Equilibria — arXiv:2606.06317

Source
arXiv (en)
Original
https://arxiv.org/abs/2606.06317
License (as archived)
CC0-1.0
Archived
2026-11-05T18:32:05.085Z
SHA-256 of the archived text
521cd8530e51084495ed6d9649cca61c4d9409eb8f8b7aa4d224470d51e5be41
Stable URL of this page
https://metraipolis.com/documento/dc_e83ebd0648f0

How to cite

Settling the Complexity of Hylland--Zeckhauser Equilibria — arXiv:2606.06317 — arXiv (en), https://arxiv.org/abs/2606.06317 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e83ebd0648f0 (Metraipolis archive dc_e83ebd0648f0, sha256 521cd8530e51084495ed6d9649cca61c4d9409eb8f8b7aa4d224470d51e5be41)
BibTeX
@misc{dce83ebd0648f0,
  title = {Settling the Complexity of Hylland--Zeckhauser Equilibria — arXiv:2606.06317},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2606.06317},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e83ebd0648f0; sha256 521cd8530e51084495ed6d9649cca61c4d9409eb8f8b7aa4d224470d51e5be41},
  year = {2026}
}

Archived text

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

The Hylland--Zeckhauser (HZ) mechanism is a foundational framework for allocating indivisible goods in one-sided matching markets via lotteries supported by competitive prices and equal artificial budgets. We resolve the exact computational complexity of the HZ scheme by proving that computing an exact HZ equilibrium is FIXP-complete, thereby settling a conjecture of Vazirani and Yannakakis. Notably, this hardness persists even when computing the equilibrium allocation alone. We establish our hardness result via a reduction that encodes quadratic fixed-point equations into a reciprocal variational inequality. On the algorithmic side, we present a deterministic polynomial-time approximation algorithm that achieves an additive error of $0.0755211 + \delta$ for any $\delta > 0$, significantly improving upon the previous $1/e$ guarantee.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2606.06317 — 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-11-05T18:21:34.065Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).