On the Proximity of Markets with Integral Equilibria
On the Proximity of Markets with Integral Equilibria
复制标题
论具有整体均衡的市场的邻近性
DOI：
10.1609/aaai.v33i01.33011748
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sanath Kumar Krishnamurthy
中科院分区：
文献类型：
--
作者：
Siddharth Barman;Sanath Kumar Krishnamurthy
我们研究了费雪市场，承认均衡，其中每一个良好的整体分配给一些代理。虽然强存在性和计算保证是已知的Fisher市场的均衡与附加估值（艾森伯格和盖尔1959; Orlin 2010），这样的均衡，在一般情况下，分配商品分数代理。因此，费雪市场并不直接适用于不可分割的商品。在这项工作中，我们表明，人们总是可以绕过这一障碍，并在代理人的预算有界变化，获得市场，承认一个完整的均衡。我们把这样的市场称为纯市场，并表明，对于任何给定的费雪市场（与添加剂估值），可以有效地计算一个“附近的”，纯市场伴随着一个完整的equilibrium.Our纯市场的工作导致新的算法结果公平分割不可分割的商品。先前在离散公平分配方面的工作表明，在加法估值下，总是存在同时实现公平和效率这两个看似不相容的属性的分配（Caragiannis et al. 2016）;这里的公平是指一种商品（EF 1）的无嫉妒性，而效率对应于帕累托效率。然而，多项式时间算法是不知道找到这样的分配。考虑放宽比例和EF 1，分别作为我们的公平性的概念，我们表明，公平和帕累托有效的分配可以计算在强多项式时间。
We study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with additive valuations (Eisenberg and Gale 1959; Orlin 2010), such equilibria, in general, assign goods fractionally to agents. Hence, Fisher markets are not directly applicable in the context of indivisible goods. In this work we show that one can always bypass this hurdle and, up to a bounded change in agents’ budgets, obtain markets that admit an integral equilibrium. We refer to such markets as pure markets and show that, for any given Fisher market (with additive valuations), one can efficiently compute a “near-by,” pure market with an accompanying integral equilibrium.Our work on pure markets leads to novel algorithmic results for fair division of indivisible goods. Prior work in discrete fair division has shown that, under additive valuations, there always exist allocations that simultaneously achieve the seemingly incompatible properties of fairness and efficiency (Caragiannis et al. 2016); here fairness refers to envyfreeness up to one good (EF1) and efficiency corresponds to Pareto efficiency. However, polynomial-time algorithms are not known for finding such allocations. Considering relaxations of proportionality and EF1, respectively, as our notions of fairness, we show that fair and Pareto efficient allocations can be computed in strongly polynomial time.