漫谈广告技术中的拍卖机制设计（经典篇）

欢迎关注：

阿里妈妈技术公众号



本文作者

：石士

搜索、推荐和广告在过去几年互联网蓬勃发展的浪潮中起到了核心助推引擎的作用，三者技术发展也是互相借鉴和相辅相成，有很多共通之处也有不少差异的地方。

本文从广告视角出发，重点介绍广告技术与搜推技术最本质的差异点——拍卖机制的原理和实践

。作为最具广告特色的技术模块，拍卖机制理解起来往往较为晦涩。一方面因为这个技术领域是基于博弈论思维，概念较多且定理推导复杂，和已经标准化的基于数据驱动的机器学习思维截然不同；另一方面因为理论假设过于严格，和实际差距较大，使得论证过程无论多么完善，实践落地仍然需要考量诸多复杂因素。本文尝试将拍卖机制的几个经典问题做一个脉络性梳理，概念和论证过程可自行查阅这里不再赘述，但概念之间的演进关系会重点阐述，希望可以勾勒清楚技术全貌，有助于大家系统性地认识计算广告领域的拍卖机制设计。

本文会按照几个小话题顺次展开介绍：

• 广告领域的拍卖机制简化而言是一个什么拍卖问题，背后最基本的博弈论概念是什么；最理想的拍卖机制长什么样，需要满足哪些条件；理想照进现实，哪些条件可以妥协松弛使得真正落地的拍卖机制即使没有非常理想但依然运行良好；本文所说的经典的拍卖机制设计范畴是什么？
  
• 社会福利最大化的拍卖机制如何设计才能使得市场蛋糕被有效扩大；点击率的不同假设这一关键变量如何影响拍卖机制的性质；机制设计需要做哪些与之对应的调整与升级？
  
• 平台营收最大化的拍卖机制如何设计才能使得市场蛋糕被最优地分配；以保留价设计为代表的这一关键技术是如何影响拍卖机制的性质；机制设计背后的假设需要做哪些与之对应的调整？
  
• 经典的拍卖机制的基本框架长什么样；多个优化目标在这个框架下是如何平衡；面向广告业务新形势下的AutoBidding模式，拍卖机制该如何重新思考面向未来？
  

1. 初识广告拍卖机制和相关博弈论基础知识

1.1. 为什么说拍卖机制是广告与搜推最本质的差异点

先从本文开头提到的“为什么拍卖机制是广告与搜推最本质的差异之处”说起。以电商场景为例，搜索推荐涉及到免费资源位的高效分配问题，广告涉及到付费资源位的高效分配问题。以最基础的单目标价值最大化为例，搜推的资源位分配按照GMV期望最大化排序，广告的资源位分配按照CPM期望最大化排序，其中和是模型预估分，是广告主报价（如果是系统自动出价，则是的相关函数）。可以看出广告领域中广告主可以通过调整自身的bid报价策略使得自身的竞争力发生改变，从而影响资源位的分配结果，然而搜推领域的分配结果商家没有办法直接干预，纯粹由平台决策。所以从分配结果来看，搜推的主角是平台，但是广告的主角是广告主。

更为重要的是，广告除了资源位分配环节以外还有广告主扣费环节，以GSP机制为例，赢得第一个资源位的广告主需要付费 ，广告主又会根据实际付费情况核算营销表现是否符合预期，从而进一步影响下一轮报价策略。如此往复，广告主个体竞价策略变化的相互博弈最终形成了广告系统整体的收敛分配结果，这个博弈收敛的过程也是搜推领域不需要考虑的。所以广告的拍卖机制包括资源位

分配

和广告主

扣费

两个环节，如何设计能够促使广告主的竞价博弈收敛结果是符合平台引导预期的拍卖机制是重点也是难点。

1.2. 广告拍卖机制相关的博弈论基础知识

提到博弈过程和收敛结果，就不得不引出博弈论的相关知识，因为博弈论是一门独立的学科，广告的拍卖机制仅仅是博弈论的一个应用案例，所以下文讲述的侧重点是博弈论在广告拍卖机制中的应用。何谓机制？机制就是设计者想方设法让参与者做设计者想让他们做的事情，手段就是利用参与者的各自偏好，引入博弈环境，使得博弈收敛后的均衡结果符合设计者初衷。注意，参与者必须是智能体，体现在理性和有能力权衡偏好得失，且智能体的偏好往往是

私有信息Private Value

（有些地方称作

Type类型

）、外界不可知，所以好的机制设计需要具备偏好诱导能力，提供某种激励方式使得智能体在博弈环境中的真实表达是他的最优策略，这样单个个体的行为结果可预期，整体博弈收敛结果可以有导向性。总结来说，机制设计有几个要点：

• 智能体有偏好需求：广告主就是智能体，他的营销偏好是理性且私有的，常见偏好模式有
  
  效用最大化（Utility Maximizer）
  
  和
  
  价值最大化（Value Maximizer）
  
  ，机制设计之初就需要先确定智能体的偏好模式，后续才能有针对性地设计偏好诱导方式，下文会结合具体技术再详细阐述。
  
• 设计者有引导目标：广告平台就是设计者，他的引导目标是明确的，常见目标有
  
  社会福利最大化
  
  和
  
  平台营收最大化
  
  ，即引导的博弈均衡结果（包括分配结果和扣费结果）是有设计初衷的。下文会按照两条迭代主线展开介绍。
  
• 偏好诱导激励相容：
  
  激励相容（Incentive Compatibility）
  
  就是鼓励竞拍者讲真话，使得竞拍者目标和平台目标可以同向发力，有两个标准：1）
  
  优势策略激励相容（Dominant-Strategy Incentive Compatibility，简称DSIC）
  
  ，不管其他智能体如何报告自己的私有信息，如实报告（即讲真话）是每个智能体的最优反应，所谓最优反应就是如果不这么做就会有损失；2）
  
  贝叶斯纳什激励相容（Bayes-Nash  Incentive Compatibility，简称BIC）
  
  ，如果其他智能体是如实报告的，那么你的最优反应也是如实报告。
  
• 博弈结果存在均衡：博弈结果可以有一个均衡，也可以有多个均衡，关键不能是非均衡，起码有确定性的
  
  纳什均衡 Nash Equilibrium
  
  存在。激励相容引导的均衡可以是较弱的
  
  贝叶斯纳什均衡 Bayesian Nash Equilibrium
  
  ，也可以是严格的
  
  优势策略均衡 Dominant Strategy Equilibrium
  
  （可进一步细分三个版本，强、弱和极弱等，这里不再进一步介绍）。
  

以最常用的囚徒困境为例，介绍一下纳什均衡的应用。有两个智能体囚徒，分别都有两个策略：抵赖NC和招供C，表格里的数字表示囚徒在不同的环境下选择不同的策略可以获得的效用utility，即利益偏好，这里数字表示判刑多少年。可见(C, C)->(-5, -5) 是

纳什均衡 Nash Equilibrium

，

纳什均衡的意思是任何智能体单方面偏离自己的均衡策略均无利可图，当下策略是其他智能体均衡策略的最优反应。

(C, C)->(-5, -5)状态表明不会有哪个囚徒会单方面改变自己的策略，因为只要对方不动，自己改变都会让自己利益受损，判刑年数更长。另外需要注意，纳什均衡仅保证参与人不会单方面偏离，但不能保证其他人或者大家共同偏离，而且纳什均衡结果不一定是整体收益最大化，显然该例子如果两个囚徒选择共同偏离、合谋采取 (NC, NC) 策略，(-2, -2) 可以使得整体收益最大。

综上该小节内容，广告拍卖机制涉及到的博弈论要研究的内容就是新设计的机制能否达到纳什均衡；达到的纳什均衡属于什么强度；均衡唯一还是均衡多值；收敛性能如何；收敛结果能否达到预期目标最大化。

1.3. 理想化的拍卖机制和理想照进现实的松弛策略

前文已经介绍基于博弈论的机制设计原则，那么最理想的广告拍卖机制需要满足哪些性质？主要有3个：

• 高动机保证，
  
  优势策略激励相容（DSIC）
  
  即如实报价是优势策略，注意均衡不仅存在，而且是以最严格的
  
  优势策略均衡（DSE）
  
  的形式存在；
  
• 高效果保证：均衡结果满足引导预期，社会福利最大化或平台营收最大化；
  
• 高效率保证：多项式时间（一般近似线性）内完成分配和扣费两个计算过程。
  

如何实现理想化的拍卖机制？大体思路可以用一句话概括：先定

分配规则（Allocation Rule）

，再定

扣费规则（Payment Rule）

。展开来说：

• 先假设所有竞拍者如实报价，则如何设计分配规则使得上述
  
  高效果保证
  
  和
  
  高效率保证
  
  都成立？
  
• 再假设得到上述分配结果之后，则如何设计扣费规则使得
  
  高动机保证
  
  成立？
  

Myerson引理

可以将上述实现理想化拍卖机制的抽象思路具象化，介绍Myerson引理之前需要先了解3个概念：

• 
  直接显示机制（direct-revelation mechanism）
  
  ：要求竞价者如实报价的机制，但是该机制能否达到均衡，更别说能否达到优势策略均衡，不在要求范畴；
  
• 
  可实施的分配规则
  
  ：对于一个分配规则x，如果存在一个扣费规则p，使得直接显示机制 (x, p) 是DISC，那么就称这个分配规则x是可实施的；
  
• 
  单调的分配规则
  
  ：当其他竞价者报价不变，当前竞价者的分配函数是报价的单调非减函数，即报价越高，广告主可以获得更高位置更高点击率。
  

Myerson引理

基于上述概念提供了具体可操作路径：

• 一个分配规则是可实施，当且仅当它是单调的；
  
• 如果分配规则是单调的，那么存在唯一的扣费规则，使得
  
  直接显示机制
  
  是DSIC的，且这个扣费规则有明确的表达式。
  

Myerson引理前者说明可实施的分配规则和单调的分配规则是等价的，言下之意就是设计分配规则非常清晰，只要满足单调性即可；后者说明一旦分配规则确定了，扣费规则也是唯一的，且有明确的解析式，这个解析式推导过程可以详见论文，具体形式会在下文详细介绍。按照Myerson引理进行机制设计，理想化的广告拍卖机制就可以应运而生。

然而理想照进现实，当拍卖环境变得复杂，需要权衡的因素变多时，理想化的三个性质很难同时得到满足，此时有选择性地适当松弛很有必要。这里给出经典的松弛思路：

• 
  高效率保证是最基本要求，通常不做松弛。
  
  原因是计算广告领域往往会面对大规模高并发请求，低时延的高性能计算能力是服务可靠性的基本保障；
  
• 
  高效果保证是第一个允许松弛的性质，主要涉及到分配规则。
  
  因为最优分配问题本质是一个背包问题，而背包问题是NP困难问题，分配规则不可能在多项式时间内被实现，所以往往采用启发式的贪心算法，也就是业界常用的排序策略。这样分配问题就转化为了排序问题，例如本文开头Rankscore计算公式的设计，可以获得高效率的近似最优解。
  
• 
  高动机保证是第二个允许松弛的性质，主要涉及到扣费规则。
  
  Myerson引理证明当分配规则确定，扣费规则就是唯一的、且有明确的表达式，假设该表达式是a。可是实际环境非常复杂，或因为计算效率问题，或因为业务约束问题，导致实际采用的扣费规则没有用a，却用了b，那么DSIC就会被破坏。但是非DSIC机制就一定很糟糕吗？答案非也。前文提到，
  
  优势策略均衡
  
  是最理想的均衡结果，机制设计的底限是要有均衡的预期，有均衡预期就有足够假设来预测智能体的行为，那么机制结果就能有效推演。所以非DSIC机制也可以有不错的均衡性质，它们在实际中很常见。例如广告拍卖机制中，假设广告主偏好模式是
  
  Utility Maximizer
  
  ，平台优化目标是社会福利最大化，那么只有
  
  VCG机制
  
  是DSIC，
  
  GSP机制
  
  不是DSIC，但是也不妨碍GSP机制盛行，详细内容下文会重点介绍。
  

1.4. 广告拍卖机制的类型划分与经典机制设计范畴

拍卖机制设计前提是需要对拍卖形式有一定规约，广告拍卖形式有很多不同的视角划分方式：

• 按照拍卖品个数划分，分为
  
  单物品拍卖
  
  和
  
  多物品拍卖
  
  。单物品拍卖理论研究完备，机制设计空间较小，可直接应用于实践，而多物品拍卖机制设计空间大，需要对理论做很多假设才能平衡好效果与性能。广告往往有多个付费资源位在一次请求下同时拍卖，所以广告拍卖形式属于多物品拍卖，而且是多个非相同物品拍卖，位置越好点击率越高，对应的价值就越大。
  
• 按照竞拍者报价个数划分，分为
  
  单参数拍卖
  
  和
  
  多参数拍卖
  
  。报价个数对应竞拍者的估值对象个数，如果广告主只需要报价流量价值，那么就是单参数拍卖；如果广告主需要同时上报多个估值例如不同资源位的流量价值，那么就是多参数拍卖。和上一个划分方式面临的问题一样，参数越多，机制设计空间就越大，无论对理论设计还是计算性能都有很大挑战。
  
• 按照竞拍轮数来划分，分为
  
  单轮拍卖
  
  和
  
  多轮拍卖
  
  。轮数越多，竞拍者的私有信息Type会越来越成为公有信息，使得竞拍者能有更多的信息做决策从而调整报价策略。虽然多轮拍卖更加契合实际广告拍卖场景，广告主一笔预算往往会参与很多轮的请求报价，但是多轮的机制设计比单轮复杂很多，一般简化为单轮拍卖形式进行分析讨论。
  
• 按照广告主优化目标是否带约束来划分，分为
  
  无约束拍卖
  
  和
  
  有约束拍卖
  
  。有约束是指在广告主追求营销目标最大化的同时会带有指标约束，例如预算约束或者ROI约束等，这样广告主报价策略会从短期收益最大化调整为长期收益最大化，这对机制性质也会带来不小挑战。
  

可见，上述划分标准每一类的后者更加接近广告拍卖实情，但是相比前者会让整个机制设计难度系数大幅提升，所以本文将广告的经典机制设计范畴规约在“异质多物品、单参数、单轮和无约束”拍卖形式下（简称多物品拍卖），这也是目前工业界实践最为成熟的版本之一。其中多物品的拍卖形式没有再进一步简化了，但是下文讲述逻辑依然会从单物品拍卖开始说起，这样便于理解逐步过渡到多物品拍卖，近似理想的拍卖机制该如何调整与设计。

另外，前文提到的广告主优化目标即偏好需求的划分标准（Utility最大化 vs Value最大化）和广告平台优化目标的划分标准（社会福利最大化和平台营收最大化）每一项都是广告拍卖实情，属于可选项，不存在升级的说法，但是广告主偏好建模Value最大化是目前较新的需求类型，本文暂且没有归类到经典机制设计范畴，后续会作为新业态下的机制设计进行介绍。所以下文的讲述逻辑会基于广告主Utility最大化即利润最大化的前提，分别介绍面向社会福利最大化和平台营收最大化的拍卖机制该如何设计。

2. 社会福利最大化的有效机制

2.1. 广告主和平台优化目标的各自确立

本文以点击付费广告类型为例（可以推广至任意出价类型广告产品），广告主对每个点击流量内心有明确的私有估值，对外报价采取策略是v的函数即，可以是的如实报价，也可以对有所隐瞒，关键看哪个策略对自己是有利的。机制设计首先需要确定竞拍者的偏好模型，本文采用经典的效用Utility最大化，即广告主追求利润最大化。如果广告主竞得该次流量对应的系统扣费为，则效用函数是简单拟线性函数，利润=价值-成本。理想的拍卖机制就是要诱导广告主的报价是私有估值的真实反映，即，使得博弈收敛均衡下广告主追求目标效用是最大的。

另一方面，平台目标视角面向

社会福利（Social Welfare）最大化

是指资源位的分配一定要物尽其用，分配给最需要的竞拍者，即分配给最高真实估价的那些广告主，同时扣费机制方面需要诱导广告主如实报价是最优策略。于是机制（包含分配和扣费）的设计首先需要确定分配规则是面向社会福利最大化，即，其中表示竞拍者个数，是广告主对于点击流量的私有估值（一个点击值多少钱），表示广告主赢得当前请求下的付费资源位的点击率（介于0和1之间）。在确保分配规则是单调（广告主提高报价，有机会获得点击率更高的资源位）的基础上，再设计扣费规则使得广告主如实报价是最优策略，即效用可以最大化。

通常，社会福利最大化的机制是对资源最有效率的配置方式，所以该类型的机制也叫有效机制（

efficient mechanism

）。

2.2. 单物品拍卖的有效机制设计

先从最简单的单物品拍卖场景说起，假设只有一个资源位需要拍卖，有多个广告主同时参与竞拍，

Second-price auction

（简称

SP机制

，也叫

Vickrey auction

）是社会福利最大化的DSIC机制。

SP机制

首先确定分配规则，将资源位分配给报价最高的广告主，使得资源分配效率最高；然后确立扣费规则为二价扣费，除广告主以外的最高报价，令，即扣费,使得广告主如实报价可以让自身效用最大化，从而让SP机制具备优势策略激励相容DSIC的性质。

接着简单论证SP机制如何保证DSIC性质。广告主报价只有两种结果：当 ，则广告主 输掉这场竞拍，效用；当，则广告主赢得这场竞拍，支付价格为，效用。然后我们再针对广告主的私有估值进行分情况讨论：当，最大效用 ，显然广告主选择如实报价，输掉这场竞拍效用最大；当 ，最大效用 ，显然广告主选择如实报价，赢得这场竞拍效用最大。证明完毕，平台优化目标和广告主优化目标均在优势策略激励相容的性质下得以满足。

2.3. 多物品拍卖的VCG机制和GSP机制比较

真实广告拍卖场景往往是多个资源位同时竞拍，而且不同资源位点击率的差异使得多物品非同质，单物品拍卖下的有效机制设计无法直接应用过来。我们先从最简单的假设说起，点击率仅和资源位本身有关，不考虑广告本身质量，这也是最早期广告技术的真实落地方式，而且对于机制性质的分析也不失一般性。假设一共有个广告位，点击率分别是，一共有个广告主，报价从高到低排序分别是，一般。如果将广告主分配到广告位，则其效用收益是，是广告主对点击流量的估值，是广告主的单位点击支付。

前文提到单调的分配规则往往较为容易制定，我们按照报价的大小从高到低排序，第高报价的广告主被分配至第好的广告位，这样平台目标即社会福利最大化就可以得以满足（分配问题贪心启发式转化为排序问题）。难点是扣费规则该如何设计，可以保证DSIC且实现广告主目标Utility最大化。Myerson引理论证，满足该性质的唯一支付公式是VCG扣费方式，多物品拍卖下的

Vickrey–Clarke–Groves auction

（简称

VCG机制

）是单物品拍卖下的

Vickrey auction

（也称

SP机制

）有效升级。单次点击VCG扣费公式：，其中，注意这里分母出现是因为按照点击扣费。VCG扣费基本原理就是该竞拍者赢得广告位后，给其他广告主带来的收益损失是该竞拍者需要支付的费用。

下图是来自《博弈论二十讲》课件中的图示，个人认为是对VCG机制的DSIC性质最为直观和形象的表述了，所以就原封不动摘抄过来。为了和本文的参数定义对齐，这里做一下简单的解释：图中 表示估值分布； 是真实估值； 是报价； 表示分配结果（对应不同坑位的点击率），仅考虑位置点击率的情况下就是对应本文的 定义； 表示扣费结果，红色面积区域是展现视角下的期望点击扣费，所以对应本文的 。根据 Utility=期望价值-期望扣费 的定义，用绿色面积来表示Utility大小，比较 (g)(h)(i) 三张图的绿色面积，可见当即如实报价，广告主效用最大。

VCG机制固然可以满足DSIC性质，使得广告主目标Utility最大化，但是其运行效率较低且给广告主解释成本较高。综合考虑诸多因素，实际系统常常选用

GSP机制（Generalized second-price auction）

，分配规则和VCG机制一致，扣费规则有差异但更简单，单次点击GSP扣费公式：。GSP机制虽然看似是SP机制的广义延伸，但不是DSIC，如实报价不能让广告主效用最大化。举例：有两个广告位点击率如下，和；有三个广告主对点击流量的私有估值如下，、和。假设另外两个广告主均如实报价，若广告主1也如实报价，则可以赢得第一个广告位，根据GSP机制扣费，他的效用收益为。但是如果其隐瞒报价，虽然只能赢得第2个广告位，根据GSP机制扣费，但是其效用反而更大。所以GSP机制下广告主有隐瞒价值出低价的动机（under-bidding incentive）。

下图是参考《博弈论二十讲》关于VCG性质图示的方法，相同定义方式下画了GSP机制的性质表现。同样紫色面积表示期望价值，红色面积表示GSP机制下的期望扣费，绿色面积表示期望效用，可见：1）GSP机制不是DSIC，即如实报价的绿色面积不一定是最大的；2）高报价的绿色面积是负数，表示高报价没有正向收益；3）低报价 绿色面积和如实报价的绿色面积两项比较孰高孰低不一定，存在获利空间，所以GSP机制下广告主有under-bidding incentive。

虽然GSP机制在广告主Utility最大化的目标下并不是DSIC的，但是它也有不错的均衡性质，包括两个视角的均衡：Pure Nash Equilibrium under Full-Information Setting 和 Bayesian Nash Equilibrium under Partial-Information Setting。以前者为例，假设多轮竞价交互之后广告主的估值成为公有信息，GSP机制达到的一种均衡结果是广告主会认为保留当前位置是最优策略，不愿意与比他顺位高的人换位置，不然利润受损，这种均衡叫 locally envy-free equilibrium（也称symmetric Nash equilibrium），对应广告主的报价策略不再是如实报价，详细可见文献。

GSP机制除了有不错的均衡性质以外，还有其他优势：1）计算高效、对客解释成本低、扩展性好；2）最新研究论证在广告主Value最大化的目标下GSP机制又是DSIC的，这点会在文章最后提及；3）GSP存在多个均衡，其中包含一个均衡结果和VCG等价，因为扣费大于VCG，所以平台营收会比VCG更高。后续技术演进都是在GSP机制框架下进行。

2.4. 点击率因素如何影响GSP机制升级

前文提到的GSP机制是最基础的版本也是互联网公司落地最早的一个版本，但是点击率仅与资源位有关的假设显然和实际情况相差甚远，对于点击付费的广告类型，离谱的点击率假设会让资源位的配置效率大打折扣。为此，引入广告质量本身的点击率 是非常自然而然的想法。关于资源位点击率 和广告质量点击率 的关系，主要有两个大版本的升级。

基础假设是整体点击率关于位置因素可分离

，即 ，GSP机制升级为

wGSP

（weighted GSP，weighted体现在广告质量分的引入）。这样平台优化目标变成 ， 是广告主个数， 是资源位个数；广告主优化目标变成 ，表示广告 分配至资源位 效用函数；分配规则是按照 进行排序，第 大的广告分配至第 好的资源位；扣费规则是 。如此升级可以论证机制性质保持不变，但因为点击率和真实情况更为接近，SW表现更好。实际真实点击率无法提前预知，往往需要有点击率预估的能力。wGSP机制要求除了具备预估粗粒度的位置点击率以外，系统还要有能力预估细粒度的广告点击率。

升级假设是整体点击率关于位置因素不可分离

，即位置点击率和广告质量点击率无法解耦，这个假设与现实更加接近，两方面原因：1）不同广告在不同位置上的点击率影响各异；2）不同广告在不同上下文影响下的点击率各异。前文提到的VCG机制满足DSIC性质的隐含假设是位置因素可分离，如果遇到位置因素不可分离则满足DSIC性质的机制就会演变成Laddered Auction，详细内容参见文献。同样对面这种情况，GSP机制也需要升级，

iGSP

（iterated GSP）可以最大限度保证 existence of efficient equilibria，但也仅限2个资源位同时拍卖，如果遇到3个及以上就仍然是一个 open question，不过还算乐观的情况是移动端的资源位往往较少。iGSP的分配规则是既然位置点击率不可分离，那就逐个坑位顺次拍卖。先根据经验选择一个拍卖序，可以假定从高到低，针对当前资源位 考虑位置因素和上下文因素重新计算每个广告主的点击率 ，获得当前资源位下的广告新排序；接着执行扣费规则，对首位广告主进行二价扣费，；然后将首位竞得广告主从队列内去除，相同逻辑继续执行下一个资源位拍卖流程；如此遍历迭代，直至资源位竞拍完。 以上通过点击率假设和预估能力的不断完善，使得SW更优，资源配置效率越来越高，市场蛋糕不断做大，接下去作为平台视角，营收最大化也是目标之一，如何合理分配蛋糕也是重要课题。

3. 平台营收最大化的最优机制

3.1. 通过对比VCG和GSP来看平台营收空间

前文介绍了面向社会福利最大化的机制该如何设计，即把资源位

有效地

分配给高估值的广告主，使得整体价值最大化。整体价值通过扣费规则一分为二，一边是对广告主的扣费形成平台营收，另一边是广告主留下的效用即利润，即Value=Utility+Price。以下图VCG和GSP机制对比为例，假设广告主都选择如实报价，因为两者分配规则相同所以社会福利对应的面积大小也相同，但是因为两者扣费规则不同所以两者的平台营收和广告主利润就会有差异。从图示面积一目了然，相比VCG，GSP的平台营收更高，同时与之对应的广告主利润就会更低，所以从平台营收视角来说GSP机制更受欢迎。

这就是一个分蛋糕的过程，如果平台收益变多了，那么广告主收益就会变少。当然，分蛋糕也不是一个简单随意修改扣费规则的事情，是不是找个小暗门扣费多一点，平台营收就能多一些，然后就解决问题了？其实不然，扣费规则和激励相容性质息息相关，前文提到即使松弛了DSIC性质，但是均衡结果是最起码的要求，否则从长期博弈结果来看短期的平台营收都不可持续。换个角度解释这个现象，GSP机制不是DSIC的，广告主有隐瞒估值低报价的动机，所以长期来看会随着广告主低报价整体社会福利不如VCG，使得虽然在分蛋糕方面GSP有优势但在做大蛋糕方面存在不利因素，此消彼长，长期看平台营收GSP一定会打折扣。GSP有不错的均衡性质尚且如此，更何况其他粗暴魔改扣费规则的机制了，所以事情看来没有那么简单。

相较社会福利最大化（简称SW）通过分配规则就可以直接达到平台优化目标的运作逻辑不同，平台营收最大化（简称Rev）则需要结合分配和扣费规则一起才能实现（因为只有知道了扣费金额才能知道平台营收），这对机制设计带来不小挑战，以点击广告为例，ppc是表示单次点击扣费，SW类似于，Rev类似于。SW的扣费规则只需要承担激励相容要求即可，但是Rev的扣费规则除了激励相容的部分还要承担平台目标，而且之前分配规则和扣费规则都是解耦地有先后地分别设计，此时两者却要耦合在一块儿共同围绕相同目标一起设计。

最优机制（optimal mechanism）

的出现就是来解决这个问题，它可以使Rev机制的设计范式像SW一样清晰明了，还能保证DSIC性质。

3.2. 单物品拍卖的最优机制设计

先从最简单的单物品拍卖说起，并且进一步简化假设只有一个竞拍者，该设定因为没有其他竞拍者和他竞争，所以如果平台不做点其他的设置，竞拍者可以瞒报自己估值，以一个很低的报价竞得这个物品，导致即使平台按照一价扣费，营收也会大大受损。为了解决这个问题，平台可以设置一个

保留价

，类似虚拟竞拍者角色。如果竞拍者报价高于保留价，则竞得物品，平台按照二价扣费，即收取保留价费用；如果竞拍者报价低于保留价，则物品流拍。这样最核心的问题就变成了保留价该设置多少才能使得平台营收最大化？显然，如果保留价刚好比竞拍者私有估值小一点点，即，竞拍者又如实报价，这样物品可以竞得，并且平台收取的费用和竞拍者私有估值相当，也就是说平台赚取了估值中的绝大部分，竞拍者仅保留微乎其微的利润，但毕竟利润还是正的，竞拍者也只能勉强接受。

上述保留价的取巧设计，可以使得平台营收最大化，前提需要猜准竞拍者的私有估值，毕竟估值是私有信息，平台无从准确知晓。可以借助贝叶斯分析方法，假设该估值服从某个分布，则竞拍者如实报价可以竞得物品的概率是，那么平台的营收期望就是。举例来说，如果是均匀分布，则，通过求导梯度为0的方式得到，则。同样计算方法继续求解稍微复杂一点的两个竞拍者场景：如果采用DSIC的

SP机制

，假设两个竞拍者的私有估值独立且服从均匀分布，此时平台期望营收为；如果采用

SP机制

配合

保留价

，上述假设基础上增设保留价，如实报价最高者竞得物品并支付第二名报价和保留价中更高的价格，此时平台期望营收为。

那么有没有其他办法可以获得更高的平台收益？换一个保留价，或者换一个拍卖形式？

Myerson机制

就是可以获得最大化期望收益的最优机制。首先定义虚拟估值，它和私有估值以及分布有关；然后可以论证在满足DSIC的机制空间上对期望收益最大化，可以等同于在同一个空间对期望

虚拟福利最大化

，这样原本关心的收益最大化问题就转变为了分配最优化问题，，与前文2.1.章节中相比仅仅是将私有估值转换为对应的虚拟估值，其他分配规则的细节以及扣费规则都与

社会福利最大化

一模一样；最后只需要保证是单调的，即私有估值的分布是

正则分布

，许多常见分布基本都是正则分布，例如normal、lognormal、uniform and exponential distributions等；非正则分布包括多峰分布和长尾分布，分配的单调性是机制DSIC性质的前提。论证过程可详见文献。

可以发现虚拟估值可能为负，在分配的过程中如果遇到<0的竞拍者会被剥夺竞拍资格，如果所有竞拍者的虚拟估值均为负，则流拍，所以即虚拟估值为0的逆函数起到了

个性化保留价

的功能。如果假设所有竞拍者的私有估值服从

独立但不同分布

，则不仅会有各自不同的保留价，还会遇到如实报价情况下报价高，但虚拟估值不一定高，导致没有竞得更好的资源位，也好理解，此时虚拟估值代表了个性化自己和自己对比的报价意愿强烈程度；如果假设所有竞拍者的私有估值服从

独立同分布

，因为估值分布相同则虚拟估值函数也相同，又因为估值分布服从正则分布，则严格递增，那么虚拟估值最高的竞拍者就是私有估值最高的竞拍者，这样虚拟福利最大化机制就和带有保留价的二价机制相同，回答上文提到的两个竞拍者估值服从独立同分布均匀分布的例子，确实是最优保留价。以下是单物品拍卖的几个机制对比：

3.2. 多物品拍卖的经典保留价方案与Squashing方案

虽然

Myerson机制

可以完美解决单物品拍卖场景下的平台营收最大化问题，但是面对多物品拍卖场景该机制性质的理想化状态就很难保持，更大方面来说目前整个多物品拍卖领域关于平台营收最大化的最优机制设计问题依然是一个开放问题。回到广告多坑位拍卖场景，经典的机制设计会围绕GSP机制做针对性改造，将Myerson机制的思路和GSP机制的流程相融合，在保持良好机制性质的前提下持续优化平台营收，获得近似最优结果。接下来会介绍3种基于wGSP机制改造的提升平台营收的常见方法。

第一种是

mGSP（myerson GSP）机制

，想法很直接，就是将Myerson保留价技术直接应用到wGSP机制上。和单物品拍卖的设计思路类似，Myerson保留价最核心的虚拟估值依赖广告主的私有估值分布，系统可以酌情根据独立同分布的颗粒度进行假设的调整，例如客户之间完全独立不同分布、相同搜索词的客户之间独立同分布、整体流量客户独立同分布等。因为广告系统是多轮拍卖系统，假设广告主是如实报价，则私有估值分布可以根据广告主历史报价进行不同粒度的分布拟合，从而得到虚拟估值。有了虚拟估值和保留价，在分配规则方面有两种类型可做尝试：Eager模式，先过滤后排序，即先根据保留价过滤没有竞争力的广告主，再按照虚拟估值排序；Lazy模式，先排序后过滤。Eager模式对最高报价无法胜出保留价的情形更友好，Lazy模式对第2高报价无法胜出保留价的情形更友好，多数情况下Eager模式在提营收方面会比Lazy更有优势。

第二种是

aGSP（anchoring GSP）机制

，是对

mGSP机制

一种松弛方式，业务落地过程中虚拟估值的求逆计算和私有估值的正则分布要求等均会让机制实现不够简洁且解释性较差，略牺牲效果的情况下精简机制设计也是可接受的迭代方向。首先保留价的计算方法和mGSP机制相同，一般保留价的颗粒度会选择数据积累较为充分的粒度。其次主要差异点就是将虚拟估值由简化为，如果假设私有估值分布是均匀分布，化简的表达式就非常接近，求逆也方便，而且业务含义与myerson思路很吻合，报价竞争力更多看重每个广告主超出个性化保留价的那部分。

第三种是

rGSP（reserve GSP）机制

，是对

aGSP机制

更加进一步的松弛。因为有文献提出，为了解决私有估值和虚拟估值趋势不一致问题，虚拟估值可以仅用于个性化保留价的过滤，分配和扣费依然按照私有估值进行，这样虽然对营收有折损但是机制实现更加简洁且易解释。

另外一类不是在报价因子上做文章，而是在wGSP的广告质量点击率上做文章，通过对广告质量点击率进行挤压，也能达到提升营收的效果，这类机制叫做

sGSP（squashing GSP）机制

。分配规则是按照进行排序，其中就是挤压因子，扣费规则按照。该挤压因子能够体现三方面的结论：1）Efficiency视角：当是社会福利最大化及Efficiency最大化，凡是的调节都提升平台的短期收入，从而影响广告主价值；2）Relevance视角：只要往大调节，整体点击率就会提升，相关性就会变好；3）Revenue视角，当相邻广告质量随排序递减即，在不改变排序的情况下调小，变大，利好营收增加，当相邻广告质量随排序递增即，在不改变排序的情况下调大，变大，利好营收增加。这一方案为了进一步挖掘营收空间，可以升级为分位置调控挤压因子等，具体详见文献。

4. 经典广告拍卖基本框架和预告进阶篇

4.1. 经典的广告拍卖基本框架

前文介绍了机制性质不算完美但还算良好的面向平台营收的拍卖机制，但也明确强调平台营收最大化是一个分蛋糕的过程，它其实是和广告主零和博弈相互争夺利润，一味提升平台营收短期来看没有问题，但长期来说一定会影响广告主的预算投入，从而影响社会福利最大化即做大蛋糕的结果。所以我们需要在两者之间做平衡，把握好做大蛋糕和分好蛋糕的节奏。同时，用户体验也是广告系统需要兼顾的重要考量，和免费资源位相比，付费资源位或多或少会牺牲用户体验换取社会福利，如果不加以约束，长期以往用户会失去对付费资源位的关注度，从而平台会彻底丧失流量变现的机会。

综上，以一个开放生态的视角看待广告系统，广告主和用户都会用脚投票，进行不同平台之间的选择，所以平衡好三者之间的利益述求就极其关键。那么经典的广告拍卖基本框架就是一个带约束的最优化问题：max 社会福利最大化；s.t. 平台营收约束、用户体验约束（电商场景可以是点击率、转化率和相关性等）。然后通过拉格朗日对偶法将分配问题转变为多目标排序问题，同时扣费规则明确为关键最小扣费，即广告主仅需要支付保持住当前广告位的最小费用。这样一套广告拍卖机制可以在业务发展的不同阶段择机调整适配，能够促进广告生态健康发展。

4.2. 广告拍卖进阶版展望

本文从机制设计原理出发，不断加强前提假设，改造机制内容，逐渐完善广告拍卖的基本框架，至此经典范畴的内容介绍完毕。但是随着广告业务和技术的不断发展，新趋势孕育新机会，主要有三个方向的持续升级：

• 业务方面，广告主优化目标的改变：广告主的营销述求不再以利润Utility最大化为第一优化目标，而是以价值Value最大化为主要优化目标；扣费不再是广告主的敏感成本项，而是一个必须要花完的预算，核心关注这笔预算花完能否最大化价值，当然了如果获得相同价值的前提下可以考虑少付费。那么一旦广告主偏好模型发生变化，现有机制就需要重新审视，哪些机制的DSIC性质会发生改变，是否需要设计新机制来满足新要求？
  
• 广告主方面，Autobidding模式的兴起：越来越多的DSP开始智能化承接广告主的营销述求，此时广告主不再对流量进行估值报价，而是以更加高阶的或者直观的优化目标形式（最大化进店等）出现，伴以业务约束要求（预算和ROI约束等），然后由智能报价系统进行在线实时地对每个流量进行自动报价。面对使用占比越来越高的Autobidding模式，拍卖机制该做哪些假设的调整，新机制该如何设计才能满足良好性质实现平台优化目标？
  
• 技术方面，数据驱动的机制设计：数据驱动的深度学习技术已经逐渐成为广告系统其他算法模块（召回和预估等）的标配，而以平台收入最大化为目标的最优机制设计目前仍然有较大的优化空间，经典的设计方案需要依赖较强的领域知识，通过先验缩小优化范围，获得的近似最优解质量不高。我们该如何为机制设计进行定制化改造，满足机制性质的同时借助数据驱动的能力使得最优值的搜索过程更加智能，而且标准化的迭代流程又可以进一步加快技术升级，从而打开优化天花板？
  
• 生态方面，生成式模型颠覆广告营销模式：以ChatGPT为代表的生成式大模型让科技行业重新兴奋起来，也为广告营销注入了新的想象力。生成式大模型几乎一定会带来用户与互联网产品交互模式的改变，例如，多模态交互式对话方式会取代搜索引擎的地位，以广告位拍卖为基础的互联网广告的逻辑也会发生改变。一方面，新的用户交互模式会孕育新的商业机会，给自动出价的产品带来颠覆的改变；另一方面，新的技术理念和技术范式也会给自动出价算法带来革命性的升级。在如此汹涌磅礴技术浪潮到来之际，我们该如何革新广告营销的技术体系？
  

以上四个方向的技术演进如今如火如荼，希望未来有机会可以以进阶篇的形式整理一下思考与实践。

5. 参考文献

[1] Ranking and Tradeoffs in Sponsored Search Auctions

[2] Optimal reserve prices in weighted GSP auctions

[3] Revenue Optimization in the Generalized Second-Price Auction

[4] Learning Algorithms for Second-Price Auctions with Reserve

[5] Reserve Prices in Internet Advertising Auctions- A Field Experiment

[6] A Field Guide to Personalized Reserve Prices

[7] Position auctions

[8] Truthful Auctions for Pricing Search Keywords

[9] GSP with General Independent Click-Through-Rates

[10] Bidding to the Top- VCG and Equilibria of Position-Based Auctions

[11] Truthful Outcomes from Non-Truthful Position Auctions

[12] Revenue Monotone Mechanisms for Online Advertising

[13] Sponsored Search Auctions with Rich Ads

[14] Revenue Analysis of a Family of Ranking Rules for Keyword Auctions

[15] Multi-Score Position Auctions

[16] Internet Advertising and the Generalized Second-Price Auction- Selling Billions of Dollars Worth of Keywords

[17] Simplified Mechanisms with Applications to Sponsored Search and Package Auctions

[18] General Auction Mechanism for Search Advertising

[19] Bayes–Nash equilibria of the generalized second-price auction

[20] Sponsored Search Auctions- Recent Advances and Future Directions

[21] On Revenue in the Generalized Second Price Auction

[22] Optimal Auction Design and Equilibrium Selection in Sponsored Search Auctions

[23] OPTIMAL AUCTION DESIGN

[24] Optimal Multi-Object Auctions

[25] Simple versus Optimal Mechanisms

[26] Auction Mechanism for Optimally Trading Off Revenue and Efficiency

[27] Efficiency-Revenue Trade-offs in Auctions

[28] Optimising Trade-offs Among Stakeholders in Ad Auctions

[29] 《斯坦福算法博弈论二十讲》

加入我们

：阿里妈妈搜索广告算法团队，诚招日常实习生和暑期实习生，欢迎对广告算法感兴趣的同学（最好有NLP、CV和信息检索背景）投递简历。邮箱：alimama_tech@service.alibaba.com