Almost Envy-Freeness with General Valuations
Almost Envy-Freeness with General Valuations
复制标题
几乎没有嫉妒与一般估值
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Tim Roughgarden
中科院分区：
文献类型：
--
作者：
B. Plaut;Tim Roughgarden
公平分配的目标是以“公平”的方式在竞争者之间分配资源。无嫉妒是公平分配中研究最多的公平概念。对于不可分割的商品，无嫉妒分配并不总是存在，这激发了对无嫉妒的放松版本的研究。我们研究了羡慕自由到任何好（EFX）的属性，它指出，没有球员喜欢的束另一个球员以下删除任何单一的好，并证明了第一个一般性的结果关于这个属性。我们使用leximin解决方案，以显示存在的EFX分配在几个方面，有时与帕累托最优。对于两个估值服从温和假设的参与者，其中一个结果提供了比Spliddit（一个流行的公平划分网站）上当前部署的算法更强的保证。不幸的是，找到leximin解决方案可能需要指数时间。我们证明，这是必要的，通过证明一个指数下界的数量需要确定EFX分配的值查询，即使是两个球员具有相同的估值。我们考虑了加法和更一般的估值，我们的工作表明，在公平划分不可分割的商品与不同类别的球员估值方面，有丰富的问题需要探索。
The goal of fair division is to distribute resources among competing players in a "fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.