如何公正地切蛋糕
计算机科学家已经为许多人开发了一种公平的饼算法
两位年轻的科学家，计算机科学领域的专家，提出了如何在任何数量的人之间诚实地分享蛋糕的方法，从而解决了数学家数十年来一直在努力的问题。他们的工作使许多研究人员感到惊讶，他们认为这种分离原则上是不可能的。共享饼图是对许多现实生活任务的隐喻，包括在对某些连续对象（无论是蛋糕还是一块土地）进行划分时，人们对它们的属性会有不同的评价。一个喜欢巧克力涂层，另一个喜欢奶油花。从圣经时代开始，就已经有一种算法可以在两个人之间划分对象，这样没人会羡慕另一个人：一个人为他将蛋糕分成两等份，另一个人选择其中一个。在创世纪中，亚伯拉罕（Abraham）（当时称为亚伯兰（Abram））和罗得（Lot）使用这种方法来划分土地，亚伯拉罕（Abraham）发明了一个隔离区，罗得（Lot）在约旦和迦南之间进行了选择。在1960年代，数学家想出了一种算法，可以让三个人“无羡慕”地分担蛋糕。但是到现在为止，这个问题对许多人来说最好的解决办法是三个以上的程序，成立于1995年的政治学家斯蒂芬·勃拉姆斯从纽约大学[史蒂芬Brams]和数学家艾伦·泰勒从联合学院[阿伦泰勒。它保证了蛋糕的“公平”共享，但是有一个条件-程序是“无限的”，也就是说，共享所需的步骤数将是任意的。Brahms-Taylor算法曾经被称为突破性算法，但是“我认为它的无限性是一个很大的缺点，” Ariel Procaccia说卡内基·梅隆大学（Carnegie Mellon University）的计算机科学家[Ariel Procaccia]，Spliddit的创建者之一，Spliddit是一个免费的在线工具，用于公平分担从家务到分摊的租金等任务。在过去的50年中，包括Procaccia在内的许多数学家和计算机科学家都说服自己，将蛋糕分成n个部分没有有限的公平算法。沃尔特·斯特罗姆克维斯特（Walter Stromkvist）说：“正是这项任务使我进入了公平分工的领域。”[Walter Stromquist]是宾夕法尼亚州布林·马弗学院的数学教授，他在1980年的蛋糕共享问题上取得了不错的成绩。 。但是，在4月，两名计算机科学专家通过发布一种公平蛋糕共享算法来反驳这些期望，该算法的工作时间取决于共享参与者的人数，而不是他们的个人偏好。卡内基·梅隆大学的一位科学家，现年27岁的西蒙·麦肯齐博士，于10月10日在第57届IEEE计算机科学基础上发表了他的工作。该算法非常复杂。 n位参与者之间的蛋糕分配可能最多需要nn n n n n n步，剪切数量大致相同。即使对于少数参与者，该数目也超过了宇宙中原子的数目。但是据第二小组成员Haris Aziz称，研究人员已经有了简化和加速算法的想法，Haris Aziz是新南威尔士大学的35岁的计算机科学专家，他在澳大利亚数据研究小组Data61中工作。据Procaccia称，研究公平分配理论的专家认为这“无疑是几十年来最好的结果”。小菜一碟
Aziz和Mackenzie算法基于数学家John Selfridge和John Conway在1960年代独立发明的一种优雅程序，可以将蛋糕平均分为三部分。
如果爱丽丝（Alice），鲍勃（Bob）和查理（Charlie）（A，B，C）想要分割蛋糕，则算法以查理（Charlie）将蛋糕分成对他来说看起来相同的三部分开始。爱丽丝和鲍勃选择他们喜欢的作品。如果他们选择不同的作品-瞧，每个人都会得到他们想要的东西。如果爱丽丝（Alice）和鲍勃（Bob）选择了一块，那么鲍勃（Bob）会切掉这块的一小部分，这样，从他的角度来看，这块就等于另一块蛋糕-鲍勃（Bob）会选择第二块。残留物被推迟。现在，爱丽丝必须从剩下的三个中选出最适合自己的一块，然后选择鲍勃-条件是如果爱丽丝不选，他将拿走自己剪下的一块。查理获得第三名。结果，没有人羡慕任何人。爱丽丝选择了第一个。鲍勃收到与他同等价值的两块之一。查理得到了他自己剪下的三幅原创作品之一。仅剩下一个小界限。但是可以对它进行划分，而无需先启动算法，也不必陷入割礼和选择的无休止循环中，因为无论如何查理都对他的作品感到满意-即使获得裁切作品的人也将获得全部剩余的作为，因为查理看起来不会很不诚实，因为切成薄片的蛋糕和剩下的蛋糕会给它一块相当于它的蛋糕-毕竟，他从一开始就将它们切成薄片。阿齐兹和麦肯齐将查理的立场描述为“主要”。现在，例如，如果爱丽丝得到了一块切块，然后鲍勃将修剪切成三部分，从他的角度来看，这等效，爱丽丝为自己选择了其中一块，然后选择了查理，然后是鲍勃。每个人都很高兴：爱丽丝首先选择，查理比鲍勃做得更好（他不在乎爱丽丝花了多少钱），从鲍勃的角度来看，这三件作品都是一样的。勃拉姆斯和泰勒利用“支配性”属性（但名称不同）来开发他们的1995年算法，但是直到出现有限算法之前，他们才完成自己的想法。在接下来的20年中，没有人能取得最佳结果。“而不是因为没有尝试，” Procaccia说。不专业的蛋糕分频器
当Aziz和Mackenzie（A＆M）在几年前决定承担这项任务时，他们是蛋糕共享任务的新手。阿齐兹说：“我们不像那些致力于此工作的人那样多。” “尽管这通常是一个缺点，但在我们看来，这是一个优点，因为我们的想法有所不同。”A＆M首先研究了从零开始将参与者分为三类的任务，分析的结果是针对去年由四名参与者发布的有限公平算法。他们无法立即展示如何将算法扩展到大于四名的参与者，但是他们热心地承担了这项任务。 “在发送了涉及四个参与者的工作后，我们真的希望快速继续工作，直到有经验的人和聪明的人将其独立推广到n个参与者的情况下，” Aziz说。大约一年后，他们的搜索成功了。像Selfridge-Conway算法一样，AiM协议不断为不同的参与者提供将蛋糕切成n个相等部分的方法，而其他人则可以选择并选择蛋糕。但是算法中还有其他步骤，例如，以特殊方式定期交换蛋糕块，以增加参与者之间的主导关系数量。这些关系使A＆M减少了任务的复杂性。例如，如果剩下的三名参与者占主导地位，那么他们已经可以被送去吃自己的蛋糕了-他们会很高兴，无论谁得到剩饭剩菜。此后，剩下的参与者就更少了，经过有限数量的这样的步骤，每个人都很满意，整个蛋糕被分割了。“回顾算法的复杂性，开发它花了这么长时间也就不足为奇了，” Procaccia说。但是A＆M已经相信他们可以简化算法，因此它不需要交换零件，只需n n n步即可完成。据阿齐兹说，他们已经在研究这些结果。勃拉姆斯警告说，即使是更简单的算法也无法实际应用-毕竟，参与者收到的蛋糕将包括蛋糕不同部位的许多小碎屑。例如，如果您要分割土地，此方法不是特别有用。但是对于正在研究该问题的数学和计算机科学家来说，新结果“重新设置了整个话题”，斯特罗姆克维斯特说。既然研究人员知道蛋糕可以分为有限的几个步骤，那么根据Procaccia的说法，下一步就是要了解AiM方法的步骤数上限与为此所需的步骤数下限之间的巨大差距。 Procaccia 早先已经证明，蛋糕的公平分离算法不能通过小于n2步-但步数比n n n n n n甚至n n n小。阿齐兹说，研究人员现在必须弄清楚如何缩小这一差距。“我认为可以在两个方向上取得进展。”Source: https://habr.com/ru/post/zh-CN398683/
All Articles