论文标题
公平有效的分配而没有明显的操纵
Fair and Efficient Allocations Without Obvious Manipulations
论文作者
论文摘要
我们认为在具有添加估值功能的战略代理商中分配一组不可分割的商品的基本问题。众所周知，在没有货币转移的情况下，帕累托有效而真实的规则是独裁的，而没有确定性的真实机制可以将所有项目和嫉妒的繁琐分配到一项（EF1），即使是两个代理商也是如此。在本文中，我们调查了Troyan和Morrill最近提出的称为非显性可操作性的真实性（NOM）的真实性（NOM）的平心相互作用。我们表明，这种放松使我们能够以非常强烈的意义绕过上述负面结果。具体而言，我们证明存在明显无法操纵的确定性和EF1算法，以及最大化功利主义社会福利（代理商的实用性之和）的算法，这些算法是帕累托有效的，但不是独裁的，但显然不是$ n \ n \ egq 3 $ nipuls（但显然是$ nipuls）的（显然是$ n n = 2 $ n = $ n = 2 $ n = 2 $ n = 2 $ n = 2 $ n = 2 $ n = 2 $ n = 2.同时，对于任何数量的代理商和物品，都可以操纵平等的社会福利（最低限度的公用事业）或NASH社会福利（代理商公用事业的产物）。我们的主要结果是从设计EF1和NOM机制的问题到设计EF1算法的问题，将黑框减少了。在途中，我们证明了有关EF1分配的有趣结构结果，以及新的“最佳世界世界”的结果（对于没有激励措施的问题）可能会引起独立的兴趣。
We consider the fundamental problem of allocating a set of indivisible goods among strategic agents with additive valuation functions. It is well known that, in the absence of monetary transfers, Pareto efficient and truthful rules are dictatorial, while there is no deterministic truthful mechanism that allocates all items and achieves envy-freeness up to one item (EF1), even for the case of two agents. In this paper, we investigate the interplay of fairness and efficiency under a relaxation of truthfulness called non-obvious manipulability (NOM), recently proposed by Troyan and Morrill. We show that this relaxation allows us to bypass the aforementioned negative results in a very strong sense. Specifically, we prove that there are deterministic and EF1 algorithms that are not obviously manipulable, and the algorithm that maximizes utilitarian social welfare (the sum of agents' utilities), which is Pareto efficient but not dictatorial, is not obviously manipulable for $n \geq 3$ agents (but obviously manipulable for $n=2$ agents). At the same time, maximizing the egalitarian social welfare (the minimum of agents' utilities) or the Nash social welfare (the product of agents' utilities) is obviously manipulable for any number of agents and items. Our main result is an approximation preserving black-box reduction from the problem of designing EF1 and NOM mechanisms to the problem of designing EF1 algorithms. En route, we prove an interesting structural result about EF1 allocations, as well as new "best-of-both-worlds" results (for the problem without incentives), that might be of independent interest.
