On Truthful Mechanisms for Maximin Share Allocations
On Truthful Mechanisms for Maximin Share Allocations
复制标题
论最大最小份额分配的真实机制
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
E. Markakis
中科院分区：
文献类型：
--
作者：
Georgios Amanatidis;Georgios Birmpas;E. Markakis
本文研究了一类不可分项的公平分配问题，即最大最小份额分配的计算问题。给定一组n个玩家，如果一个玩家以她喜欢的任何方式将物品分成n个捆，然后得到她最不想要的捆，那么她能保证自己得到的最大最小份额就是最大最小份额。然后目标是找到一个分配，使每个玩家都能保证她的最大份额。以前的工作主要是研究这个问题的算法，提供常数因子近似算法。在这项工作中，我们走上了一个机制设计的方法，并调查真实的机制的存在。我们提出了三个模型的信息，该机制试图从球员，基数和序数表示的偏好的基础上引出。我们建立积极的和消极的（不可能）的结果，为每个模型，并强调了真实性的问题的近似性所施加的限制。最后，我们特别注意两个玩家的情况，这已经导致了具有挑战性的问题。
We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of $n$ players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem mostly algorithmically, providing constant factor approximation algorithms. In this work we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. Finally, we pay particular attention to the case of two players, which already leads to challenging questions.