Mechanism design for fair division: allocating divisible items without payments
Mechanism design for fair division: allocating divisible items without payments
复制标题
公平分配的机制设计：无需支付即可分配可分割的物品
DOI：
10.1145/2482540.2482582
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
G. Goel
中科院分区：
文献类型：
--
作者：
R. Cole;Vasilis Gkatzelis;G. Goel
我们从机制设计的角度重新审视了公平划分的经典问题，并提供了一种优雅的真实机制，可以为广泛使用的比例公平解决方案提供令人惊讶的近似值。众所周知，我们无法以真正的方式实施，这是减轻此问题的主要缺点，我们提出了一种新的机制我们称局部分配机制，该机制丢弃了分配的资源的精心选择的部分，以激励代理商在报告其价值时是真实的。 。
对于具有任意数量的代理和项目的多维域，对于非常大的均匀价值函数，我们证明我们的机制为每个代理提供至少1/e≈0.368的0.368比例公允价值的分数。据我们所知，这是给每个代理的近似近似值的结果，以完成该结果。机理可以保证超过0.5的近似值，即使对于添加的线性值的限制类别，我们也可以发现部分分配机制和基于VCG的机制设计之间的联系。
我们还询问在更受限制的设置中是否可以使用更好的近似值。高度要求。
We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option.
For a multi-dimensional domain with an arbitrary number of agents and items, and for the very large class of homogeneous valuation functions, we prove that our mechanism provides every agent with at least a 1/e ≈ 0.368 fraction of her Proportionally Fair valuation. To the best of our knowledge, this is the first result that gives a constant factor approximation to every agent for the Proportionally Fair solution. To complement this result, we show that no truthful mechanism can guarantee more than 0.5 approximation, even for the restricted class of additive linear valuations. In addition to this, we uncover a connection between the Partial Allocation mechanism and VCG-based mechanism design.
We also ask whether better approximation ratios are possible in more restricted settings. In particular, motivated by the massive privatization auction in the Czech republic in the early 90s we provide another mechanism for additive linear valuations that works really well when all the items are highly demanded.