欢迎关注：阿里妈妈技术公众号本文作者：石士
搜索、推荐和告白在过去几年互联网蓬勃发展的浪潮中起到了核心助推引擎的作用，三者技术发展也是互相借鉴和相辅相成，有很多共通之处也有不少差异的地方。本文从告白视角出发，重点介绍告白技术与搜推技术最本质的差异点——拍卖体制的原理和实践。作为最具告白特色的技术模块，拍卖体制理解起来往往较为晦涩。一方面因为这个技术领域是基于博弈论思维，概念较多且定理推导复杂，和已经标准化的基于数据驱动的机器学习思维截然不同；另一方面因为理论假如过于严格，和实际差距较大，使得论证过程无论多么完善，实践落地仍然必要考量诸多复杂因素。本文尝试将拍卖体制的几个经典问题做一个脉络性梳理，概念和论证过程可自行查阅这里不再赘述，但概念之间的演进关系会重点阐述，希望可以勾勒清楚技术全貌，有助于大家系统性地认识计算告白领域的拍卖体制安排。
本文会按照几个小话题顺次展开介绍：
告白领域的拍卖体制简化而言是一个什么拍卖问题，背后最基本的博弈论概念是什么；最理想的拍卖体制长什么样，必要满足哪些条件；理想照进现实，哪些条件可以妥协松弛使得真正落地的拍卖体制即使没有非常理想但依然运行良好；本文所说的经典的拍卖体制安排范畴是什么？
社会福利最大化的拍卖体制如何安排才能使得市场蛋糕被有效扩大；点击率的不同假如这一关键变量如何影响拍卖体制的性子；体制安排必要做哪些与之对应的调整与升级？
平台营收最大化的拍卖体制如何安排才能使得市场蛋糕被最优地分派；以保持价安排为代表的这一关键技术是如何影响拍卖体制的性子；体制安排背后的假如必要做哪些与之对应的调整？
经典的拍卖体制的基本框架长什么样；多个优化目的在这个框架下是如何平衡；面向告白业务新形势下的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/智能体2方略NC方略C方略NC-2，-2-10，-1方略C-1，-10-5，-5
综上该小节内容，告白拍卖体制涉及到的博弈论要研究的内容就是新安排的体制能否达到纳什平衡；达到的纳什平衡属于什么强度；平衡唯一还是平衡多值；收敛性能如何；收敛结果能否达到预期目的最大化。
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和信息检索背景）投递简历。邮箱：[email protected]