论文标题
具有end赋的单方面匹配市场：均衡和算法
One-Sided Matching Markets with Endowments: Equilibria and Algorithms
论文作者
论文摘要
单方面匹配市场的经典Hylland-Zeckhauser方案的箭头 - debreu扩展（本文称为ADHZ）具有自然应用，但实例不承认Equilibria。通过引入近似值，我们定义了$ε$ - approximate ADHz模型，并给出以下结果。 *线性实用程序功能下的平衡存在。我们证明，平衡满足帕累托的最优性，近似嫉妒性和近似弱的核心稳定性。 *用于$ε$ - $ x型ADHz平衡的组合多项式时间算法，用于二分法，更普遍的双重价值实用程序。 * ADHz的实例，具有二分实用程序和紧密连接的需求图，该图不接受平衡。 由于计算HZ的平衡可能会高度棘手，并且由于很难将Hz扩展到更通用的效用函数，因此Hosseini和Vazirani提出的（丰富的）基于NASH-BARGAINGAING的匹配市场模型。对于其模型线性箭头纳什纳什（Nash Nash）的二分法实践案例（1LAD），我们提供了一个组合，强烈的多项式时间算法，并表明它承认了一个合理的convex程序。
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the $ε$-approximate ADHZ model, and we give the following results. * Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. * A combinatorial polynomial-time algorithm for an $ε$-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. Since computing an equilibrium for HZ is likely to be highly intractable and because of the difficulty of extending HZ to more general utility functions, Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based matching market models. For the dichotomous-utilities case of their model linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a combinatorial, strongly polynomial-time algorithm and show that it admits a rational convex program.
