没有合适的资源?快使用搜索试试~ 我知道了~
13590领域中的动态机制设计 �0Vahab MirrokniGoogle纽约,纽约mirrokni@google.com0Renato Paes LemeGoogle纽约,纽约renatoppl@google.com0Rita RenGoogle纽约,纽约rren@google.com0Song Zuo †0中国北京清华大学songzuo.z@gmail.com0摘要0动态机制是设计收入最大化的重复拍卖的强大技术。尽管它们的强大,但由于多种原因,例如复杂性和对买家价值分布预测准确性的敏感性,这些类型的机制在实践中并未被广泛采用。在本文中,我们旨在解决这些缺点,并开发出可以高效实施的简单动态机制,并为降低动态机制对买家价值分布预测准确性的敏感性提供理论指导。我们证明了我们提出的动态机制在动态激励兼容性方面是可证明的,并引入了动态机制中买家遗憾的概念,并表明我们的机制在改善收入和社会福利的同时实现了有界的遗憾,与静态保留定价策略相比。最后,我们通过对来自在线广告的真实数据集的广泛实证研究来验证我们的理论分析。例如,我们展示了我们的动态机制可以提供超过17%的收入提升,相对遗憾小于0.2%。0CCS概念0• 计算理论 → 算法机制设计;计算定价和拍卖;计算广告理论;•应用计算 → 经济学;0关键词0动态机制设计;动态拍卖;动态二价拍卖;银行账户机制0ACM参考格式:Vahab Mirrokni,Renato Paes Leme,Rita Ren和SongZuo。2018年。领域中的动态机制设计。在WWW2018:2018年网络会议中,0� 我们感谢匿名审稿人的有益评论。†本文作者在Google实习期间完成了这项工作。该作者获得了以下资助:2011CBA00300,2011CBA00301,NSFC61033001,NSFC61361136003,NSFC61303077,NSFC61561146398,清华大学创新科研基金和中国青年千人计划。0本文发表在知识共享署名-非商业性使用-禁止演绎 4.0 国际许可证(CC BY-NC-ND4.0)下。作者保留在个人和公司网站上传播作品的权利,并附上适当的归属。WWW2018,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.318604102018年4月23日至27日,法国里昂。ACM,纽约,美国,11页。https://doi.org/10.1145/3178876.318604101 引言0大多数在线广告平台通过运行一系列重复拍卖来销售其页面浏览量。尽管现有的许多关于此类广告拍卖的文献都讨论了静态一次性拍卖,但使用在不同时间段优化的动态拍卖可能会在收入和社会福利方面带来显著的收益。动态机制的强大之处已经被一些最近的论文观察到[2,5-8,11,17-19]。我们参考Bergemann和Said[4]的综述对该主题进行了全面的处理。尽管动态机制在最大化收入和社会福利方面可能更加有效,但它们在实践中并未被广泛采用。其中的主要问题部分是动态机制的缺点:一个主要问题是由指数级增长的设计空间引起的复杂性,使得解决或甚至描述这样的机制变得困难。另一个问题是动态环境下的激励依赖于卖方和买方对当前行动对未来结果的影响的一致性,而这种一致性需要更高阶的共同知识假设,通常在实践中并不成立。例如,卖方对买方估值的准确性在机制确保动态激励兼容性的水平中起着关键作用;卖方对买方估值的信念越不准确,违反激励约束的程度就越大。在学习买方价值分布非常困难且估计可能存在噪声的高维设置中,这变得更具挑战性。最近的一系列工作在上述复杂性问题上取得了重大进展。例如,Ashlagi等人[1]和Mirrokni等人[14]通过动态规划证明了可以高效计算ϵ-近似最优动态机制。然而,这种方法依赖于对未来项目序列的预测,然后通过反向归纳递归地解决大型线性规划问题。Mirrokni等人[12]引入了所谓的银行账户机制,该机制具有简单的结构,并且可以在单个买方案例中实现前期个体合理性的最优收入。随后,作者将银行账户框架扩展到保证后期个体合理性,并展示了一种简单的随机构造,可以对一般多买方案例的最优收入进行5倍逼近[13]。Balseiro等人[3]0跟踪:网络经济学,货币化和在线市场WWW 2018年4月23日至27日,法国里昂the accompanying fees should be carefully calculated not to harmincentive compatibility and individual rationality.Secondly, we introduce the notion of buyer regret (or simplyregret) to quantify how much the dynamic incentive compatibilityis violated (Section 4). Intuitively, the regret of a buyer means howmuch the buyer can increase his/her utility by rejecting all thedynamic discounts. We import the bank account limits studied byMirrokni et al. [12] to enable a trade-off between revenue lifts andbuyer regrets: the regrets can be bounded by the product of bankaccount limits and prediction errors (Theorem 4.2). Such insightsprovide theoretical guidelines to reduce the regret.Finally, we conduct empirical studies to justify our insights onreal data from online ad auctions (Section 5). To the best of ourknowledge, this is the first work that examines the power of simpledynamic auctions on real data sets. In the first part, we simulateDSPs with different baseline reserves and dynamic discounts andshow how the revenue lifts, regrets, and buyer utilities change asbank account limits increase. In particular, the revenue lift couldbe as much as +150% comparing to the second price auctions withmonopoly reserves [10] while incurring relative regret 13% (of thecorresponding buyer utility), or +17% revenue lift with relative re-gret less than 0.2%. In the second part, we compare the statistics forthe same auctions but with empirical distributions of different lev-els of accuracy (including simulations on synthetic data generatedfrom known distributions, so we have access to the ground truthdistributions in this case) and observe that the regrets decreasesignificantly while keeping the revenue lifts almost unchanged.Combining the observations from both parts, we conclude that theguidelines from Theorem 4.2 do help in reducing the regrets.2PRELIMINARIES13600考虑一个类似的单个买家设置,不同时期的物品具有独立同分布的价值,并设计简单且确定性的机制,以接近最优收入。尽管在复杂性问题上进行了所有这些改进,但上述现有方法在多个买家情况下仍然需要随机分配规则,这在实际应用中是不可取的。更重要的是,它们中没有一个讨论实践中对买家价值分布的准确先验知识的不可用性,然而它们都采用了对买家价值的预测误差敏感的动态激励概念。0学习对激励的影响。博弈论和机器学习交叉领域的一个核心问题是如何从数据中学习最优机制(例如,参见Morgenstern和Roughgarden的论文[15,16])。对于静态机制设计(之前的论文中研究的情况),估计分布的误差可能会损害收入,但不会损害激励约束。在动态机制设计中,估计误差也会损害激励兼容性。据我们所知,我们是第一篇正式定义和估计机制的鲁棒性(买家遗憾)的论文。这一点特别重要,因为动态机制在收入和分配效率方面都有相当大的改进(无论是在理论上还是在数据上)。0我们的贡献。首先,我们提出了一族特殊的银行账户机制,称为动态第二价格拍卖(DSP),用于一般的多个买家设置,解决了前一段提出的实际问题。拍卖具有非常常见的拍卖格式(带保留价的第二价格拍卖),只是保留价根据拍卖的历史动态调整。我们在本文中的主要目标不是设计收入最优的拍卖,而是提供一种实践中可以实施且易于从带保留价的第二价格拍卖切换的动态机制设计,这是大多数广告交易所默认运行的拍卖。我们假设基线是带个性化保留价的静态第二价格拍卖。我们对这些保留价的性质持中立态度,它们可以是收入最优的保留价,也可以是为了最大化收入和福利的组合而选择的保留价。我们的主要定理展示了如何处理现有的保留价并产生一个动态激励兼容的拍卖(定理3.1),并且在收入和社会福利方面都明显优于基线拍卖(命题3.2)。此外,我们通过数据验证了这种改进是相当显著的(第5节)。DSP的思想如下:在静态第二价格拍卖中,保留价通过引入基于买家在过去时期累积的效用来改善效率。DSP还引入了额外的支付(称为“银行账户支出”),使买家有权以较低的保留价参与拍卖。这些支付将通过降低保留价来补偿收入损失。折扣政策和相关费用应该经过精心计算,以不损害激励兼容性和个体合理性。其次,我们引入了“买家遗憾”(或简称为遗憾)的概念,以量化动态激励兼容性的违反程度(第4节)。直观地说,买家的遗憾意味着买家通过拒绝所有动态折扣可以增加多少效用。我们引入了Mirrokni等人研究的“银行账户限制”,以在收入提升和买家遗憾之间进行权衡:遗憾可以由银行账户限制和预测误差的乘积来界定(定理4.2)。这些见解为减少遗憾提供了理论指导。最后,我们进行了实证研究,以验证我们对在线广告拍卖的真实数据的见解(第5节)。据我们所知,这是第一篇在真实数据集上研究简单动态拍卖的工作。在第一部分中,我们模拟了具有不同基线保留价和动态折扣的DSP,并展示了随着银行账户限制的增加,收入提升、遗憾和买家效用如何变化。特别地,与具有垄断保留价的第二价格拍卖[10]相比,收入提升可能高达+150%,而相对遗憾为13%(对应买家效用的相对遗憾),或者收入提升为+17%,而相对遗憾小于0.2%。在第二部分中,我们比较了具有不同精度水平的经验分布的相同拍卖的统计数据(包括对从已知分布生成的合成数据进行的模拟,因此在这种情况下我们可以访问基本事实分布),观察到遗憾显著减少,同时保持收入提升几乎不变。结合两部分的观察,我们得出结论,定理4.2的指导原则有助于减少遗憾。01Balseiro等人[3]和Mirrokni等人[12]提出的动态机制是确定性的,但都限制在单个买家的情况下。2虽然这个想法来自于Mirrokni等人[12,13],但是该机制经过精心重新设计以满足实际需求(第3节)。0我们研究的是一个卖方与n个买方在T个周期内重复交互的情景。每个代理人i∈[n]对于t∈[T]期间的物品的价值是vit∈V。如果xi∈[0,1]表示代理人i在t期间被分配物品的概率,他的效用是vit∙xit。在本文中,(i)我们使用上标作为代理人的索引,用粗体字体表示所有代理人的向量(即a=(a1,...,an)),并使用上标−i表示除第i个元素之外的向量(即a−i=(a1,...,ai−1,ai+1,...,an));(ii)我们使用下标作为周期的索引,a1..t表示序列a1,...,at。假设vit的值是从独立的3分布Fit中抽取的。分布Fit被假定为共同知识,但随机变量的实现对于代理人和设计者来说最初是未知的。每个周期发生以下事件:(1)每个代理人i学习他的值vit�Fit;(2)每个代理人i报告值ˆvit给设计者;(3)设计者实施结果xt∈[0,1]n并向代理人收费pt;(4)每个代理人获得效用uit=vit∙xit−pit。然后可以用每个周期的一对映射来描述动态机制,这些映射将报告的历史与结果相关联02初步研究0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, FranceTrack: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France13610实际上,假设代理人(买方)的价值是独立的,条件是每个特定的库存和cookie。如果不独立,则仍然成立弱版本的真实性,即如果所有其他买家都真0uit(vit;ˆv1..t)=vit∙xit(ˆv1..t)−pit(ˆv1..t)0ˆv1..t=(ˆv1,ˆv2,...,ˆvt)对于结果xt和付款pt,即xt:Vnt→[0,1]n和pt:Vnt→Rn。因此我们可以定义:02.1动态激励相容性0如果xt和pt仅是时间t报告的估值vt的函数,则机制是静态的。0vit=argmaxˆvituit(vit;ˆv1..T)0对于所有i,ˆv1..T−1,ˆv−iT,viT。为简化表示,从现在开始我们将省略“对于所有”量化,并假设所有表达式在其自由变量中都是“对于所有”量化的。对于倒数第二个周期,鉴于代理人在下一个周期将真实报告,应该是激励相容的:0vit−1=argmaxˆvit−1uit−1(vit−1;ˆv1..T−1)0+EviTuit(viT;�ˆv1..T−1,viT,ˆv−iT�)。0通过反向归纳进行所有周期,我们要求:0vit=argmaxˆvituit(vit;ˆv1..t)+Uit(ˆvi1..t |0其中第二项是继续效用,即假设代理人真实报告后从机制的后续周期获得的期望效用:0Uit(ˆvi1..t | ˆv−i1..T):=Evi(t+1..T)0T0τ = t + 1 u_i^τ(v_i^τ; �ˆv_1..t,v_i^t+1..τ, ˆv^-i^t+1..τ�)0�0在动态机制设计中一个众所周知的事实是DIC意味着代理i在每个周期中如实报告可以使其期望总效用U_i^0(ˆv^-i_1..T)最大化。02.2 事后个体合理性0另一个理想的约束是事后个体合理性,即代理在每个值的实现中应该从机制中获得非负效用:�∑_{t=1}^T u_i^t(v_i^t; v_1..t) ≥ 0 (eP-IR)0我们将重点关注在DIC、eP-IR和可行性约束下最大化收益的问题:0max Rev = E[∑_{t=1}^T ∑_{i=1}^np0s.t. (DIC), (eP-IR) , and feasibility: ∑_{i=1}^nx_i^t(v_1..t) ≤ 102.3 银行账户机制0满足DIC和eP-IR的机制空间非常广泛且无结构。在本节中,我们将限制注意力在Mirrokni等人引入的一类动态机制的子类上,称为银行账户机制。这些机制简单,动态激励兼容,并且具有显著特点,即0对于任何分布,都存在一个收益最优的银行账户机制。更具体地说,对于任何满足DIC和eP-IR的动态机制,都存在一个至少具有相同福利和收益的银行账户机制。银行账户机制为每个买家保留一个称为余额的标量状态。每个周期都通过买家余额的向量依赖于前几个周期。另一个主要特点是,在这个框架中,设计者需要指定与有效的余额更新策略一起满足单期拍卖的单期激励兼容性约束。也就是说,一旦有效的余额更新策略到位,设计者只需要关注单期激励兼容性约束。银行账户机制B在每个周期中定义了以下函数:0• 一个由余额向量b ∈R^n+参数化的静态单期拍卖,即(single-period)激励兼容,对于每个b,即:0≥ v_i^t ∙ x_B,i^t(�ˆv_i^t, v^-i^t�, b) - p_B,i^t(�ˆv_i^t,v^-i^t�, b) . (IC)0请注意,我们不要求机制是(单期)个体合理的。我们还要求代理的效用在期望上与余额无关,即:0� v_i t ∙ x_B,i_t(v_t, b) -0是一个不依赖于b的非负常数。 (BI)0• 一个余额更新策略b_B_t(v_t,b),它将先前的余额和报告映射到当前的余额,满足以下余额更新条件:00 ≤ b_B,i^t(v_t, b) ≤ b_i + v_i^t ∙ x_B,i^t(v_t, b) -p0给定余额更新函数,我们可以递归地定义b_t: V_t →R^n+,如下所示:0b_0 = 0且b_1(v_1) = b_B_1(v_1, 0)0并且b_t(v_1..t) = b_B_t(v_t,0这使得我们可以按照标准的方式定义一个动态机制:0在给定余额更新函数的情况下,我们可以递归地定义0在接下来的内容中,我们将滥用符号,省略上标B,并将x_t(v_1..t)和x_t(v_t,b_t-1)互换使用。先前研究中的一个重要定理是任何银行账户机制都满足DIC和eP-IR的更强要求。0定理2.1(Mirrokni等人)。满足IC、BI和BU的银行账户机制是动态激励兼容(DIC)和事后个体合理(eP-IR)的。02.4 银行账户限制0每个买方的余额是一个非负变量 b i,随时间变化。Mirrokni等人表明,余额可以用作跨周期依赖的度量。一种极端情况是对于所有买方,机制始终将余额保持为零。由于银行sit =ttmax r it,wit1 − Fit (v) dvbit−1 =ttmax r it,wit1 − Fit (v) dv.bit = min bit−1 + vitxit − pit, Li .Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France13620银行账户机制只能通过余额来依赖于之前的周期,如果余额恒定为零,机制必须在每个周期内独立运行静态拍卖。基于这一观察,作者提出了带有限制的银行账户机制作为限制跨周期依赖的一种方式。形式上,买方 i 的银行账户限制 L i意味着银行账户机制满足额外的银行账户限制约束:0� t ,0 ≤ b i t ≤ L i 。 (BL)0在第4节中,我们将展示在买方价值预测误差存在的情况下,银行账户限制如何在DIC保证和收入提升之间建立权衡。03 动态二价拍卖0Mirrokni等人提出了遵循银行账户框架的简单拍卖,这些拍卖在理论上是近似最优的,但仍然依赖于随机分配来保证收入。每个周期中的拍卖格式也是非标准的。相比之下,实践中使用的大多数拍卖都是基于保留价的二价拍卖的变体。本文的重点是设计一族实用的动态机制,这些机制可以在当前用于运行带保留价的二价拍卖的基础设施上轻松实现。我们的拍卖仍然基于银行账户框架,与通常的二价拍卖相比,不同之处在于保留价是动态的,并根据过去周期的报告进行调整。在描述我们的动态拍卖之前,我们回顾一下个性化保留价的二价拍卖的两种实现方式。给定每个代理的报告值 v i 和保留价 r i,以下拍卖是单周期激励兼容的:0• 急切保留价:获胜者是最高出价且满足 v i ≥ r i的买方,他的支付金额是他的保留价和高于保留价的第二高出价中的较大值。如果没有买方高于他的保留价,则没有获胜者。•懒惰保留价:我们选择出价最高的买方。如果他的出价高于保留价,他是获胜者,他的支付金额是他的保留价和第二高出价的较大值(无论第二高出价是否低于或高于保留价)。如果所选买方低于他的保留价,则没有获胜者。0它们在过滤和排序的顺序上有所不同。在急切模式下,我们首先过滤出低于保留价的买方,然后对他们进行排序。在懒惰模式下,我们首先根据他们的出价对买方进行排序,然后根据他的保留价筛选出最高的买方。我们提出的拍卖是一种混合模式,对于每个买方,我们有一个急切保留价向量 rE t 和一个懒惰保留价向量 r L t ,其中 r i ,E t ≤ r i ,L t。我们的拍卖将有两个过滤阶段,一个是在选出获胜者之前,另一个是在之后:0• 第1步:以保留价 r E t运行二价拍卖,按字典顺序进行打破平局。设代理 i为获胜者,使用 w i t 表示第二高出价。• 对于获胜者 i ,在 r i,L t ≥ r i ,E t 的条件下运行额外的公开价格拍卖。如果 v i t≥ r i ,L t ,代理 i 赢得物品并支付 max { r i ,L t ,w i t } 。0我们将通过随时间动态调整懒惰保留价 r i ,L t来使拍卖变得动态化,其调整是根据之前步骤中累积的余额 b t − 1的函数。除了上述定义的支付方式外,每个代理还将被额外收取一笔费用(由他/她的银行账户支付),我们称之为花费,用 s i t表示。我们的想法是,在每一步中,我们将向买方收取一笔预付费,以换取更有利的懒惰保留价。03.1 拍卖描述0本文的目标是设计实用的动态机制,以与具有储备的简单静态二价拍卖竞争。我们对储备价格的计算方式不关心,而是假设在每次迭代中都应用基线拍卖来确定储备价格 r i t。这些储备价格可以是收入最优的储备价格,也可以是在对福利损失进行约束的情况下优化收入的储备价格。我们的目标是处理这些储备价格,并提出一个动态拍卖,以在福利和收入方面改进原始拍卖。我们的拍卖将以每个买家 i 和步骤 t 的基线储备价格 r i t ,分布 F i t和银行账户限制 L i 作为输入。根据 r i t 和 F i t,我们将进行预处理步骤,生成储备下限 r i t ≤ r i t。在第3.2节中,我们将讨论预处理步骤需要满足的属性。现在,我们只是假设DSP拍卖可以访问每个 i 和 t 的一系列动态储备 [ r i t , r it ] 。0动态二价拍卖(DSP)输入:对于每个 i ,t ,F i t 和 [ r i t , r it ] 。对于每个 i ,L i 初始化所有买家的余额为零 b i 0 = 0每个时间步 t :(1)代理报告其价值 v i t ,并让 j 是出价高于r j t 的代理。(2)让 w i t 是其他代理 i ′ � i 的出价 v i ′ t 高于r i ′ t 或者在没有其他代理 i ′ 出价 v i ′ t 高于 r i ′ t的情况下为零。(或者等效地,如果从此拍卖中移除代理 i ,则w i t 是步骤1中的获胜出价。)(3)我们使用余额 b i t − 1计算动态懒惰储备 r i t ∈ [ r i t , r i t ] 。让0如果 b i t − 1 ≥ ¯ s i t ,则设置:r i t = r i t 和 si t = s i t 。否则,设置 s i t = b i t − 1 ,并找到r i t ,使得:0(4)如果 v j t ≥ r j t ,我们将项目分配给 j ,并设置 x j t= 1。对于其他 i � j ,x i t = 0。(5)向买家 i 收取金额p i t = x i t max ( w i t , r i t ) + s i t 。(6)更新银行账户为bit 1 − sit ≤ bit ≤ bit 1 + vit · xit (vt,bt ) − pit (vt,bt ).Evit [ˆuit ] = Evit[vit − max{rit,wit }]+=∫ ∞max{r it,wit }�v − max{rit,wit }� dFit (v)=∞max r i,wi1Fit vdv,(1),,13630定理3.1.上述定义的DSP满足IC、BI和BU。因此它是DIC和eP-IR。此外,还满足银行限制约束(BL)。0定理3.1的证明。根据DSP的定义,每个周期的2步拍卖是激励兼容的,并且附加支付 s i t 显然与 v i t无关。因此满足约束(IC)。通过将 p i t 替换为 b i t的构造,我们得到0由于 s i t ≤ b i t − 1,满足约束(BU)。然后我们验证约束(BI)。考虑代理 i从2步拍卖中获得的预期效用。0其中 [ x ] + : = max { 0 , x },最后一个等式来自分部积分。然后根据 s i t 的构造,0= E vit [ ˆ uit ] - sit = ∫ ∞ max { rit, wit } � 1 - Fit (v) �dv,(2)0这是一个与b无关的非负常数。因此,约束条件(BI)得到满足。最后,银行账户限制约束(BL)直接由bit的构造所蕴含。□03.2 收入和社会福利保证0我们证明,只要(i)动态懒惰储备rt和rt被适当设计,(ii)先验分布Fi1..T在基准储备附近具有正的概率密度,4(iii)基准储备既不明显过高也不明显过低,DSP拍卖总是能够产生比基准储备r1..T的二价拍卖更高的收入和社会福利。当银行账户余额bt足够大,动态储备可以设置为rt =rt而不违反BU约束时,DSP拍卖对于静态二价拍卖尤为有效。在这种情况下,每个周期的分配与具有储备rt的二价拍卖完全相同,因此社会福利高于具有更大储备rt ≥rt的基准。如果通过减少储备来增加分配概率,可以通过适当选择rt轻松实现,只要基准储备不明显过低,即社会福利尚未通过基准最大化。同时,收入严格增加,因为预期的买方效用减少。对于每个买方i,根据约束条件BI,他/她的预期效用是关于余额bt-1的常数,特别是当bit-1 =0时的预期效用相同。在这种情况下,拍卖等同于二价拍卖0事实上,这里的假设甚至可以更弱,只要买方价值vit落在[rit, rit]的概率是正的,即Fit (rit)< Fit (rit)。0对于买方i,他/她的预期效用受到其他买方储备减少的影响,与花费sit无关,独立于花费sit。50如果余额bt很大,算法将选择懒惰储备rit =rit,并且社会福利将优于基准拍卖的社会福利。然而,如果余额bt太低,懒惰储备rit可能更接近rit,并导致社会福利变得更糟。让sW为具有储备rit和dW (bt)的静态拍卖的福利,定义如下:0lift = max b dW (b) - sW loss = [sW - min b dW (b)] +0现在,如果我们能够保证大部分时间余额较高,那么福利提升将更接近于lift而不是-loss。余额bit是在区间[0, Li]内的随机游走,其中:0E [ bit + 1 - bit ] = E � xt i (vit - max { rit, wit })� + > 0,0对于δ = max i { rit - rit },有bit + 1 - bit ≥ -sit ≥ -(rit - rit) ≥-δ。通过随机过程的标准论证,平衡与Li的距离以指数速度减小,其概率为E [ bit + 1 - bit ]/δ,因此:0E [ dW (b) - sW ] = lift + exp (-1 / δ) (lift -0当δ足够小时,社会福利在DSP中是正的。换句话说,当rit足够接近rit时,DSP中的社会福利保证严格增加。总结起来,我们有以下命题。0命题3.2(收入和社会福利保证)。对于任何给定的基线储备rt,我们总是可以设计一个DSP,在收入和社会福利方面严格优于储备为r t的二价拍卖,除了以下极端情况:0• 给定的基线储备明显过高或过低,0� i,Pr [ v i t > r i t ] = 0或Pr [ v i t < r i0• r i t 附近的概率密度为零,即0� i,� δ > 0,Pr [ r i t − δ ≤ v i t < r i t] = 0。04 后悔和银行账户限制0在我们之前的理论分析中,一些假设在实践中不一定成立。特别地,一般情况下无法获得真实的先验分布F i t,而是常常使用经验估计˜ Fit进行收入最大化。在这种情况下,DIC约束不再保证,因为支付的一部分s i t可能由于F i t和˜ F i t之间的不一致性而被错误计算。05读者可能会想知道是否可能设计一个在同一时间内产生更高买家效用的DSP。正如我们将在第5节通过模拟展示的那样,可以通过使用略低的基线储备而不是给定的储备来实现。0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, France136404.1 后悔0为了从实证角度证明动态机制的激励保证,我们引入了买家后悔的概念,它衡量了通过禁用其银行账户(即存款d i t ≡0)而获得的买家效用增益。对于其他买家的固定行动、物品序列和买家i的估值,买家i的后悔指的是他/她从动态机制到一个禁用了动态组件的副本机制的效用变化,仅限于他/她自己。禁用某个买家的动态组件意味着禁用他/她的银行账户,即余额被固定为零。因此,他/她对第t个物品的储备价格将被固定为r i t = r it,与过去的时期无关。这种机制的一个实际特点是,通过禁用某个买家的存款,即d i t =0,买家将面临一个静态拍卖,即他/她在一个迭代中的出价不会影响他/她在后续轮次中的分配概率或定价。这提供了一个平滑的过渡,买家可以选择参与动态机制,否则继续参与静态拍卖。如果我们对买家的分布有完美的访问权限,买家选择参与动态组件对于买家的效用来说应该是无关紧要的。然而,如果先验计算不完美,买家可能会后悔参与动态拍卖的决定。在本节中,我们正式定义并限制了动态机制中买家后悔的概念。0定义4.1(后悔)。对于任何固定的物品和估值序列,买家i对于DSPM的后悔定义为他/她从M获得的效用(用˜ Utl i ( v 1 .. T)表示)与另一个除了买家i的动态懒惰储备被固定以外与M相同的DSP M'(用˜ Utl ′ i ( v 1 .. T )表示)之间的差异,即r ′ i t = r it。形式上,0R i ( v 1 .. T ) = ˜ Utl ′ i ( v 1 .. T ) − ˜ Utli ( v 1 .. T )。04.2 后悔、限制和预测误差0正如我们之前提到的,银行账户限制可以上界预测误差存在下的预期后悔的绝对值。特别地,以下定理量化了预测误差和银行账户限制对预期后悔绝对值的上界。0定理4.2(遗憾上界)。E[Ri] ≤ T ∙ limiti ∙prediction-errori0≤ TLi maxt, r'∈[rit,rit]01 -0∫ritr' (1 - Fit(v))0∫ritr' (1 - ˜Fit(v))dv01-0让我们从买方i在机制M的第t期使用估计˜Fit获得的效用开始:0˜uit(vit; vt, ˜bt) = vit ∙ ˜xit(vt, ˜bt) - ˜pit(vt,˜bt)0= [vit - max{˜rit, wit}] + - ˜sit(˜bt), (3)0其中˜符号表示可能受到估计˜Fit影响的项:0• ˜bt是机制M在第t期开始时实现的余额向量,0• ˜rit是买方i在第t期的动态储备价格,•˜sit(˜bt)是买方i在第t期的花费。0请注意,其他代理人的最高出价wit与余额向量˜bt和估计˜Fit都是独立的。机制M'的效用可以表示为˜uit(vit; vt,˜bt'),其中与机制M的效用唯一的区别在于买方i的银行账户被禁用,即(i)动态储备被固定为rit,(ii)花费始终为0,即0˜uit(vit; vt, ˜bt') = [vit - max{rit, wit}] +. (4)0以下引理捕捉了证明定理4.2的关键洞察力:0引理4.3。买方i每个单独期t的预期遗憾仅来自于由于不完美估计˜Fit引起的花费计算误差,即0E[vit�Fit]0|˜uit(vit; vt, ˜bt') - ˜uit(vit; vt, ˜bt)| = ˜sit(˜bt) -sit(˜bt).0引理4.3的证明。对v it�Fit的(3)和(4)取期望,我们得到预期效用60E[vit�Fit] ˜uit(vit; vt,0= ∫∞max{˜rit, wit} (1 - Fit(v)) dv - ∫max{rit, wit}max{˜rit,wi0E[vit�Fit] ˜uit(vit; vt, ˜bt') = ∫∞max{rit, wit} (1 -Fit(v)) dv.0因0E[vit�Fit] ˜uit(vit; vt, ˜bt') - ˜uit(vit; vt,0= ∫max{rit, wit}max{˜rit, wit} (1 - ˜Fit(v)) - (1 - Fit(v)) dv =˜sit(˜bt) - sit(˜bt).0□0定理4.2的证明。我们使用引理4.3来限制期望总遗憾:E[Ri] ≤ ΣTt=1E[vit�Fit] ˜uit(vit; vt, ˜bt') - ˜uit(vit; vt, ˜bt)0≤ ΣTt=1 ˜sit(˜bt) - sit(˜bt) ≤ ΣTt=1 ˜sit(˜bt) ∙ maxt', b01 - sit'(˜b)0˜sit'(˜0。0请注意,花费˜sit(˜bt)不超过余额˜bit,而余额受限于限制Li,因此ΣTt=1 ˜sit(˜bt) ≤ TLi。0对于预测误差项,如果wit ≥rit,则花费将为零,因此没有预测误差;否则,积分都是从某个动态储备rit到基准储备rit。因此,0maxt, b01 -sit(˜b)0˜sit(˜b)0���0∫ max{rit, wit} max{˜rit,wit} 1 - Fit(v) dv0∫ max{rit, wit} max{˜rit, - ˜Fit(v) dv0�������0= max t, r' ∈[rit, rit]0���0∫ rit r' 1 - Fit(v)0∫ rit r' 1 -˜Fit(v) dv0������ .0□0省略了中间步骤,这些步骤与定理3.1的证明中的(1)和(2)类似。0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27,
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebLogic集群配置与管理实战指南
- AIX5.3上安装Weblogic 9.2详细步骤
- 面向对象编程模拟试题详解与解析
- Flex+FMS2.0中文教程:开发流媒体应用的实践指南
- PID调节深入解析:从入门到精通
- 数字水印技术:保护版权的新防线
- 8位数码管显示24小时制数字电子钟程序设计
- Mhdd免费版详细使用教程:硬盘检测与坏道屏蔽
- 操作系统期末复习指南:进程、线程与系统调用详解
- Cognos8性能优化指南:软件参数与报表设计调优
- Cognos8开发入门:从Transformer到ReportStudio
- Cisco 6509交换机配置全面指南
- C#入门:XML基础教程与实例解析
- Matlab振动分析详解:从单自由度到6自由度模型
- Eclipse JDT中的ASTParser详解与核心类介绍
- Java程序员必备资源网站大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功