Computational Hardness of the Hylland-Zeckhauser Scheme
Computational Hardness of the Hylland-Zeckhauser Scheme
复制标题
DOI：
10.1137/1.9781611977073.90
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Thomas Chen;Xi Chen;Binghui Peng;M. Yannakakis
中科院分区：
文献类型：
--
作者：
Thomas Chen;Xi Chen;Binghui Peng;M. Yannakakis
我们研究了单边匹配市场的经典Hylland-Zeckhauser方案的复杂性。我们证明，在HZ方案中找到$\epsilon$-近似平衡的问题是PPAD困难的，即使$\epsilon$呈多项式小并且每个代理的效用值不超过四个，这一点也成立。我们的硬度结果，当结合PPAD成员的结果[VY'21]，解决了HZ方案的近似复杂性。我们还表明，在一定的常数因子内的HZ均衡所能达到的最优社会福利（匹配的权重）的近似问题是NP困难的。
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 HZ scheme is PPAD-hard, and this holds even when $\epsilon$ 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.