ACM通信
研究突出了
技术视角:公平事业部最神秘问题的答案
切蛋糕问题是著名数学家雨果·施泰因豪斯(Hugo Steinhaus)的智慧结晶，他在20世纪40年代初制定并研究了这个问题，当时他正在躲避占领他祖国波兰的纳粹。施泰因豪斯提出的问题肯定也发生在很多人身上(尽管可能是在更容易获得蛋糕的环境下):一个人如何在多人之间公平地分配蛋糕?困难在于蛋糕是异质的，参与者有不同的喜好，所以简单地给他们同等大小的蛋糕是不行的。
在概念层面上，施泰因豪斯的主要见解是公平——一个表面上抽象的概念——可以用数学来具体说明。作为公平的缩影，出现了一个特别的概念:无嫉妒，这意味着每个参与者都喜欢自己的那块蛋糕，而不是分给其他参与者的那块。
那么，什么样的算法能让两个玩家不嫉妒地分蛋糕呢?简单:我切;你选择。我不嫉妒，因为我对这两件作品漠不关心，你得到了你喜欢的那件。三个球员呢?这已经很棘手了。这个普遍的案例被公开了几十年，被认为是一个重大的悬而未决的问题，直到1995年史蒂文·布拉姆斯和艾伦·泰勒解决了它。
布拉姆斯和泰勒的无嫉妒协议保证终止于蛋糕的无嫉妒分配。然而，该算法的运行时间是无限的:通过仔细调整参与者的偏好，可以使协议执行任意数量的步骤。结果，布拉姆斯和泰勒刚解决了切蛋糕的问题，就立刻把一个新问题送上了公平组织的头号通缉犯名单:存在一个有界的envy-free切蛋糕的协议。
不可分割商品的分配引发了一些既具有数学挑战性又非常实际的问题。
这个问题存在了20年，直到2016年被阿齐兹和麦肯齐破解。本文给出了解决方案;这是一个复杂的协议，它建立在以前的想法之上，同时又加入了一些巧妙的成分。
那么，有抱负的切蛋糕师是否应该收起他们的马刺呢?没有相当。Aziz-Mackenzie协议所需的步骤数受限于参与者数量的函数，但这个函数的增长速度快得可笑。事实上，对于两个参与者来说，界限是一个数字，它的位数是如此之大，以至于它本身几乎有20,000位!这就引出了一个问题，即是否存在一种既无嫉妒又计算效率高的切蛋糕协议。
除了切蛋糕，公平分割算法已经从理论过渡到实践。例如，解决租金分配问题的无嫉妒解决方案——将房间分配给室友，并在他们之间分配租金——被广泛使用。其他的应用包括分配计算资源，给学生分配大学课程的座位，甚至通过证明公平的政治重新划分程序来消除不公正的选区划分。
尤其是不可分割商品的分配，引发了一些既具有数学挑战性又具有深刻实践性的问题。一个典型的用例是将珠宝或艺术收藏品分给几个继承人。由于商品不能在参与者之间分配，因此无法保证无嫉妒。相反，让我们允许一个参与者更喜欢分配给另一个人的商品束，但必须是这样的情况任何善自束后者的参与者总是会消除前者的嫉妒;这个性质被称为没有嫉妒对任何好处简称EFX。此外，假设每个参与者对一捆商品的价值仅仅是个别商品价值的总和。EFX分配是否保证存在?这个基本的、看似容易回答的问题是开放的。在我看来，这是继无嫉妒切蛋糕之后，公平分割的最大问题。
从更广泛的角度来看，近年来，“公平”一词被机器学习研究人员用来指缺乏偏见或歧视。这一观点根植于罗尔斯伦理学，似乎与80年来公平划分研究中所推崇的基于偏好的公平概念不一致。然而，这两个领域之间有很强的协同作用。特别是，像无嫉妒这样已经确立的公平概念可以——也应该——帮助指导合乎道德的人工智能的设计。
数字图书馆是由计算机协会出版的。版权所有©2020 ACM, Inc.
没有发现记录