互联网广告拍卖的数学描述及最优拍卖机制设计

拍卖对大多数人来说并不陌生，且形式简单。拍卖活动产生于古代奴隶社会，最早可追溯至公元前500年古希腊的新娘拍卖。

然而拍卖又是一个较为复杂的问题，主要体现在对拍卖本质的认识与研究上，对拍卖理论的研究有利于拍卖机制的有效设计，进而促进资源的合理有效配置。

就互联网广告来说，从本质上讲也是一种特殊资源（流量）的拍卖形式，对拍卖理论的理解将有助于设计和修正实践中的广告竞价机制，获得更为长远的收益。本文将从单物品拍卖视角，从数学角度对拍卖理论进行相关介绍，并给出最优拍卖机制的设计。

1. 从单物品拍卖谈拍卖建模

1.1 单物品拍卖

单物品拍是诸多拍卖形式中较为简单的且运用场景较多的一种形式，具体的问题可表述为：“一个卖家有一个物品出售， 同时有若干个买家愿意购买该物品，但卖家并不清楚该物品对这些买家的实际价值，也不清楚买家愿意为其支付的费用。这时对于卖家来说，希望有一套合适的拍卖机制可以实现售卖该物品的期望收益最大化”。

为了研究方便，我们假设买家都是对称的，且报价是按照自己的对物品价值的真实估值披露给卖家（即满足直接披露机制假设），虽然做了这个假设，但Myerson证明了，何一个可行的机制都有一个直接披露机制能够产生与其相同的买家和卖家收益期望，所以基于直接披露机制得出的最优机制设计，也具有一般性，即只需要在直接披露机制中找到最优机制，就是所有可行机制中的最优解。

从上面的问题描述可以看出整个拍卖活动涉及到买家的估价、买家的报价、卖家的资源分配、买家的支付等环节，如下图所示。拍卖机制的核心问题就是制定或设计一套能够达成最大化期望收益，且能够保证买家与卖家长期可持续发展的机制。

1.2 拍卖的几个基本假设

从单物品拍卖的问题描述，我们可以对拍卖作出以下几个合理的基本假设：

风险中性

买家在拍卖中的目标是最大化自己的预期收益，预期收益指买家的期望所得和期望支付之差。

私有估价

买家对物品的估价, 属于买家的私有信息，只有自己知道，卖家和其他买家是不知道的。

独立性

所有买家对物品的估价是独立随机变量。

理性假设

估值为0的买家预期支付也为0。

1.3 单物品拍卖的数学描述

如前所述，拍卖机制本质上是一套规则，依据参竞者的报价来决定拍卖的物品分配给哪一个买家，以及决定该胜出的买家应该支付的费用。本节将用数学语言对拍卖进行建模描述。假设卖家要拍卖一个商品，有 个参竞的买家集合表示为 。

(a) 估值描述

为 个买家对拍卖物品的价值估计，表示第  个买家对物品的私有价值估计，也是买家  愿意为这个物品出的最大价格。估值向量  对卖家不可知，且买家之间相互也不知。

注：虽然买家的 对卖家不可知，但是卖家可以通过数据分析（比如广告平台对广告主的历史竞价数据的分析）对 的分布有一个大概的估计，即的取值概率分布，其中，在定义域内单调增且大于 0。

同理卖家可以利用累积概率分布得到买家  的最大价值估计为 的概率为。

由于买家之间的估价是相互独立的，所以所有买家的估值向量服从概率分布。

类似地，除买家 以外，其他买家的估值向量服从分布。

(b) 分配规则

设计一个分配函数 ，依据买家的估价向量  来得到拍卖物品被分配给每一个买家的概率，一般地，分配函数满足：

(c) 支付规则

设计一个计价函数：，表示买家在分配结果确定之后每一买家应该支付的费用。

至此，元组描述和确定了一个拍卖机制。

2. 互联网广告常见的拍卖机制

互联网作为新兴行业也不例外，拍卖活动的身影也随处可见。互联网广告其实就是一个平台（流量方）对资源（流量）的拍卖活动，目前常见的拍卖机制（竞价机制）的分配、支付及特点如下。

GFP(Generalized First Price)广义第一价格拍卖

分配规则：按出价高低进行资源分配，价高者得；

支付规则：竞拍成功后需要支付自己的出价；

特点：简单易理解，但由于竞买者会采用“微小差分策略”导致价格波动，从而导致平台方收益不稳定，竞价效率不高。

GSP(Generalized Second Price)广义第二价格拍卖

分配规则：按出价高低进行资源分配，价高者得；

支付规则：竞拍成功后需要支付出价第二高者报价再加上一个最小值；

特点：GSP是一种稳定的竞价方式， 可操作性较强，也是现阶段互联网广告主流的竞价方式。缺点是GSP不是一种“鼓励讲真话”的机制，讲真话不是一种占优策略，竞价的结果也不一定是全局最优的。

VCG (Vickrey-Clarke-Groves)

分配规则：按出价高低进行资源分配，价高者得；

支付规则：支付因自己参与竞价，而对其他广告主造成的效用损失；

特点：可以保证社会效用最优，讲真话是参与者的弱占优策略，缺点是VCG讲真话的收益是GSP无妒忌均衡的下限，实际工程实现较为复杂，解释成本高，对平台收益造成损失。

3. 最优拍卖机制的设计

如上所述，当前主流的几种拍卖机制都存在着各自的优缺点，那么是否存在一种从平台期望利益最大化来看的最优的拍卖机制呢？回答这个问题，首先需要明确最优拍卖机制需要具备的特点：

(a) 概率约束：一个物品至多分配给一个买家，也即公式（1）满足；

(b) 个体理性：买家自愿参与拍卖，也即买家参与拍卖的期望收益大于等于0；

(c) 激励相容：买家按其真实估价报价本身就是最优策略，也即，买家按其真实估价报价时能够达成一个纳什均衡。

(d) 该拍卖机制下，平台的期望收益是最大化的。

满足(a)、(b)、(c) 的机制为可行机制，同时满足(d)的可行机制为最优拍卖机制。那最优拍卖机制是否存在呢？

通过对拍卖过程中涉及到的各方的期望收益进行了数学建模和描述，世界著名经济学大师Roger Myerson将最优拍卖机制的问题转化为一个数学上的优化问题，并给出了最优解，该理论也获得了2007年度诺贝尔经济学奖，本节将主要介绍最优拍卖机制的基本理念和数学推导。

3.1最优拍卖机制的优化目标及约束条件

优化目标

沿用第1节的符号描述，在拍卖机制下，首先，我们来定义买家的收益。买家  在出价为其真实价值估计 的期望收益(也即买家效用)：

其次，我们来定义卖家(平台)的收益。这里先定义，卖家保留持有物品的价值为 ，那么其收益期望可以定义为：

(3) 式的物理解释为：加号前一项是物品流拍时，卖家持有物品的价值；加号后面的一项表示物品成功卖出去所收入的费用总和。至此，我们得到了最优拍卖机制的优化目标，即平台期望收益最大化，其数学表达为公式(3)。

约束条件

最优拍卖机制同时也是一个可行机制，需要满足以下三个条件:

（a）概率约束，即需要满足公式 (1)；

（b）个体理性约束，即，满足

（c）激励相容约束：买家出价为其真实估价时是一种占优策略。假设买家  的真实估价为 ，而其提交的出价为 ，此时其收益期望为：。鼓励讲真话，则机制需要保证以下不等式的成立：

综上所述：最优拍卖机制在数学上可以描述为：满足约束条件下最大化  的解 。

至此，我们已经定义出了直接披露机制中如何设计最优机制的数学表达，虽然是基于直接披露机制，但是Myerson给出了理论证明：任何一个可行的机制都有一个直接披露机制能够产生与其相同的买家和卖家收益期望，所以基于直接披露机制得出的最优机制设计，具有一般性，也就是只需要在直接披露机制中找到最优机制，就是所有可行机制中的最优解。

3.2可行机制的充分必要条件

可行机制的描述公式(1), (4), (5)有很强的物理解释，但不能直接用于最优机制的推导，为此我们先推导出可行机制的另一种形式（充要条件），也即下文中的公式(7), (8), (9)。

记买家  出价  时，其竞拍成功的概率是，则买家  出价  时其期望收益为：

将其代入式(5) 可得：

式(6)的右边为如果买家没有按真实估价进行报价(即买家说假话)其收益期望为：通过不真实出价获得的额外收益的期望，加上以虚假报价  衡量物品的价值时的收益期望 。由公式（6）可以进一步得出：

式（7）的直观解释是：买家出价越高，其竞得率越大。

由公式(6)，还可以推导出：

由（7）知道为单调递增函数，满足黎曼积分条件，于是有

有定义可知：

必要性的证明较为简单，略。

3.3 最优拍卖机制的求解

在(7),(8),(9) 约束条件下，将优化目标（3）进行改写以下式(10)，具体过程见附录。

如前所述，最优拍卖机制的设计问题转化为一个带约束条件的最优化数学问题：在约束条件(7), (8), (9)下对找到使得(10) 最大的。

最优支付规则P的求解

由(10)可知，p仅仅只和最后一项有关系，要使得(10) 最大，则可令

通过对(11)进行如下求解，可知，在确定了分配规则q下，最优的支付规则也就确定了，于是最优拍卖机制的求解核心在于最优分配规则的确定。

最优分配规则Q的求解

Myerson在论文中的推论指出，在可行机制下，卖家的期望收益完全由分配q和买家在其最低估价下的收益来决定，于是最优分配规则可以描述为式(12)。该式求解比较复杂，但是在某些特定条件下，我们可以很方便的求解出最优解。

常规单物品拍卖下的最优拍卖机制

首先定义一个实质价值函数(virtual value)：。

根据  的性质，很容易得到  在 上是连续有界的。如果是一个严格单调增函数，称其满足常规假设 (regularity assumption)，对于很多分布函数来说，常规性假设都能满足。

考虑常规假设下的单物品拍卖：拍卖的物品是单一的，且最多仅有一个买家胜出。此时(12)的一个最优解的形式是：“将物品分配给  最大且非负的买家”。

非负要求，但同时还需要满足可行机制约束条件，尤其是式(7)。由于是满足常规假设下的拍卖，即 越大，对应的越大，胜出的概率 也越大，满足(7)。

此时对应的计价函数为：

其中

即在买家  胜出的估价点之上。

由上可知，这套最优拍卖机制其实是一个修正的vickery拍卖，相当于使用为保留价，按“出价高者得”的分配规则，按照二价计费规则。

对于多物品多买家拍卖，对卖家和每个买家的期望收益的数学表达将会变得非常复杂, 难以给出形式化的求解，一般都是给出一些较强的假设，得到一个近似最优的解。

参考文献

1. Optimal Auction Design, Myersion, 1981, Mathematics of Operations Reseach

另，附式(10)的推导过程：

☆ END ☆