课题组报告回顾 | 贝小辉教授谈公平分配：嫉妒与诚信

关键词：资源分配

编者按

2020年11月12日，daGAME课题组组会上，南洋理工大学的贝小辉教授在线带来了题为《公平分配：嫉妒与诚信》的报告。

以下为虽然迟到但是非常详细干货满满的报告总结。

资源分配是历史悠久的问题。资源分配中往往面对着两类资源：可分资源与不可分资源。土地，金钱等资源一般被认为是可分资源，而艺术品、房屋、车辆等属于不可分资源。贝小辉老师分别介绍了可分资源，不可分资源以及混合资源三种设定下的公平资源分配问题的近期进展。

可分资源公平分配中最经典的问题是蛋糕分割问题。其中蛋糕被表示为 [0,1] 的连续区间，而所有参与者对于蛋糕的估值函数是  的一个函数（满足可加性，归一性以及可分性）。由于估值函数不一定能有限表示，研究问题的询问复杂度更为合适。Robertson-Webb 模型（R-W 模型）提出了两种对于估值函数的询问，被广泛采用。每个参与者对于蛋糕各部分的估值可能非常不同，如何刻画一个分割方案的公平性呢？蛋糕分割问题通常研究两种不同程度的公平性，分别是相称性（proportionality）和无嫉妒性（envy-freeness）。

对于  个参与者的蛋糕分割问题，相称性要求每一个参与者得到的部分在他自己看来价值都不小于  ，而无嫉妒性要求每一个参与者不会嫉妒其他参与者分到的蛋糕，即在他看来，他分到的蛋糕的价值不小于任何其他参与者分到的蛋糕的价值。容易看出无嫉妒性包含了相称性。

满足无嫉妒性的分割方案的存在性是已知的，如何设计一个公平的蛋糕分割机制是长久以来的研究问题。在仅有两个参与者的时候，相称性和无嫉妒性是一致的。此时，我们可以让第一个参与者把蛋糕分成两份，然后让第二个参与者先选择蛋糕。很容易证明，这个简单的机制就是公平的。而对于更多的参与者，Dubins-Spanier 机制能构造一个满足相称性的分割方案。然而，找到一个满足无嫉妒性的机制却非常困难。最早在1960年左右，研究者就提出了一个针对三个参与者的无嫉妒性机制。三十多年以后，研究者才在1995年提出了一个针对任意多个参与者的无嫉妒性机制，并且这个机制询问的次数并没有上界。直到最近，研究者在2016年的两篇文章中分别提出了针对四个参与者和任意多参与者的询问次数有界的无嫉妒性机制。不过这个机制非常复杂，并且最大的可能询问次数是  ，设计一个更高效的机制依然是公开问题。

虽然现有机制已经保证了分割方案的无嫉妒性，但是却不是诚信机制。诚信机制要求参与者说出真相是最优机制，即参与者在任何情况下说谎都不会得到更高的回报。一个自然的问题就是存在一个满足无嫉妒性的诚信机制吗？不幸的是，研究者在2013年证明并不存在 R-W 模型下询问次数有界的满足无嫉妒性的诚信机制。

因此，研究者开始研究特殊的估值函数。其中一种估值函数是分段均匀（piecewise uniform）函数，即蛋糕的每一部分对于参与者来说，要么无价值，要么价值相同。换句话说，蛋糕中对于参与者有价值的部分的估值分布是均匀的。当参与者的估值函数均为分段均匀函数时，研究者曾在2010年提出了一个确定性、无嫉妒性的诚信机制，但是这个机制可能会丢掉一部分蛋糕，而不分给任何参与者。它隐式地假设了丢掉蛋糕的任何一部分都不会带来开销。但是这个假设在部分情况下会显得十分不合理。贝小辉老师和合作者在2018年为两个参与者的蛋糕分割问题提出了一个确定性，无嫉妒性，帕累托最优的诚信机制。这个机制不需要前述假设。对于三个以及更多的参与者，满足这些性质的机制的存在性目前仍是公开问题。

另一种估值函数是分段常数（piecewise canstant）函数，分段均匀函数是分段常数函数的特殊情况。分段常数函数仅要求参与者对于蛋糕连续的正价值区间的估值是均匀的，而不同的区间的估值可以不同。可以发现，当区间的分割细化时，分段常数函数可以近似一般的估值函数。贝小辉老师与合作者在2017年证明了在额外假设下，参与者估值为分段常数函数下的无嫉妒性诚信蛋糕分割机制不存在，即使仅有两个参与者。

在不可分资源分配问题中，参与者对于每一件物品有估值，他对于物品集合的估值是集合中每一件物品估值的总和。此时也有两种常研究的公平性：至多一件物品的无嫉妒性（envy-free up to one good, EF1）以及至多任意一件物品的无嫉妒性（envy-free up to any good, EFX）。其中 EF1 要求对于任意一个参与者，如果去掉每一位其他参与者分配的物品集合中的某一件物品，他就不会嫉妒其他参与者，而 EFX 进一步要求，即使去掉每一位其他参与者分配的物品集合中的任意一件物品，他都不会嫉妒其他参与者。可以看出 EFX 包含 EF1。

满足 EF1 的机制是存在的。我们可以给参与者排个序，然后让每一位参与者依次拿走剩余物品中的一件，一直循环直到物品分配完毕，可以证明这种 Round-Robin 机制就满足 EF1。然而对于 EFX，目前人们的认识还很少。直到今年2020年，研究者才证明对于三个参与者，满足 EFX 的分配一定存在。满足 EFX 的分配是否对于任何情形都存在是目前公平分配领域最重要的公开问题之一。

当待分配的资源同时包含可分资源与不可分资源时，该如何定义公平性呢？此时资源中包含 m 件不可分物品以及一个可分的蛋糕，参与者的估值与之前定义相同，且其对于分配资源的总估值是可加的。简单的融合无嫉妒性和 EF1 即要求在仅考虑可分资源时，分配是满足无嫉妒性的，而在仅考虑不可分资源时，分配是满足 EF1 的，并不是一个好选择。在某些情况下，满足这种性质的分配看起来一点也不公平。

为了解决这个问题，贝小辉老师与合作者提出了针对混合资源的公平性（envy-free for mixed goods, EFM）。EFM 要求如果某个参与者被分配的资源仅包含不可分资源，则需满足 EF1，否则需满足无嫉妒性。EFM 在仅有可分资源或者不可分资源时自然地退化为无嫉妒性和 EF1。与此同时，贝小辉老师与合作者证明了满足 EFM 的分配一定存在，并且可以在多项式时间内计算出来。值得一提的是，该算法会调用完美蛋糕分割预言机，而后者在 R-W 模型中并不能在有界时间内构造。因此如何得到一个在 R-W 模型下有界的满足 EFM 的机制是一个公开问题。如果放松 EFM 为 ε-EFM，即放松原本的无嫉妒性到允许最多为 ε 的嫉妒，贝小辉老师与合作者提出了一个在  时间内找到满足 ε-EFM 的分配算法。

文字 | 郑炜强

deGAME课题组

往期讲座回顾

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转报告简介