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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

图文 | 李宁远

PKU daGAME Lab