论文标题
与琐事的竞争平衡：组合算法和硬度
Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness
论文作者
论文摘要
我们研究了当试剂具有线性偏好时，发现具有琐事的竞争平衡（CE）的计算复杂性。 CE是在代理商中分配一组项目的最优选的机制之一。 CE具有相同的收入（CEEI），Fisher和Arrow-Debreu（交换）是研究分配问题的基本经济模型，其中CEEI是Fisher和Fisher的特殊情况，是交换的特殊情况。当物品是商品（提供实用程序）时，即使在交换模型中，CE集也是凸的，可以促进几种组合多项式时间算法（从Devanur，Papadimitriou，Saberi和Vazirani的开创性工作开始）。与之形成鲜明对比的是，当项目是杂务（给出无效）时，CE集已知是非凸的，即使在CEEI模型中也是断开连接的。此外，这些模型没有任何组合算法或硬度结果。在本文中，我们为CE提供了两个主要结果： 1）用于计算$（1- \ varepsilon）$的组合算法 - 时间$ \ tilde {\ Mathcal {o}}}（n^4m^2 / \ varepsilon^2）$，其中$ n $是$ n $ nas overs and $ m $。 2）在足够的条件下，在交换模型中找到$（1-1/\ mathit {poly}（n））$的ppad-hardgess。据我们所知，这些结果表明，当代理具有线性偏好时，CEEI和交换模型之间的第一个分离，假设PPAD $ \ neq $P。 最后，我们表明我们的新见解意味着在代理商构成双方偏爱时，在离散设置中，在离散设置中既无嫉妒的分配）的直接证明。
We study the computational complexity of finding a competitive equilibrium (CE) with chores when agents have linear preferences. CE is one of the most preferred mechanisms for allocating a set of items among agents. CE with equal incomes (CEEI), Fisher, and Arrow-Debreu (exchange) are the fundamental economic models to study allocation problems, where CEEI is a special case of Fisher and Fisher is a special case of exchange. When the items are goods (giving utility), the CE set is convex even in the exchange model, facilitating several combinatorial polynomial-time algorithms (starting with the seminal work of Devanur, Papadimitriou, Saberi and Vazirani) for all of these models. In sharp contrast, when the items are chores (giving disutility), the CE set is known to be non-convex and disconnected even in the CEEI model. Further, no combinatorial algorithms or hardness results are known for these models. In this paper, we give two main results for CE with chores: 1) A combinatorial algorithm to compute a $(1-\varepsilon)$-approximate CEEI in time $\tilde{\mathcal{O}}(n^4m^2 / \varepsilon^2)$, where $n$ is the number of agents and $m$ is the number of chores. 2) PPAD-hardness of finding a $(1-1/\mathit{poly}(n))$-approximate CE in the exchange model under a sufficient condition. To the best of our knowledge, these results show the first separation between the CEEI and exchange models when agents have linear preferences, assuming PPAD $\neq $ P. Finally, we show that our new insight implies a straightforward proof of the existence of an allocation that is both envy-free up to one chore (EF1) and Pareto optimal (PO) in the discrete setting when agents have factored bivalued preferences.
