大型市场中的激励感知学习问题

13690大型市场的激励感知学习�0Alessandro EpastoGoogle研究纽约市，纽约aepasto@google.com0Mohammad MahdianGoogle研究纽约市，纽约mahdian@google.com0Vahab MirrokniGoogle研究纽约市，纽约mirrokni@google.com0Song Zuo†0清华大学北京，中国songzuo.z@gmail.com0摘要0在典型的学习问题中，一个关键步骤是使用训练数据从一组模型中选择一个模型，以优化一个目标函数。在许多多代理设置中，训练数据是通过代理的行为生成的，并且模型用于做出影响代理的决策（例如如何出售物品）。拍卖中学习保留价的问题是一个说明性的例子。在这种情况下，代理有动机影响训练数据（例如，在拍卖中操纵竞标），以操纵系统并获得更有利的结果。在本文中，我们研究了这种激励感知学习问题在一个通用的设置中，并且表明在两个假设下可以近似优化目标函数：（i）每个个体代理是一个“小”的（市场的一部分）；（ii）操纵是有成本的。对于我们的说明性应用，这可以很好地转化为在没有任何个体代理具有重要市场份额的拍卖中设置近似最优保留价的机制。对于这个应用，我们还表明第二个假设（操纵是有成本的）是不必要的，因为我们可以“扰动”任何拍卖，使其对代理来说成本高昂。0CCS概念0•计算理论→算法博弈论和机制设计；学习模型；博弈中的收敛和学习；计算广告理论；多代理学习；0关键词0激励感知学习；与策略性代理学习；大型市场；广告拍卖0�我们感谢匿名审稿人的有益评论。†本文作者在Google实习时完成了这项工作。该作者得到了以下资助：2011CBA00300，2011CBA00301，NSFC61033001，NSFC61361136003，NSFC61303077，NSFC61561146398，清华大学创新科研基金和中国青年千人计划。0本文根据知识共享署名-非商业性-禁止演绎4.0国际（CC BY-NC-ND4.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.31860420ACM参考格式：Alessandro Epasto，Mohammad Mahdian，VahabMirrokni和Song Zuo。2018。大型市场的激励感知学习。在WWW2018：2018年网络会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318604201引言0机器学习是计算一个模型或假设（来自一个固定的假设空间），最好地描述数据的科学，其中一个关键步骤是在数据上优化某个目标函数。这是通过使用一组观察到的历史数据点（称为训练数据）来完成的。许多机器学习的应用都是在博弈论环境中，即涉及到多个自利的代理，他们的行为会影响机器学习算法观察到的数据点，并且会受到底层优化算法选择的结果的影响。一个典型的例子是自动拍卖市场，比如在线广告市场，其中代理是竞标者，他们可以通过竞标行为影响观察到的数据点。在这个例子中，优化算法通常用于微调拍卖中的各种参数（例如保留价），这些参数对竞标者的直接经济影响很大。在这样的博弈论环境中进行学习可能非常具有挑战性：代理是策略性的，他们试图优化自己的效用函数。如果学习任务的结果对这些代理的效用有一定的影响，他们可能会试图操纵训练数据，以推动算法做出对他们有利的决策。主要的挑战是开发底层的优化算法，鼓励代理行为真实，从而得到正确的结果。过去已经研究了在存在这样的策略性代理的情况下的学习问题，然而已知的结果要么是针对特定的估计问题，要么主要是在无先验机制设计的背景下，不利用任何训练数据，或者只有少量的非策略性样本。在本文中，我们在一个简单（通用）的激励感知学习模型中研究了这个问题，该模型从训练数据中剥离了任务的学习复杂性，专注于策略性组成部分（第2节）。这个模型的一个激励应用是学习拍卖参数，如保留价。在我们的模型中，目标是从一个（潜在无限的）机制族（称为groundset）中选择一个机制，以优化目标函数（例如收入）。我们的主要结果是，在以下两个假设下，可以在这种情况下近似优化目标函数：0主题：网络经济学、货币化和在线市场 WWW 2018，2018年4月23-27日，法国里昂13700（1）个体代理是“小”的。0（2）真实机制集合中的机制是强激励兼容的，即不仅虚报值对于代理来说不比真实报告更好，而且比真实报告更差，差距是指定的。0在第3节中给出了上述属性在一般情况下的正式定义（定义3.2）。在上述条件下，我们可以证明存在一个近似激励兼容的机制，其目标函数的值接近于真实机制集合中最佳机制的值（定理3.4）。我们认为这些假设在许多实际情况下是合理的。第一个假设适用于没有任何代理具有显著市场力量的大市场。例如，在线广告市场通常满足这一条件。事实上，经济学中有越来越多的关于大市场的市场设计的文献，这些文献在类似的假设下设计市场机制[5,20]。第二个假设适用于环境中存在固有的不确定性，以至于买方（例如广告商）不能安全地虚报他的数据（例如出价）而不影响他的利益。例如，在第二价格拍卖中，如果最高竞价存在足够的方差，过高的出价会冒着以高于其价值的价格赢得物品的风险，而低于其价值的出价会冒着未能赢得低于其价值的物品的风险。这种方差在实践中普遍存在，可能来自于点击率预测的不确定性（例如在按点击付费拍卖中由搜索引擎预测）、其他买方的出价策略的变化、随机限制等。另一方面，对于干净的理论模型，我们将证明在拍卖的保留价格学习的激励兼容性应用中，即使真实机制集合最初不满足这个条件（定理4.1）：可以通过添加一个小的“扰动”来修改它们，使得所得到的机制满足上述条件，并且由于扰动而导致的收入损失很小（第4.1节和第4.2节）。我们提出的算法（算法1）简单实用：不是选择最大化目标函数值的真实机制集合中的机制（在没有激励约束的情况下这将是自然的选择），而是使用一个随机算法，在机制中选择一个“软”最大值。直观地说，这消除了当机制的目标函数值发生微小变化时，算法输出发生突变的情况。大部分工作是分析这个机制，并证明它具有所需的激励属性，并且实现的目标值接近最优值。0我们的贡献和技术。总之，我们在本文中的贡献如下：0•我们为一类主要的学习问题形式化了一种新颖的激励感知学习框架（第2节）。•在这个框架下，如果满足某种强激励兼容性约束（参见[13]），我们将展示一个一般的01个“小”的代理可能通过采用不同的策略对优化目标产生重大影响，但她虚报的意愿相对较小，与设计者在真实机制集合内可实现的最优目标相比较。直观地说，这意味着设计者的权力相对于代理来说相对“大”。0从给定的满足强激励兼容性的真实机制集合中，可以“学习”一个近似最优机制的随机优化策略。特别地，学习过程保证近似真实，并且随着买方市场力量的减弱，真实程度和近似最优性变得更强（定理3.4）。具体而言，我们展示了这种学习策略如何在重要的行业应用中使用，即第二价格拍卖中的保留价格学习（定理4.1）。特别地，我们通过对拍卖进行“微小扰动”来手动引入第二价格拍卖与保留价格的强激励兼容性（第4.1节和第4.2节）。从技术角度来看，正如前面讨论的那样，我们的一般优化算法基于一个“软”最大函数，从真实机制集合中选择近似最优机制。事实上，这样的“软”最大函数源自McSherry和Talwar的指数机制[22]。然而，我们强调，在强激励兼容性属性存在的情况下，我们采取了一种不同的方法来实现近似激励兼容性的保证。特别地，当一个代理对学习目标的影响足够大时（见第5节的一个具体例子），这样的保证更加强大。Nissim等人[26]表明，如果所有代理都存在足够大的常数虚报成本，甚至可以实现更强的后激励兼容性保证，然而，这与本文采用的强激励兼容性相比，是一个相当强的假设。为了将我们的一般结果应用于拍卖定价应用，我们需要强激励兼容性，这不是自动满足的。为了解决这个问题，我们引入了一些新颖的技术来“扰动”给定的拍卖。其中的高级思想是通过牺牲一小部分收入来消除系统中的不连续性和消除弱支配。0相关工作。我们在这里讨论一项密切相关的工作，并在第7节中详细讨论更多。Balcan等人研究了通过将市场分为两部分并将从每部分学到的价格应用于另一部分的技术来设计数字商品拍卖（因此供应无限）的问题。这样的技术实际上创建了许多非战略样本。然而，它仍然局限于可分离环境中的应用。特别地，对于单品拍卖，一般化（i）将买家分成不同的群体，（ii）从每个群体的出价中学习保留价格，以及（iii）将这些保留价格应用于其他群体，永远不会比简单地运行二价拍卖更好。因为从每个群体学到的保留价格永远不会超过该群体中的最高出价，并且将这样的保留价格应用于其他群体不能比将买家放在一起并运行二价拍卖更好，其中第二高的出价不低于保留价格（更多细节请参见示例6.1）。02 PRELIMINARIES0我们首先定义了一个经典学习问题中优化的一般框架，然后通过引入战略代理，将其扩展为这些代理共同持有数据点作为私有类型的情况。0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, France13710经典学习中的优化。广泛的一类学习问题的关键步骤是从给定的假设空间H中找到一个（近似）最优函数h，该函数最大化一些目标函数（或等价地最小化一些损失函数）在一组样本上的值。更具体地说，有m个样本d1,...,dm来自样本空间D，并且有一个预定义的目标函数W:H×D→R+。然后，目标是找到一个h∈H，使得平均上该目标最大化（有时是近似最大化）。0h�∈argmaxh∈H1m�j∈[m]W(h,dj)。0事实上，通常假设样本是从一个潜在分布中抽取的，并且目标是最大化，例如，从相同分布中抽取的下一个样本的预期目标。与学习非战略样本的情况相比，学习战略样本（意味着样本由自私代理私下持有）的任务在没有关于这些样本的先验知识假设的情况下通常更加困难。原因是一方面，设计者在这种情况下拥有较少的信息，另一方面，代理有更多的自由来战略行为。0通过引入战略代理，我们扩展了上述经典学习框架。如前所述，在这种情况下，m个样本是由n≥1个不同代理的联合行动产生的。特别地，每个样本由这n个代理分别私下持有的n个部分组成。请注意，这可能是最一般的设置，我们不强制要求不同代理持有同一样本的部分之间存在任何特定关系（例如，这些部分可以是整个样本的n个副本，或者是样本的n个不相交的组件等）。同时，每个代理可以任意虚报她持有的部分，而不管其他代理向设计者报告了什么。为了与常见的机制设计术语保持一致，我们将代理持有的部分称为私有类型，用θ∈Θ表示。因此，在战略设置中，每个样本可以由代理报告的私有类型的向量θ=(θ1,...,θn)∈Θn来表示。与标准的机制设计设置一样，我们假设设计者选择一个机制M:Θn→[0,1]，将代理报告的类型向量（即样本的表示）映射到结果o∈[0,1]。在要求代理报告其私有类型之前，该机制将公开地向所有代理宣布。设计者的目标W以及每个代理i的效用ui基于此结果o定义：•设计者目标W：[0,1]→R+，对每个结果都有定义；•代理效用ui：Θ×[0,1]→R+，对每个私有类型θi和结果o都有定义。最后，设计者在这个战略设置中的目标是提出一种优化算法，从给定的集合M中选择一个机制M（近似地）最大化m个结果（每个来自一个样本）的平均目标¯W。0¯ W = 0m ≤ j ∈[ m ] W ( o j ) =0m ≤ j ∈[ m ] W ≤ M ( ˆ θ 1 j ,. . . , ˆ θ nj ) ,0其中 ˆ θ ij 是样本 j 中代理 i 的报告类型，M = A( ˆ θ ) 是优化算法A 选择的机制。我们允许 A是随机的，因此选择的机制可以被看作是机制集合 M上的一个分布。0可以被看作是机制集合 M上的一个分布，并且设计者的目标是最大化期望的平均目标，其中期望是针对优化算法 A的随机性（以及所选择的机制的随机性，如果有的话）进行的。类似地，每个策略代理i，在提前知道优化算法的情况下，旨在最大化自己的（预期的）平均效用，¯ U i：0¯ U i =0m ≤ j ∈[ m ] u i ( θ ij , o j ) 10m ≤ j ∈[ m ] u i ≤ θ ij , M ( ˆ θ 1j , . . . , ˆ θ nj ) = .0当优化算法是随机的时候，期望是针对 A和所选择的机制的随机性进行的。这个学习任务的最终结果在每个代理根据其他代理和设计者事先承诺的优化算法的行动做出某种最佳反应（或近似最佳反应）的均衡点上进行评估。0启示原理和真实性。对于优化算法A，到目前为止，我们只指定了它的输出应该是机制集合 M的一个元素或分布。我们没有对 A的输入类型进行任何限制：它可以是设计者和代理之间的交互通过自适应输入给 A，或者是 A用来从代理那里获取私人信息的更复杂的方案。幸运的是，机制设计理论揭示了如何在不损失任何广义性的情况下限制优化算法的设计空间。观察到优化算法实际上可以被看作是该系统中更高层次的一个机制。然后，机制设计中的一个通用工具，启示原理[25，p.224]，建议将设计空间限制为直接机制是没有损失广义性的。通过应用机制设计中的标准论证，我们能够直接关注以私有类型作为输入并满足真实性属性的优化算法，这通常被称为激励兼容性。0定义2.1（激励兼容性（IC））。如果对于任何代理i（不考虑其他代理的行动），向 A真实报告她的私有类型是一个占优策略，那么优化算法 A就是激励兼容的。形式上，对于任何类型向量 θ i = ( θ i 1 , . . . , θim ) ∈ Θ m ，其（预期的）平均效用不低于报告任何其他类型向量θ ′ i ∈ Θ m ，给定其他代理报告的类型向量 θ − i ∈ Θ ( n − 1 )×m ，01 m ≤ j u i ≤ θ ij , A j ( θ i , θ − i ) ≥0m ≤ j u i ≤ θ ij , A j ( θ ′ i , θ − i )≤ , (IC)0其中我们使用 A j ( θ ) 表示机制 M 在输入 θ 上对样本 j 的结果。当A 是随机的时候，期望应该在两边都考虑到 A 的随机性。0我们还采用了标准的 ϵ-近似激励兼容性的概念，这意味着真实报告与任何其他报告相比不会更差。形式上，01 m ≤ j ∈[ m ] u i ≤ θ ij , A j ( θ i , θ − i )≥ 10m ≤ j ∈[ m ] u i ≤ θ ij , A j ( θ ′ i ,θ − i ) ≤ - ϵ ,0跟踪：Web经济学，货币化和在线市场WWW 2018年4月23日至27日，法国里昂ui vij,oj = xij vijpij,RevA(v) :=ui θi, M(θ ′i ,θ−i) ≤ ui θi, M(θi,θ−i) − δ(|θi − θ ′i |).Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France13720这等价于 ϵ = 0 的激励兼容性。此外，通过启示原理，由 ϵ-近似激励兼容算法实现的结果对应于某个间接机制的 ϵ-均衡，反之亦然。最后，我们要求基础集合 M中的所有机制都是激励兼容的，可以通过将机制 M 视为始终选择 M作为输出的优化算法来定义。02.1 具体拍卖设置0作为激励感知学习框架的一个具体应用，我们将考虑拍卖设置，其中设计者/卖家（他）通过 m 个并行的单物品拍卖将 m 个物品同时卖给n个代理人/买家（她）。物品是异质的，买家具有加性价值和准线性效用。设买家 i 的私有类型 v ij = θ ij ∈ Θ = R + 表示她对物品 j的价值。作为价值的标准概念，我们将在整篇论文中使用 v ij表示拍卖设置中买家的私有类型/价值。那么她从拍卖 j（卖出物品 j的拍卖）中获得的效用是0其中结果 o j = �( x 1 j , . . . , x nj ) , ( p 1 j , . . . , p nj )� 包括分配 x ij∈ [ 0 , 1 ] 和每个买家 i 在此拍卖中的支付 p ij ∈ R +。此外，对于每个拍卖 j ，必须满足以下可行性约束：0对于任意 v ∈  R n × m + , i ∈[n ] x ij ( v ) ≤ 1 .0为了简化表示，我们滥用 x ij 和 p ij的重载，即将其作为分配规则和支付规则，即从报告的值到分配和支付的函数，这样拍卖（或机制） M可以简单地由这对函数定义。对于拍卖的具体应用，卖家通常被要求为每个买家提供离开拍卖的选项。通过离开拍卖，买家不支付任何费用并且什么都不得到。特殊选项和 IC约束的组合被称为个体合理性。01 m ∈[ m ] u i v ij ,  A j ( v i , v − i ) ≥ 0 . (IR)0由于我们要求 M中的每个拍卖都是激励兼容的，我们还要求它是个体合理的。特别是为了简化表述，我们主要考虑作为具有匿名保留价的二价拍卖的拍卖集合，这在拍卖理论中得到了广泛研究并被行业广泛采用[6, 18,27]。我们以卖家的目标即收入为基础，即从买家收集的总支付金额。0m ∈[ m ] W  ( o j )  =  10m ∈[ m ] i ∈[ n ] p ij (v ) .03 以放松真实性约束进行学习0我们现在提出我们的第一个主要结果：我们首先介绍我们的强激励兼容性概念，并基于这个属性，展示一个通用的激励感知学习方法，可以用来从给定的基础集合中学习一个近似最优机制（以任何给定目标为准），同时确保（近似）激励兼容性。为了获得一个选择基础集合中的机制的激励兼容算法，我们0自然地，我们需要基础集合中的机制也是激励兼容的。事实证明，对于任何优化算法来说，一些更强的激励兼容性概念，如强激励兼容性，是必要的。03.1 强激励兼容性0为了解释强激励兼容性的概念，让我们从拍卖的例子开始。激励兼容性要求对于每个代理人，真实报告价值（作为代理人的出价）至少与任何错误报告的价值一样有利可图。对于强激励兼容性，我们要求错误报告价值比真实报告更差。此外，我们要求这种“错误报告成本”的大小至少与错误报告的大小成比例。具体来说，0定义3.1. 令  δ是定义在正实数上的函数。如果对于每个代理人i，任何类型θ和代理人i的错误报告θ ′ i ，机制M都满足以下条件，则机制M是δ-强激励兼容的。0在一般情况下，我们需要对定义更加谨慎，因为在这种情况下，“出价”没有数值意义（例如，它甚至可以是一个分类值），因此我们必须用另一种数量来替代错误报告的幅度（| θ i  −  θ ′ i|）。事实证明，衡量错误报告幅度的正确数量是代理人可以对设计者的目标函数产生的差异量。这给出了以下定义。0定义3.2（强激励兼容性）。对于给定目标W，机制集合M是δ-强激励兼容的，如果通过错误报告来操纵任何M ∈M的目标值，使得代理人i遭受的损失不小于δ（λ），其中δ：R+ →R+是一个弱增函数和非负函数。形式上，对于所有θ ∈ Θn，θ ′ i ∈Θ，M ∈ M，0其中λ i ：= max M ′ ∈M �� W  � M ′ ( θ  ′ i , θ − i ) �  − W  � M ′( θ i , θ − i ) ��� .0强激励兼容性定义的直观理解来自于复杂环境中大型实际系统的观察。虽然要求激励兼容性，但通常假设代理人具有无限的知识和无限的计算能力。然而，在实际应用中并非如此。在实践中，对于代理人来说，操纵可能在计算上是困难的[11,12]，因此对他们来说是一种昂贵的选择。更重要的是，系统中的不确定性和动态性使得代理人几乎不可能完全预测其他代理人的行动，系统中某些部分的随机性，或者未来。因此，在这种部分可观察的环境中进行错误报告对代理人来说是有风险的。与真实行动相比，偏离真实行动越大，他们可能遭受的损失风险就越高。因此，在实际应用中，代理人将承担错误报告的成本。这个成本可能很小（与通过操纵学习系统获得的潜在收益相比），但随着错误报告的幅度增加而增加。w Mexp α1mjm]W M( ˆθ1j, . . . , ˆθnj);Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France13730算法1：随机激励感知学习0输入：有限的基础集合M，代理人报告θ  j，� j ∈ [ m ]输出：一个由Pr [ M ]描述的随机机制初始化：对于所有M ∈ M，w ( M ) ←0；对于基础集合M中的每个M，执行以下操作0计算0对于基础集合M中的每个M，执行以下操0随机机制选择M的概率是Pr [ M ] ← w ( M ) � M ′ ∈M w( M ′ ) ;03.2 强激励兼容性和可学习性0强激励兼容性的概念实际上部分地描述了在该系统中学习的难度。然后我们展示了两个例子，一个易于学习，一个难于学习，都是在单品拍卖的背景下。0最大化社会福利。考虑设计者的目标是社会福利，机制集合是VCG机制的情况。具体来说，让我们关注单品拍卖，其中VCG机制是第二价格拍卖，设计者的目标是社会福利，即W ( o ) = � i ∈[ n ] x i ∙ θi。在这种情况下，δ ( λ ) =λ，学习任务在所有代理人都有动力真实报告的意义上是容易的。0针对一个主导买家的最大化收入。考虑第2.1节中描述的拍卖设置。更具体地说，只有一个买家对物品有很大的价值，而其他买家只有微不足道的价值。在这种情况下，δ(λ) =0，学习几乎是不可能的，因为主导买家总是可以假装拥有略大于其他人价值的小价值。第二个例子表明，为了获得具有合理近似保证的优化算法，对于代理商来说，操纵设计者目标的一些成本是必要的。03.3一个通用的优化算法0现在我们提出了一个通用的优化算法，该算法由一个称为学习率的正实数α参数化。为了简化演示，我们主要关注M是一个有限基础集合的情况，但我们将在后面展示对无限基础集合的自然推广（见第6.6节）。上述优化算法本质上返回给定基础集合M上的一个分布，其中每个机制M∈M的概率与f(¯W(M))成比例：0Pr[M] ∝ f(¯W(M)) :=0m�j∈[m]W(M(ˆθ1j,...,ˆθnj))是机制M的平均目标。下一个定理说明了算法1返回的随机机制是ϵ-激励兼容和近似最优的。特别地，ϵ和算法的次优性依赖于三个参数：学习率α，δ(∙)强激励兼容性和代理市场力量u�的定义如下。0定义3.3（代理市场力量）。代理市场力量u�是一个衡量代理商能够从机制选择中获益的量，即0u� := ma) − ¯ui(M′′)),0¯ui(M) := 10m�j∈[m]ui�θij, M(θ1j,...,θij,...,θnj)�.0如果一个代理商的市场力量相对于在M中实现的最优目标OPT来说很小，则称该代理商为“小”。0定理3.4.算法1返回的随机机制是ϵ-激励兼容和近似最优的，其中tanh(∙)是双曲正切函数。2:0ϵ = max λ ≥ 0 [u� ∙ tanh(αλ/2) − δ(λ)] and ALG ≥ OPT − 10αln|M|,0从定理3.4中得出的两个结论：(i)算法的鲁棒性（激励兼容性的强度）和最优性之间的权衡（由学习率α控制）以及(ii)由激励兼容性的强度δ(∙)和代理市场力量u�所表征的权衡的难度/效率。学习率α：学习率越大，算法的最优性保证越强，激励兼容性保证越弱，反之亦然。直观地说，当α非常接近零时，随机机制几乎是在基础集合上均匀随机的。在这种情况下，代理商几乎没有动机报告错误的私有价值（因此具有更强的IC保证），因为机制的选择几乎与他们的报告无关。然而，均匀随机机制可能与最优解相差甚远。相反，当α非常大（趋近于∞）时，随机机制几乎将所有的概率质量分配给最优机制。在这种情况下，算法几乎是最优的，但IC保证与从基础集合中选择最大目标的机制一样糟糕。激励兼容性的强度δ(∙)：系统能够保证的激励兼容性越强，我们的算法就能够得出越好的近似激励兼容性结论。正如我们在第3.2节的例子中讨论的那样，δ(∙)越大，学习具有良好IC保证就越“容易”。代理市场力量u�：代理市场力量越大，我们能够保证的激励兼容性就越弱（因此学习越困难）。直观地说，当代理市场力量较小时（与OPT相比较小），即从代理商的角度来看，基础集合M中的机制之间几乎没有差异，任何优化算法都必须接近激励兼容，反之亦然。该定理的证明分为两个步骤：引理3.5用于近似激励兼容性和引理3.6用于近似最优性。这些引理的主要结论相当直观，但其中的数学技巧相当具有挑战性。我们将证明放在第6节中。0引理3.5.算法1的随机机制是ϵ-激励兼容的。特别地，对于每个代理i，ϵ不超过ϵ i = max λ i ≥ 0 [ u � i ∙ tanh ( αλ i / 2 ) − δ ( λ i )] .0引理3.6. 算法1是近0ALG = ¯ W (A) : = 10m ∈[ m ] W A ( θ ) ≥ OPT - 10α ln |M| .0定理3.4的证明。直接由引理3.5和3.6。□02 tanh ( x ) = e x0e x + e − x ≤ min { 1 ,x } .13740权衡的具体例子。再次考虑单项拍卖设置的例子，看看我们应该牺牲多少激励兼容性来实现（1 - ρ）-近似最优机制，其中ρ >0是一个小常数。假设δ（λ）是一个二次函数（关于这个假设的进一步讨论见第4节），我们有以下推论：tanh（x）≤ x（对于x ≥ 0）：0推论3.7. 当δ（λ）= δ（2）∙ λ 2是一个二次函数时，0ϵ ≤ max λ ≥ 0 [ u � ∙ λα / 2 − δ ( 2 ) ∙ λ 2 ] = (αu �0使用定理3.4，我们需要学习速率至少为α = ln |M|/(ρ ∙OPT)。因此，当OPT � u�时，ϵ非常小。类似于代理市场力量，实际上，可以将OPT视为设计者的市场力量。然后，OPT � u�意味着设计者对代理有优越的市场力量。如果买方真实报告的效用接近零（或小于ϵ），则可能会担心ϵ-激励兼容性是可加的，这可能没有太多意义。幸运的是，我们可以通过牺牲最多一小部分收入将机制转换为具有乘法近似激励兼容性约束的另一个机制。注意，在单项拍卖设置下，对于买方来说，更理想的拍卖（来自具有保留价的二价拍卖）是普通的二价拍卖（即没有保留价），其中买方效用至少为u�。通过对原始机制和普通二价拍卖（后者以小概率选择）进行凸组合，收入减少不超过一小部分，同时获得强大的乘法激励兼容性保证，只要OPT � u �。04 将学习应用于二价拍卖的保留价0在本节中，我们展示了如何将一般的激励感知学习框架应用于一个说明性例子 -学习二价拍卖中的保留价。如第2.1节所述，我们考虑单项拍卖设置，其中每个样本对应于出售一个物品的二价拍卖，卖方的目标是找到最大化他的收入的保留价。基础集M包括具有不同保留价的二价拍卖。为了方便起见，我们考虑为所有样本学习一个匿名保留价的问题。请注意，在经典学习的背景下，这是一个简单的任务，因为买方不是策略性的。然而，当买方是策略性的时，这通常是具有挑战性的，因为M中的具有保留价的二价拍卖不满足强激励兼容性，因此我们不能直接使用第3节中介绍的优化算法。在我们的第二个主要定理中，我们展示了通过对机制进行一些“扰动”，我们可以应用我们的一般学习方法，但会损失一小部分额外的收入。0定理4.1.以一小部分收入损失为代价，我们可以“扰动”M中的机制，然后应用我们的一般激励感知学习算法，同时保证近似激励兼容性和最优性（与原始基础集M中的最优拍卖相比）。303我们省略了具体的近似数值，因为它们涉及我们尚未介绍的“扰动”的一些参数。0在本节的剩余部分，我们通过两个步骤对基础集M进行一些更改，以获得强激励兼容性，以便我们的一般激励感知学习算法适用：•使得任何买家操纵任何候选拍卖的收入都必须显著改变她的出价；•使得任何买家的效用损失与她出价的变化成二次关系。04.1 第一步：买家必须显著改变出价才能影响收入0在具有任何固定保留价的二价拍卖中，一些买家可以通过微小的出价变化显著改变收入。接下来，我们将展示如何对基础集M进行一些更改，以使得必须显著改变出价才能影响任何M∈M的收入。0定义4.2（具有随机匿名保留价的二价拍卖）。具有随机匿名保留价的二价拍卖由两个参数r≥0和γ∈[0，1]参数化。拍卖只是运行一个具有从[γr，r]均匀分布中随机抽取的匿名保留价的二价拍卖，即˜r�U[γr，r]。0假设M是具有匿名保留价的二价拍卖的原始基础集。然后我们构造一个相应的具有随机匿名保留价的二价拍卖的基础集M'。更具体地说，对于M中的每个具有保留价r的二价拍卖，我们构造一个具有从U[γr，r]中随机抽取的随机匿名保留价的二价拍卖。然后以下引理说明对于任何机制M'∈M'，任何买家i的误报所导致的平均收入变化λi不会超过她出价的平均绝对变化的一个常数倍。同时，在这个突变基础集M'中可以实现的最优收入OPT'接近原始M的OPT。因此，我们不会因为这种变异而损失太多。0引理40λ ≤ 10(1-γ)m�j | ˆvij-vij |和OPT'≥OPT-γOPT/2。04.2 第二步：在竞标变化中的二次效用损失0在标准的二价拍卖中，真实出价是弱支配策略，这意味着真实出价弱优于任何其他策略。这种弱优势给战略性买家在学习保留价时选择真实价值带来了困难。因为对于某些情况，买家可以进行显著的误报而不会在效用方面遭受任何损失。然而，在实践中，大多数拍卖设置固有的不确定性有几个来源，例如广告拍卖中的预测点击率，随机限制策略，甚至是互联网连接状态等。在存在这些不确定性的情况下误报可能会导致买家的效用损失显著增长（与误报的幅度超线性增长）。直观地说，买家在一次拍卖中提高出价的越多（与幅度成线性关系），她赢得物品的可能性就越大，价格也越高，她必须支付的价格也越高（与幅度成线性关系）。因此，她的效用损失往往与她的误报幅度成二次关系（降低出价的情况类似）。接下来，我们通过“扰动”拍卖和出价手动引入这种不确定性到系统中，即以一定的小概率β∈[0，1]，(i)将保留价r重置为从U[0，r]中随机抽取，(ii)以概率1/2独立地从拍卖中移除每个买家，其中r是基础集M中使用的最大保留价。通过这样做，我们将不得不牺牲一小部分β的收入，但这不会损害我们实现近似最优收入的目标。0跟踪：Web经济学，货币化和在线市场WWW 2018年4月23日至27日，法国里昂Lemma 4.4.δi(λi) ≥ (1−γ )β8mr�j λ2ijandOPT′′ ≥ OPT − (γ/2 + β)OPT.5COMPARING WITH MECHANISM DESIGNVIA DIFFERENTIAL PRIVACYIn this section, we compare our incentive guarantee (Theorem 3.4)with McSherry and Talwar [22] under the incentive-aware learningframework. In particular, our guarantee is stronger than theirs whenthe impact of each agent on the learning objective is sufficientlylarge.Suppose that the objective on two data sets differing on thereports of agenti is at most λ∗i , and λ∗ = maxi λ∗i . Then according toMcSherry and Talwar [22, Lemma 3 and Theorem 6], the incentive-aware learning algorithm is ϵ-approximately incentive compatible,whereϵ = u∗� exp(2αMT · λ∗) − 1�.In other words, applying their bounds, the learning rate αMT shouldbe at mostαMT = ln(1 + ϵ/u∗)/2λ∗.Suppose that the function δ(·) is quadratic, as we argued in Sec-tion 4 for second price auctions, i.e., δ(λ) = δ(2)λ2. Then to achievethe same ϵ-approximate incentive compatibility, by Corollary 3.7,we require the learning rate to be at most αIA:αIA = 4�δ(2)ϵ/u∗.Therefore, when λ∗ ≥ u∗ ln(1 + ϵ/u∗)/8�δ(2)ϵ,αIA = 4�δ(2)ϵ/u∗ ≥ ln(1 + ϵ/u∗)/2λ∗ = αMT.In practice, we will need ϵ ≪ u∗, therefore, when λ∗ ≥ u∗ ln(1 +ϵ/u∗)/8�δ(2)ϵ ≈�ϵ/δ(2)/8, with our analysis for incentive-awarelearning, a higher learning rate is acceptable. Hence the loss interms of the optimality could be made smaller (cf. Theorem 3.4).6EXAMPLES AND MISSING PROOFS6.1The limitation of separation tricksIn single-item auctions, separating buyers into two groups cannotbe better than simply running a second price auction.Example 6.1. Consider a single item auction with N i.i.d. buyers,values drawn from uniform [0, 1]. For large N, by randomly splittingthe buyers into 2 groups, the seller can almost perfectly estimate thebest reserve, 0.5, but with very high probability only about N/2 buyersin each group. Since there is only one item for sale, the seller mustdecide (maybe randomly) to which group the item should be sold,where the expected revenue is roughly (N − 2)/(N + 2). Howeve