AAAI 2024 | 成对抽奖竞赛之间的竞争

关键词：竞赛设计、平行竞赛、均衡分析

导  读

本文是对会议 AAAI 2024 上发表的论文 Competition among Pairwise Lottery Contests 的论文解读。本研究由北京大学前沿计算研究中心邓小铁课题组与中国人民大学合作完成，作者为邓小铁课题组博士生李宁远、博士后研究员李维安、南开大学本科生甘杭鑫、北京大学讲席教授邓小铁和中国人民大学副教授祁琦。本文建模分析了一种多竞赛竞争场景下参赛者和竞赛设计者的均衡行为。

← 扫码跳转论文

论文地址：

https://arxiv.org/abs/2312.11953

01

问题背景

竞赛模型建模了现实中的各种竞争性场景。在一个竞赛中，若干参赛者投入努力相互竞争，争夺预先设置的奖励。传统竞赛设计理论通常研究单个竞赛如何设计奖励规则以激励参赛者的努力投入，然而在许多现实场景中，存在多个同时进行的竞赛。在这样的环境下，参赛者需要将有限的努力分配到不同竞赛中。因此，不仅参赛者之间存在竞争，竞赛设计者之间也为了吸引参赛者而相互竞争。本文研究了在多个竞赛同时进行的情况下，参赛者以及竞赛设计者之间的竞争行为与均衡策略。本文主要关注成对竞赛的情形，即每个竞赛中仅有两个参赛者。

02

模  型

本文考虑了一个多竞赛博弈模型：存在  位潜在参赛者和  位竞赛设计者，每位参赛者  具有总努力值  ，每位设计者  具有总预算  。每位竞赛设计者举办一场或多场成对抽奖竞赛（Pairwise Generalized Lottery Contest）。具体地，一场成对抽奖竞赛表示为一个三元组：  ，其中：

1.   是  的大小为  的子集，代表本竞赛邀请的两个参加者。设  ；

2.   是一个正实数，代表获胜的参赛者获得的奖金；

3.   是两个正实数，代表对两参赛者设置的提升系数。

两个参赛者  各自决定自己投入的非负努力值  和  ，每人的获胜概率与他的努力值与提升系数之积成比例。具体地，参赛者  以  概率在竞赛  中获胜，而参赛者  的获胜概率是  。特别地，当  时，我们规定两人各以  概率获胜。

本文考虑一个两阶段博弈模型：

第一阶段称为设计者阶段，每个设计者设置自己举办的竞赛。本文研究了两种设计者模型，区别在于每个设计者是否能分割其预算来举办多场竞赛：

• 可分模型：每个设计者可以举办任意数量的竞赛，记为集合  ，只需满足总奖金不超过其预算：  ；

• 不可分模型：每个设计者只能举办一场竞赛，记为  ，满足  。

第二阶段称为参赛者阶段。每个参赛者  决定自己在参加的各比赛投入的努力值  ，并且总和不超过  。

每个参赛者希望最大化自己期望下获得的总奖金，而每个设计者希望最大化在其举办的所有竞赛中参赛者投入的努力值总和。

我们关心这一博弈模型下的序贯均衡，即子博弈精炼纳什均衡。也就是说，我们研究第二阶段中参赛者在已知所有竞赛的设置的情况下分配努力值的均衡策略，以及假定参赛者总会达成均衡时第一阶段中设计者设置竞赛的均衡策略。

03

参赛者均衡策略

我们首先在所有竞赛已经给定的情况下刻画参赛者的均衡策略。作为分析和刻画参赛者均衡的主要工具，我们定义均衡乘子向量。一个均衡乘子向量  是一个  维向量，代表在一组参赛者均衡策略  下每个参赛者的所得奖励关于努力值的边际效用。粗略地说，在均衡状态下每个参赛者的努力值分配是以下优化问题的最优解： 

其中  表示  在竞赛  中的对手，而  表示在竞赛  中投入  时的获胜概率，是关于  的凹函数。通过分析，可以保证不会出现分母为  的情况。这一问题可通过添加拉格朗日乘子  转化为  ，这里的  即为均衡乘子向量  的第  个分量。

从均衡乘子向量  可以计算出一组对应的参赛者策略  ，它是所有对应于  的策略的一个下界。对每个  ，若  则  ，若  则  。这允许我们将关于策略  的均衡条件转化为关于向量  的条件。为了找到参赛者均衡策略，只需要找到一个满足条件的均衡乘子向量。我们利用布劳威尔不动点定理证明了均衡乘子向量的存在性，并利用一种单调性质证明了均衡乘子向量的唯一性。由此，全体参赛者均衡的集合被这一唯一的均衡乘子向量刻画出来。另外，我们还设计了多项式时间的迭代算法，以多项式级别精度求解均衡乘子向量  ，进而计算参赛者均衡。

04

竞赛设计者均衡策略

基于对参赛者均衡的刻画，我们假定第二阶段中所有参赛者总是采用均衡策略，并研究第一阶段中竞赛设计者设置竞赛的竞争行为和均衡策略。

在不可分模型中，每个竞赛设计者只能举办一场竞赛。此时我们注意到，即使对于最简单的实例，子博弈精炼纳什均衡也常常不存在。例如，考虑  个完全相同的参赛者和  个完全相同的竞赛设计者构成的实例，不妨设  ，  ，我们可以说明此时不存在子博弈精炼纳什均衡。具体地，这一实例满足如下性质：如果固定所有竞赛的设置，而单独改变一个竞赛中提升系数的设置，以最大化此竞赛中两参赛者投入的总努力值，那么最优的提升系数是“平衡的”，即恰好使双方的获胜概率都等于  。事实上，已有文献指出这一性质在某些模型下总是成立的。根据这一性质，我们可以作出分析：假如存在均衡，可以得出两个竞赛设计者邀请的参赛者恰有一位重合，不妨设  ，  。由前述性质，  和  中参赛者都各有  概率获胜。注意到参赛者2、3分别在参加的竞赛投入全部努力，参赛者1向两个竞赛各投入  努力，故两个竞赛的提升系数满足  。然而，此时任何一个设计者都有动机偏离此状态，例如当设计者2改变  并设置最优的提升系数时，可以发现  中的提升系数  造成参赛者1比参赛者3的获胜概率更大，即不再最优，于是这使得设计者1的效用降低，而设计者2的效用提高。

这表明子博弈精炼纳什均衡的要求过强，为了分析设计者的策略行为，我们放松均衡解概念的定义，将竞赛设计者阶段划分为两个子阶段，在第一个子阶段中所有设计者设置并固定竞赛的参赛者和奖金，而在第二个子阶段中所有设计者设置竞赛的提升系数。将此时的序贯均衡称为弱均衡。我们通过后向归纳分析，证明了弱均衡在所有实例中都存在。首先，对于第二子阶段，我们发现虽然在一些情况下最优提升系数并不一定是平衡的，但如果所有竞赛都使用平衡的提升系数，那么每个竞赛的提升系数都达到最优，也就是形成第二子阶段的一个均衡。对于第一子阶段，我们证明假定所有竞赛都使用平衡的提升系数时，那么第一子阶段中设计者总是使用全部预算作为奖金，并且对于参赛者的选择等价于一种加权拥塞博弈。基于拥塞博弈的相关结果，我们证明第一子阶段存在纯策略均衡，进而证明了弱均衡的存在性。

在可分模型中，每个设计者可以举办任意数量的竞赛，这允许设计者更加平滑地调整奖金分配以达到均衡。但另一方面，同一设计者的不同竞赛之间存在着相互影响和竞争，这使得策略的制定更加复杂。我们注意到，在一些情况下即使所有竞赛都使用平衡的提升系数，设计者仍然可能有动机更改提升系数。尽管如此，我们对于大多数实例证明了子博弈精炼纳什均衡一定存在。具体地，假设参赛者的最大总努力值不超过全体参赛者努力值总和的一半，即  ，那么我们可以构造设计者和参赛者的一组策略，形成子博弈精炼纳什均衡。同时，这一均衡具有以下性质：

1. 每个竞赛中两个参赛者的获胜概率各为  ；

2. 每个设计者向各参赛者分发的奖金与其总努力值成比例；

3. 每个参赛者从各设计者获得的奖金与其预算成比例。

总的来说，这一均衡下奖金和努力的分配都具有均匀性，也可以理解为一种公平性。

05

结  论

本文研究了一个多场成对抽奖竞赛的博弈模型，对于此模型下参赛者和竞赛设计者的均衡行为都给出了较好的刻画。本文成果能够帮助更好地理解现实中的多竞赛场景下的博弈行为和设计高效的竞赛规则，并为分析更一般的模型下的多竞赛博弈提供了基础。

图文 | 李宁远

PKU daGAME Lab

算法博弈论实验室

Distributed and Automated Games and Managerial Economics Lab

算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。关注计算与通讯技术兴起中应用领域的问题，特别关注互联网广告机制设计、共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。

↑↑扫码转实验室主页↑↑

实验室 PI 简介：邓小铁 讲席教授

实验室相关新闻：#PKU daGAME

daGAME近期动态

• NeurIPS 2023 Spotlight | 仿射最大化拍卖机制设计的可拓展神经网络方法

• ICML 2023 | 重复二价拍卖下有预算约束的协同竞价在线算法

• ICML 2023 | 排列等价的均衡近似器的优势与局限

• AAMAS 2023 | 纳什均衡近似器是否可学

—   版权声明  —

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

点“阅读原文”转论文链接