近日，信息科学与技术学院赵登吉课题组与上海财经大学理论计算机研究中心合作完成的论文“Incentives for Early Arrival in Cooperative Games”被第23届智能体及多智能体系统国际会议（International Joint Conference on Autonomous Agents and Multi-Agent Systems, AAMAS 2024）接收，并荣获本届会议唯一的最佳论文奖。
传统的合作博弈主要研究“如何将合作产出的价值分配给合作者”问题，分配目标包括合作的稳定性和分配的公平性。为了公平性，诺贝尔经济学奖得主劳埃德·夏普利（Lloyd Shapley）在1951年提出了夏普利值（Shapley value）的合作奖励计算方式，核心是把一个合作者加入到一个团队所带来的边际贡献作为此合作者奖励计算的依据。由于传统的合作博弈不考虑加入顺序，所以无法用某一种特定的加入顺序计算所有人的边际贡献。为此夏普利提出了将所有可能的加入顺序都考虑一次从而计算出每个合作者的平均边际贡献，以此作为他们的奖励分配。
但在现实生活中，参与者确实有一个参与顺序（而且这个顺序是自然形成的），比如投资者投资一个初创企业，或者用分批的大数据训练一个大模型。在这些特定加入顺序下，就不能直接用夏普利的上述方法来计算参与者的奖励分配。例如在投资问题中，必须在每笔资金进入后确定好现有的参与者的股权或者利益分配，另外现有的参与者也不知道未来是否还有新的投资者加入。
在这个新的合作场景下，不仅需要关注奖励分配的公平性和稳定性，还需要关注他们是否愿意按照一个给定顺序加入。比如当一个投资者首先发现一家不错的初创企业时，他是否会选择马上投资还是等其他投资者先投，因为不同的加入时间点可能带来不一样的回报。研究人员在论文中首次提出了一个新的研究目标：激励（合作者）早加入（Incentives for Early Arrival）。激励早加入不仅消除了合作者担心加入太早会使利益受损的问题，而且也更快地促成了合作（比如企业更早地获得融资）。
针对激励早加入，研究人员设计了新的奖励分配方案（Reward First Critical Player, RFC），并且刻画了在什么样的场景下可以实现这个目标。新方案的核心思想是把新加入合作者的边际贡献分配给最早加入且发挥关键作用的合作者。如下图中，假设扳手、螺钉和螺母一起可以产生1的价值，当螺母在第4位加入合作时，它可以带入1的边际贡献，但是此贡献需要被分配给第1位到的扳手。这样看似失去了公平性，但是可以证明在期望上每位合作者的奖励分配是和不考虑顺序下的夏普利值相等的（满足了一定的公平性）。
论文的选题和解决方案都获得了AAMAS 2024评委们的一致好评，最终从1000多篇投稿中脱颖而出斩获AAMAS 2024唯一的最佳论文奖。新的研究目标不仅可以引领一波新的理论创新，也将为很多现实的在线合作问题提供解决方案，包括投资、社会福利分配、成本分摊、众包以及数据资产定价等。论文的第一和第二作者是赵登吉课题组的博士研究生葛垚鑫和张尧，通讯作者是赵登吉教授。合作者还包括上海财经大学理论研究中心的唐志皓教授、伏虎教授和陆品燕教授。
论文全文：https://dl.acm.org/doi/10.5555/3635637.3662917
AAMAS 2024最佳论文证书：
AAMAS 2024颁奖现场作者合照：
沪公网安备 31011502006855号