互联网广告拍卖机制设计

机制设计的起源

机制设计理论的产生源自于经济学家对于市场经济的讨论。传统的经济分析把经济体制看作是给定的。比如新古典微观经济学主要把市场机制作为对象进行研究，它讨论市场机制如何运转，有什么样的优越性及局限性。对计划经济机制的讨论也是如此。但是，无论是市场机制还是计划体制，从经济学的角度看都是资源配置的机制，它们的目的都是为了能够使资源得到有效的配置。因此，一个自然的问题是， 为了实现资源有效配置，除了市场机制和计划机制，是不是还应该有其他的机制？ 一旦提出这个问题，原先那种将制度视作给定的做法就不再可行了。而Leonid Hurwicz最早提出了解决这一问题的基本框架，这也标志着机制设计理论的产生。

完美世界：激励相容的机制

所谓机制，是指那些人为能够控制的用于组织与协调经济行为的系统。机制设计理论所讨论的问题是：对于任意的一个想要达到的既定目标，在自由选择、自愿交换的分散化决策的条件下，能否并且怎样设计一个经济机制，使得经济活动参与者的个人利益和设计者的既定目标一致，即每个人主观上追求个人利益时，客观上也同时达到了机制设计者既定的目标。但是，在达到这个既定目标的过程中，存在这样一个问题：许多关键的信息是机制设计者不知道的，比如互联网广告对广告主带来的收益。不知道这些信息，设计者就无法有效实现特定的目的。而解决这个问题的方法无非两种：一种是直接机制，采用强迫、强制的方法。通俗地讲，就是设计者强迫相关的主体把关键的信息说出来。另一种就是间接机制，采用某种方法，让相关的主体自愿把他们的偏好等信息显示出来。前者显然是大家无法接受的，而后者听起来可能更合意。因此，又产生了一个问题：这种使相关主体自愿地把他们的偏好显示出来的可能性存在么？机制设计理论也对这个问题进行了解答。

诺贝尔经济学奖得住Roger Meyerson在他1981年的论文《Optimal Auction Design》中提出了著名的显示原理：

直接机制所能达到的效果都可以由一个间接机制来实现，而且可以通过一个说真话（truth－telling）的直接机制实现。

说真话的直接机制是指在一个直接机制中，利益相关者都向设计者如实地报告自己的类型。这样的一个机制也称为激励相容的直接机制，也就是说，讲真话是利益相关者在这个机制下的最优选择；这时，经济活动参与者的个人利益和设计者既定目标一致，即每个人主观上追求个人利益时，客观上也同时达到了机制设计者既定的目标，达到双赢。

最优拍卖问题

如果一个卖方可以在许多机制当中进行挑选，那么他应该使用哪一个机制来出售单个不可分割（比如一幅名画，一件古董）的物品，以使他的预期收益最大化呢？Myerson把这个问题称为“最优拍卖问题（optimal auction problem）”。

为了解决这个问题，他提出了一个定理，称为Myerson引理或收益等价定理。因为Myerson提出的问题称为“最优拍卖问题”，那么我们就用一个拍卖的例子来说明收益等价定理。

拍卖其实就是一种机制，拍卖的卖方通过拍卖这样的一个机制，使得竞标者通过竞争把他们关于拍卖商品的偏好尽可能的表现出来，从而使得卖方用相对少的信息租金得到一个相对合理的收益。而拍卖的形式是多种多样的，典型的拍卖形式有四种：

1. 一阶价格密封拍卖：每个竞标者都告诉卖方一个价格，但这个价格除了其本人及卖方，其他的竞标者都不知道，最后出价最高的竞标者中标，并支付他所承诺的价格；
2. 二阶价格密封拍卖：每个竞标者都告诉卖方一个价格，但这个价格除了其本人及卖方，其他的竞标者都不知道，最后是出价最高的竞标者中标，所不同的是，他所支付的价格是所有价格当中第二高的价格；
3. 荷兰式拍卖，卖方先定一个很高价格，然后逐步地降低这个价格，在降低的过程中，第一个应价的人即是中标人，其支付的是他所应承的价格；
4. 英国式拍卖，卖方先定一个极低的价格，然后逐渐提高这个价格，在提高的过程中，那些认为价格已经超出自己估价的竞标者不断退出，最后剩下的就是中标者，他支付当时的价格水平。

既然有这么四种拍卖形式，那么现在摆在卖方面前的问题是：他可以使用哪一个拍卖形式，使自己的收益（所赚的钱）最多？Myerson在1981年证明了如下结论 >在一定条件下，一阶价格密封拍卖、二阶价格蜜蜂拍卖、荷兰式拍卖和英国式拍卖，这四种拍卖形式对于卖方的期望收益是相同的。

互联网广告拍卖机制

对于互联网广告拍卖机制来说，主要的设计指标有三个、收益、效率和相关性。收益指的是公司的实际收益，效率指的是广告主和公司的收益之和，相关性指的是广告跟用户实际搜索之间的关系，跟用户体验相关。

目前的互联网广告关键词拍卖机制主要有两种：GSP（及其变种）和VCG。

GSP：二阶价格拍卖机制

GSP，也就是我们常说的二阶价格拍卖。为什么是二阶价格拍卖，而不是GFP，也就是一阶价格拍卖呢？事实上，最早的互联网广告拍卖机制采用的就是GFP（Overture）。在这种拍卖机制下，广告主的出价是完全公开的。但是这种拍卖机制不是激励相容的，在广告主的策略行为下，广告价格会出现巨大的波动，严重损害效率（如下图）。GSP拍卖机制存在价格均衡，减少了广告主出价的波动性，也易于为广告主所接受。

GSP拍卖规则：

1. 广告主$i$出价$b_i$;
2. 将广告主按照$b_i \times e_i$进行排序，其中$e_i$为权重，通常为点击率CTR，出价乘上点击率，可以认为是预期收益（事实上，由于我们采用的是二阶拍卖，$b_i \times e_i$会比真实的逾期收益大一些）；
3. 广告主为每一次点击所支付的价钱等于其为保留在当前排名所需要的最低出价计费.
   $p_s e_s = p_{s+1} e_{s+1}, 即 p_s = \frac{b_{s+1} e_{s+1}}{e_s}$
   GSP存在多种变体，UWR/QWR/Squash等等。Google和Baidu使用的都是UWR。

VCG拍卖机制

VCG（Vickrey–Clarke–Groves）拍卖机制，是按照竞价者对其它竞价者造成的损失来计费的。
VCG是激励相容的机制，按自己的真实预期出价是每位竞价者的强占优策略。

VCG拍卖规则举例：

假设我们现在有2个广告位，3个客户进行竞标。广告位和广告主的属性如下表所示：

• 当广告主A不参与拍卖时，广告主B和C获得的社会总效用是 $200 \times 4 + 100 \times 2 = 100$;
• 当广告主A参与拍卖时，广告主B和C获得的社会总效用是$100 \times 4 + 0 \times 2 = 400$;
• 广告主A造成的效率损失是1000 - 400 = 600
• 所以广告主A为每一次点击的支付是$600 \div 200 = 3$

Myerson拍卖机制

Roger Myerson在《Optimal Auction Design》中提出了一种能够实现收益最大化的直接机制，并给出了构造这种直接机制的方法。这种机制被称为Myerson机制，它使用虚拟出价而不是实际出价进行排序，并且需要提前知道广告主的出价分布。

Myerson拍卖机制规则：

1. 计算虚拟估价
   $\varphi(\theta_i) = \theta_i - \frac{1-F(\theta_i)}{f(\theta_i)}$
   其中$\varphi(\theta_i)$为虚拟出价，$F(\theta_i)$为客户实际出价的累积分布函数，$f(\theta_i)$为客户实际出价的概率密度；
2. 对虚拟出价$\varphi(\theta_i)$运行VCG机制即可。

Myerson机制需要知道广告主竞价分布的先验知识，因此，在工程中很少使用，它的期望收益通常被用做各种机制收益的上限。