Computational Hardness of the Hylland-Zeckhauser Scheme

We study the complexity of the classic Hylland-Zeckhauser scheme [HZ79] 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 [VY21], 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.