具有凸成本的简化最优竞赛设计

Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France14290具有凸成本的简单与最优竞赛0AmyGreenwald布朗大学计算机科学，美国普罗维登斯0TakehiroOyakawa布朗大学计算机科学，美国普罗维登斯0VasilisSyrgkanis微软研究新英格兰剑桥，美国0摘要0我们研究了一个最优竞赛设计问题，其中贡献者的能力是私有的，他们的成本是作为他们努力的凸函数，设计师寻求最大化他们的总生产力。我们解决了设计近似最优机制的问题，这些机制是鲁棒的，即它们不依赖于能力分布和成本函数的具体形式。我们证明了一个非常简单的全额支付竞赛，其中奖金平均分配给贡献者的前四分之一，是对于一类大多数凸成本函数的最优近似，当贡献者数量大于某个常数时。这个结果与线性成本的竞赛形成了对比，其中将奖金授予单个顶级贡献者（“赢家通吃”）是近似最优的；当成本是凸的时候，赢家通吃远非最优。我们通过模拟实验证实了我们近似最优竞赛设计的性能，发现其在实证性能方面比最坏情况保证要好得多。我们的结果得益于具有凸成本的最优机制设计领域的新结果，这可能具有独立的兴趣。0ACM参考格式：Amy Greenwald，Takehiro Oyakawa和VasilisSyrgkanis。2018。具有凸成本的简单与最优竞赛。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318604801 引言0Netflix挑战是一个比赛，Netflix从公众中征集预测算法，并承诺如果某个团队的准确度超过他们自己的准确度至少10%，将获得100万美元的奖金。这种众包比赛在网络经济中变得普遍：Kaggle竞赛、用户生成内容和Topcoder都是众包比赛的例子。由于主办方的目标通常取决于贡献的质量，一个明显的问题出现了：如何设计能够激发潜在贡献者之间最大创新的比赛。虽然这类问题最早由弗朗西斯∙高尔顿在1902年提出，但网络上的比赛普及性激发了计算机科学和经济学交叉领域的更近期研究，解决了最优比赛设计的问题[3,9,11,12,14-17,20]。从经济学文献中的一项开创性工作[22]开始，典型的比赛设计模型制定了一个游戏，其中有一个奖金。0本文发表在知识共享署名4.0国际（CC BY4.0）许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31860480根据他们的贡献质量，奖金将分配给玩家。他们的质量水平是一个战略决策，玩家会因此选择而产生成本（以必要的努力形式），这些成本取决于这个选择。玩家还拥有私人能力，可以抵消他们的成本：即，更有才能的玩家可以用更少的努力产生相同质量的贡献。因此，每个玩家的目标是通过做出有价值的贡献来最大化他们的奖金份额，同时最小化他们的努力/成本；他们的效用是这两个数量之间的差异。现有关于最优竞赛设计的大部分工作要么假设玩家基本上具有相同的能力[14-17]，要么成本是贡献质量的线性函数[3,9,11,20]。然而，构建高质量贡献所需的努力自然以非线性方式增加。设计一个模板化的解决方案很容易；而创造一个原创设计则更加困难。换句话说，努力通常以（显著）递减的方式表现。著名的80/20法则，即“20%的工作让你达到80%的目标”，就捕捉到了这种非线性关系。解决同时具有非线性成本和异质能力玩家的竞赛设计问题的困难在于，这两个因素的结合使得竞赛设计问题等同于具有非准线性效用函数的机制设计问题。因此，与线性成本（和准线性效用）的情况不同，Myerson关于最优机制设计的标准结果[23]并不完全适用。在这项工作中，我们研究了具有凸成本（因此，凹效用）和来自某个先验分布的异质玩家能力的最优竞赛设计。此外，根据最近关于无先验机制设计的文献[19,25]，我们的目标是设计简单的近似最优竞赛，这些竞赛与设置的细节无关，对于我们的情况来说，这意味着先验分布的细节或成本函数的细节。我们使用Moldovanu和Sela的经典工作中提出的一般模型进行研究[22]。设计师的目标是最大化玩家贡献的总质量，假设玩家为贡献p付出了成本c(p)/v，其中v是能力，c是一个凸函数。如果一个玩家赢得奖金x，那么他们的整体效用是u(x,p;v)=x-c(p)/v。尽管定义了这个一般模型，[22]只在线性成本的情况下获得了最优或近似最优的结果。对于凸成本，他们分析了最多可以分配给两个贡献者的机制，在这种情况下，他们陈述了仅分配给顶级贡献者（即“赢家通吃”）是最优的条件。然而，对于凸成本，赢家通吃的分配可能非常次优。01 等价地说，他们在做决策时不知道自己的能力。2其他研究分析了各种固定竞赛机制的均衡和性能特性[12]。3在完整版本中，我们提供了一个具体的例子，其中赢者全拿的竞赛的低效性随着参与者数量的增加而增加。Given this simulation theorem, it suffices to focus on direct mech-anisms, which we do, using the language of contests (i.e., ability, forvalue, and contribution, for payment). As already noted, Myerson’stheory of optimal mechanism design is not fully applicable in ourconvex cost model. Hence, we begin by deriving an upper boundon the total contributions achievable by any direct mechanism.Subsequently, we analyze a simple class of threshold mechanisms,where the prize is equally divided among all contributors whoseability surpasses some threshold. We show that very simple thresh-olds, including the median of the ability distribution as well as arandomly sampled ability, achieve a constant-factor approximationto our upper bound on the optimal, and hence the optimal.We then show that when the number of contributors is largerthan a constant,4 an approximately-optimal threshold mechanismcan be well approximated (at the loss of an extra constant factor)by a contest that awards the prize to a carefully chosen top fractionof contributors. For instance, awarding the top half of contributorsis similar to the threshold mechanism that awards all contributorswhose ability is above the median; likewise, for other quantiles ofthe ability distribution. This observation allows us to establish ourmain result: awarding the top quartile of contributors is a constant-factor approximation to the optimal contest. We note, once again,Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France14300结果摘要。我们的主要结果是证明了一个简单的竞赛，将奖励平均分配给前四分之一的贡献者，对于一大类能力分布（有界单调危险率分布）和形式为 c ( p )  =  p d 的凸成本函数（其中 d ≥ 2是凸性的度量），当贡献者的数量大于某个常数时，可以实现对最优解的常数近似。我们的结果是通过一个模拟定理（对于所有凸成本函数都成立）实现的，该定理使得直接机制的中期结果（设计者征询玩家的私人能力，然后决定每个玩家应该贡献多少以及每个玩家将获得多少分配）可以作为竞赛的贝叶斯纳什均衡（BNE）来实现，玩家选择自己的贡献质量。这个模拟定理与启示原理一起，建立了最优机制设计和最优竞赛设计之间的等价关系。这个等价关系有两个主要的含义：0(1)这指出了在具有凸成本的情况下进行最优竞赛设计的困难，因为它是具有非准线性效用的最优机制设计的一个实例。因此，尽管我们的主要结果依赖于特定形式的单项式成本函数（ c ( p )  =  p d），即使是这一小步的难度也是显而易见的。0(2)它表明，限制在竞赛中并不需要设计者在性能上做出任何牺牲（假设他们愿意接受BNE实现）。即使设计者试图设计一些更复杂的机制，任何这样的机制都可以通过启示原理实现为直接机制，而任何直接机制都可以通过我们的模拟定理实现为竞赛的BNE。因此，任何间接机制的总转移（无论如何解释：例如收入、贡献等）都可以在某个竞赛的BNE中实现。0这取决于能力分布的上界与中位数之比的对数。0这个结果的特点与线性成本模型的特点非常不同，在线性成本模型中，最优的设计是赢者通吃。当成本是凸的时候，更好的方法是激励多个贡献者提供额外的努力，而不仅仅是那些能力最强的人。最后，我们通过模拟实验评估了所提出的竞赛的性能。我们展示了四分位竞赛和其他更精细的竞赛，其阈值取决于成本函数的凸度，平均表现显著优于我们定理的最坏情况界限。我们的结果对于非准线性效用的收入最大化有着重要意义[1，7，13，18，21，24]。一个含义是，假设我们的效用函数形式，存在一个先验无关的近似最优机制，这对于Myerson关于最优拍卖设计的文献可能具有独立的兴趣。02全付竞赛模型0我们考虑一个竞赛模型，我们将其称为“全付”竞赛模型，因为它可以理解为全付反向拍卖。在这个模型中，竞赛设计者有一单位的奖金要授予一组n个贡献者/玩家。每个玩家i∈N={1，...，n}都有一个私人能力vi，从连续概率密度为f的原子分布F中独立地抽取，该概率密度在支持集上严格为正，支持集是闭区间T=[0，¯v]。我们用v=(v1，...，vn)∈Tn表示一个样本能力向量，从分布Fn中抽取。在能力的条件下，每个玩家i选择一个贡献质量bi∈Rn，我们在此仅称之为贡献。为了贡献bi，玩家i需要承担成本ci（bi）/vi，其中ci：R≥0→R≥0是一个递增的连续凸成本函数，满足c（0）=0。给定贡献向量b=(b1，...，bn)∈Rn0然后设计者选择一个奖金分配x（b）∈[0，1]n，使得∑i∈Nx（b）=1。玩家i的效用是获得的奖金减去承担的成本：0ui（bi，b-i;vi）=xi（bi，b-i）-ci（bi）/vi。 （1）0对于向量b等，我们使用符号b=(bi，b-i)来区分玩家i在竞赛中的角色和其他玩家N\{i}。0解决概念。我们假设每个玩家选择一种贡献方式，以便在自己的能力和对手能力的期望上最大化他们的预期效用。形式上，如果存在一个函数向量b（v）=（bi（vi），...，bn（vn）），满足以下条件，则向贝叶斯-纳什均衡（BNE）：�i∈N，�vi∈[0，¯v]，�b'i∈R≥0，0E v-i [ui（bi（vi），b-i（v-i）;vi）]≥E v-i0ui（bi'，b-i（v-i）;vi）。（2）0设计者的目标是设计一种分配规则，以在产生全付竞赛的BNE时最大化总预期贡献，即：E v[∑i∈Nbi（vi）]。0效用转换。出于技术原因，将上述竞赛模型转化为数学上等价的模型更为方便，其中玩家的效用形式为：0ui（bi，b-i;vi）=vi xi（bi，b-i）-ci（bi）。 （3）0由于玩家在自己的能力条件下最大化效用，所以在方程（1）中最大化效用等价于在方程（3）中最大化效用，两者之间的差异是常数因子vi。后一种形式的效用更方便，因为它允许ui wi, w i;vi = vixi wi, w ici pi wi, w i ,(4)14310我们将设置解释为正向方向，其中玩家i的价值（能力）为每单位商品（奖品）的vi，并且产生的成本是他的付款（贡献）bi的函数。然后，我们可以利用在收入最大化文献中开发的广泛工具箱。这种效用转换在先前关于具有线性成本的竞赛的工作中也被使用[9, 11, 20]。0直接机制。根据经典的揭示原理[23]，全付竞赛在结果上等效（即，在私人信息（即能力）的条件下，引起相同的奖品分配和每个玩家的相同贡献）为所谓的直接机制。在直接机制中，设计者直接引导玩家的私人信息，而在我们的设置中，这是每个玩家i的能力报告wi∈T。给定报告向量w=(w1,...,wn)∈Rn，对于所有i∈N，机制由分配规则x(w)∈[0,1]n定义，使得∑i∈Nxi(w)=1，以及贡献规则p(w)∈Rn≥0，指定每个玩家i所需的贡献pi(w)。然后，每个玩家i的效用为：0为了方便阅读，我们经常写c i ( w i ,  w − i )代替c i ( p i ( w i ,  w −i))。这是玩家i的成本，它取决于他们的贡献pi(w)。类似于贡献规则，我们将由ci(wi,w−i)组成的ci(w)∈Rn≥0称为直接机制的成本规则。给定一个直接机制，我们分别定义中期分配、中期贡献和中期成本规则，如下：ˆxi(wi)=Ew−i[xi(wi, w−i)]；ˆpi(wi)=Ew−i[pi(wi,w−i)]；ˆci(wi)=Ew−i[ci(wi,w−i)]。这些变量是每个玩家的预期分配、贡献和成本，作为他们报告的函数。我们称机制为贝叶斯激励兼容（BIC），如果在期望中通过真实报告来最大化效用，假设其他人也是真实的：�i∈N和�vi,wi∈T，viˆxi(vi)−ˆci(vi)≥viˆxi(wi)−ˆci(wi)。中期个体合理性（IIR）要求期望中的效用为非负，再次假设其他人是真实的：�i∈N和�vi∈T，viˆxi(vi)−ˆci(vi)≥0。设计者的目标是找到一个BIC和IIR机制，最大化总预期贡献，定义为Ev[∑i∈Npi(v)]=∑i∈NEvi[ˆpi(vi)]。0引理2.1（揭示原理的应用）。在某个BNE上，全付竞赛可实现的总预期贡献也可以通过直接的BIC/IIR机制实现。0这个引理是众所周知的揭示原理的一个应用（以及一个简单的事实，即在竞赛的BNE上，所有玩家都获得非负的中期预期效用），因此省略了其证明。直接机制的分配和贡献规则模拟了全付竞赛的分配和支付规则；而且，由于模拟了BNE，所以这个模拟必然是BIC和IIR的。更有趣的是，在下一节中，我们将展示另一个方向也成立，即任何直接的BIC/IIR机制的总预期贡献都可以作为全付竞赛的BNE实现。通过这种方式，我们建立了最优直接机制和最优全付竞赛之间的等价关系。0直接机制的特征化。Myerson[23]表明，要使机制满足BIC和IIR，需要满足几个条件0需要满足。其中，必须使用特定的成本公式。我们在此重述他的结果，适应我们的设置。为简单起见，我们假设报告零能力的效用为零：即，对于所有i∈N，ui(0,b−i)=0，正如我们所有机制的情况一样。0引理2.2（[23]）。机制是BIC和IIR的充要条件是以下条件成立：•分配规则是单调的：0ˆxi(vi)≥ˆxi(wi),�i∈N,�vi≥wi∈T,(5)0•中期0viˆxi(vi)−ˆci(vi)=∫vi0�i∈N,�vi∈T,0ˆxi(zi)dzi(6)0此外，这种机制的总预期成本可以用虚拟价值函数φi来描述，定义如下：0φi(vi)=vi−1−Fi(0fi(vi).(7)0定理2.3（[23]）。在BIC/IIR机制中，玩家的总预期成本满足：0i∈NEvi�Fi[ˆci(vi)]=�0i∈NEvi�Fi[φi(vi)ˆxi(vi)](8)0在传统的准线性设置中，Myerson的定理告诉我们，预期虚拟剩余（方程（8）的右手边）等价于总预期贡献（方程（8）的左手边，假设成本函数是恒等函数）。根据这个结果和即将出现的模拟定理，我们可以推断出，为了最大化贡献，奖励应该分配给具有最高非负虚拟价值的玩家。然而，在凸成本设置中，Myerson的引理（方程6）不能确定玩家的中期贡献；它只限制了他们的中期成本。因此，虚拟价值表征定理对于最优机制并没有提供太多启示。0所有付费竞赛的BNE是最优的0我们现在提出我们的模拟定理：BIC/IIR直接机制可以实现的总预期贡献也可以作为某个全付费竞赛的BNE实现。这个定理是引理2.1中应用启示原理的逆向结果。在我们证明这个命题之前，我们首先证明一个引理，它连接了BIC/IIR直接机制中的中期成本和中期贡献。具体地说，我们证明了对于所有可能依赖于v−i的贡献规则pi(v)，存在一个与v−i无关的相应贡献规则hi(vi)，并且它实现的总预期贡献至少与之一样高。考虑一个随机化的直接机制A，其中pAi(vi,v−i,r)表示机制A中玩家i的贡献，r是某个随机化设备的结果。我们定义另一个直接机制B，其贡献规则为：0pBi(vi,v−i,r)=ci−10�Ev−i,r0证明。我们从第一部分开始。观察到所提出的贡献规则保持了中期成本，因此也保持了中期效用。更具体地说0我们将后者简写为hi(vi)；注意它只依赖于vi。0引理3.1.对于直接机制A，任意分配规则x和相应的贡献规则ˆpA或ˆpB，如果它满足BIC和IIR，则它满足直接机制B的BIC和IIR。此外，B的总预期贡献至少等于A的。0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, France14320证明。我们从第一部分开始。观察到所提出的贡献规则保持了中期成本，因此也保持了中期效用。更具体地说：0ˆcBi(vi)=Ev−i,r0证明。我们从第一部分开始。观察到所提出的贡献规则保持了中期成0=ci0�c−1i0�Ev−i,r0�ci�pAi(vi,v−i,r)����=ˆcAi(vi)。0因此，对于所有玩家i∈N和能力vi,wi∈T，当且仅当viˆxi(vi)−ˆcBi(vi)≥viˆxi(wi)−ˆcBi(wi)时，viˆxi(vi)−ˆcAi(vi)≥viˆxi(wi)−ˆcAi(wi)，且viˆxi(vi)−ˆcBi(vi)≥0当且仅当viˆxi(vi)−ˆcAi(vi)≥0。现在我们证明第二部分。由于ci(∙)是凸函数，根据Jensen不等式，0hi(vi)=c−1i0�Ev−i,r0�ci�pAi(vi,v−i,r)���0≥Ev−i,r0�c−1i�ci�pAi(vi,v−i,r)���=Ev−i,r0�pAi(vi,v−i,r)�。0换句话说，机制B中的贡献只能超过机制A中的贡献。因此，机制B的总期望贡献至少与机制A的总期望贡献相同。□0这个引理意味着，在我们寻找最优直接机制时，我们只需要限制我们的注意力在像机制B这样的机制上，其中每个玩家i的贡献是一个（确定性）函数i的能力：0推论3.2.对于任何BIC/IIR直接机制，存在一个相应的机制，其总期望贡献至少与之相同，其中每个玩家的贡献仅是他们自己能力的确定性函数，给定为：对于所有i∈N，对于所0hi(vi)=c−1i(ˆci(vi))=c−1i0� viˆxi(vi)−∫vi00ˆxi(zi)dzi0�. (9)0这个推论还允许我们证明我们承诺的模拟定理，即总是存在一个全付费竞赛和一个相关的BNE，其实现了最优BIC/IIR直接机制的总期望贡献。关于该定理的证明可以在附录A.1中找到。0定理3.3（全付费竞赛最优性）。对于任何BIC/IIR直接机制，存在一个相应的全付费竞赛，其对应的BNE实现了至少与之相同的总期望贡献。特别地，最优解是可实现的。0我们将在后面看到（参见引理7.1），方程（9）导致了最优直接机制的贡献的简单计算，因此根据定理3.3，导致了最优全付费竞赛。然而，这种联系仍然不能得出最优直接机制或竞赛的清晰特征，因为凸优化问题的解可以是任意复杂的。为了实现我们的主要定理，我们在第5节提出了近似最优的简单机制。为了确定它们的近似比率，我们首先证明了最优竞赛的总期望贡献的上界。04. 最优的上界0我们首先根据仅基于IIR属性的最优机制的总期望贡献证明一个上界。我们0引用[18]中的一个简单论证，即在对称设置中，即假设成本函数ci(∙)和能力分布对所有玩家都相同的情况下，最优机制也必须是对称的。0引理4.1（[18]）。如果所有玩家的成本函数ci(∙)和能力分布都相同，则存在一个对称的最优BIC/IIR机制，其结果在玩家之间是对称的。0n�1/d，对于d≥2。0证明.根据引理4.1，我们只需要考虑对称机制。此外，根据推论3.2，我们只需要对形式为方程（9）给出的贡献规则的机制的总期望贡献进行上界限制。（关键是要观察到，当所有玩家的成本和能力分布相同时，引理3.1保持对称性）。因此，我们只需要考虑每个玩家的贡献仅是他们自己能力的确定性函数的对称机制。对于任何这样的机制，对于任何玩家i∈N，根据IIR：0hi(vi) = c-1i(ˆci(vi)) ≤ c-1i(viˆxi(vi)) = vi^1/dˆxi(vi)^1/d (10)0因此，第i个玩家的预期贡献被上界0Evi[hi(vi)] ≤ Evi0vi^1/d(ˆxi(vi))^1/d (11)0根据柯西-施0Evi0vi^1/d(ˆxi(vi))^1/d≤0Evi0vi^2/d≤0Evi0(ˆxi(vi))^2/d (12)0当d ≥ 2时，函数x^2/d对于x ≥0是凹的。因此，根据Jen0Evi0vi^2/d ≤ Evi[vi]^2/d = µ2/d (13)0Evi0(ˆxi(vi))^2/d ≤ Evi[ˆxi(vi)]^2/d (14)0根据对称性，对于任意i ∈ N，Evi[ˆxi(vi)] =κ，其中κ是某个常数。然后根据可行性，κ = 1/n，因为ΣiEvi[ˆxi(vi)]= Ev[Σix(v)] = 1。将0Evi[hi(vi)] ≤ µ1/dΣ(1/n)01/d (15)0然后根据OPT = Σi Evi[hi(vi)]，定理得证。□0MHR分布的改进。我们通过提供对于单调危险率（MHR）分布情况下最优贡献的更有用的上界来结束本节。为此，我们引入与分布F的性质相关的一些有用的符号和术语。对于任意分布F，令q(v) = 1 - F(v)为分位函数，令v(q) =q-1(∙)为逆分位函数。换句话说，能力v的分位数是从F中随机抽取的值超过v的概率。观察到分位数在[0, 1]上均匀分布。我们用κ =v(1/2)表示分位数1/2对应的值：即中位数。在通常的准线性设置中，与能力分布F相关的收入函数R(q)定义为R(q) = v(q)q = v(q)(1 -F(v(q)))。直观地说，这个公式表示一个卖家发布一个保留价格为v(q)（即以概率q被超过的价格）。由于F是支持为[0, ¯v]的无原子分布，R(0) = R(1) =0。最后，令q� ∈ arg max q ∈ [0, 1]R(q)为对应于最优收入的分位数，我们将其称为垄断分位数。此外，令η =v(q�)为对应于垄断分位数的发布价格，我们将其称为垄断保留价。我们将研究两个标准的分布类。较小的类是单调危险率（MHR）分布，要求h(v) = f(v)/(1-F(v))是单调非递减的。较大的类是正则分布，要求R(q)是凹函数，或者等价地ϕ(v(q)) = R′(q) = v(q) - 1 - F(v(q))0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, Franceis surpassed with probability q). Since, F is atomless with support[0, ¯v], R(0) = R(1) = 0.Finally, let q∗ ∈ arg maxq∈[0,1] R(q) be the quantile correspond-ing to optimal revenue, which we will refer to the monopoly quan-tile. Further, let η = v(q∗) be the posted price corresponding tothe monopoly quantile, which we will refer to as the monopolyreserve.We will be investigating two standard classes of distributions.The smaller class is that of monotone hazard rate (MHR) distri-butions, which require that h(v) = f (v)/(1 − F(v)) be monotonenon-decreasing. The larger class is that of regular distributions,which require that R(q) be a concave function, or equivalentlyϕ v q= R′ q = v q1(16).(17)=14330f(v(q))是单调递减的。因为0对于h(v(q))，很容易看出MHR分布也是正则的。MHR分布包含几个众所周知的家族，比如均匀分布和指数分布（参见[4]）。我们现在陈述两个引理，描述了收入曲线的上下界，这取决于对能力分布所做的假设。0引理4.3（[10, 26]）。对于任何正则分布，R(q�) ≤κ。对于任何MHR分布，R(q�) ≥ µ/e。0这个引理意味着对于MHR分布来说：µ ≤ eR(q�) ≤eκ。将这个结果与定理4.2结合起来，我们得出结论：0推论4.4.如果能力分布F是一个MHR分布，那么OPT ≤ n(eκ/n)1/d。05 QUANTILE THRESHOLD MECHANISMS0现在我们转向设计简单无细节的机制和竞赛。我们从量化阈值机制开始分析：即，将奖励均匀分配给所有能力vi高于某个能力阈值的玩家，或者等价地，给那些量化qi低于某个量化阈值的玩家。在这些机制中，根据方程（9）的表征要求玩家贡献，这使得机制具有BIC和IIR性质。对于阈值为ˆq的量化阈值机制，这个贡献采取简单的形式：0hi(vi) = c-1i0v(ˆq) 1/vi ≥ v(ˆq) Ev-i0除以101 + Σj≠i 1/vj ≥ v(ˆq)0除以d的1次方0全额支付实施。根据定理3.3的相同论证，阈值为ˆq的量化阈值机制可以作为全额支付竞赛来实施。实际上，对于量化阈值机制，这个竞赛具有简单的形式。我们省略以下引理的证明，因为它与定理3.3的证明类似。0引理5.1（量化阈值机制的竞赛实施）。考虑一个全额支付竞赛，将奖励均匀分配给所有贡献bi ≥ b�i的玩家i，其中：0b�i = c-1i0v(ˆq) Ev-i0除以101 + Σj≠i 1/vj ≥ v(ˆq)0除以d的1次方0存在一个与阈值ˆq相同的量化阈值机制的BNE，其实现了相同的总预期贡献。0当所有玩家具有相同的成本函数，并且能力是从独立和相同分布中抽取的时候，这个全额支付竞赛为所有玩家设置相同的贡献阈值，并且采用在实践中普遍存在的直观形式（例如，徽章机制[2]）。我们还注意到，这个阈值机制可能有多个均衡，但只有一个均衡实现了与原始机制相同的结果。在下一节中，我们构建了具有唯一均衡的近似最优竞赛。我们从分析阈值为ˆq的量化阈值机制的预期贡献开始，其中玩家具有形式为b的成本函数。0引理5.2.考虑形式为c i (b) =b的d次方的凸成本，对于所有的i∈N，其中d≥1。设APX(ˆq)是一个机制中在所有玩家之间均匀分配的总预期贡献，其中q i ≤ˆq，并且出0APX(ˆq) ≥ n乘以v(ˆq)01 +(n-1)的q次方0除以d的1次方的ˆq ≥n乘以1-1/d乘以v(ˆq)的1/d次方的ˆq。（18）0证明。根据贡献等式（方程16），根据Jensen不等式，由于1/(1+x)是一个凸函数，并且因为v i ≥ v(ˆq)的概率是1-F(v(ˆq))=ˆq:0hi(vi) ≥0v(ˆq)≥v(ˆq)的概率01 + Σj≠i Evj[1/vj ≥v(ˆq)]0除以d的1次方 =v(ˆq)≥v(ˆq)的概率01 +(n-1)的ˆq次方0除以d的1次方0根据预期贡献的定义0APX(ˆq) =0n0i = 1 Ev i �F0除以d的1次方01 +0除以d的1次方0n次0i = 10v(ˆq)01 + (n -01 / dˆq.0我们已经证明了方程（18）的第一部分。第二部分通过注意到ˆq ∈[0, 1]得出。□0无细节机制。我们现在展示，如果设计者对能力分布有一定的了解，机制可以产生比其他情况下更大的总期望贡献。具体来说，了解分布的中位数可以获得更好的近似比率。我们通过提供两个无细节机制的例子来结束本节，这些机制通过优化分位数阈值ˆq来获得更好的近似比率。0定理5.3（中位数阈值）。当能力阈值κ（即ˆq = 1 /2）时，机制的近似比率为：0APX OPT≥ 102n0e(n + 1)01 / d. (19)0中位数机制可以在全付竞赛的BNE下实现，该竞赛将奖励均匀分配给所有贡献超过以下阈0b* = κ(2 - 2n - 1)0n0≥ 1 / d (20)0证明。当ˆq 时，0APX ≥ nκ01 + (n - 1) /201 / d102 = n02κn +101 /d,0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, France=1In order to avoid a dependence in our analysis on a lower boundon the density of the ability distribution, we actually propose amore competitive all-pay contest where we allocate to a smallerfraction of the contributors. In the theorem that follows, we pickthe top quarter, but we note that the constants could be furtheroptimized by picking a more involved fraction. The proof of thistheorem appears in Appendix A.3.6Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France14340根据定理4.4，0APX OPT≥ n02κn +101 / d 10n(d - 1) / d(eκ)^(1/d)0= 102n0e(n + 1)01 /d0该定理的最后部分由引理5.1得出，并且通过观察对于中位数分位数：0E(v -i)0101 + ∑ j ≠ i 1 v_j ≥v(ˆq)0≤02n -10n -10t = 00n - 1≤ t010t + 1 = 2 - 2(1 - n)0n0□02 ≤ 2e ≤ 1 / d。当 d ≥ 2 时，这个比率至少为0.42。此外，当 d趋近于无穷大时，比率趋近于1/2。接下来，我们将展示如果我们使用一个也依赖于成本函数凸度 d的分位数阈值，那么我们可以进一步改善近似比率。关于该定理的证明和分析将推迟到附录A.2。0定理5.4（成本优化阈值）。假设能力分布满足单调危险率（MHR）条件，并且对于每个玩家i ∈ N，成本函数的形式为ci(b) = bd，其中d ≥ 2。那么，具有阈值ˆq = max{1/ d,}的分位数阈值机制可以实现总期望贡献：0n + 1 / d 10至少有以下比例的最优解：n0d ∈ [2,3)，以及n02√e for0(4e(d - 2))^(1/d) fo≥ 3.0n + 1 / d 10观察到对于 d → ∞，这个界限收敛到1，因为 (d - 2)^(1/d) →1。因此，随着支付函数变得更加凸，成本优化的储备机制趋近于完全最优。此外，像中位数阈值机制一样，成本优化的阈值机制也可以作为适当选择的贡献阈值的全付竞赛的BNE来实现（详见附录A.2）。我们已经看到，将奖励均匀分配给所有贡献超过某个阈值的玩家的简单竞赛可以获得最优的常数近似。虽然它们是无细节的，即它们不需要完全的分布知识，但它们需要一些关于分布和/或成本函数的知识才能实施。在下一节中，我们将完全消除对分布和成本函数的依赖，代价是假设贡献者的数量大于某个常数。0注1（对于收入最大化的影响）。在我们继续进行鲁棒最优竞赛的努力之前，我们注意到本节的结果对于具有非准线性效用的收入最大化问题具有影响。特别地，如果我们用支付替代贡献，那么我们的设置的最优机制设计问题就是一个玩家支付的成本是其支付的凸函数的收入最大化问题。根据这种解释，定理5.3表明，随机均匀分配给所有价值高于价值分布的中位数的玩家是最优收入的一个常数近似。使用类似的技术，我们还可以证明，与其选择中位数阈值，选择一个从价值分布中随机抽取的阈值也会导致一个常数因子的近似。0近似。值得注意的是，这种机制可以完全无先验地实施，其中我们使用一个玩家作为阈值设定者，并随机均匀分配给所有剩余玩家，其价值高于阈值设定者的价值。这个结果是我们设置的经典结果Bulow和Klemperer[6]的类比。最后，所有这些机制都可以以一种使真实报告成为事后优势策略的方式实施，而不仅仅是确保机制是BIC的方式。06 主要结果：先验和成本独立竞赛0在本节中，我们提出了我们的主要结果：一种几乎最优的全付竞赛，它不依赖于能力分布或成本函数的凸度d。我们从我们的分位数阈值机制及其全付竞赛实现中获得直观。我们看到这些竞赛是几乎最优的，但面临一个困难：适当的贡献阈值的设置，以便它转化为目标分位数阈值（对应于目标能力阈值），取决于指数 d。因此，似乎不太可能存在一个适用于所有 d的通用