不可分商品的最大纳什福利分配：公平性和经济效率的惊人解决方案

Nash福利最大化的不合理公平IOANNIS CARAGIANNIS，希腊帕特雷大学DAVID KUROKAWA，卡内基梅隆大学，美国英国格拉斯哥大学和俄罗斯圣彼得堡高等经济学院的埃尔文·穆林阿里尔·DPROCACCIA，卡内基梅隆大学，美国NISARG SHAH，多伦多大学，加拿大JUNXINGWANG，卡内基梅隆大学，美国最大纳什福利（MNW）的解决方案，它选择了一个分配，最大化的产品的效用，是众所周知的，以提供出色的公平保证分配时，可分割的商品。虽然它似乎失去了光泽时，适用于不可分割的商品，我们表明，事实上，MNW解决方案是惊人的公平，即使在这种设置。特别是，我们证明，它选择的分配是羡慕免费的一个很好的一个令人信服的概念，是相当难以捉摸的经济效率时，再加上。我们还建立了MNW解决方案提供了一个很好的近似另一个流行的（但可能不可行）公平性，最大份额保证，在理论上，甚至更是如此，在实践中。在寻找MNW解决方案的同时，是计算困难的，我们开发了一个非平凡的实现，并证明它的规模以及真实数据。这些结果使MNW成为分配不可分割商品的令人信服的解决方案，并支持其在流行的公平分配网站上的部署。CCS概念：·计算理论→数学机制设计;·应用计算→经济学;附加关键词和短语：公平分配，资源分配，纳什福利ACM参考格式：放大图片作者：Joannis Caragiannis，David Kurokawa，Hervé Moulin，Ariel D. Procaccia，NisargShah，and Junxing Wang. 2019. 最大纳什福利的不合理公平 ACM Trans. 经济Comput. 7，3，第12条（2019年9月），32页。https://doi.org/10.1145/3355902这篇文章的初步版本出现在第17届ACM经济学和计算会议的会议记录305这项工作得到了美国国家科学基金会的部分支持，基金IIS-1350598，CCF-1215883和CCF-1525932;斯隆研究奖学金; COST行动IC 1205“计算社会选择”;来自帕特雷大学的Caratheodory研究基金E.114;以及NSERC的发现资助计划。作者地址：I. Caragiannis，帕特雷大学，Panepistimioupoli Patron，帕特雷，265 04，希腊;电子邮件：caragian@ceid.upatras.gr; D.Kurokawa，A.D. Procaccia和J.王，卡内基梅隆大学，5000福布斯大道，匹兹堡，宾夕法尼亚州，15213;电子邮件：{dkurokaw，arielpro，junxingw}@cs.cmu.edu; H。Moulin，格拉斯哥大学，格拉斯哥大学Av- enue，G12 8 QQ，英国，圣彼得堡高等经济学院，16 Soyuza Pechatnikov St，St.Petersburg，190121，Russia; email：herve. glasgow.ac.uk; N.Shah，多伦多大学，10 King's College Rd，Toronto，ON，M5 G2 R3，Canada;电子邮件：nisarg@cs.toronto.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2019版权归所有者/作者所有。授权给ACM的出版权。2167-8375/2019/09-ART12 $15.00https://doi.org/10.1145/3355902ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月12十二：I. Caragiannis等人ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月..1介绍我们感兴趣的是公平分配不可分割的商品，如珠宝或艺术品的问题但为了更好地理解我们工作的背景，让我们从一个更简单的问题开始：公平分配可分商品。具体地说，假设有m个同质可分物品，n个参与者对这些物品有线性估值;也就是说，如果参与者i得到xi <$分数的物品<$，她的价值是vi（xi）=<$xi <$ vi（<$），其中vi（<$）是她对（整个）物品<$的非负值。当然，问题是每种商品分配给每个参与者的比例是多少;它有一个优雅的回答，四十多年前由瓦里安[41]给出在他的平等收入竞争均衡（CEEI）解决方案下，所有参与者都被赋予了平等的预算，比如每人1美元均衡是一个分配加上商品的（虚拟）价格，这样每个参与者都以给定的价格购买她最喜欢的一捆商品，市场出清（所有商品都被出售）。论证这个解决方案是公平的一个正式方法是通过令人信服的嫉妒自由度概念：每个参与者都弱地喜欢自己的包而不是任何其他参与者的包。CEEI显然满足了这一属性，因为每个玩家都可以买得起任何其他玩家的捆绑包，但却选择购买自己的捆绑包。虽然CEEI解决方案乍看起来在技术上似乎很难操作，但它总是存在的，事实上，在上述设置中具有非常简单的结构：CEEI分配（这是我们所关心的，因为价格是虚拟的）恰好与最大化纳什社会福利ivi（xi）的分配x重合[5，第2卷，第14章]。因此，CEEI分配可以通过Eisenberg和Gale [22]的凸程序在多项式时间内计算。现在让我们重新讨论我们最初的问题--在附加价值下分配不可分割的物品：一个参与者对她的一捆物品的效用仅仅是她对她所得到的单个物品的价值之和。这是一个不友好的世界，像嫉妒自由这样的核心公平概念无法得到保证（想想一个不可分割的好东西和两个玩家）。不用说，CEEI分配的存在不再有保证。尽管如此，最大化纳什社会福利（即效用的乘积）的想法本身似乎是自然的[19，37]。非正式地说，它在边沁的功利主义的社会福利概念（最大化效用总和）和罗尔斯的平等主义概念（最大化最小效用）之间找到了一个最佳点此外，这个解决方案是无标度的，在这个意义上，缩放玩家但是，当最大纳什福利解从可分商品世界中消失时，它似乎失去了效力。是吗我们在这篇文章中的目标是证明最大纳什福利（MNW）解决方案的我们希望让读者相信，. . . MNW解决方案展现了公平和效率特性的难以捉摸的组合它提供了迄今为止最实用的方法，可以说是最终的解决方案，为不可分割的货物下的附加估值的划分1.1现实世界的联系和影响我们对更公平算法的追求是计算公平除法实际应用中不断增长的工作的一部分[1，16，24，27，36]。我们对通过Spliddit（www.spliddit.org）产生现实世界的影响感到特别兴奋，Spliddit是一个非营利性的公平划分网站[25]。自2014年11月推出以来，该网站已吸引了超过9万用户。Spliddit的座右铭是可证明公平的解决方案，这意味着从网站的五个应用程序中获得的解决方案都这些属性被仔细地解释给用户，Nash福利最大化的不合理公平十二：ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月从而帮助用户理解为什么解决方案是公平的，它们将被采用（相比之下，试图解释算法本身将更加棘手）。Spliddit的五个应用程序之一是分配货物。在我们看来，这是Spliddit试图解决的最困难的问题，而之前的解决方案还有一些不足之处。这里是如何首先，为了表达他们的偏好，用户只需要在商品之间划分1K点。这个简单的启发过程依赖于附加偏好的假设，在我们看来，这就是为什么这个假设在实际应用中是不可或缺的。给定这些输入，该算法考虑三个公平水平：嫉妒自由度（上文解释），最大化（每个玩家获得所有商品价值的1 / n），以及最大化份额保证（例如，一个玩家可以获得一个至少m×X1的捆绑包， ... . ，Xnminjvi（Xj），其中X1，. . ，Xn是将货物分成n捆的部分该算法找到最高可行的公平级别，并且在此前提下，最大化功利主义的社会福利。重要的是，最小最大份额分配（给每个参与者最小最大份额保证）可能不存在，但（2/ 3）近似总是可行的;也就是说，每个参与者可以获得至少2/ 3的最小份额保证[36]。这使得Spliddit能够为不可分割的商品提供可证明的公平保证。也就是说，在实践中总是可以找到（完全）最小化份额分配[12，28]。虽然该算法通常提供了很好的解决方案，但它是高度不连续的，并且它直接依赖于最大最小份额-当嫉妒自由和比例无法获得时-有时会导致非直观的结果。例如，考虑一下Spliddit用户在2016年1月7日发送的电子邮件的摘录：“你好啊！ 伟大的应用程序：）我们是4兄弟，需要划分30+家具项目的继承. 这将节省我们的拳头打架;）我玩了演示应用程序，似乎有至少两种情况下，每个人都分配相同的价值到相同的商品非最佳结果。尝试3个人，5个商品，与每个人在每件商品上押200美元[3]一个人有三个人，每个人有一个人。他人“那怎么行用户问题的答案是，嫉妒自由和比例在例子中是不可行的在五个货物分成三个捆的每一个分区中，有一个捆最多有一个货物（价值200分），因此每个玩家的最小份额保证是200分。因此，给一个参与者三种物品，给其他参与者一种物品，确实使功利主义的社会福利最大化，但要保证每个参与者的最大份额请注意，在这个例子中，MNW解决方案产生直观的公平分配（两个玩家每人得到两个物品，一个玩家得到一个物品）。基于下面描述的结果，我们坚信MNW解决方案优于以前的分配货物的算法（以及我们知道的所有其他方法，如我们下面讨论的）。它自2016年5月24日起部署在Spliddit上。1.2我们的结果为了规避可能不存在的无嫉妒分配，我们考虑一个稍微放松的版本，嫉妒自由度高达一个好（EF1）[30]。在满足这个性质的分配中，参与者i可能会嫉妒参与者j，但这种嫉妒可以通过从参与者j的捆绑中移除一件物品来消除。我们表明，MNW的解决方案总是输出一个分配，是免费的一个很好的，以及帕累托最优的经济效率的一个著名的概念虽然在孤立的情况下，达到一种善的嫉妒自由度是很容易获得的，但将它与帕累托最优一起实现是具有挑战性的; MNW解决方案这样做的事实是对其有利的有力论据特别是，如第1.1节所述，在Spliddit上，能够解释十二：4I. Caragiannis等人ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月√−–NP用户了解每种方法的保证是什么;在我们看来，这两个属性特别引人注目，并且易于理解。作为MNW解公平性的另一个度量，我们研究了最大最小份额性质。如前所述，目前部署在Spliddit上的算法依赖于此属性的近似版本的存在[36]。考虑到这一点，我们表明，MNW解决方案总是保证每个n个球员的πn-分数，她的最大最小份额保证，其中πn=2/（1 +4 N3）。引人注目的是，这一比例非常接近。此外，我们还介绍了一部小说，同样有吸引力的变体，成对maximin份额，这是无法比拟的原始属性。利用前面的结果，我们证明了在MNW解下，每个局中人至少得到一个Φ-她的成对最大最小份额保证的分数，其中Φ=（Φ51）/ 20。618是黄金比例共轭，这个比例也很紧。实验提供了进一步的证据，的MNW解决方案：它提供了一个很好的近似MMS和成对MMS在实践中。在我们在Spliddit上记录的1281个真实世界的公平划分实例中，它分别在超过95%和90%的实例上实现了完全MMS和成对MMS，并且在任何实例上都不会差于3/已知计算MNW分配的问题是强相关的。 - 硬[33]。我们的主要贡献之一是我们设计的算法，用于计算Spliddit上引起的估值形式的MNW分配，其中要求玩家在可用商品中划分1K点我们的算法扩展性非常好，在不到30秒的时间内解决了50名球员和150件商品的相对较大的实例，而我们描述的其他候选算法甚至无法在两倍的时间内解决5名球员和15件商品的小实例1.3相关工作直到一个好的嫉妒自由度的概念起源于利普顿等人的工作。他们处理一般的组合估值，并给出了一个多项式时间算法，保证最大嫉妒是有界的最大边际值的任何球员为任何好;这一保证减少到EF 1的情况下添加剂的估值。然而，在加法的情况下，EF1可以通过简单地以循环方式将货物分配给玩家来实现，正如我们下面讨论的那样。Lipton等人的算法。[30]不保证额外的属性。Budish [16]引入了近似CEEI的概念，这是CEEI对不可分割商品设置的适应（在这篇美丽的论文中，他还引入了最小份额保证的概念他表明，一个近似的CEEI存在，并（approxi-100）保证某些性质.当物品的数量固定时，近似误差趋于零，而玩家的数量以及每种物品的复制数量则趋于无穷大。他的方法在MBA课程分配设置中是切实可行的，这激发了他的工作--学生多，每门课程的座位多，课程相对较少但它并没有为我们在Spliddit上遇到的实例类型提供有用的保证，在Spliddit上，玩家数量很少，并且通常每种物品都有一个副本纳什福利最大化在可分商品的情况下是很有吸引力的。瓦里安[41]指出，在一个与我们几乎相同的环境中，除了每种商品都是完全可分的，纳什福利最大化产生了一个CEEI分配，这意味着它是无嫉妒的和帕累托最优的。韦勒[42]将其推广到切蛋糕的环境[39]，在这种环境中，一种异质商品将被分割。对于蛋糕切割，Berliant et al.[8]通过证明纳什福利最大化满足“群体无嫉妒”来加强公平性保证人们对具有不可分割商品的纳什福利最大化的公理性质知之甚少。从算法的角度来看，Ramezani和Endriss [37]表明，Nash福利最大化的不合理公平十二：5ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月.∈NP−→∅∈M|M|{} NM联系我们在某些组合投标语言下（包括在加法估值下），福利是困难的。Cole和Gkatzelis [19]给出了在加法赋值下的多项式时间常数因子近似（准确地说，他们的目标函数是效用的几何平均值）。Anari等人。[4]和Cole等人。[18]提高了近似比，Anari等人。[3]提供了 更一般的分段线性凹估值的常数因子近似。Lee [29]表明这个问题是APX困难的;也就是说，常数因子近似是人们希望在多项式时间内实现的最佳近似。然而，一个常数因子近似不需要满足我们在本文中建立的MNW解决方案的任何理论保证。当只有两个参与者时，可以使用其他强制性的分配商品的方法。事实上，Spliddit曾经通过Adjusted Winner算法单独处理这种情况[15]。调整后的赢家的缺点是，除了在刀刃的情况下，它必须分裂一个两个玩家之间的货物。调整后的赢家可以解释为一个特殊的情况下， Pazner和Schmeidler的平等主义等价规则[35]，它定义为任何数量的玩家对于n> 2个参与者，可能需要拆分到n1货物（或所有货物，如果mn）;因此，<将其适用于不可分割货物是不切实际的。让我们简单地提一下分割不可分割财货的另外两种模式。首先，一些论文假设参与者表达顺序偏好（即，[ 6][11][13][14]。这个假设（可以说）不会导致明确的公平分配目标通常是设计计算公平分配的算法（如果存在的话）。其次，可以允许随机分配[9，10，17];这几乎不适合我们在Spliddit上发现的结果只使用一次的情况。我们还注意到，在建立在本文会议版本基础上的工作中，Conitzer等人。[20]研究了一个比我们不可分割的商品分配设置更一般的公共决策设置，并建立了MNW分配的有吸引力的属性（尽管比我们弱）。最后，值得注意的是，纳什[32]在他的经典谈判问题的背景下研究了效用乘积最大化的思想这就是为什么这个社会福利的概念是以他的名字命名的。在网络社区中，同样的解决方案被称为比例公平，这是因为当商品可分时，它满足另一个属性[26]： 相对于任何其他分配，效用增加的参与者的总收益百分比最多等于效用减少的参与者的总损失百分比;因此，在某种意义上，没有这样的转换是社会优选的。2模型令[k]1、...，k.让=[n]表示参与者的集合，并且表示该套货物，m=0。在整个文章中，我们假设货物是不可分割的（即，每个物品必须完全分配给一个玩家），但是我们的方法及其保证无缝地扩展到某些物品是可分的情况（见第6节）。每个参与者i被赋予一个估值函数v i：R0使得v i（）= 0。与除了第3.1节之外，在本文中，我们假设玩家S，v i（S）=<$Svi（<$）.为了简化符号，我们将好的<$i写成v i（<$）而不是v i（<$）。.在关于公平分配的文献中，附加估值的假设很常见，不可分割的货物的阳离子[12，36]。此外，在实践中，引出更一般的组合偏好通常是困难的，这就是为什么，据我们所知，所有用于不可分割商品的公平分配方法的部署实现-包括调整后的赢家[15]和Spliddit上实现的算法（见第1.1节）-也依赖于加法估值。也就是说，我们的主要结果（定理3.2）推广到更有表现力的子模赋值（见3.1节）。考虑到球员的估值，我们有兴趣找到一个可行的分配。对于一个商品集S<$M，k∈N，令<$k（S）表示S到k个丛的有序划分集。一十二：6I. Caragiannis等人ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月∈M∈N∈M∈M∈∈M∈M可行分配A=（A1，.，A n）1999年，）是分配给每个参与者i的货物子集A i的货物划分。在这种分配下，参与人i的效用是vi（Ai）（她得到的一组物品的价值）。我们的目标是公平分配。公平分配的文献通常采用公理化的方法来定义公平;最令人信服的定义是无嫉妒。定义2.1（EF：无嫉妒）。一个分配An（）被称为无嫉妒，如果对于所有参与者i，j，我们有vi（Ai）vi（Aj）.也就是说，每个参与者对自己的捆绑包的重视程度至少与对其他参与者的捆绑包的重视程度一样一般来说，嫉妒的自由性是不能保证的;例如，将一个不可分割的物品分配给两个积极评价它的参与者将不可避免地导致嫉妒。事实上，计算上很难确定是否存在EF分配[21]。为了保证存在性，需要一个更弱的定义;下面的定义是一个相当小的松弛，当货物的数量大于参与者的数量时仍然很有趣定义2.2（EF1：羡慕自由度高达一个好）。一个分配A n（）被称为在一个商品（EF1）内无嫉妒，如果1n∈N， n ∈Aj，vi（Ai）v i（A j\{д}）.换句话说，我可能嫉妒j，但这种嫉妒可以通过从j的捆绑中移除一个单独的好来消除。更一般地说，人们可以将嫉妒自由度定义为每k个k个商品N可正如我们在这篇文章中所展示的，EF1总是可以与其他期望的属性一起得到保证，从而消除了进一步放宽要求的需要。另一种对嫉妒自由的放松被称为最小份额保证[16]。这是一个自然的延伸2球员切割和选择的想法的情况下，n个球员。非正式地说，参与者的最大最小份额保证是如果她被允许将商品集分成n个捆绑包，但然后最后选择一个捆绑包（因此，可能最终得到她的最小值捆绑包），她可以获得的价值。定义2.3（MMS：Maximin Share）。参与者i的最小份额（MMS）保证由下式给出：MMSi=maxmin v i（A k）。A∈<$n（M）k∈[n]我们说A是α-MMS分配，如果对所有局中人i∈N，vi（Ai）α·MMSi.注意，原则上，MMSi取决于vi和n;这些参数不是符号的一部分，因为它们将始终从上下文中清楚虽然不可能保证所有参与者都有完整的最大最小值份额[28，36]，但（2/3+O（ 1/n））-MMS分配总是存在[36]，并且可以在多项式时间内计算[2]。我们使用EF1和MMS保证的近似值作为公平性的衡量标准此外，我们还希望我们的解决方案具有经济效益。[2]为此，我们使用了帕累托最优（Pareto optimality）这一不受限制的概念。定义2.4（PO：帕累托最优）。一个分配A jn（）称为帕累托最优，如果没有任何替代分配AJn（）可以使一些参与者严格更好，而不会使任何参与者严格更差。形式上，我们要求<$AJ∈<$n（M），.当vi（AiJ）> vi（Ai）时，则v i ∈N.<$j∈N，vj（AJj）0|不|;//一个最大的玩家集合，可以//同时给定一个正效用2 A← arg max AS（）i∈Svi（Ai）;//S中参与者的MNW分配3AiMNW<$Ai，i∈S;4AMNW<$，i∈N\S;//N\S中的玩家没有收到任何物品S，我们的结果保持独立的平局打破），（ii）找到一个分配的商品的球员在S，最大限度地提高他们的产品的效用。算法1中正式描述了MNW解决方案。我们说，分配是一个最大纳什福利（MNW）分配，如果它可以选择的MNW解决方案。我们现在准备陈述我们的第一个结果，它相对简单，但我们认为，特别引人注目。第3.2节.每一个MNW分配是无羡慕的一个好（EF1）和帕累托最优（PO）的不可分割的商品加性估值。P屋顶。令A表示MNW分配。首先，我们假设NW（A）>0。A的帕累托最优性是平凡的，因为另一种分配增加了一些参与者的效用，而没有减少任何参与者的效用，这将增加纳什福利，这与A下的纳什福利最优性相矛盾。为了避免矛盾，假设A不是EF1，即使从参与人j的捆绑中拿走了任何一件物品，参与人i仍然嫉妒参与人j设<$i=arg min<$A，v（<$）>0vj（<$）/vi（<$）.注意，<$i的定义是很好的，因为参与人i嫉妒参与人j意味着参与人i在Aj中至少有一个物品的价值为正值。设AJ表示在A中将<$i从参与者j移动到参与者i所获得的分配。我们现在证明了NW（AJ）>NW（A），这给出了期望的矛盾，因为纳什福利在A下是最优的。具体地说，我们证明了NW（AJ）/NW（A）>1。该比率是很好定义的，因为我们假设NW（A）>0。注意，对于所有k i，j，vk（AJ）=vk（Ak），vi（AiJ）=vi（Ai）+vi（Aj），并且vj（AJj）=vj（Aj）vj（д）.因此，我们认为，NW（AJ）> 1惠1−vj（<$）·1+vi（<$）> 1惠vj（<$）·.v（A）+v（<$）.0的证明中，我们已经知道S中的参与者之间没有嫉妒，因为A是这些参与者的MNW分配，并且在A下，产品S中参与人的效用是正的。此外，因为S中的参与者没有得到任何物品，我们只需要证明参与者i S不羡慕参与者j S得到一件物品。想对于她所做的矛盾。选择<$jAj使得vj（<$j）>0。这样一种商品存在，因为我们知道vj（Aj）>0。因为参与人i羡慕参与人j的最多一个好处，所以我们有vi（Aj<$j）>vi（Ai）=0. 因此，存在一个好的<$iAj<$j使得vi（<$i）>0。但是，在这种情况下，从参与人j到参与人i的<$i为参与人i提供正效用，同时保留对参与人j的正效用（因为参与人j在vj（<$j）>0时仍然具有好<$j这与S是一个可以提供正效用的最大参与者集合的事实相因此，MNW分配A是EF1和PO两者。□3.1一般估值在此，我们重点讨论了附加估值的情况。正如我们前面所讨论的，这种情况在实践中至关重要。但无论如何，理解这些保证是否延伸到更大类别的组合估值是有理论意义的。具体地说，定理3.2指出，MNW保证EF1和PO下的加法估值。我们问EF1和PO是否可以同 时 实 现 的 任 何 算 法 ， 不 一 定 MNW 下 ， subadditive ， superadditive ， submodular（subadditive的特殊情况），supermodular（superadditive的特殊情况）的估值。附录C给出了这些赋值类的定义以及本节所有结果的证明。不幸的是，我们得到一个否定的结果为三个四个估值类。第3.3节. 对于不可分商品的次可加性和超模（因此也是超可加性）估价类，存在不允许在一种商品和帕累托最优条件下无嫉妒的分配的实例。我们不能解决这个问题的类的子模赋值。虽然存在子模赋值的例子（参见，例如，例C.3）中没有MNW分配满足EF1，我们可以证明每个MNW分配满足EF1和PO的松弛。定义3.4（MEF1：边际嫉妒自由度高达一个好）。 我们说分配A ∈n（M）满足MEF 1，如果i，j ∈ N，在比较MEF 1的定义和EF 1的定义时，我们可以看到，在右侧，v i（A j即，参与人i对Aj的价值 用v i（A i）代替一个j（д）v i（A i），是参与人i对A j的边际价值 д 假设参与者i已经被分配了Ai。对于子模赋值，MEF1严格弱于EF1，而对于加法赋值，MEF1与EF1一致。因此，定理3.2直接由下一个结果得出（尽管我们对定理3.2的直接证明更简单）。第3.5章.每一个MNW分配满足边际嫉妒自由到一个好的（MEF1）和帕累托最优（PO）的子模块估值不可分割的商品。十二：I. Caragiannis等人ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月∈∈N \{}∈∈N∗⎪v(д)i4最大NASH福利大约是MMS在这一节中，我们表明，MNW解决方案的公平性延伸到另一种放松嫉妒自由度的最小份额保证，以及其变体在理论和实践中。4.1理论上的近似MMS从技术的观点来看，我们最复杂的结果是下面的定理。第4.1章.每个MNW分配是πn-最小份额（MMS），用于不可分割商品的附加估值，其中2πn =1 + π4 n − 3。此外，因子π n是紧的，即，对于每个nN和n>0，存在具有n个具有加性估值的参与者的实例，其中没有MNW分配是（π n+ n）-MMS。在我们提供证明之前，让我们回忆一下MMS的最著名的近似-到目前为止-是2/ 3+O（ 1/n） [36]，其中n=3的界限是3/ 4。但唯一已知的方法来实现一个良好的界限是建立周围的MMS近似目标的算法[2，36]。相比之下，MNW解决方案“有机地”实现其πn=Θ（1/πn）比几个有吸引力的属性。此外，在几乎所有现实世界的情况下，玩家的数量n是相当小的。例如，在Spliddit上，玩家的平均数量非常接近3，我们的最坏情况近似保证是π3=1/ 2-定性地类似于3/ 4。也就是说，在真实世界的实例中实现的近似比要好得多（见第4.3节）。THEOREM 4.1的 P屋顶我们首先证明了MNW分配是πn-MMS（下界），然后证明了近似比πn（上界）的紧性。下界的证明：设A是MNW分配。与定理3.2的证明一样，我们首先假设NW（A）>0，然后处理NW（A）=0的情况。修复播放器i.对于一个球员j i，设<$j=arg max<$Ajvi（<$）表示参与人j我们需要建立一个重要的引理。4.2. blog 它认为vi（Aj\{<$j}）≤min⎧⎪⎨⎪vi(Ai), （vi（Ai））J其中，如果vi（дj）=0，则RHS被定义为vi（A i）。⎭P屋顶。 首先，vi（Aj\{<$j}）≤vi（Ai）直接从A是MNW分配的事实得出因此是EF1（定理3.2）。如果vi（<$j<$）=0，则我们完成。假设vi（<$j）>0。根据MNW分配的定义，将商品从参与人j转移到参与人i不应该增加纳什福利。因此，在本发明中，v（ A） {}）·v（A\ {}）≤v（A）·v（A））v（A）−vi（Ai）·vj（Aj）。（四）i ijj jjii jjjjjjvi（Ai<${<$j<$}）注意，上面表达式中的RHS是正的，因为vi（<$j）>0。因此，我们也有vj（<$j<$）>0。类似地，将Aj中除<$j<$以外的所有物品从参与人j转移到参与人i也不会增加纳什福利。因此，我们认为，v i（A i<$A j\{<$j<$}）·v j（<$j<$）≤ v i（A i）·v j（A j）。、Nash福利最大化的不合理公平十二：ACM Transactions on Economics and Computation，卷。号73.第12条。出版日期：2019年9月- -一种||- -一种||{∈ N}}XJ.⎪−（）k∈∈⎧⎪n−.1I[x>β]如果0≤xk<1，我们的结论是v（ A） \ {де}）≤vi（Ai）·vj（Aj）−v（A）≤v i（A i）·v j（A j）−v（A）我我i jjvj（<$j<$）v（A）−vi（Ai）·vj（Aj）J J⎡⎢1⎤⎥vi（Ai<${<$j<$}）⎡⎢vi(Ai∪{дj∗})（vi（Ai））2=v i（A i）·1 −vi（Ai）−1=vi（Ai）·vi（<$） −1<$= vi（д），⎣⎢vi(Ai∪{дj∗})⎥⎦吉吉其中，第二转变由等式（4）得出。（引理4.2的证明）现在，让我们为玩家i找到MMS保证的上限。回想一下，MMSi是参与者i可以保证自己的最大价值，如果她将商品集分成n个捆绑包，但收到她的最小价值捆绑包。关键的直觉是，货物的不可分割性只限制了玩家可以创建的分区。也就是说，如果一些商品变得可分割，它只能增加玩家的MMS保证，因为她仍然可以创建所有的捆绑包，她可以与不可分割的商品。设T=<$j<$：j i，vi（<$j<$）>MMSi中除货物外的所有货物都是可分的.很容易看出，在下面的分区中，参与者i把T中的每一件商品（全部）放在它自己的一捆中，把剩下的商品分成n个T捆，每个捆的价值与参与人i相等。因为后n个T中的每一个 bundle必须至少具有MMSi的值，对于播放器i，我们得到MMS ≤vi（Ai）+.j∈Ni.vi（<$j）·I..vi（<$j<$）≤MMSi..+vi（Aj\{<$j}），（5）in−。v（正常）>MMS其中r e I（·）表示指示函数。j∈NiJI∗接下来，我们使用来自引理4.2的vi（Aj\{<$j}）的上界，并将等式（5）的两边除以vi（Ai）。为了简单起见，让我们表示xj=vi（<$j）/vi（Ai），并且β=MMSi/vi（Ai）。注意，β是我们感兴趣的MMS近似上的界的倒数。然后，我们得到1+。j∈Ni.xj·I[xj≤β]+min.1，1个月.n−。j∈NiI[xj>β]设f（x;β）表示上述不等式的RHS。 然后，我们可以写β≤f（x;β）≤ maxxf（x;β）。注意，如果β≤1，则参与者i已经收到了她的全部最大最小份额值，这给出了（比）期望的MMS近似。因此，我们假设β>1。到求f（x;β）在