论文标题
单方面匹配市场的Hylland-Zeckhauser方案的计算复杂性
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
论文作者
论文摘要
1979年，Hylland和Zeckhauser \ Cite {Hylland}提供了一种简单而通用的计划，以使用定价机制的力量实施单方面的匹配市场。他们的方法具有不错的属性 - 它在大型中兼容并产生帕累托最佳的分配 - 因此，它为运行涉及这种市场的应用程序提供了一种有吸引力的，现成的方法。随着匹配的市场变得越来越普遍和有影响力，必须最终解决该计划的计算复杂性。 我们提出以下部分解决方案： 1。专用案例$ 0/1 $实用程序的组合，强烈的多项式时间算法。 2。一个仅具有非理性平衡的示例，因此证明了这个问题不在PPAD中。此外，它的平衡是断开连接的，因此表明该问题不承认凸编程公式。 3。在类FixP中，问题的成员资格证明。 我们打开（难以确定问题是否是解决问题的问题）。当实用程序在集合$ \ {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.
