近日，第二十三届ACM经济与计算会议（ACM Conference on Economics and Computation，ACM EC'22）在美国举行。电子信息与电气工程学院约翰·霍普克罗夫特计算机科学中心助理教授陶表帅以独立作者身份在该会议上发表了题为“防策略性公平蛋糕分配机制的存在性”（On existence of truthful fair cake cutting mechanisms）的论文。

该论文对资源分配问题中一个10余年未解的重要难题作出了解答，证明了在可分割异质资源的分配问题中，公平性和防策略性两者是无法兼容的。同时提出了一个可以与公平性兼容的弱化版本的防策略性概念——风险厌恶防策略性，并给出了相应的资源分配机制。陶表帅是继图灵奖得主姚期智之后国内第二位以独立作者身份发表EC论文的学者。

研究背景

蛋糕分配问题（cake cutting problem）研究如何将可分配的（divisible）、异质的（heterogeneous）资源公平地分配给若干个参与者。蛋糕分配问题是一个受到数学家、经济学家和计算机科学家广泛关注的问题。以往的工作已经证明了公平分配的存在性，并给出了相应的分配机制。

然而，当把这些公平分配机制运用到实践当中，参与者是具有策略性的：参与者可以通过谎报自己价值标准来获取更大价值的分配。这促使从博弈论（game theory）的角度研究蛋糕分配问题。我们希望一个机制具有防策略性（truthful/strategy-proof），即对于每一个参与者来说——真实地汇报自己的价值标准是一个支配性策略（dominant strategy）。通俗地说，在一个具有防策略性的机制下，每个参与者“说真话”得到的收益总是大于等于“说假话”得到的收益。

那么，一个自然的问题是，是否存在一个既满足公平性又满足防策略性的机制？该问题由Chen et al.于2010年提出，并在过去的12年以来被数篇其它文章反复提出。尽管该问题受到了广泛的关注并且大家取得了一些部分进展，但该问题始终未得到解决。

研究成果

该论文研究了蛋糕分配机制中公平性与防策略性是否兼容的问题，并对该问题做出解答。本文证明了不存在一个能同时满足防策略性和公平性的蛋糕分配机制，即在蛋糕分配的问题中，公平性和防策略性是无法兼容的。本文还把该不存在性结论强化到了一些更特殊的情况，证明了该不存在性结论甚至在以下特殊设定同时满足的情况下依然成立：

①一共只有两个参与者；

②每个参与者的价值标准可以被一个按段常数（piecewise constant）的价值函数所表达；

③每个参与者对每段蛋糕上的价值是严格大于0的；

④机制在满足公平性前提下允许将一部分蛋糕丢弃。

主要不存在性结论证明

作为该不存在性结论的一个应对方案，并旨在对蛋糕分配机制在现实应用中提出一个具有建设性的替代选项，本文提出了一个比传统的基于“支配性策略的”防策略性更弱一些的防策略性标准——风险厌恶防策略性（risk-averse truthful），并证明了该弱化版本的防策略性能与公平性兼容。具体来说，本文设计了两个能同时满足风险厌恶防策略性和公平性的蛋糕分配机制。

关于ACM经济与计算会议

ACM经济与计算会议（简称“ACM EC”）专注于经济学与计算机科学的交叉研究，是计算经济学领域最权威的学术会议，由ACM特殊兴趣学组SIGecom于1999年主办。

关于作者

陶表帅，约翰·霍普克罗夫特计算机科学中心助理教授，研究方向为经济学和理论计算机科学的交叉领域，具体研究问题包括资源分配问题、社会网络问题、社会选择学、算法博弈论，以及其它经济学相关问题。陶表帅本科毕业于新加坡南洋理工大学，于2020年获得美国密歇根大学安娜堡分校计算机科学博士学位。陶表帅于2020年底加入上海交通大学。

论文链接

https://dl.acm.org/doi/10.1145/3490486.3538321

来源丨约翰·霍普克罗夫特计算机科学中心

文稿丨陶表帅、张力文