# Computational Hardness of the Hylland-Zeckhauser Scheme

arXiv: https://arxiv.org/abs/2107.05746 · HTML: https://mlsanity.com/paper/2107.05746/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2021.

## Built on by (most cited first, 3 of 3)

- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations](https://mlsanity.com/paper/2610.19690/) (2026)

## Abstract (arXiv)

We study the complexity of the classic Hylland-Zeckhauser scheme [HZ'79] for one-sided matching markets. We show that the problem of finding an ε-approximate equilibrium in the HZ scheme is PPAD-hard, and this holds even when ε is polynomially small and when each agent has no more than four distinct utility values. Our hardness result, when combined with the PPAD membership result of [VY'21], resolves the approximation complexity of the HZ scheme. We also show that the problem of approximating the optimal social welfare (the weight of the matching) achievable by HZ equilibria within a certain constant factor is NP-hard.