自动出价拍卖设计：随机化提高了VCG之外的效率

1731+C≥ ∈（/）（）下一页2α2+1+自动出价环境下的拍卖设计：随机化提高了VCG之外的效率Aranyak Mehta谷歌研究美国加利福尼亚州aranyak@google.com摘要自动出价是在线广告领域中日益重要的领域。我们研究了在自动投标环境下，以系统均衡时福利最大化为目标的拍卖设计问题。先前的结果表明，在VCG下的无政府状态（PoA）的价格是2，并且即使有两个投标人，这也是紧 这就提出了一个有趣的问题，即VCG是否在这种情况下产生最佳效率，或者PoA是否可以改进。我们提出了一个事先免费的随机拍卖，其中的PoA是约。1.896的情况下，两个投标人，证明一个可以实现的效率严格优于在VCG在这种设置。我们还提供了一个明显的不可能的结果，一般的问题，因为投标人的数量增加-我们表明，没有（随机）匿名真实拍卖可以有一个PoA严格优于2渐近每个查询的投标人的数量增加。虽然它在以前的工作中，可以提高PoA的2，如果拍卖被允许使用投标人的价值的查询除了投标人的出价，我们注意到，我们的随机拍卖是事先免费的，不使用这样的额外信息，我们的不可能性结果也适用于拍卖没有额外的价值信息。CCS概念• 应用计算机→经济学。关键词拍卖设计，自动竞价，均衡ACM参考格式：阿拉尼亚克·梅塔2022.自动出价设置中的拍卖设计：随机化提高了VCG之外的效率。在ACM Web Conference 2022（WWW '22）的会议记录中，2022年4月25日至29日，虚拟活动，法国里昂。ACM，New York，NY，USA，9页。https://doi.org/10.1145/3485447.35120621引言自动出价是在线广告生态系统中越来越重要的领域（参见，例如，[9，13]，近年来有重大创新和采用。 通过自动出价，每个广告客户向自动出价代理陈述其目标和限制，然后自动出价代理将其转换为每次拍卖的出价。在一个所有人本 作 品 采 用 知 识 共 享 署 名 国 际 协 议 （ Creative Commons AttributionInternational）授权4.0许可证。WWW广告客户使用自动出价，每个广告客户一个代理，相对于其他代理最优地出价。然后，我们感兴趣的是系统平衡的性质。一个典型的自动出价设置是每次获取目标成本（tCPA），其中广告客户的目标是最大限度地提高他们的转换（广告点击后的销售），但要遵守ROI约束，即每次转换的平均成本不大于给定的目标。广告支出目标回报率（tROAS）将tCPA推广为也考虑转化的价值最近的研究抓住了这一背景下的理论问题在文献[1]中，作者介绍了在广告主目标和约束下的自动出价问题，并给出了两个结果：第一，他们给出了一个出价公式，以最优出价进入真实拍卖。其次，他们证明了无政府状态的价格结果：如果所有广告客户都采用这种最优自动出价来竞标（按查询）VCG拍卖，那么均衡时的福利至少是最优分配所获得的价值的一半。 他们还提出了一个问题的例子（有两个投标人），其中存在一个均衡，福利等于最优的一半，这表明他们的分析是严密的。因此，他们表明，在VCG下无政府状态（PoA）的价格是2. 进一步的研究[6]通过允许拍卖访问广告商的价值来改进PoA2。例如，他们表明，通过增加每个投标人的 出 价 等 于 广 告 价 值的c倍，然 后运行第 二价格拍 卖产生的PoA 为 2 + c。在本文中，我们研究了拍卖的设计，以改善在[1]中介绍的设置的PoA 与[6]中所采取的方向相反，我们考虑拍卖无法获得任何其他信息（例如，值）之外的出价。这种限制具有实际的动机：拍卖可能无法获得每个展示的价值，例如，将价值、目标和约束转换成出价的出价系统可以是单独的系统，或者甚至可以由不同于拍卖平台的第三方拥有。此外，与贝叶斯设置相反，我们不假设拍卖可以获得价值或目标的分布，或者确实存在这样的潜在分布我们的拍卖是免费的 我们提出这样一个问题：除了出价之外，在没有任何额外信息的情况下，是否有可能在无先验设置中改进VCG？1.1结果首先考虑两个投标人的情况，引入一个简单的无先验随机真实拍卖R和α，p（参数为常数α1，概率p0， 12）和d显示（定理1）在p=2和α∈ [1，1+1，85]的情况下，©2022版权归所有者/作者所有5 62α +6+2ACM ISBN 978-1-4503-9096-5/22/04。https://doi.org/10.1145/3485447.3512062拍卖的无政府状态的代价并不比α。选择α174≥≥≥（）下一页.（）下一页（）下一页∈∈WWWα = 1 +85 1 703，这表明R和（α nd，2）的PoA是后者描述了几种不同的设置模式）;在COM-6约1. 896. 我们还证明了（定理25）我们的分析我们的工作不考虑广告商的激励措施（例如，到对于α的这个范围是紧的，即， 存在误报目标的情况），但仅误报系统响应（如[1，6]中）。研究生福利（22α +6+2这里引入的拍卖（RA nd（α，p））让人想起auc-α，5）在平衡时正好是2 α 1α。我们注意到在一些以前的研究结果。我们将定义R和+ +2当α = 1时，拍卖与第二价格拍卖相同，PoA界降为2，这意味着我们的结果严格推广了[1]中的结果.因此，我们有一个优先级自由拍卖的均衡福利严格优于VCG（[1]提供了一个严格的例子，有两个投标人的PoA的VCG）。这是令人惊讶的，并且突出了ROI约束自动出价设置与标准准线性设置之间的差异，其中VCG实现最大福利。此外，在用于改善VCG的收入的准线性设置中的类似结果取决于值的分布的先验知识（贝叶斯拍卖设计）[15]，或者取决于对其中值从来自良好形成的类（如规则分布）的一些未知分布中挑选的实例的评估（先验独立拍卖设计，例如，[7]）。相比之下，我们的结果是在无先验设置，拍卖没有其他输入，除了出价和评估的任何一组值，但改善了福利的VCG在均衡。我们注意到，我们设定的福利目标是流动福利，它既反映了支付的愿望，也反映了支付的能力 即使效用函数是非标准的，激励相容性和机制设计的问题仍然很重要：如[1]所示，只有在真实拍卖中才有一个简单的（统一的）最优投标公式。我们也只关注真实的拍卖。我们上面的结果表明，在两个投标人设置的VCG的PoA的严格改善因此，人们可以要求一种更一般地可以得到比2更好的PoA的 auc- tion虽然有可能将定理1中的分析扩展到固定数量的投标人，并保持PoA严格小于2（我们在这里不包括在这种情况下用完全不可能的结果来补充我们的正结果 我们证明了（定理5），随着投标人数量的增加（特别是每个查询投标的投标人数量的增加），则任何（随机）真实匿名拍卖的PoA渐近不超过2。这一结果解决了文献[1]中提出的无先验拍卖问题（仅限于没有任何额外信息的拍卖）。最后，我们注意到，模型，拍卖设计和分析结果是在风格和理论设置（见下文相关工作），并不意味着准确地代表现实世界的实际实现的所有方面和复杂性1.2相关工作如前所述，最密切相关的工作是[1]和[6]。文[1]中的工作介绍了这一问题，并提供了PoAα，p节中2，但非正式地说，只有当出价高的投标人的出价比另一个投标人大α 1因子时，它才分配给出价高的投标人;否则，它随机分配给两个投标人，出价高的投标人的概率更高。在文献[11]中，作者引入了一种先验独立拍卖，称为δ，δ-膨胀第二价格拍卖，其中参数δ1与我们的α参数类似，但使用方式不同：在概率为δ的情况下，它运行第二价格拍卖，而在其余概率下，最高出价者只有在其出价比下一个最高出价高出δ1倍时才获胜（否则物品未分配）。对于这个拍卖，证明了它实现了严格优于n-1的最优收入的一小部分（在标准拟线性效用集n，其中n是投标的数量两个投标人的投标率提高到0.512这个结果在文献[2]中得到了推广，文献[ 2 ]引入了一类称为阈值拍卖的先验独立拍卖，并证明了在先验独立设置下更强的收益结果，重点是两个投标人设置。实际上，R和α，p都属于阈值拍卖族人们可以预期，阈值拍卖家族的其他类似成员也可能在自动出价设置中改进VCG的PoA-尽管可能不是[ 2，11 ]中研究的特定拍卖。我们注意到，[14]在不同的背景下描述了一种类似的拍卖，称为比率拍卖流动性福利的定义在自动投标设置中的应用[1]基于[8]中为预算设置引入的流动福利定义（另见[3]）。最后，我们注意到，在基于ROI的自动投标产品（如tCPA和tROAS）之前，一个成熟且经过充分研究的模型是预算优化模型-如何在简单的预算约束下投标。在这个模型中有几条工作线，例如，[5，10]其中。2预赛2.1自动投标和tCPA/tROAS约束在[1]中介绍的一般自动投标问题中，每个广告商都有一个目标和一组约束。我们将限制我们的注意tCPA，其中广告主的目标是最大化转化的数量（点击广告后的销售），其受到转化的平均成本不超过广告主输入目标T的约束。换句话说，tCPA投标的目标是最大化转化，前提是预期花费最多为预期转化的T倍。因此，单个投标人i的问题是：最大（1）第一次见面在更一般的设置（具有多个ROI约束）中对VCG进行分析;我们将我们的分析限制为原型tCPA设置（但它直接应用于tROAS），并且还限制为每个查询设置的单个时隙。在[6]结果的背景下，有趣的是，S. t.J.Qj∈Qxijctrijcpcij T（i）J.Qxijctrijvij我们还可以在没有附加价值信息的情况下改进VCG的PoA最近也有关于理解贝叶斯设置中的最优机制设计的工作[4，12]（其中j∈Q：0≤xij≤1这里，Q是查询的集合，xij是关于广告商i是否应该购买第j个查询上的时隙的决策变量175（）下一页）≥（）（）∈∈--（{}）（{}）I（I）I（I）.≥ ∈（/）p（）下一页Ijpi′jctrijxi′j>（1+γ）αα...ΣJJ自动出价设置中的拍卖设计：随机化提高了VCG WWW'22的效率，2022年4月25日至29日为简单起见，每个查询一个时隙），ctrij是广告客户i的广告在第j个查询上的点击率（给出印象的点击概率），cpcij是广告的每次点击成本（由来自其他广告客户最后，vij是在第j个查询上广告商i的广告上的点击值对于tCPA，vij是转化率（点击的转化概率）。通过将vij取为点击之后的总值，该公式容易地扩展到tROAS，例如，销售的价值竞价公式。文献[1]证明了投标人可以根据一个简单的投标公式投标，该公式基于LP（1）的对偶变量的最优值。 如果拍卖是真实的，并且我们有最优对偶变量的正确值，那么这个出价公式是最优的，即，投标人i购买LP（1）的最优解。在上述tCPA设置中，给定最佳对偶我们对PoA的积极结果（第二节）。3）将使用平衡的精确定义（其中γ=γ=0，而我们的不可能性结果（Sec.4）对任意的ε，γ> 0成立。液体福利。 由于支出受到限制，我们需要仔细定义福利。在这种情况下，福利的适当定义是流动福利（LW），首先在[8]中针对预算分配情况定义，然后在[ 1 ]中推广到自动投标设置。流动性福利反映了支付特定分配的意愿和能力对于一般的自动投标问题（可能有多个支出约束给定分配的液体福利被定义为[1]，即该分配中投标人LP约束右侧的最小值的投标人之和tCPA LP（1）具有单个约束，并且LW变得等同于tCPA加权转换的总和：我在2号线。在tCPA设置中，对于tCPA约束，变量γi 0，投标人i的最优投标采用简单形式LW（{xij}）=.T（i）。xij国际新闻中心国际新闻报（三）1i∈Aj∈Qbid（i，j）=μi·vij，其中μi：=1+γi（2）µi≥1称为投标人A的投标乘数。均衡问 题 的 一个实例是一组查询j Q和一组投标人i A，每个都有自己的（私有）tCPA常数Ti。每个i，j对具有ctrij和值vij。我们感兴趣的分配结果时，所有的广告客户投标使用最佳投标公式（2）。注意，每个投标人的出价取决于其LP（1）的对偶最优变量，其中cpc在拍卖中基于其他投标人的出价来确定。 因此，我们必须研究处于平衡状态的系统。其中A是广告商的集合，T（i）是广告商i的目标CPA，xij表示分配，并且vij是广告商i的广告在查询j上的转化率。因此，流动福利是tCPA加权转换的总数将LWi，xi，j定义为广告客户i对液体福利的贡献（等式1）。3），并且令spendi，xij表示广告主i在拍卖中的总预期花费我们从LP（1）中看到，后者是前者的下界spend（i，{x·}）≤LW（i，{x·}）（4）无政府状态的代价被定义为1上的定义 考虑一个（可能是随机的）拍卖A和一个实例I，其中有一组投标人A和一组查询Q。 设vij为PoA=max我Maxeq∈Eq（I）LW（OPT（I））LW（当量）在该实例中，对于查询j，投标人i的值，并考虑一组投标乘数{µi}i ∈A，使得bid（i，j）：= µivij是投标人i对于查询j的投标。 令{xij}i ∈A，j ∈Q是在拍卖A下通过出价bid（i，j）实现的（概率）分配，并且令pij是针对查询j向出价者i收取的每单位价格（cpc）。当γ≥ 0时，其中表示问题的实例，Eq是实例中的均衡集，OPT表示该实例的最高流动福利2.2拍卖R and（α，p）{bid（i，j）}被称为处于（n，γ）-均衡，如果下面的成立。• 每个投标人满足其tCPA约束，直到乘法我们定义两个投标人的拍卖R和（α，p），参数为γ因子：i∈A：pij国际新闻中心xij≤（1 + γ）T（i）.国际新闻报国际新闻中心xijα1和p0， 1 2 .如SEC所述。1.2，这是来自[2]的阈值拍卖家族的成员，并且有点类似于来自[ 11 ]的出价膨胀拍卖和来自[14]的比率拍卖。j∈Qj∈Q三号线上。 让出价，并不失一般性任何投标人都不能单方面偏离其投标乘数，并在满足其tCPA约束（直至γ）的情况下获得超过10%的附加值。更准确地说，假设“我”的“我”的“我”。分配到{xi′j}，价格到{pi′j}。则n∈ Avijctrijx ′ 1）的权衡是不同的。在积极的首先，请注意，对于所有j Q，使用最优投标公式（等式2），并且每个投标人的最优投标乘数至少为1，我们得到bid（i（j），j）=μ（i）·T（i（j））·v（i（j），j）≥T（i∈（j））·v（i∈（j），j）=OPT（j）（5）查询划分：我们根据ij和io j的出价的相对值将Q划分为四个部分。对于每个部分中的查询j，我们将使用R和α的定义（3）计算p：(a) j被分配给i的概率为$j，以及(b) 查询j上的预期花费。(1) 设Q1是查询j的集合，使得它的出价比选择性出价人的出价大α倍以上，那么我们可以看到上面情况2中的属性增益，因为bid（i≠（j），j）≤bid（io（j），j）α这一支出严格大于选择性投标人3）。然而，这也带来了潜在的归因损失：当选择性投标人是最高的，但第二高的出价接近其出价，那么我们只选择选择性投标人w.p. 1 p<1，并且花费也低于第二价格拍卖。当选择性出价者不是最高出价者，但接近最高出价者时，也会出现类似的情况，在这种情况下，你会将加权平均利润分配给选择性出价者，但支出再次低于第二价格拍卖。在这种相反的情况下，只有当α和p被很好地调整到基本值时，人们才会期望在聚集体中获得增益-例如，在贝叶斯设置中，当值分布已知时，或者甚至在先验独立设置中，当存在潜在的规则或MHR类型分布时。令人惊讶的是，我们表明，对于α和p的范围，对于任何固定的值集，权衡总是对我们有利，即，以无前科的方式3.2界定行动纲领定理1. 当p = 2，α ∈ [1，1 +1，85]时，R和（α，p）的PoA对于每个j ∈ Q1，R and（α，p）将j分配给io（j）w. p. 一曰：Pr[AlgB（j）=i（j）]= 0此外，在j上的预期花费为E花j= p α+12 p + pbid ij，jα≥p·α+（1 − 2 p）+α ·OPT（j）（使用等式5）(2) 设Q2是查询j的集合，使得bidioj，j我 j，ji j，jα对于每个j∈Q2：Pr[AlgB（j）=i（j）]=p在j上的总期望花费是两个投标人的期望花费之和，其为：E[spend（io（j），j]=p·bid（i（j），j）+（ 1−2p）· bid（i（j），j），5（定义为两个投标人）最多6α2 α+6 +2。特别是，αα=∗2α +1 +2E[spend（i（j），j）]=p·bid（i（j），j）≥p·bid（i（j），j），1 +685 1。703中，R和（α nd，2）的PoA最多为值α 1。896.αoα5ProoF. 考虑由两个投标人和一组查询Q组成的任何实例。投标人i0， 1的tCPA为T i。投标人i在查询j Q上的ad的值为了便于说明，我们假设所有的点击率都是1。确定一个最优分配OPT，以及任何均衡分配EQ。对于j Q，令i=j表示OPT将j分配给的竞标者，并且令io j表示另一竞标者。设AlgBj是拍卖在等式中分配j的投标人最后一个不等式是因为bid i j，jbid i j，j在这种情况下。因此，使用等式5，我们得到E花费j2p+1 2pOPTjα(3) 设Q3是查询j的集合，使得bid（io（j），j）≤ bid（i（j），j）≤α· bid（io（j），α178j）则对于每个j∈Q3：Pr[AlgB（j）=i（j）]= 1−p179α.得到.Σ.52个p52α2+6+..z−αα21+S1对偶目标的值为δ =。=+ +α。这αΣ. ..（i（j），j）≥.在− −≤，（））k=1自动出价设置中的拍卖设计：随机化提高了VCG WWW'22的效率，2022年4月25日至29日总预期支出是两个投标人的支出之和，即：E[spend（io（j），j]=p·bid（i（j），j）和通过揭示LP的因子来界定PoA 定义变量xk：= OPT（Qk），k= 1..................................................4。归一化OPT（Q）= 1，我们xk=1（10）K- 是的p·bid（io（j），j）o我们现在可以通过最小化无政府状态的总体代价来限制无政府状态的E[spend（i（j），j）]=≥。α+（1− 2p）· bid（i（j），j）p·bid（i（j），j）+（1− 2p）·bid（i（j），j）ELWQ在约束（8）、（9）、（10）上。设z表示ELWQ，则我们有以下线性规划及其对偶LP（其中α2α其中最后一个不等式是因为bidobid（i<$（j），j）在这种情况下。因此，使用等式5，我们得到α变量γ、β、δ）：最小化zS. t. z −mkxk ≥0K最大化δS. t. k：−mkγ − sk β + δ ≤ 0E[spend（j）]≥1−p+pα·OPT（j）。γ+β≤1γ、β、δ≥0(4) 设Q4是查询j的集合，使得bid（i∈（j），j）≥α· bid（io（j），j）则对于每个j∈Q2：∗Kxk≥1Kk，xk≥0Pr[AlgB（j）=i（j）]= 1考虑以下对偶解决方案：而预期花费可以是0（如果bid（i0（j），j）=0）。设定福利界限：定义以下常量：δ=.δ1 、 γ=δ， β=s1S1（十一）m1=0s1=p·α+（ 1− 2p）+我们表明，这是一个可行的解决方案的选择1p=2，αm2=p s2=α+（1 −2p）a的范围。对于k=1和k=4，满足对偶LP中的约束，并且实际上是紧的，因为m1=0，m4= 1，并且s4=0。注意又m3=1−p s3=1 −p+p.1Σm4=1s4= 0从上面的计算，我们有：1. 4：Pr[AlgB（j）=i<$（j）]=mk（六）所以最后一个约束是满足的并且也是紧的对于k= 2，我们需要：m2γ s2β + δ0。插入选择p=2，m2、s2、γ、β、δ的值简化为：1. 4：<$j ∈ Q k，spend（j）≥ s k·OPT（j）（7）现在，对于每种情况k = 1。. . 4，我们得到以下两个界3α2−α− 7≤ 0，其中α ∈ [1，1 +<$85]满足。请注意，1 +185 1。703.在均衡中获得的福利首先，考虑j被分配给opti的概率6对于k=3，我们需要：−m3γ−s3β+δ≤0，6其简化为：在均衡中，我们得到，使用Eq.第六章：4α3+ 2α2− 11α− 10≤ 0.4 ..∗.这对于α ∈ [1，r]是满足的，其中r ≠ 1。8.E[LW（Eq）]≥k=1j∈Qk PrAlgB（j）=i（j）·OPT（j）因此，我们看到解（11）是一个可行的解决方案，对偶LP，其中α∈ [1，1+<$85]..4612 α 12第二、E[LW（Eq）]= E[ LW（i，Eq）] ≥spend（i，Eq）这意味着原始LP的最小值，这是一个较低的在拍卖均衡中所得到的价值上界，不小于这个价值。由于OPT被标准化为1，这就完成了i∈Ai∈A证明定理。对于α=1+α85，双重目标的值44=E[spend（j）] ≥.sk·OPT（j）约为0。6527，即，无政府状态的代价大约是1 . 896.1+p1+α2skxk≥0γ+β=δ=1个≥mk·OPT（Qk）（1S11180.k=1j∈Qkk=1j∈Qk为了完整性，我们注意到存在一个原始解，与此对偶解相同的值：x4=z=δ，x1=δ，4s1=sk OPT（Qk）（9）x2=x3 = 0。□k=1[1]p = 2的选择是通过搜索找到的，几乎是最优的。我们注意到，其中，第一个不等式由使用Eq.第二个51不等式由Eq.第七章可以说，更自然的选择是p=3（这使得分配均匀增加随着出价的增加，概率）只是稍微差一点，给出大约的PoA。一点九一181（）下一页·（−）2α21/（）下一页αS1花费为出价（A）p+（1−2p）>αp+（1− 2p）。但S1S1S112s1WWW3.3一个很好的例子-如果它出价到100万在项目中有可能。bility 1−p，则其平衡的性质αs1α1−p满足约束（在等式中）。9），但没有使用的属性，没有投标人有动机改变其投标乘数。所以我们这至少是B的期望值，–S1 （自可能会期望边界非常宽松。令人惊讶的是，我们发现，如果B出价以概率p赢得物品2，则其花费是p·bid（A）>p，这是B的期望值。存在一个例子，其中边界是紧的，并且xk：=OPT（Qk）在该例子的平衡中的值精确地为α s1因此，B不想背叛其投标，µB= 1。对应于上述证明中的最优LP解的那些因此，出价乘数（12）处于平衡状态。在这个均衡中，得到的总值是1 + 1，而最优分配（项目1到A，项目2到B）得到的值是1+1，从而证明了定理，当n → 0时。□图1：一个简单的例子。定理2. 定理1中的分析是严密的，即，在R和α，p下存在一个平衡的例子，其中均衡中的最优福利是1+14多个投标人的不可能结果在本节中，我们将展示一个不可能的结果，当我们有大量的投标人投标每个查询。4.1直觉假设我们尝试在Sec中扩展证明3的情况下，许多投标人每个查询（为一些适当的推广R和超过两个投标人）。由此产生的问题是，类Q2和Q3中的查询对福利的贡献可能变得非常小。 要看到这一点，请注意，类型Q2或Q3中的查询具有在某个保证金（α）内的最高出价者中的opt-bidder。现在，选择性投标人获胜的概率可以是p2s1如果在保证金范围内有大量投标人其中s1=p α+12 p+α。特别地，对于p=5，比率为：2α +6+2由于匿名拍卖必须在所有人之间进行随机分配就是α。正+ +其中因此，m2和m3可以接近于0。坏的情况是αProoF. 考虑图中的例子1.一、 这个例子与[1]中使用的例子类似，除了边B上的值，2（从1减少到1 s1）。我们有两个广告商a，b和两个查询1， 2。广告客户a的值是va=1和va=1，并且广告客户a的值是v a = 1和v a = 1。可能发生的情况是，存在一个实例和一个均衡，其中在 Q1（x1=0）中没有查询，并且混合查询，一半在Q4（拍卖选择了选择性投标人），一半在Q2或Q3。如果这种情况出现在均衡中，那么在任何这样的R和 nd的推广中，福利都不会超过最优福利的一半。b=vb=1 20且vb=1。所有广告查询的点击率福利pairs设置为1。 对于两个广告商，我们都有一个tCPA约束，tCPA = 1，所以约束是支出最多应该是价值。考虑出价乘数：µA=+1 ， µB=1（ 12）第一章我们首先证明这是一个均衡：• 对于第2项，A事实上，我们表明，这样的情况下，可以构建在任何随机拍卖的均衡。我们通过使用上述R和的直觉为任何给定的随机拍卖创建一个实例来实现。第四季度将是第四季度（即， opt-bidder在没有任何竞争的情况下获胜），或者将是这样的，即存在具有几乎相等的出价的大量出价者，并且opt-bidder是其中最低的。 在这种情况下，选择性投标人获胜的机会很低，但其他投标人的总支出是物品2的概率为1，并支付s1乘以B1. 由于B的出价是0，A也可以免费获得物品1。因此，A的花费是1，对于所获得的两个项目，它小于它的价值1 +1。因此，满足A1.它没有动机偏离其μ A的出价。B什么也得不到，但它不能以任何概率出价（增加µB）以获得物品2，并且仍然满足其tCPA约束：–随机拍卖的空间非常大，因此我们必须构造一个依赖于非常基本的拍卖性质的实例，以便每个索赔对所有拍卖都成立4.2抗干扰性和最大阈值我们首先定义两个拍卖属性。在4号线找到一个随机拍卖被称为匿名的，如果它的分配不依赖于投标人的身份，但只依赖于相对出价值。·人们可能会注意到，上面获得的界限并不完全使用也不足以增加福利。技术难度182K（）[]（）下一页[-]{}（）（·（））（）·（）··· ）·∈[−]（·ϵ21一2≥−–伊古里iπ（）下一页自动出价设置中的拍卖设计：随机化提高了VCG WWW'22的效率，2022年4月25日至29日我们对不可能性结果的证明只适用于匿名拍卖。匿名性通常是得出一般结果时的标准;注意，匿名性排除了一些已知的拍卖，例如具有个性化储备的拍卖（但无论如何，这些拍卖在无先验设置中并不我们将使用以下内容（附录A.2中的证明）：Lemm A3. 在任何匿名拍卖中，如果有k个出价者，那么出价最低的出价者赢得物品的概率最多为1。接下来，由于我们想证明所有（匿名）随机拍卖的结果，我们需要确定我们将在构建中使用的任何拍卖的技术属性。 这是一个技术要求，用于考虑拍卖的情况，即即使出价人是唯一的出价人，也没有将物品完全出售给出价人，并且出价与所需的一样高;直观地说，这种拍卖只会有更差的效率。我在5楼。考虑当物品只有一个投标人并且出价为b时的设置。 随着b的增加，在真实拍卖中，以出价b赢得物品的概率P b = Pr必须增加。定义最大概率ππ=lim P bb→∞是投标人获胜的最大可能性为了简化符号，我们将假设极限达到2。将最大阈值定义为达到此最高概率的最低出价。Qi的值：Q i的投标人的值采用以下模式。首先，对于每个i∈ [0，k − 1]，v（Bi，Qi）= V，且v（Bj，Qi）= 0，则<$j<$i。接下来，我们定义k长元组τ0=（a·V + ρ，a·V +2 ρ，. . . ，a·V + kρ）这里ρ>0是一个非常小的常数，只用于平局决胜。对于i1，k1，定义τi为τ 0的第i次旋转，即，τi=a V i+1 ρ，aV+i+2 ρ，.，a V+kρ，a V+ρ，a V+2 ρ，. . .，a V+iρ.现在，对于每个i 0，k 1，投标人A j的值 对于Q i，确定如下。设k>0是一个常数，以后再确定。值的元组（v（A0，Qi），v（A1，Qi），. . . ，v（Ak −1，Qi））被设置为等于πτi，其中后一乘法是坐标式的（因此，例如，vA0，Qi=aV+i+1ρ）。图图2示出了k=2的实例，即，四个投标人。M=min{b：P（b）=π}我们将使用以下（附录A.2中的证明）。LemmA 4. 对于任何一个最大概率为π <$m，最大阈值为M<$M的（随机）真实拍卖，当有一个投标人出价b ≥ M<$m时，成本至多为π <$M<$m。4.3证明边界图2：k = 2的实例，即，4个投标人和4个查询。这里，V> 1，a> 1，α> 0。我们取V为大，a→ 1，且n → 0。 ρ可以被认为是平局决胜的形式变量。出价乘数：在这种情况下，考虑以下出价乘数：µ（Ai）=1，i，µ（Bi）=1，i。因此，对于每个i，bid（A，P）=a·V并且bid（X，P）= a·V。定理5.对于任何随机真实匿名拍卖，我0，XAi.我i·πi任何n，γ> 0，存在一个有足够多投标人n的实例，对于该实例存在一个（n，γ）-均衡，其中当n → ∞时，总价值渐近地是该实例的最优值。ProoF.设给定的随机拍卖具有最大概率和最大阈值。 为了简化符号，如果M> 1，那么我们重新缩放以下构造wlog中的所有值，使得M = 1。注意，我们可以假设π1，否则我们将通过一个投标人和一个项目的实例完成。构造实例。 考虑以下实例。对Qi的出价：对于每个i，查询Qi得到以下出价：bid（Bi，Qi）=V，并且bid（Bj，Qi）=0，此外，元组（bid（A0，Qi），bid（A1，Qi），.，bid（Ak −1，Qi））= τ i。其余证明的目标为了证明定理，我们需要证明对于这个例子和这些出价乘数：(1) 这些出价在拍卖中实现的福利接近最优可能福利的一半(2) 出价形成均衡，即，对于每一个投标人。（Def. 1）、(a) 他们的tCPA约束在这些投标中得到满足（最多总共有2k个投标人：k个投标人A0，. . . ，A k −1，和k个投标人因子1+γ）。(b) 他们不能改变他们的出价乘数而获得更多B0，. . . ，Bk 1. 所有投标人的tCPA均为1，即，它们的总成本被限制为最多是所实现的总价值（最多为1+γ的因子）。相应地，存在2k个查询：k个查询P0，.，P k1和k个查询Q0，.，Qk1.我们选一个1，V1稍后再修正Pi的值：对于每个i ∈ [0，k − 1]，只有Ai对于P有非零值，其中v（A，P）=a·V。2例如，消费者主权的标准假设意味着ππ=1并以足够高的出价获得在保持tCPA约束的1+γ内的证明任何随机拍卖的结果 挑战是证明上述任何随机拍卖。要做到这一点，首先要注意，我们的实例几乎是普遍的，即， 它只依赖于给定的拍卖，通过最大概率π和最大阈值M来缩放实例中的所有数字。其次，我们只依赖于所有匿名随机真实拍卖满足的基本性质：（a）引理4，它解决了依赖性183（（））·--因为它是+1k+中最低...Σ..（）−≤（）−（）下一页.∗π+一项目投标人0，..，K在这个设定中显然，s=0×s≤J一个π∗π∗）的。一一1拉瓜π ∗1WWW（b）匿名性的结果，如引理3，（c）真实性的简单性质(1) 福利：有了这些出价，Pi的拍卖只有一个出价人Ai，并且其出价至少是最大阈值（其为1），所以从定义。5Pi被分配给Aiw.p.ππ查询Qi获取X如上定义现在，由于Qj上的旋转对称性，Ai是A中Qj的tij：=i+jmodk+ 1个最低投标人（而Bj是Qj的最低投标人）。因此，作为匿名性的结果，Ai以概率χtij被分配Q j。当j在[0，k− 1]范围内时，tij在[1，k]范围内。因此，我们得到：分配给“1个投标人（引理3）。因此对于Pj获得的期望值为a·V，对于每个Qj为k−1j=0P[分配给Ai的Qj]=Ks=1χs≤1（17）至多k11V+k（a·V+kρ）（后一项是上限，也就是说，对于所有i，Ai被分配至多一个单位的期望总和B为Q的A中的+最高可能值）。我任何Qj的量。因此，在这些出价下的拍卖中实现的总价值是。17在Eqs。15和16，我们得到：（忽略带ρ的项）3.1ΣLW EQ∗a·V kcost（Ai）≤ 1+ a·V值（Ai）（18）（）≤π·π·k+k+1V+·a·V·k1（2b）界定投标人Ai的叛逃收益：=a+k+1+V·a·V·k。（十三）降低投标乘数没有帮助，因为这只能减少所获得的价值。现在，即使Ai将其出价增加到无穷大，最优分配将每个Pi分配给Ai，并且将Qi分配给Bi，它可以达到的最大值是（忽略ρ项）：给出的值为OPT=ππ+1·V·k。（十四）ππ·v（Ai，Pi）+k−1j=0v（Ai，Qj）≤a·V+k·k·a·V(2) 证明均衡：我们还需要证明这组出价构成了一个π，γ均衡。（2a）投标人A1的约束：根据引理4：A1被分配P1w.p. 并且P1的成本最多为π，因为我们重新缩放以设置最大阈值M= 1。此外，Ai对任何Qj的每单位价格至多是它对Qj的每单位出价。所以我们得到（去掉涉及ρ的项）：v值（Ai）=v（Ai，Pi）·P[Pi分配给Ai]K.−1因此，使用Eq.15，A i通过偏离μ（A i）（即使忽略其tCPA约束）可以获得的最高值为增益（Ai）≤k·k·a·V（19）我们在附录A.1中提供了论证的其余部分，以证明投标人B i也是满意的，因此投标乘数处于均衡状态。设置参数。 现在我们可以设置参数，满足所有的约束条件，使福利接近最优福利的一半从等式18、我们看到γ+ j=0 v（Ai，Qj）·P[Qj分配给Ai]K.−1通过取V>1，并注意a≥1，Ai的tCPA约束为满足1+γ因子（每个Bi的tCPA约束为严格满足）。从等式20（附录A.1），我们看到，通过采取≥a·V+ j=0 ·a·V·P[Qj分配给Ai]（15）k+1>aV（a−1−γ）>a（a−1−γ）γcost（Ai）≤πk−1+j=0bid（Ai，Qj）·P[Qj分配给Ai]我们得到增益（Bi）不大于π。从等式19、我们看到，取k → 0，足够小，使得k aV<，我们得到Gain（A i）不超过。最后，通过取a→1（回忆a≥1），我们得到K.−1j=0从等式13和14，通过任何投标获得的价值为了掌握方程中的概率15和16，我们认为一 +1+（k+1）（a +1）a +1→