展示广告拍卖中激励兼容性的测试

14190在展示广告拍卖中测试激励兼容性0Sébastien LahaieGoogle研究纽约，美国slahaie@google.com0Andrés Muñoz MedinaGoogle研究纽约，美国ammedina@google.com0Balasubramanian SivanGoogle研究纽约，美国balusivan@google.com0Sergei VassilvitskiiGoogle研究纽约，美国sergeiv@google.com0摘要0考虑一个参与重复拍卖的买家，例如在展示广告中普遍存在的拍卖。她如何测试拍卖是否具有激励兼容性？为了有效地竞标，她对拍卖是否具有单次激励兼容性（纯二价拍卖，具有固定保留价）和动态激励兼容性（她的竞标不用于设置未来的保留价）感兴趣。在这项工作中，我们开发了基于简单竞标扰动的测试，买家可以用来回答这些问题，重点关注动态激励兼容性。有许多潜在的A/B测试设置可以使用，但我们发现许多自然的实验设计实际上是有缺陷的。例如，我们展示了加性扰动可能导致矛盾的结果，其中更高的竞标价导致更低的最优保留价。我们准确地描述了这一现象，并表明只有满足单调危险率（MHR）属性的分布，保留价才能得到保证。实验者还必须决定如何分割流量以应用系统性扰动。随机化分割可能很诱人，但我们通过实证研究证明，除非扰动与卖方用于计算保留价的分区对齐，否则结果将无法得出结论。我们通过对真实展示拍卖数据进行实验证实了我们的结果，并表明买家可以在仅观察到印象成本（而不是确切的保留价）的实际条件下量化单次和动态激励兼容性。我们分析了运行此类实验的成本，揭示了测试准确性、成本和基础市场动态之间的权衡。0CCS概念0• 应用计算 → 电子商务；在线拍卖；0关键词0广告拍卖，激励兼容性0本文根据知识共享署名-非商业性使用-禁止演绎 4.0国际许可发布。作者保留在其个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY-NC-ND 4.0许可发布。ACMISBN 978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31860470ACM参考格式：Sébastien Lahaie，Andrés MuñozMedina，Balasubramanian Sivan和Sergei Vassilvitskii。2018年。在WWW2018：2018年Web会议中测试展示广告拍卖的激励兼容性。2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318604701 引言0展示广告行业可能在其交易实践方面发生重大转变，因为许多大型交易所，包括AppNexus和IndexExchange，目前正在考虑从二价拍卖转向一价拍卖[21]。推动一价定价的主要原因是广告买家不再相信交易所是否正确遵守二价定价规则。人们担心交易所可能使用其他机制来提取更高的利润，例如在收集竞标后而不是之前设置保留价。因此，二价定价背后的主要动机，即激励兼容性，就会丧失[4]。原则上，市场参与者可以通过比较广告买家和发布者之间的数据来审计交易所的做法。实际上，这只有在个别情况下才可能实现，并且耗时太长，无法代表一种系统化、可扩展的解决方案。相反，广告买家需要根据自己的交易数据了解底层拍卖动态，以便为他们的竞标策略提供信息。受到这些问题的激励，本文开发了一种买家可以使用的统计测试，用于估计重复拍卖的激励兼容程度。我们首先解决了单次拍卖的激励兼容性问题：检测拍卖是否纯粹是二价拍卖，或者支付在任何程度上取决于最高竞标价。我们提出了一个简单的实验设计，广告商随机调整其对印象的价值，以某个离散的比例（10％，20％等），然后验证没有调整的流量产生最高的剩余价值。我们的论文的核心是测试动态激励兼容性的更微妙的问题，特别是动态保留定价的问题：检测买家的历史竞标在多大程度上被用于设置她未来的保留价。我们在本文中的主要贡献有两个方面：0(1)为了检测和评估动态储备定价的程度，我们引入了一种实验设计，其中广告商根据出价调用中提供的信息将查询流量分区，并在每个分区内以随机选择的方向（向上或向下）系统地扰动出价。0Track: Web Economics, Monetisation, and Online Markets WWW 2018, 2018年4月23日至27日，法国里昂14200在下一个时间段，广告商观察到应用的噪声与储备价格变化之间的相关性。正相关表明储备价格取决于过去的出价。更正式地说，我们提供了一个统计量，可以检验拍卖是否使用过去的出价来设定储备价格的零假设。请注意，动态储备定价在一价和二价拍卖中都是一个相关的概念。0(2)在分析各种实验设计的过程中，我们对经济学和算法博弈理论文献中广泛使用的单调风险率（MHR）分布族进行了新的直观描述。0我们研究了影响实验有效性的两个关键方面。首先是扰动的性质：加法或乘法。我们观察到，在出价分布中进行正的加法偏移并不一定会导致更高的最优（即收入最大化）储备价格，并证明了只有当出价分布具有单调风险率（MHR）时，这个简单的性质才成立。这是对独立兴趣的MHR分布的新的直观描述。由于在实证建模中使用的许多相关分布（例如对数正态分布）都不是MHR分布，因此在这些情况下进行加法扰动将导致买方观察到混乱的结果-在出价更高的情况下降低储备价格。因此，我们使用乘法扰动，并解释了这如何导致一种可以检测到基于过去出价的任何标度不变的动态储备定价方案的测试，其中包括最优储备。下一个关键方面是流量分区。我们表明，除非流量分割与交易所用于计算储备的分区完全一致，否则结果将无法确定。这突显了在与卖方对齐的较少粗分区和增加统计功率的更多细分区之间的实际权衡。我们通过对Google的DoubleClickAdExchange的两天数据进行反事实模拟来验证我们的方法，根据我们的测试，扰动第一天主要广告商的出价。我们实施了一种储备定价方案，该方案将库存进行分区，并根据该广告商的出价计算每个分区的Myerson最优储备价格，并模拟了广告商如何检测到这种储备定价逻辑。我们还发现，使用我们的测试，即使广告商使用的流量分区比储备定价方案中使用的分区粗糙得多，广告商仍然可以检测到动态储备定价。此外，尽管对买方来说代价很大，但是即使广告商只能观察到一个展示的最终成本，而不是确切的储备价格（可能被第二高的出价屏蔽），仍然可以进行检测。本文的组织如下。在第2节中，我们描述了我们的统计测试适用于的储备定价方案的类型：根据买方在查询流量的固定分区上的出价历史来设定储备，使得储备与出价成比例。我们还对单次和动态激励兼容性的概念提供了正式定义。第3节提供了基于出价扰动的实验设计，并证明了除非出价分布满足严格条件，否则加法扰动可能会有问题。第4节我们验证了我们的测试在Google的DoubleClick AdExchange的真实拍卖数据上的效果，以及0演示保留价格观察质量（例如，精确或被审查）与检测基础保留定价方案的能力之间的关系。我们还测量了在各种出价扰动幅度下运行测试的成本效益。第5节总结。01.1 相关工作0一次性保留定价。保留价格显著增加卖方收入的想法在拍卖理论中是核心的。事实上，Myerson的开创性结果[17]表明，具有n个投标人和独立从（正常）分布F中抽取的价值的单次收入最优拍卖只是运行每个投标人的保留价格的福利最优二价拍卖。保留价格的作用已经得到了很好的理解，并且已经进行了大量研究，以在各种约束条件下（近似）优化它们。Hartline和Roughgarden[11]在各种设置中构建了具有保留价格的二价和VCG拍卖，并且显示它们近似于最优收入。Chawla等人[5, 6]和Yan[22]进一步表明，仅仅保留价格（即，发布价格机制）在许多单参数和一些多参数设置中足以近似最优收入。0样本复杂性。Dhangwatnotai、Roughgarden和Yan[9]强调了在最小程度了解买方价值分布的情况下计算这些保留价格的必要性，并展示了如何在仍然获得最优机制收入的情况下实现这一点。Cole和Roughgarden [7]、Huang、Mansour和Roughgarden[12]以及Morgenstern和Roughgarden[16]进一步推动了这项关于样本鲁棒保留定价的工作，他们给出了需要的样本数量的界限，以便获得（1-ϵ）-接近最优收入。当涉及发布个性化保留价格（即，非匿名保留价格）时，拍卖人运行懒惰拍卖还是急切拍卖会产生显着差异。Paes Leme、Pal和Vassilvitskii[18]详细研究了这种差异，并显示出，尽管最优懒惰拍卖可能在计算上很容易，而不是最优急切保留价格的NP困难问题，但在实践中，甚至次优的急切保留价格产生的收入也比最优懒惰保留价格更好。Roughgarden和Wang[20]进一步详细研究了近似个性化急切保留价格的方法，展示了如何获得对最优收入的1/2近似，并将他们的离线算法转化为在线学习算法。0动态机制。与我们的工作相关的另一条线是关于顺序、动态和重复机制的文献。当买方与同一卖方反复互动时，卖方可以通过将不同回合之间的激励约束相互关联，即使未来的分配和定价决策严重依赖于买方过去的出价，也可以获得显著更高的每轮收入。最近的一系列研究（参见[2, 3,14]）以动态激励兼容性为中心主题，研究了卖方在各种约束条件下可以获得的额外收入。0跟踪：网络经济学，货币化和在线市场WWW 2018年4月23日至27日，法国里昂by the seller, and the goal is to understand her optimal strategyin the presence of bid-dependent reserve prices. Kanoria and Naz-erzadeh [13] propose a dynamic mechanism that is almost incentivecompatible. That is, even though a strategic buyer could achievehigher surplus from playing an optimal bidding strategy, the in-cremental gain is negligible compared to the cost of playing theoptimal strategy. Similarly Amin, Rostamizadeh and Syed [1], Mohriand Muñoz Medina [15] and Drusta [10] study a repeated postedprice auction set up where the buyer attempts to maximize herdiscounted surplus. The main result of this line work is that thebuyer’s strategy can only deviate from truthfulness for a small num-ber of rounds if the discounting factor is less than 1. However, [1]show that without any form of discounting, a buyer can force theseller to reduce the reserve price to a constant fraction of her truevaluation. Devanur, Peres, and Sivan [8] study a different settingwhere the buyer’s values are not drawn freshly from a distributionevery round. Instead they are initially drawn from a publicly knowndistribution and continue to remain the same afterwards. The sellercan simply post a take-it-or-leave-it reserve price in every round,based on the previous round prices and buyer decisions. In thePerfect Bayesian Equilibrium (PBE) of this game where the selleris unable to make any commitments about how he will increaseor decrease reserve prices in the future, the authors show that theseller gains non-trivial revenue only in the last few rounds of thegame.The results of these papers rely critically on the unrealistic as-sumption that the buyer has access to the full mechanism. In prac-tice, the buyer may only know the type of auction run by the seller,but not all of the details of the pricing function; and even in thecase of full information, verifying that the seller is following themechanism is far from trivial.14210尺寸不变的保留定价。我们定义 h′s = (1 + ϵ)hs，如果b′i = (1 +ϵ)bi对于所有1 ≤ i ≤ ℓ。我们称 h′s 为 h s 的 (1 + ϵ)倍缩放版本。在本文中，我们假设卖方的保留定价方案是尺寸不变的，即在固定其他输入的情况下，02 预备知识0可验证正确的拍卖。与我们研究的问题有关的一个相关问题是能够验证拍卖者是否确实运行了承诺的拍卖，即拍卖是否可验证正确？（参见[19]）。与我们的工作不同，[19]侧重于检测拍卖者是否通过偏离承诺的协议来恶意行事。我们的工作侧重于检测运行的拍卖是否提供了不报告真实价值的出价的激励。0买方，从分析的角度来看，每个拍卖中的买方数量并不重要，因为它们的集体行为可以通过竞争出价分布来捕捉。0考虑一个买方参与与单个卖方（例如广告交换）进行的重复拍卖。查询是卖方向访问网页的用户展示广告的机会。卖方通过向不同的买方征求竞标并可能为每个买方指定不同的保留价格来为每个查询运行拍卖。我们考虑的设置是，卖方将查询空间划分为桶以计算保留价格，其中每个桶由查询和买方特征的特定组合定义。买方的目标是弄清楚交换是否在运行真实（即二价）拍卖，以及她当前的出价是否被用来影响未来的保留价格。在每个桶中，买方的价值在每一轮中都是独立地从绝对连续分布 F中抽取的，其密度为f。不同桶中的价值分布可能不同。因为我们从单个买方的分析角度研究这个问题，所以每个拍卖中的买方数量并不重要，因为它们的集体行为可以通过竞争出价分布来捕捉。0请注意，尺寸不变性等价于说价格不应该依赖于出价是以美元还是以分为单位。特别地，根据历史（即样本）(b1, ..., bℓ) 引起的分布计算Myerson 最优保留价格的自然方案是尺寸不变的。0请注意，尺寸不变性等价于说价格不应该依赖于出价是以美元还是以分为单位。特别地，根据历史（即样本）(b1, ..., bℓ) 引起的分布计算Myerson 最优保留价格的自然方案是尺寸不变的。0样本鲁棒的保留定价。实际上，卖方根据一个阶段内的历史出价（即样本）来设定保留价格，而不是根据真实分布 F来设定。然而，在广告交换的背景下，可以合理地假设每个桶中有足够的样本，使得采样分布和真实分布之间的差异可以忽略不计。特别地，虽然可以构造出一些边界情况的保留价格函数，即使样本中有小的噪声，它们输出的保留价格也可能相差很大，但我们假设卖方遵循一个样本鲁棒的保留定价算法，其中随着样本数量足够大，保留价格中的噪声变得可以忽略。再次强调，像根据样本引起的分布计算Myerson最优保留价格这样的自然方案是样本鲁棒的。在本文的其余部分，我们忽略了这个采样误差。0四个世界：历史-{独立 vs 依赖}-卖方，静态 vs动态市场。如果对于所有历史hs，hs′，rs+1(hs, ∙) = rs+1(hs′,∙)，则卖方是历史独立的。由于保留价可能是市场因素、其他竞标人的竞标等的函数，我们对静态市场和动态市场进行区分。如果对于所有y的值，rs+1(hs,y)相同，则市场是静态的。动态市场中的“y”的波动被建模为计算出的保留价中的噪声，即，如果我们固定历史hs，其他因素“y”的变化将表现为rs+1(hs, y) = (1 + η)rs+1(hs,y′)，其中η是从某个分布D中抽取的零均值随机变量。噪声也可以被建模为加性的，我们的结果不会因这些修改而改变。0买方效用和激励兼容性。我们假设买方是标准的准线性效用最大化者，即他们的目标是最大化所有回合（跨越多个时期）的总和0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, Franceαk ∈argmaxα ∈{α1,...,αk }Ut (vt ,αj ).(2)Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France14220vx -p其中v是他们在任何给定回合中的价值，x表示他们是否被分配了商品，p是他们被收取的价格。在分析交易所实施的定价方案时，有两个主要类别：买方是否在任何单次拍卖中通过错误报告其真实价值而获益（单次激励兼容性），以及她是否通过在当前回合中错误报告来获得整体效用的收益（动态激励兼容性）。0单次激励兼容性。任何单次拍卖如果报告真实价值对买方最有利，则是激励兼容的。让0Ut (vt, v′t, hs(t)−1, ∙) = vt xt (v′t, hs(t)−1, ∙) − pt (v′t, hs(t)−1,0表示买方在第t轮通过报告vt′时获得的效用，当她的真实价值为vt时。分配和支付函数中的“∙”捕捉到其他买方报告的估值和其他潜在特征。单次激励兼容性要求0Ut (vt, v′t, hs(t)−1, ∙) ≥ Ut (vt, v′t, hs(t)−1, ∙) � vt，v′t ∈ R. (1)0动态激励兼容性。总共有T个拍卖，跨越多个阶段。动态激励兼容性要求：0T �0t = τUt0� vt，vt，hs(τ)−1 + (vτ,...,vt−1)，∙ �≥0T �0t = τUt0� vt，vt′，hs(τ)−1 +(v′τ,...,v′t−1)，∙ �0对于任意 τ ∈ [1, T]，对于任意 t ∈0买方的目标。买方的目标是设计测试来评估单次激励兼容性和动态激励兼容性。我们采用统计方法，并寻求拒绝激励兼容性的零假设的测试。对于动态激励兼容性，我们特别关注发现动态保留定价的测试。注意，动态激励兼容性是一个依赖于拍卖机制更多方面的一般属性，而不仅仅是动态保留价，因此这只是拒绝零假设的一种方式。动态保留定价是将激励跨越回合的主要手段，因此我们在本文中重点关注这个重要的特殊情况。03 实验设计0在本节中，我们描述了检测单次激励兼容性和动态激励兼容性违规的测试。03.1 单次激励兼容性0虽然使用简单的统计量（如出价与成本比）来测试单次激励兼容性是很诱人的，但很容易看出这种方法无法区分激励兼容和非激励兼容的拍卖。事实上，带有保留价的第二价格拍卖如果保留价接近买方的出价，出价与成本比可以接近1。相反，我们提出了一个简单的测试，受到(1)的启发。让k > 0且0 < α1 < ... < αk =1是一个乘法器序列。滥用符号，我们让Ut (vt, αj) = Ut (vt, αjvt,hs(t)−1, ∙)。它0根据激励兼容性的定义，我们有0因此，我们的测试定义如下：我们将流量随机分成 k 个桶 B 1，...，B k 。然后，买方通过 α j 缩放桶 B j中的出价，并计算每个桶的总剩余价值 S j 。根据 (2)，一个单次激励兼容机制应该验证 S k在所有分区中最大化剩余价值。0为什么不能使用相同的测试来测试动态激励兼容性？然而，动态激励兼容性的情况要困难得多。很容易看出，不能使用与单次设置相同的测试——随机分割查询是不明确的，因为桶的关联需要在多天中持续存在。其他分桶方案也会失败——我们将在第3.3节中展示，卖方需要沿着与买方用于计算保留价格相同的维度划分其流量。在本文中，我们考虑了一种特定的动态激励兼容性被违反的方式，即昨天的出价影响今天的保留价格。我们称这样的卖方为历史依赖卖方。我们设计的测试基于简单的出价扰动和直观的观点，即更高的出价应该产生更高的保留价格。更准确地说，我们考虑的测试系列满足以下两个条件：0•校准。如果卖方的保留价格不依赖于历史，扰动和保留价格之间的相关性应该为零。•结论。如果卖方的保留价格依赖于历史，扰动和保留价格之间的相关性应该严格为正。0虽然这两个条件是自然的，但我们证明了一个简单的相关性测试的实现并不一定是确定性的。这样的实现包括使用加性扰动以及使用随机分桶方案。然而，拍卖的性质（一价、二价或其他）对于这个测试来说是无关紧要的，该测试纯粹检查保留价格。03.2 加性扰动0我们测试的加性版本的设置很简单：固定一个桶，在该桶中的第 s +1 阶段将出价增加一个加性扰动 ϵ ，与第 s阶段的出价相比。人们期望在具有这种加性扰动的桶中，保留价格不会小于未修改的桶的保留价格。然而，即使对于非最高报价分布，这个非常基本的要求也只对于非最高报价分布成立，即买方在提高出价后可能观察到较小的保留价格！设 F为我们感兴趣的桶中值的绝对连续分布的累积分布函数（cdf），f为其密度函数。我们用 G ：= 1 − F 表示 F 的相关生存函数，并用 x： [0 , 1] → R 表示由 x ( q )  = G − 1 ( q )给出的分位函数。考虑一个买方，她通过添加 ϵ ∈ R来扰动她的出价。也就是说，卖方观察到的出价遵循分布 F ϵ ( x )  =F  ( x  −  ϵ ) 。不难证明分位函数与 F ϵ 相关的分位函数xϵ (q) = x(q) + ϵ.(3)���x′(q∗ϵ )�14230x ϵ  由以下给出0我们感兴趣的分布集合是函数  ϵ  �→  argmax r  rG ϵ  ( r )严格单调的分布集合。这个分布集合的重要性是明显的：这是一个买方可以衡量出价扰动对未来保留价格的影响程度的分布集合，当卖方从她的出价中学习时。虽然直觉上认为最优保留价格应该随着扰动  ϵ的大小单调递增，但下一个例子表明这在一般情况下并不成立。0例1.令G(x)=e−x1/2为形状参数为1/2的Weibull分布。让我们计算rϵ=argmaxrGϵ(r)。根据Gϵ的定义并对收入函数进行导数运算，我们可以看到：0(rGϵ(r))′=(re−(r−ϵ)1/2)′=e−(r−ϵ)1/2�2√r−ϵ−r)02√r−ϵ.0将上述表达式等于0并解出r，得到rϵ=2+2√01−ϵ。注意这是ϵ的递减函数。因此，通过将竞标价格增加ϵ来扰动竞标者实际上会观察到更低的保留价格！0正如前面的例子所示，即使是正则分布也不满足从扰动分布中获得的保留严格单调性。然而，我们将证明具有单调危险率属性的函数恰好是满足此条件的函数。0定义1.如果一个分布满足单调危险率（MHR）条件，则称为满足MHR。0HR(x)=f(x)/G(x)0是x的弱增函数。0命题1.如果一个分布满足MHR，则对于每个q∈[0,1]，满足以下不等式：0qx′′(q)x′(q)+1≥0.0证明。根据MHR的定义，我们可以看到G(x)/f(x)必须是弱递减的，因此根据一阶条件：0−f(x)20f(x)2≤0. (4)0这意味着01+f′(x0f(x)2≥0. (5)0现在让我们计算x关于q的二阶导数。根据反函数定理，我们有：0x′=−10f(x)x′′=f′(x)0f(x)2x′.0f(x2)。通过变量变换q=G(x)将不等式(5)代入结果。□0定理1. 如果一个正则分布F满足MHR，则rϵ是ϵ的递增函数。0证明。符号：在证明中，我们将处理对q和ϵ的导数。我们使用′符号表示对q的导数和d0对于对ϵ的导数dϵ。令ϵ>0，q�ϵ表示分布Fϵ的最优收入分位数，即q�ϵ=argmax q∈[0,1] Rϵ(q)=argmax q∈[0,1]qxϵ(q)。我们首先证明函数ϵ→q�ϵ是严格递增的。根据方程(3)，得到最优储备价格r�ϵ=xϵ(q�ϵ)=x(q�ϵ)+ϵ。从方程(3)还可以得到Rϵ(q)=qxϵ(q)=R(q)+ϵq；对该方程关于q求导，得到R′ϵ(q)=R′(q)+ϵ，特别地，由于根据定义R′(q�0)=0，我们有R′ϵ(q�0)=ϵ>0。由于F是MHR分布，所以R(q)是凹函数（标准结果），因此Rϵ(q)也是凹函数。我们刚刚证明了R′ϵ(q�0)=ϵ>0，即凹函数Rϵ(∙)在q�0处是递增的。这意味着它在一个严格大于q�0的点上达到最大值，即q�ϵ>q�0。我们可以类似地证明对于ϵ<0，q�ϵ 0。此外，由于 x = G - 1，根据定义，G 是递减的，因此 x也是递减的，使得 x ′ < 0。因此，当 RHS 是非负时，唯一的方式是 q � ϵ x ′′ ( q � ϵ )0x ′ ( q � ϵ ) + 1 ≥ 0 对于所有 ϵ 都成立。根据命题1，如果且仅当 F满足 MHR 条件时，这个表达式对于所有 ϵ 都是非负的。 □03.3 扰动的非对齐桶0最自然的检测动态保留定价的 A/B测试之一是：（i）选择一个任意的特征将查询空间分成两部分；（ii）在其中一半中增加出价，在另一半中降低出价；（iii）验证第二天这两个半部分的保留价格的变化。0Track: 网络经济学，货币化和在线市场 WWW 2018，2018年4月23日至27日，法国里昂14240然而，如果买家选择的特征不是卖家用来将查询空间划分为桶的特征之一，则结果保证是不确定的。0定理2.无论扰动是加法还是乘法，基于卖家未使用的特征的买家A/B测试的结果都是不确定的。0证明。让买家根据卖家未使用的特征将查询空间划分为两个桶 B1 和B2。考虑任意卖家定义的桶 B。令 B 中未扰动分布的 cdf 为F，支持在 [0 , 1] 上。令 q1 是来自 B1 的查询在 B 中的比例，q2 =1 - q1 是来自 B2 的查询在 B 中的比例。令 F A 和 F M分别是加法和乘法扰动后的同一桶 B 中的分布。加法扰动在 B1中将出价增加 ϵ，在 B2 中将出价减少 ϵ。乘法扰动在 B1中将出价乘以 1 + ϵ，在 B2 中将出价乘以 1 - ϵ。令 F1 是桶 B ∩ B1中的分布的 cdf，F2 是桶 B ∩ B2 中的分布的 cdf。很容易验证：0������� 同样地，0� F M ( x ) = �01 - ϵ ) , 0 ≤ x ≤ 1 - ϵ q1 F1 ( x01 + ϵ ) + q2 , 1 - ϵ ≤ x ≤ 1 + ϵ0考虑一个简单的情况，其中 F ( x ) = F1 ( x ) = F2 ( x ) = x （即 U [0 , 1] 分布），且02 。F 的 Myerson 最优保留价格，没有任何扰动时为 max x x ( 1 − F ( x )) = 102 。对于 x ∈ [ ϵ , 1 − ϵ ]，我们有 F A ( x ) = x ，因此对于小的 ϵ，扰动后的最优保留价格（即 max x x ( 1 − F A ( x )) ）将恰好为 102 ，即在 B 1 和 B 2 中都不变。这是因为卖家为整个桶 B设置了一个单一的保留价格。观察到这一点的买家会得出结论认为卖家没有进行动态保留定价。同样，对于 x ∈ [0 , 1 − ϵ ]，我们有 F M ( x ) = x01 − ϵ 2 ，因此对于小的 ϵ ，op-0扰动后的最优保留价格（即 max x x ( 1 − F M ( x )) ）将为 1 − ϵ 20在 B 1 和 B 2 中，无论是分布 F、F 1 还是 F 2，卖家的新保留价格都是一个单一数字（根据 B是卖家的桶的定义）。如果新的保留价格恰好与旧的保留价格相同，买家会错误地得出结论认为没有动态保留定价，即使实际上是存在的。如果新的保留价格增加，买家会对在 B ∩ B 2中降低出价的查询的增加保留价格感到困惑。如果新的保留价格降低，买家会对在 B ∩ B 1中增加出价的查询的降低保留价格感到困惑。□0上述定理 2 强调了构建用于检测动态保留定价的 A/B测试的微妙之处。请注意，买家选择的特征可能确实是一个非常有用的特征，即 B 1 中的分布与0B 2 中的分布（或者，B ∩ B 1 中的分布 F 1 与 B ∩ B 2 中的分布 F2不同）。上述测试的失败与买家选择的特征是否相关无关。卖家是否也认为它是相关的是一个问题，这就是为什么对于买家来说，A/B测试设计变得复杂的原因。03.4 乘法扰动0我们现在介绍基于乘法扰动的主要测试。请注意，任何尺度不变的保留价格选择都将满足定义，即导致更高出价的扰动将导致更高的保留价格。设 { B 1 ,. . . , B n } 为将流量分成 n 个桶的分区。设 α ∈ [0 ,1] 为出价扰动幅度。对于每个桶 B i ，设 β i 为 { 1 − α , 1 + α }中的均匀随机变量。我们提出的实验步骤如下：在第 s轮中，对于落在桶 B i 中且买家价值为 v ij 的每个查询 q j，买家提交出价 β i v ij。在第0s + 1 时，买家观察到保留价格 r ( i ) s +1。我们的统计测试受到以下直觉的启发：如果卖家使用过去的出价来影响保留价格，那么从第 s 天到第 s + 1天的保留价格变化幅度应该与出价扰动幅度 β i −1高度相关。更准确地说，我们定义商0Q i : = r ( i ) s + 1/ r ( i ) s0并将 Q i 与噪声幅度 β i − 1 的平均相关性表示为0C α = E [ Q i ( β i −1 ) ]。0使用第 2 节中描述的条件，我们现在确定了本文中考虑的情景下 C α的性质。0•历史独立卖家。根据定义，历史独立卖家的保留价格与出价无关。因此，比率 Q i 与 β i 和 C α 无关，且 C α =0。这个等式在静态和动态市场中都成立，因为动态噪声 η 与 β i无关。•历史相关卖家。在假设鲁棒和尺度不变的定价下，我们必须有 Q i= β i。因此，E [ Q i β i ] = E [ β i ( β i − 1 ) ] = α2。在动态市场条件下，由于噪声 η 与 β i无关，同样的等式成立。0我们现在可以定义一个测试来区分具有历史依赖性和独立于历史的卖方。让 C α = 10|C α - C α |≤0i = 10Var(Q0δn 2. (7)0请注意，我们可以使用任何其他集中度或自助法来获得 C α的置信区间。方程（7）意味着，如果 C α的置信区间不包括0，我们可以以小于 δ的错误概率拒绝卖方独立于历史的零假设。同样，如果该区间不包含α 2，我们可以拒绝卖方具有历史依赖性并使用尺度不变的保留价的零假设。0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, France0.10.30.50.70.90501001502002500.10.30.50.70.90204060801001200.10.30.50.70.9050100150200250Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France14250遮蔽因子0遮蔽因子0遮蔽因子0(a) γ = 0.95 (b) γ = 0.75 (c) 二价拍卖0图1：剩余提升（相对于最差的竞标策略）与出价遮蔽因子 δ 的关系。04 实验结果0对于我们的实验评估，我们选择DoubleClickAdExchange上的一个大型广告主，并考虑2017年10月连续两天广告主参与的一组随机拍卖。然后我们人为地引入保留价，或调整个别买方的出价，并使用一个拍卖模拟器，能够从记录的数据中重新播放交易所拍卖逻辑以模拟拍卖结果。然后我们计算每个买方的剩余价值和卖方的收入。为了测量单次激励兼容性和动态激励兼容性，我们实施以下保留价选择方法：我们通过可观察特征（在出价调用中）对流量进行分区，并使用第一天的出价计算Myerson最优保留价；请注意，Myerson最优保留价是尺度不变的，因此我们的理论适用于此方案。04.1 单次激励兼容性0为了展示我们的单次激励兼容性测试的简单性和强大性，我们在三种不同的机制下进行了测试。我们将 γ -价格拍卖定义为将保留价设置为最高出价的 γ 倍。请注意，γ = 1对应于一价拍卖。此外，只有当 γ = 0 时，γ-价格拍卖才是激励兼容的；否则买方的付款可能取决于她的出价。我们的测试参数为 k= 10 和 α i = i。010. 我们修改了交易所拍卖，模拟了 γ -价格拍卖，其中 γ = 0.95 和γ =