Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
复制标题
DOI：
10.4230/lipics.itcs.2021.59
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
V. Vazirani;M. Yannakakis
中科院分区：
文献类型：
--
作者：
V. Vazirani;M. Yannakakis
1979年，Hylland和Zeckhauser给出了一个简单而通用的方案，利用定价机制的力量来实现单边匹配市场。他们的方法具有很好的特性--它在很大程度上是激励相容的，并且产生帕累托最优的分配--因此它提供了一种有吸引力的现成方法来运行涉及这样一个市场的应用程序。随着匹配市场变得越来越普遍和有影响力，必须最终解决该方案的计算复杂性。我们提出以下部分决议：1。一个组合的，强多项式时间算法的特殊情况下的$0/1$公用事业。2.一个例子，只有非理性均衡，从而证明这个问题是不是在PPAD。此外，它的平衡点是不连通的，因此表明该问题不允许凸规划公式。3.证明问题属于FIXP类。我们留下了一个（困难的）问题，即确定问题是否是FIX困难的。当实用程序在集合$\{0，{\frac 1 2}，1 \}$中时，解决特殊情况的状态似乎更加困难。
In 1979, Hylland and Zeckhauser \cite{hylland} gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties -- it is incentive compatible in the large and produces an allocation that is Pareto optimal -- and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalant and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1. A combinatorial, strongly polynomial time algorithm for the special case of $0/1$ utilities. 2. An example that has only irrational equilibria, hence proving that this problem is not in PPAD. Furthermore, its equilibria are disconnected, hence showing that the problem does not admit a convex programming formulation. 3. A proof of membership of the problem in the class FIXP. We leave open the (difficult) question of determining if the problem is FIXP-hard. Settling the status of the special case when utilities are in the set $\{0, {\frac 1 2}, 1 \}$ appears to be even more difficult.