本文作者：少平、妙临

导读： 传统拍卖机制不存在了！出价产品智能化成为行业发展趋势，自动出价（Auto-bidding）已成为互联网广告主营销的主流，经典效用最大化模型（Utility Maximizer）的假设已经不再能良好地刻画此类广告主，传统拍卖机制在Auto-bidding下的激励性质和最优性需要被重新思考。

摘要

数字广告是互联网平台的主要收入来源之一。近年来，很多广告主开始采用自动竞价（Auto-bidding）工具来优化广告效果，这使得拍卖理论中经典的效用最大化模型（Utility Maximizer）不再能够良好地刻画此类广告主。因此，近年来业界研究提出了一个新的模型，称为价值最大化模型（Value Maximizer），用于有投资回报率（ROI）约束的自动竞价广告主。然而，无论是效用最大化还是价值最大化的模型，都只能刻画实际广告平台中的一部分广告主。在效用最大化广告主和价值最大化广告主并存的混合环境中，真实的广告拍卖设计属于多参数机制设计问题，因为广告主可以同时操作他们的广告点击价值和所属的类别两个信息。

本文提出了一种满足真实性(Truthfulness)的拍卖机制，其通过巧妙结合经典的VCG和GSP机制中的扣费规则来解决多参数机制设计中的复杂性问题。同时该机制具备良好的机制性质，其社会福利的近似比为2，我们同时也证明了该近似比的下界为1.25。特别值得一提的是，我们所设计的拍卖机制是针对效用最大化广告主的VCG和针对价值最大化广告主的GSP两种拍卖机制的自然推广。基于该项工作整理的论文已被AAAI 2023录取，欢迎阅读交流。

论文：Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising

下载：

一、背景介绍

在典型的数字广告场景中，平台通过Vickrey-Clark-Grove（VCG）拍卖机制或广义第二价格（Generalized Second Price，GSP）拍卖机制进行广告位的分配并为广告主计算相应的扣费。在近二十多年的研究中，学术界和工业界已经发现，VCG是一种能够满足真实性（Truthfulness，也称诚实性或激励兼容性）的机制，而GSP虽然是工业界更普遍的选择，却并不满足真实性，不过GSP拍卖中存在无嫉妒纳什均衡，而且所有无嫉妒纳什均衡的收益都不比VCG低[1,2]。

现有的关于VCG和GSP的分析主要建立在拟线性效用模型上，也被称为效用最大化广告主（Utility Maximizer，UM），即广告主的目标是优化其分配的价值和扣费之间的差值。然而，在当前的很多在线广告系统中，广告主已经开始使用自动竞价（Auto-bidding）工具，利用自动竞价工具，广告主只需要设置高层次的约束条件，即在一定的预算下，指定一个投资回报率（Return On Investment，ROI，所分配得到的价值和扣费之间的比例）的阈值约束。当投资回报率约束接近于1时，它可以由UM模型中的个体理性的性质来刻画。

然而，当投资回报率约束变得较大时，经典的UM模型无法刻画出广告主在自动竞价中的行为。因此，雅虎公司的研究人员Wilkens、Cavallo和Niazadeh[3]为广告主提出了另一个模型，称为价值最大化广告主（Value Maximizer，VM），该模型将分配的价值作为广告主的首要目标，将扣费作为其次的目标，只有当价值相同时才偏好扣费更少的结果。他们通过理论分析和实际系统中的观察发现，只要广告主的投资回报率约束稍高（高于2或3），其行为模式就会接近VM模型对应的行为模式。这个新模型带来了一个重要的理论结果，即工业界常用的GSP拍卖成为一个满足真实性的机制，这为GSP在工业界的普遍使用提供了一个新的视角，也使得VM模型吸引了学术界和工业界的广泛关注。

然而，无论是UM还是VM模型，都只能代表一部分广告主，其中，UM代表投资回报率约束相对较低的广告主，而VM则代表投资回报率约束相对较高的广告主。由于广告主的投资回报率约束可能多种多样，那么当UM和VM这两类广告主同时存在于一个广告系统中时，如何设计一个满足真实性的机制呢？

这个问题包括两个层次：1）类别信息是公开的，即一个广告主只能自主上报他的广告点击价值； 2）类别信息是私有的，即一个广告主可以同时自主上报他的类别和他的广告点击价值。即使是较简单的第一种情况，也不是一个简单的问题，因为在这种情况下，广告主的策略性行为是未知的，也就是说VCG或GSP机制都不会满足真实性。而后一种情况更加符合实际场景，因为广告主可以很容易地操纵自己的投资回报率约束，以改变相应的类别，进而从中获益。这种私有的类别信息给广告拍卖机制设计带来了实质性的挑战，这一问题属于多参数机制设计领域，而这一领域通常面临较难解决的开放性问题。

在为了解决上述问题，我们要为公开类别信息和私有类别信息两种情况设计满足真实性的机制。针对公开类别信息的情况，存在以下满足真实性的机制，且能够保证最佳的社会福利：根据广告主对广告位的出价进行排序并分配坑位，然后按照VCG扣费规则向UM收费，按照GSP扣费规则向VM收费。该机制是直观的，但在某种程度上对VM是“不公平的”，因为VM与UM相比，获得相同的分配的前提下，在该机制中可能需要付出更多费用。这意味着该机制在类别信息是私有信息的情况下是不满足真实性的。

因此，我们进一步提出了一个针对私有类别信息的混合广告主的机制（Mechanism for bidders with PRivate classes，MPR）。MPR的关键思想是为每个坑位而不是每个广告主指定这样一个扣费规则：从下方最近的UM推导出的VCG式扣费值和从下方最近的VM推导出的GSP式扣费值中取最大值。有了这个扣费规则，MPR先通过自下而上的方式用所有的VM填充广告位，然后迭代地每次给一个UM分配一个具有最优效用值的广告位。大量实验证明，这种机制在广告点击价值和类别信息两个维度上都是满足真实性的，同时也保证了社会福利的近似比最高为2。我们还证明了，没有任何机制可以达到比1.25更好的近似比。

本文提出的MPR机制，主要成果包括两方面：一方面，我们首次研究了UM和VM并存的混合环境下满足真实性的广告拍卖机制设计，这为VCG和GSP机制的结合提供了一个有趣的视角：当所有的广告主都是UM时，我们提出的两个机制都会简化为VCG；当所有广告主都是VM时，会简化为GSP。另一方面，针对投资回报率约束的广告主的机制设计是近年来的一个热门研究问题[4,5]，我们的工作为理解该问题迈出了重要的一步。此外，我们的机制发现，一个满足真实性的机制可能会将更高的坑位分配给具有高投资回报率约束的广告主（即本工作中的VM），尽管他们的出价可能低于那些具有低投资回报率约束的广告主。

二、问题建模

在我们考虑的场景中，每个广告主可以是一个效用最大化广告主（UM），也可以是价值最大化广告主（VM）。它们的定义如下：

一个理想的拍卖机制应该满足以下三个要求：激励相容性（Incentive Compatibility，IC）、个体理性（Individual Rationality，IR）和稳健性（Robustness）。

定义3（激励相容性，IC）：一个机制是激励相容的，当且仅当

定义4（个体理性，IR）：一个机制是个体理性的，当且仅当

定义5（稳健性，Robustness）：如果当所有广告主都是UM时，结果与VCG相同，而当所有广告主都是VM时，结果与GSP相同，则该机制是稳健的。

换句话说，IC保证了机制中的所有广告主都没有虚报类型的动机，IR保证了广告主在诚实出价时不会得到负的效用值，而稳健性保证了机制是现有机制的自然扩展。我们将宽泛地使用“真实性（Truthfulness）”一词来描述一个既满足IC又满足IR性质的机制。众所周知，VCG对于UM是满足真实性的。近年来，也有工作证明了GSP对VM是满足真实性的。这些研究都集中在只有一类广告主且类别信息是公开的情况下。而在本工作中，我们的目标是为类别信息私有的混合广告主设计一个满足真实性的机制，同时使拍卖的整体福利最大化。在这里，混合广告主可以是UM也可以是VM。

值得注意的是，经典的社会福利概念，即所有广告主的效用和卖方的收入之和，对于VM来说并不是一个可行的定义，因为在社会福利的计算中，广告主和卖方之间的交易金额不能恰好抵消（这一点与UM不同）。因此，我们从此前针对预算约束的广告主的机制设计的文献[4,6]中借鉴了可变现社会福利（Liquid Social Welfare，LSW）的概念：

定义6（可变现社会福利，LSW）：一个机制中的分配结果的可变现社会福利 是所有广告主对该分配结果的最大付费意愿之和，即

我们定义可变现社会福利的比较基准为所有可能分配中的最大LSW，即

三、公开类别信息

首先，我们考虑一个简单的设定，即广告主的类别是公开的。在这种情况下，该问题属于单参数机制设计的范畴，相对比较简单，但对于理解后面章节中我们设计的机制很帮助。针对这种简单情况，我们提出了以下针对公开类别信息的广告拍卖机制（Mechanism for bidders with PUblic classes，MPU）。

机制1（MPU）：

直观地说，MPU直接按价值将坑位分配给广告主，而不考虑其类别。此外，UM的扣费遵循VCG，VM的扣费遵循GSP（注意我们使用自下而上的坑位索引）。我们接下来表明，这个机制是IC、IR和稳健的，同时也保证了最佳的LSW。

定理1：当广告主的类别是公开信息时，MPU满足IC、IR和稳健性，同时是LSW最优的。

参考此前基于UM模型和VM模型的文献，定理[1]的证明是直接的，因此这里将证明省略。

四、私有类别信息

在上一节中，我们提出了针对公开类别的混合广告主的最优机制。然而，当类别信息是私有的时候，这个问题就变成了一个多参数的机制设计问题，这在一般情况下很难解决。我们可以首先分析MPU在私有类别的设定下是否满足IC性质。我们可以很容易地观察到，如果一个VM把他的类别虚报为UM，同时如实地报告他的价值，他有可能会享受到更低的扣费同时不改变他的分配。换句话说，MPU在某种意义上对VM是不公平的，而这种不公平可能在类别信息是私有的情况下带来策略性操纵的可能性。

4.1 针对私有类别混合广告主的机制设计

上述分析意味着，在一个私有类别设定下的真实机制中，广告主的扣费应该只依赖于他被分配的位置，而不是他的类别。换句话说，假设一个广告主在两种情况下被分配到一个相同的坑位，而其他人的分配结果也是相同的，那么无论他是UM还是VM，扣费都应该是一样的。这一要求促使我们基于坑位设计扣费规则，而非基于广告主类别设计扣费规则，这一规则应当基于该坑位下方的广告主的类型，同时应当结合VCG和GSP。因此，我们提出将一个坑位的价格设定为以下两个条件的最大值：1）从下方最近的UM推导得出的VCG式扣费，以及2）从下方最近的VM推导得出的GSP式扣费。

当没有低于坑位的VM或UM时，我们将相应的扣费项定为0。基于这一扣费规则，我们提出了混合广告主机制（MPR），它是IC、IR和稳健的，同时在LSW上达到了理想的近似比。

图一 MRP机制算法流程

MPR的完整伪代码在图一中给出。MPR的关键思想是用所有的VM来填充坑位，然后迭代地给一个UM分配一个具有最优效用的坑位。

在图一中，MPR首先根据广告主的价值对其进行排序，并获得价值排名前 K 名的广告主的集合 N(第2-3行)。然后将价值第 (K + 1) 高的广告主分配到索引为0的坑位，作为定价的基础（第4行）。我们把 N 中所有的UM集合表示为 S，把 N 中所有的VM集合表示为 T（第5-6行）。接下来，MPR将 T 中的所有VM根据它们的值依次填充到最低坑位（第7-9行）。然后，我们基于分配的VM，按照公式一计算以下坑位的价格1≤ k ≤ [T] ≤1（第10行）。

最后，如果一个广告主被分配到了坑位，他的点击扣费将是该坑位对应的价格；否则，他的付费将是0（第21行）。

接下来，我们提供一个例子来说明MPR的运行过程。我们可以从这个例子中观察到一个有趣的结果：出价较低的VM可能比出价较高的UM获得更高的坑位。

图二（左边）例1中的示例，（右边）分配结果与价格

例1：假设有四个位置和五个广告主，他们的CTR和类别信息如图二（左边）所示。

4.2理论性质

在证明MPR的理论性质之前，我们首先定义两个坑位的_边际扣费增加值_的概念，以衡量广告主获得更高坑位时的成本表现。基于这个概念，我们提出几个引理来帮助理解MPR背后的思想，这些引理将对IC和IR的证明有帮助。

基于边际扣费增加值的定义，我们证明以下引理。由于篇幅原因，我们将证明过程略去。

基于以上这些引理，我们证明以下定理，作为本工作的主要结果。由于篇幅原因，我们将证明过程略去。

定理2：MPR是一个稳健的机制。

定理3：MPR满足个体理性。

定理4：MPR满足激励相容性。

定理5：MPR在LSW上可以实现不超过2的近似比，即：

定理6：没有任何一种IC、IR且稳健的机制可以实现低于的近似比。

五、结论

本文中，我们研究了UM和VM混合的广告环境中的机制设计问题，并提出了两种机制MPU和MPR，分别在类别信息公共和私有的情况下能够保证IC、IR、稳健性和（近似）最优LSW。这项工作为后续关于投资回报率约束广告主的研究提供了启发，同时也产生了一些开放性问题。其中最主要的开放性问题是如何缩小近似比的下界和上界之间的差距。我们猜想MPR在某种程度上是解决这个问题的最优机制，在后续的研究中我们希望能严格证明这一点。此外，我们将对这一机制进行推广，使之能够适用于多种类型投资回报率约束的广告主。

参考文献：

[1] Edelman, B.; Ostrovsky, M.; and Schwarz, M. 2007. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review, 97(1): 242–259.

[2] Varian, H. R. 2007. Position auctions. International Journal of Industrial Organization, 25(6): 1163–1178.

[3] Wilkens, C. A.; Cavallo, R.; and Niazadeh, R. 2017. GSP: the cinderella of mechanism design. In Proceedings of the 26th International Conference on World Wide Web, 25–32.

[4] Deng, Y.; Mao, J.; Mirrokni, V.; and Zuo, S. 2021. Towards Efficient Auctions in an Auto-bidding World. In Proceedings of the Web Conference 2021, 3965–3973.

[5] Balseiro, S.; Deng, Y.; Mao, J.; Mirrokni, V.; and Zuo, S. 2021. The Landscape of Auto-Bidding Auctions: Value Versus Utility Maximization. In Proceedings of the 22nd ACM Conference on Economics and Computation, 132–133.

[6] Dobzinski, S.; and Paes Leme, P. 2014. Efficiency guarantees in auctions with budgets. In International Colloquium on Automata, Languages, and Programming, 392–404.