一个CM通信
研究突出了
一种有界无嫉妒切饼算法
来源:盖蒂图片社
我们考虑研究得很好的切蛋糕问题，其目标是根据来自代理的查询找到一个可分割资源的无嫉妒分配。这个问题在数学、经济学和计算机科学领域都得到了关注。是否存在离散有界无嫉妒协议一直是一个重大的开放问题。我们报告了解决开放问题的算法。
1.简介
切蛋糕问题是一个基本的数学问题，其中“蛋糕”是一个用单位区间[0,1]表示的异质可分资源的隐喻。4资源可以表示时间、土地或某些计算资源。目标是把蛋糕分配给n被称为“代理”的实体。每个代理的分配由一组子区间组成。假设每个代理在区间的各个区段上具有可加的和非负的值。蛋糕切割算法/协议与代理交互，以确定一个公平的分配。
公平最重要的标准之一是envy-freeness。一个代理人会嫉妒另一个代理人，如果她宁愿得到另一个人的作品而不是自己的。一个切蛋糕的协议/算法被称为envy-free如果每个经纪人在报告自己的真实估值时都保证不会嫉妒。如果一个协议是无嫉妒的，那么一个诚实的代理将不会嫉妒，即使其他代理错误地报告了他们的估值。
协议与代理的交互使用两种类型的查询EVALUATE和CUT。EVALUATE询问代理我报告两点之间子区间的值x而且y。CUT问一个特工我选择一个点y使一个给定的间隔x而且y值一个给定的值吗t。这种自然查询模型是由罗伯逊和韦伯推广的。8
一个没有嫉妒的协议是什么样子的?最著名的无嫉妒切蛋糕协议可能就是最好的例证。这是切选协议两个代理。其中一名特工被要求将蛋糕分成两份。另一个代理被要求挑选她最喜欢的一块，而切割者得到剩下的一块。该协议在<一个href="https://dl.acm.org/cms/attachment/94db66ae-e273-4806-b45b-a49a1ea22c72/f1.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=680,height=329'); return false;">图1．它的正式指定为<一个href="https://dl.acm.org/cms/attachment/47d6f5fa-55f5-41b9-b15f-12b9a8775a63/uf1.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=485,height=221'); return false;">算法1．为了一块蛋糕D(这只是蛋糕的一个子集)，我们写道V我（D)表示代理我这幅画的价值D。切割和选择协议是无嫉妒的证明如下。代理人1得到了一个同样喜欢的棋子，所以她不嫉妒。特工2得到了她喜欢的那块，至少和另一块一样，所以她也不嫉妒。
图1。切割和选择协议。
算法1。切割和选择协议。
是否存在一个切蛋糕算法，它对3个、4个或更多数量的代理是无嫉妒的?在过去的几十年里，这个问题一直是激烈研究的主题。它可以追溯到数学家雨果·施泰因豪斯的工作，他在20世纪40年代提出了切蛋糕的问题。8，<一个href="#R9">9要了解切蛋糕问题的历史，我们可以参考Procaccia的ACM论文通讯7布拉姆斯和泰勒的畅销书。4在三特工的情况下，约翰·l·塞尔弗里奇和约翰·h·康威在1960年左右独立发现了一种优雅的方案。在我们的工作之前，Brams和Taylor提出了一种通用的无嫉妒切饼算法，使用有限数量的步骤和切块。3.但是，它可能需要任意多的步骤，即使是四个代理。这就引出了一个问题:是否存在一个有界的无嫉妒算法。换句话说，是否存在一个无嫉妒的算法它的步数有一个可证明的界限它只依赖于的函数n(代理人数)?
在本文中，我们报道了第一个有界和无嫉妒切饼算法。1，<一个href="#R2">2接下来，我们介绍了通用算法背后的思想。
2.协议概述
在较高的级别上，我们的协议(称为主协议)以无嫉妒的方式分配足够大的蛋糕部分。然后，它尝试以结构化的、无嫉妒的方式将未分配蛋糕的一小部分添加到已分配的部分，目标是将问题减少到对少量代理无嫉妒的分配。在整个协议中，有一个蛋糕的部分分配，保持它是没有嫉妒的。我们所说的部分是指整个蛋糕可能没有分配到。
主协议调用其他协议(特别是核心协议、差异协议和GoLeft协议)，以找到一个无嫉妒的分配。核心协议用于获得无嫉妒的部分分配。主协议对未分配的饼多次应用它，使未分配的饼越来越小。
在找到一个足够大的没有嫉妒的部分分配后，主协议使用两种可能的方法将我们的问题分解为一个涉及较少代理的问题。第一种情况是，当我们发现一些代理主要对未分配蛋糕的一部分感兴趣，而其他代理主要对剩余的部分感兴趣。这种代理估值上的差异被差异协议所利用。如果没有出现第一种情况，我们使用GoLeft协议来交换代理的子分配，以使一组代理能够“主宰”另一个代理。主导代理认为他们不会嫉妒被主导代理，即使其中一个被主导代理得到所有未分配的蛋糕。在这种情况下，我们将问题简化为涉及剩余蛋糕和占主导的代理的问题。统治是我们的协议所基于的关键思想，它帮助我们将问题减少到更小的问题。看到<一个href="https://dl.acm.org/cms/attachment/2d9539e4-bd53-4146-b97a-90ae8b84f9d4/f2.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=734,height=393'); return false;">图2浏览主协议概述。
图2。鸟瞰我们的协议。
图3提出了一个可实现的步骤序列，捕获了我们协议的一些关键思想。
图3。协议的一些思想的说明。终端状态是6英尺和10英尺。
3.协议:更多细节
在本节中，我们将详细介绍主协议的每个组件。
3.1.核心协议
我们协议的一个关键构建块是核心协议，它找到了一个没有嫉妒的部分分配。
核心协议要求n代理——切蛋糕的人——把蛋糕分成n同样喜欢。回想一下，这个步骤类似于Cut and Choose协议的第一个步骤。然后，它找到一个可能的部分分配，其中每个代理的分配是一块连续的蛋糕。每个代理接收由“切割机”定义的一块。代理商可以得到修剪后的碎片。我们保证切割者和至少一个其他代理获得完整的一块，没有代理羡慕其他代理。分配的另一个特点是，对于每一个部分分配的棋子，它被切掉的确切点对应于另一个代理的标记，以确保她不嫉妒那个棋子。当我们第一次设计核心协议时，它被设计为建立满足上面讨论的属性的分配的存在性。一旦建立了这样的分配，就有一种更简单的方法来定义实现这种分配的协议。简化版本的总体思路在一篇有趣而详细的后续论文中得到了明确阐述，该论文解决了家务或烧焦蛋糕情况下的姐妹问题(代理有非正估值)。5在此，我们提出核心协议的简化版本(<一个href="https://dl.acm.org/cms/attachment/0ea2ae50-084e-4bc9-bf7e-b89fe8d0c7c4/uf2.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=484,height=466'); return false;">算法2)切蛋糕。协议要求最多(n！)2n查询。
算法2。(简化的)核心协议。
在核心协议中，切割代理得到一整块。另一名特工也得到了一份。所以从切割者的角度来看，至少是2/n通过核心协议的一次调用来分配。同样地，切割者认为她剩余蛋糕的价值不超过(n- 2) /n整块蛋糕的价值。
如果我们每次都用不同的切割器调用核心协议来进一步分配未分配的蛋糕，我们只需要n调用核心协议，以获得一个无嫉妒的部分分配，同时满足比例性(给每个代理值至少1/n整个蛋糕)。<一个href="https://dl.acm.org/cms/attachment/5a4864bd-b42a-452e-8fd7-e1e351650a39/uf3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=486,height=179'); return false;">算法3这是真的吗n！2n2Queries找到一个满足无嫉妒性和比例性(两个最重要的公平性概念)的部分分配。一个本文的其余部分描述了当我们确实想要分配整个蛋糕时应该做什么。
算法3。一个没有嫉妒和比例的协议。
3.2.统治和显著优势
由于核心协议本身没有足够的能力在有限的时间内分配所有的蛋糕，我们依靠的是统治我们的目标是将我们的问题分解成一个涉及较少代理的问题。在本节中，我们表示代理我的分配,X我．
回想一下，在没有嫉妒的分配中，每个代理人我认为自己比其他代理人有优势(即使是零优势)j：
统治是优势的一种极端形式。一个代理我主宰另一个代理j如果她不羡慕j即使没有分配的蛋糕R给j：
使用其他协议时铭记以下目标:找到一组代理一个⊂N这样，每个代理人都在N \中的控制每个代理一个。以保证每个代理在某一集合N \中的控制每个代理一个，它需要改变代理的当前分配以及未分配的蛋糕。在进行这些更改时，我们要确保当前的部分分配不会令人羡慕。通过识别这样一个集合N \，我们将这个问题简化为为更少的代理进行无羡慕的分配。的代理N \不羡慕没有分配的蛋糕分配给代理人吗一个。这一关键思想在<一个href="https://dl.acm.org/cms/attachment/a92d53d1-f2c1-425d-861e-92b62aab5e84/f4.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=419,height=419'); return false;">图4．
图4。在图中，如果一个代理控制了另一个代理，则一个代理会指向另一个代理。假设我们在四个代理中找到一个无嫉妒的部分分配，使得[2,4]中的每个代理支配[1,3]中的每个代理。然后我们可以简单地在[1,3]中以无嫉妒的方式分配剩余的蛋糕。
代理人的支配地位我在另一个代理j与代理关系密切我她认为自己有“明显的优势”j。为了定义显著性，我们考虑一个以某个函数为界的合适的大常数n。为一个部分分配的蛋糕，一块一个,一个代理我发现价值V我（一个)如果值为至少，则为显著值<我mg alt="cacm6304_a.gif" src="https://dl.acm.org/cms/attachment/73312ada-8f81-499e-87df-22f571eb0e3a/cacm6304_a.gif">在哪里R是未分配的蛋糕吗
一个片段的显著性是相对于剩余的，所以如果剩余变小，一个显著值仍然是显著的。定义显著值的基本原理是，如果代理我她认为自己的分配比经纪人的价值高得多j的分配，那么这个显著的优势可以通过调用核心协议的有限次数变成支配我刀。我们将在下面解释这个想法。
假设我们部分分配蛋糕和代理我被分配X我而代理j被分配Xj．假设代理我认为她比探员更有优势j：
考虑我们在未分配的饼上运行核心协议的情况R与代理我作为指定的切割机，我们这样做B乘以，所以最终未分配的蛋糕是R＊．然后
因此,后B核心协议的呼叫，探员我谁以前比代理人有明显的优势j现在主导着她:
当我们得到核心协议的结果时，切割器已经比切割器估计的蛋糕最少的代理具有显著的优势。通过调用核心协议，这个显著的优势可以很容易地转化为优势。主要的挑战是获得更多对代理之间的支配关系。在整个主协议中，临时的部分分配始终没有令人羡慕的地方。其次，如果一个代理支配另一个代理，尽管分配更新，支配仍然保持。
3.3.提取
在我们调用了更新的未分配饼的核心协议(足够但有限的次数)之后，我们就可以提取从残留。在核心协议的每一次调用中，都有相应的无嫉妒分配。在每一个这样的分配中，每一个代理人都没有嫉妒j是否有非负优势我。对于每个核心分配和每个我，j∈N、代理我被要求从未分配的蛋糕中提取一块价值的优势超过j在核心分配中。
提取的块e会不会在考虑依附我的对应分配块，因此j她的分配和之间是无所谓的我的分配。如果j的预期提取值有显著值，我们不进行提取，因为我们只想从剩余的部分中提取对所有代理都不显著的部分。如果预期的提取不显著，我们将其放在一边，以考虑附件。如果不能使它一致地不重要，那么我们说这块是不符点，我们称之为不符点协议，它利用或“消除”这种不符点。
图5。代理从剩下的蛋糕中提取到比代理1更大的优势。
将尝试将提取的碎片附加到代理1的碎片上，如<一个href="https://dl.acm.org/cms/attachment/1abc58b4-3452-4d19-91d7-060788ad5955/f6.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=480,height=193'); return false;">图6．
图6。提取的碎片放在代理1的分配旁边作为附件的目的。
假设我们有一组核心协议分配，相应的提取片段按适当的顺序放置。我们称之为一组核心协议分配同构彼此若为每一块c我在代理我的分配，从残渣中提取饼的代理人和关联c我都是一样的，而且顺序也是一样的。稍后，我们将识别彼此同构的核心协议分配的子集。同构分配将在后面的GoLeft协议中考虑。
3.4.差异的协议
当碎片被从残留物中提取出来时，可能会有一个碎片e对某些药剂来说，考虑提取是很重要的。在这种情况下，不提取片段，调用差异协议来消除或利用这种差异。有差异的部分e与残留物分开存放。如果某个片段是“几乎重要的”，我们可以通过调用核心协议的有限次数来减少剩余，从而使其重要。
通过这样做，要么差异部分变得一致重要，要么我们仍然有一些代理考虑的情况e重要而别人没有。第一种情况是有帮助的，因为在重要性方面没有差异，我们的协议利用了这种一致性。在第二种情况下，如果存在一些我∈N这样V我（R) /n<V我（e) <V我（R）n，我们继续运行与代理的核心协议我刀。通过这样做，我们实现了在有限数量的核心协议调用中，每个代理的情况我,要么V我（e)≥V我（R）n或V我（e)≤V我（R) /n。这种情况在<一个href="https://dl.acm.org/cms/attachment/5b6db11a-705c-408e-b9a3-faaf19017c86/f7.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=497,height=109'); return false;">图7．
图7。差异。的代理一个想想左边的部分n比正确的部分更有价值。的代理N＼一个认为正确的部分已经n比左边的价值多一倍。在这种情况下，如果我们把左边的部分分配给一个以一种不嫉妒的方式和正确的部分N＼一个以一种不羡慕的方式，我们获得了一个整体不羡慕的分配N。
如果V我（e)≥V我（R）n,然后我主要是对e而不是残留物。如果V我（e)≤V我（R) /n,然后我主要是对R。因为特工们最感兴趣的是n比另一块价值多一倍的，任何获得无嫉妒(因此是成比例的)优先一块分配的代理最终也会得到1/n首选块的值。该价值至少与较不受欢迎的那部分的价值相同。
3.5.主协议
继续在更新后的剩余蛋糕上调用核心协议并不能保证即使在有限的时间内蛋糕也能被充分分配。因此，我们需要使用主协议调用的其他协议。我们给出了主协议的直观概念<一个href="https://dl.acm.org/cms/attachment/2d9539e4-bd53-4146-b97a-90ae8b84f9d4/f2.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=734,height=393'); return false;">图2．我们以的形式给出协议的更详细的高层草图<一个href="https://dl.acm.org/cms/attachment/e5e405d6-bb62-4d28-9076-f3388cd96887/uf4.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=486,height=531'); return false;">算法4．
算法4。主要protocol-high-level草图。
主协议的前两个阶段是调用核心协议，以进一步分配饼，然后实现前面章节中解释的提取。在提取片段时，我们可能需要调用差异协议。在主协议的整个步骤中，我们保持一个无嫉妒的分配，并跟踪更新的未分配蛋糕。之后，主协议调用GoLeft协议。在接下来的小节中，我们将给出GoLeft协议的更多细节。
3.6.GoLeft协议
在本节中，我们将概述GoLeft协议(<一个href="https://dl.acm.org/cms/attachment/930ea4ac-4ef7-4987-a852-4124bbd450aa/uf5.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=487,height=775'); return false;">算法5)．当调用GoLeft协议时，由于对核心协议的调用，我们已经有了有限的无羡慕分配。我们还从残留物中提取了一些碎片，这些碎片将被考虑作为代理的相应核心分配的附件。
5算法。GoLeft protocol-high-level草图。
从残留物中提取碎片的目的是我们可以把它们附加到相应的核心分配碎片上我这j她分配的块和之间是无所谓的我的一块。这使它更容易j如果她得到额外的无关紧要的萃取物就换掉她的棋子。让代理交换它们的分配，同时给它们额外的提取片段，这有助于使具有显著优势的代理之间的关系多样化。
我们详细阐述了为什么依附有助于获得额外的显著优势。让我们说在一些核心分配中，探员k比代理有明显的优势吗我的分配和代理j有什么微不足道的优势我的分配。为了让k对…有明显的优势j而不是我，我们想做一些局部无嫉妒的保存操作，这样j得到我的分配块连同j的无意义提取对应于j的优势胜过那块我的年代。
排列图。当GoLeft协议启动时，它首先标识一个工作集年代的C核心拨款来自于C '我们关注的核心分配。作为C '是选得足够大，我们能找到吗C同构的核心分配。然后该协议构造一个排列图对应同构分配的工作集。
在排列图中，每个节点我对应一个代理我谁在同构分配的工作集中持有一组同构碎片和她所附的提取碎片年代。代理我指出了代理j如果j包含同构块年代直到我的提取。每个节点的进位为1。最初，排列图由所有具有自循环的节点组成<一个href="https://dl.acm.org/cms/attachment/9a26f0bf-a47c-4c65-84f8-e3e542962c16/f8.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=698,height=175'); return false;">图8)．
图8。排列图的初始状态以及同构分配的工作集的代表分配的对应状态。
我们把排列图的节点分成集合T而且T’。集T节点/代理的集合中包含同构块吗年代没有n- 1附件)。T '节点/代理的集合中包含同构块吗年代有n- 1附件。
该协议在排列图中标识包含至少一个节点的循环我从T。这样的循环总是存在的。在每个工作集中年代对于同构分配，我们实现了循环中代理持有的片段的交换:循环中的每个代理都得到了与该代理在循环中指向的节点对应的片段。在实现交换之后，排列图被更新以反映交换。在交换过程中，如果一个代理人得到了一个劣质的棋子，她总是得到与之相关的额外的棋子，直到代理人的提取为止。因此，每个代理分配的价值保存在中的每个分配中年代即使她得到了与最初核心分配不同的部分。对于任何代理我，只要没有药剂被提取碎片超出我的提取,我不会嫉妒。在GoLeft协议中，可以出现这样的情况:一些代理j获取超出的提取片段我的提取片段，但在GoLeft协议最后一部分的任何此类附件之前，我们确保没有嫉妒产生。
在实现循环之后，我们将重点放在一个节点上我∈T这是一个循环。代理/节点我，我们知道对于工作集中的所有分配年代、代理我已经分配到原始同构块了吗ck以及所有相关的作品，直到我的提取。如果一块蛋糕代理我当前是否在分配中分配年代没有更多的提取碎片附着在它上面，但它已经没有了n- 1个附件，这意味着所有未被提取/附加相应组件的代理比已被提取/附加组件的代理具有显著优势。在本例中，GoLeft协议将占主导的代理集返回给主协议，我们将面临较小的无嫉妒分配问题，因为它涉及的代理数量更少。
如果节点我不导致GoLeft协议的退出，我们知道仍然有相关的片段可以附加到由我在核心分配的工作集中年代。我们关注下一组相关的作品ek（l+ 1)我们感兴趣的是附加到碎片上ck已经有了相关的部分ek2，ek3.、……e吉隆坡附在相应的主要部分ck(见<一个href="https://dl.acm.org/cms/attachment/bdd321eb-f8b3-4a37-9a58-ebf2a1428db8/f9.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1103,height=278'); return false;">图9)．另外附加件ek（l+ 1)成碎片ck能让提取它们的特工对碎片感兴趣吗ck因为额外的ek（l+ 1)以及之前的附件。
图9。最初分配给代理1的一块蛋糕上的GoLeft协议的说明。代理k+ 2n不会往左走，他们是未来的统治者吗?因为他们找到了边缘之间的阴影空间k+ 2,k+ 1显著。代理2k+ 1是向左移动的代理。
在附加提取的碎片时避免嫉妒。天真地附加碎片可能会产生问题，破坏我们所保持的分配的自由。我们处理这个问题的方法如下。
- -没有提取碎片的特工ck碎片和提取未附加碎片的代理被要求“保留”一个足够大的子集年代⊂年代在分配中，他们对奖金价值的差异进行了评估ck和被提取出来的部分ck最多。这些配置年代是远离年代剩下的未连接的相关片段被送回残留物中。通过保持核心分配的优势年代，这些代理不会嫉妒，即使{1，…，l}额外获取所有其他提取的片段ek（l+ 1)的剩余核心拨款年代。
- —索引从1到的代理l谁已经把自己的碎片粘上了ck被要求选择足够高的比例的核心分配年代他们认为ek（l+ 1)碎片。我们称之为分配年代”。的ek（l+ 1)从S”聚合在一起，调用主协议以一种没有嫉妒的方式在索引从1到l在哪里l严格小于n。因为无嫉妒意味着相称性，他们获得了足够的价值，如果代理索引，他们就不会嫉妒l+ 1得到集合中的所有其他棋子ek（l+ 1)．对应的分配集S”然后从更新的考虑中删除。
因此，每次我们附加同构提取的片段ek（l+ 1)同构的作品ck在美国，我们“冻结”拨款年代∪S”从工作集年代并且仍然保持一个没有嫉妒的分配。注意，在剩余的分配中年代，代理目前可能持有一个不同的同构片，但由于它们还持有与同构片相关联的相应附件，每个代理在每个同构分配中的总价值年代保持不变。在<一个href="https://dl.acm.org/cms/attachment/d46ae060-3dc4-4c00-999b-460d794758f6/f10.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=632,height=996'); return false;">图10，我们给出排列图的状态和相应的代表性Core分配以及相应的提取片段。
图10。排列图以及同构分配的工作集的分配代表的对应状态。
当协议附加提取的片段ek（l+ 1)分配的块ck目前由代理人持有l，它删除节点/代理的传入边缘l然后用来自代理的一条边代替它l+ 1提取碎片在ek（l+ 1)．直观地说,l+ 1现在愿意被分配到c它的附加部分，而不是她当前的部分年代。我们删除以前的边，以确保直到终止，节点在T有一个正好为1的进位，这保证了无论一个节点在哪个循环中T根据协议，我们会在终止协议方面取得进展。下面的示例展示了如何将提取的片段附加到同构Core分配的工作集中。
例1。在<一个href="https://dl.acm.org/cms/attachment/d46ae060-3dc4-4c00-999b-460d794758f6/f10.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=632,height=996'); return false;">图10，我们演示了在GoLeft协议中排列图和同构分配的工作集是如何变化的。请注意，即使在代表性分配发生变化时，仍然存在与以前的代表性分配同构的分配，但这些分配已从分配工作集中排除。彩色/阴影部分代表核心协议给每个代理的部分。左边的小块彩色碎片是提取出来的碎片，每个碎片都由提取它的代理人标记。首先，提取的片段与特定的分配片段相关联。然后它们被附加到它(用虚线表示)。最后，当一个彩色/阴影块实定位到一个新代理时，附加到它的提取块也分配给新代理(在图中，我们现在将提取块聚合到主块)。在同构分配的第二种状态下，agent2指出了代理1因为这块被代理人提取了2已经附属于1的举行。在同构分配的第三种状态下，代理3.指出了代理2因为这块被代理人提取了3.已经附属于2的举行。在同构分配的第四种状态下，代理1指出了代理3.因为这块被代理人提取了1已经附属于3.的举行。在第五种状态下，代理1、2、而且3.交换他们目前持有的一块，分配蛋糕到他们提取的一块。在同构分配的第五种(最后一种)状态下，代理1在她被抓出来之前还留了一块但两个探员都没有2或4提取的片段为片段的代理1成立。这意味着代理2而且4与代理相比有显著优势吗1.最初，这幅画被3.仍然是废弃的同构分配。这意味着……的显著优势2而且4在3.因此,代理2而且4能被做成主宰吗1而且3.
通过以适当的顺序附加足够多的提取片段，GoLeft协议最终到达存在一些同构片段集的点ck在一组年代所有可能的相关片段都被附加了但是有一些代理N＼一个他们没有相关的片段。代理进入的原因N＼一个不能提取这样的片段是因为它们具有一致的显著优势，优于索引得到这些片段的代理1ck．通过逐渐地将(一致无关紧要的)相关的碎片连接到碎片上ck确保所有提取了对应片段的代理都得到了同构的片段ck(以及相关的不重要的附件)，我们确保代理在N＼一个现在支配代理一个。此时，我们可以从GoLeft协议返回。我们已经成功地将无嫉妒分配问题减少到涉及较少代理数量的问题。通过递归调用主协议，将剩余的饼分配给较小集合中的代理一个，我们最终分配了整个蛋糕。
4.结论
我们介绍了我们的有界无嫉妒协议的高级概述。该协议有一个上限，即功率塔为6n另一方面，任何无嫉妒的协议至少需要Ω(n2)查询。6
此外，我们还表明，即使我们没有运行我们的协议到完成，它最多可以找到n调用核心协议的部分分配蛋糕，实现了比例(每个代理至少得到1/n整个蛋糕的价值)和无嫉妒。如果我们允许部分分配，一个有趣的开放问题是:无嫉妒性和比例性能否在多项式的步骤数中实现?
致谢
Haris Aziz得到了新南威尔士大学科学奖学金的支持。他感谢Xin Huang, Sven Koenig, Omer Lev, Bo Li和Simon Rey的反馈。他还感谢西蒙·雷伊(Simon Rey)帮助制作了一些数字。
参考文献
1.一个离散的、有界的、无嫉妒的四个体切蛋糕协议。在48个国家的议事记录thACM年度计算理论研讨会(STOC)(ACM出版社，2016)，454-464
2.对于任意数量的代理，一个离散的、有界的、无嫉妒的切蛋糕协议。在57人会议记录th计算机科学基础研讨会(2016), 416 - 427
3.布拉姆斯，s.j.，泰勒，ad，一个无嫉妒的蛋糕分割协议。点。数学。月1。102(1995), 9到18。
4.布拉姆斯，s.j，泰勒，公元公平划分:从切蛋糕到纠纷解决。剑桥大学出版社，1996。
5.Dehghani, S.， Farhadi, A.， Taghi Hajiaghayi, M.， Yami, H.无嫉妒的家务部门，为任意数量的代理。在第29届离散算法ACM-SIAM年会论文集，SODA 2018(2018年1月7-10日，美国洛杉矶新奥尔良)，2564-2583。
6.公元普罗卡西亚，你应该觊觎邻居的蛋糕。在廿一年会议记录圣国际人工智能联席会议(美国科学技术出版社，2009)，239-244。
7.切蛋糕:不只是孩子的游戏。Commun。ACM 7， 56(2013)， 78-87。
©2020 0001 - 0782/20/4 ACM
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限<一个href="mailto:permissions@acm.org">permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2020 ACM, Inc.
评论
Nandakumar拉马纳坦
请列入关于下列至少两个有关问题的有关出版物的参考资料，并尽可能将其与当前情况的关系列入附件。1.在给定区域/体积中瓦片/包的最佳包装(图论应用);在地理信息系统中尽量减少条子多边形的面积。- Dr. R. Nandakumar (r_nand)又名Nandakumar Ramanathan
Nandakumar拉马纳坦
在我看来，如果蛋糕上有一些奶油漩涡和/或樱桃，就可以在脚注上加上“a”;而他们的总人数少于有志于从中分一杯羹的经纪人的人数，就不会有任何可行的无嫉妒的解决方案来解决这个问题。- Dr. R. Nandakumar (r_nand)又名Nandakumar Ramanathan
显示所有2评论