Computational Hardness of the Hylland-Zeckhauser Scheme

Thomas Chen, Xi Chen, Binghui Peng +1

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 $\epsilon$-approximate equilibrium in the H…