The Unreasonable Fairness of Maximum Nash Welfare
The Unreasonable Fairness of Maximum Nash Welfare
复制标题
DOI：
10.1145/2940716.2940726
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
I. Caragiannis;David Kurokawa;H. Moulin;Ariel D. Procaccia;Nisarg Shah;Junxing Wang
中科院分区：
文献类型：
--
作者：
I. Caragiannis;David Kurokawa;H. Moulin;Ariel D. Procaccia;Nisarg Shah;Junxing Wang
最大纳什福利(MNW)解决方案-它选择了使公用事业乘积最大化的分配--众所周知，它在分配可分割商品时提供了突出的公平保证。尽管当它应用于不可分割的商品时，它似乎失去了光泽，但我们表明，事实上，即使在这种情况下，MNW解决方案也出人意料地公平。特别是，我们证明，它选择了令人羡慕的分配，最多只有一个好处-一个令人信服的概念，当与经济效率结合在一起时，它是相当难以捉摸的。我们还证明，MNW解决方案在理论上和-甚至在实践中-提供了与另一种流行的(但可能不可行的)公平性质--最大限度份额担保--的良好近似。虽然寻找MNW解决方案在计算上很困难，但我们开发了一个不平凡的实现，并证明了它在真实数据上具有很好的伸缩性。这些结果使我们相信，MNW是分配不可分割的商品的最终解决方案，并将其部署在一个广受欢迎的公平分工网站上。
The maximum Nash welfare (MNW) solution --- which selects an allocation that maximizes the product of utilities --- is known to provide outstanding fairness guarantees when allocating divisible goods. And while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is unexpectedly, strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy free up to one good --- a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and --- even more so --- in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation, and demonstrate that it scales well on real data. These results lead us to believe that MNW is the ultimate solution for allocating indivisible goods, and underlie its deployment on a popular fair division website.