Network 20Q--Q2 How does Google sell ad spaces?

在使用Google搜索的时候会发现，搜索出来的页面除了在左边显示搜索结果以外，还会页面的右边推荐一些广告。那么Google是怎么从这些广告挣钱以及广告商可以通过Google广告获得什么利益呢？

Google的搜索页面不同的广告位有不同的价值，非常明显，就像我们搜索一样，一般会看排名靠前的结果。广告位也是一样，排名靠前的广告位的点击率要比排名靠后的点击率要高，而点击率越高就越可以让广告商被大家知道，从而广告商可以挣取很多其它的利益。设广告位的点击率为C（times/h, 一个小时点击次数），而且如果广告位的点击率和该广告位投放的广告内容独立，也就是说广告位的点击率不会受到投放广告内容的影响。

广告商想要将他们的内容显示在广告位的话，他们就得先出价（投标），Google综合各个广告商的出价决定将哪些广告商显示到广告位，并让被显示的广告商支付广告费；那么广告商可以得到什么呢？刚才讲到显示到广告位可以添加他们的点击率和曝光率，如果平均每次点击可以将给广告商带来R（这个值是由广告本身的内容决定的）美元的收益，那么每小时广告商能从广告中获得的收益就是R*C，这也称为广告商对将他们的广告内容显示到广告位的评估值（Evaluation）。投放广告，广告商要支付费用给Google（设为pay），这个值不一定等于他们的出价，和Google的收费方案也有关系，或者说是和广告的拍卖方法有关（后面会讲到），而他们又能从这次广告中收益Evaluation这么多利益，那么他们的净挣量为：Evaluation-pay。

广告商出价，Google决定他们之间的哪些显示到广告位，并向他们收取广告费……。非常明显，这就是一个拍卖过程，广告商出价相当于在投标，而他们显示到广告位就相当于中标，整个过程能够抽象成这样一个形式：

1 个卖家（Google）

N 个买家（广告商）

K 个东西（广告位）

买家：投标

卖家：分配资源给买家，而且想买家收取费用（收取费用的方法有详细的拍卖方法来决定）

拍卖能够分为单个物品拍卖和多个物品拍卖，首先从单个物品拍卖讲。单个物品拍卖有公开拍卖和密封拍卖。

在公开拍卖中通常有两种拍卖方法：一种是升价拍卖，这样的拍卖也应该是我们最常见的拍卖方法，首先卖家给个起价，这个起价通常较低，然后买家各自去竞价，当某个买家的投标足够高时，以至于没人和他竞争时，卖家就宣布这位买家中标；第二种是降序拍卖，相同地买家先给一个起价，这个起价通常较高，假设这个起价没有人购买，就继续往下降，一旦有买家宣布购买，那么拍卖结束，这位买家中标。

在密封拍卖中，投标者之间不知道各自的投标价格，仅仅能凭借着自己对拍卖物品的估值以及自己的策略去投标。在密封拍卖中，通常又分为两种方式：一种是最高价格密封拍卖（sealed-first-price-auction），这样的拍卖方式，首先让投标者各自将投标价投上来，然后卖家比較他们的投标价格，将物品卖给竞标价最高的买家，并让这位买家按他自己的竞标价支付给买家；还有一种是第二高价格密封拍卖（sealed-first-price-auction），这样的方式和最高价格密封拍卖类似，卖家相同比較他们的投标价格，而且将物品卖给竞标价最高的买家，可是仅仅须要让这位买家按第二高竞标价支付给卖家。从直觉上来讲，似乎最高价格的最好，由于可以收取最高投标价，为什么还要依照第二高投标价来收取费用呢？事实上不一定如此，假设依照最高价格密封来拍卖的话，卖家的投标价就会有意识的减少，由于他们的支付费用就是他们的投标费用，投多少直接关乎到中标后要支付多少，另外，他们不能一味的减少他们的投标价，否则就会非常大程度上减少他们的中标概率，所以他们要去搜集各种资料，去预计对手们的出价，这些都是须要花费时间精力和金钱的，从而会继续影响到他们的投标价格；而假设依照第二高价格密封拍卖的话，卖家仅仅须要依照他们对拍卖物品的评估值去出价，由于他们中标以后所须要支付的价格与自己的投标价没有直接的联系，由第二高的投标价决定，这样一来买家不须要花费大量时间精力和金钱去搜集各种信息，仅仅须要依照自己对物品的评估价来出价就好了，由于舍去了搜集信息的花费，他们对物品的评估价也会上升。相比較而言，对单个物品而言，第二高价密封拍卖更加可以吸引用户依照自己对物品的评估来出投标价（后面会分析为什么会这样），这个行为称为（Truth
for bidding）。

假设将第二高价密封拍卖延伸到多个物品的拍卖，这个拍卖方法就变成了通用化第二高价密封拍卖（GSP，Generalized Second Price），这也是Google所用的广告位拍卖方法。比方说有3个广告位，4个人去竞标，分别投标价格为R1 > R2 > R3 > R4，那么第一个人将得到第一个广告位（点击率最高），支付的费用为R2；第二个人得到第二个广告位，支付的费用为R3；第三个人得到第三个广告位，支付的费用为R4；而第四个人因为他的投标价格过低，没有中标。这样的方式并不能吸引用户的Truth for
bidding 行为，而还有一种针对多个物品密封的拍卖方法却可以吸引用户Truth for bidding，这样的方法叫做VCG，Vickrey-Clarke-Groves。

作为一个拍卖方案应该考虑一下几个因素：

1、卖家的收益。也就是买家支付给卖家的费用。

2、买家的回报。也就是从卖家那里得到的价值减去自己支付给买家的费用。

3、作为拍卖方案的设计者，也应该考虑拍卖的公平和效率，以及让买家尽可能做出Truth for bidding，也就是让他们依照自己对拍卖物品的估值投标。

第二高价密封拍卖方案就较好地考虑到了上面三个因素，它将拍卖中的中标和定价两个过程去耦合了，能不能中标看买家的投标价格，中标之后的详细定价则是看其它买家的价格（详细地讲是看第二高价买家的投标价格）。刚才提到，第二高价密封拍卖可以吸引用户依照自己对物品的评估值来投标，假设某个买家A对一个拍卖物品的评估值为v（评估值最高），而他的投标值为b，假设v = b， 那么说明他的行为是Truth for bidding。假设投标价格小于评估值，即b < v，这时假设另外一个买家B（评估值第二高）依照评估值投标而且投标价格为b1，假设b
< b1 < v，那么买家A就不能中标，得到的回报是0；可是假设他依照评估值投标，那么他就能够中标，而且得到的回报是：v-b1。假设买家A的评估值是第二高，而且他的投标值高于评估值，即b > v，而买家B的评估值是最高的，而且依照评估值投标b1，这时假设v < b1 < b，那么他能够中标，可是得到的回报却是：v-b1 < 0，而假设他的行为是Truth for bidding的，他得到的回报是0。综上所述，Truth for bidding才是投标者的最佳投标策略，因而就吸引了非常多买家Truth for
bidding，这个方法也被非常多机构所採用。而假设依照最高价密封拍卖方案，用户就不会把依照他们的评估值来投标，由于这种话，假设他们中标，所得到的回报是0。因此，他们会有意的减少投标价格，这样会给Google造成非常大的损失，详细原因可能要从非常多方面解释，或许是通过详细实验验证这个结论的。

与第二高价密封拍卖方案类似的是eBay的拍卖方案，这样的拍卖主要有下面几个特点：

1、拍卖持续时间。

2、起始价格。

3、每次叫价的最低增量（delta）。

4、托管代理。代理买家投标，直到买家给的最高价格低于当前拍卖的叫价。

如果第一天，eBay上有个拍卖物品，開始叫价5$，而且最低增量delta为1$，Alice投标12$，系统就会将其视为中标，而且中标价格为5$，此时的叫价就变成：min(5, 5)+delta = 6$。

第二天Bob投标8$，此时因为12$ > 8$+1$，Alice的托管代理能够通过加价击败Bob，所以自己主动投标9$（而且系统继续觉得他是中标的），此时拍卖的最高价格和第二高价格分别为：9$， 8$，拍卖最新叫价为：min(9$, 8$+delta) + delta = 10$。

第三天，Bob投标10.5$，此时因为12$ > 10.5$+1$，Alice的托管代理能够加价击败Bob，所以自己主动投标11.5$， 此时拍卖的最高价格和第二高价格各自是：11.5$, 10.5$，拍卖最新叫价为：min(11.5$, 10.5$) + delta = 12.5。

第四天，Bob投标17.5$，此时因为12$ < 17.5$+1$，Alice的托管代理放弃投标，此时最新叫价为：min(17.5$, 11.5$+1$)+delta = 13.5$。

第五天，Chris投标18$，此时因为17.5$ < 18$+1$，Bob的托管代理放弃投标，此时拍卖的最高投标价格为：min(18$, 17.5$+1$)+delta = 19$。

终于Chris中标，须要支付min(18$, 17.5$+1$) = 18$。

（公开课的这部分也讲的比較模糊，之后查资料又一次去整理一遍思路把这部分再改动一下）

将第二高价密封拍卖拓展到多个物品，就变成了GSP，也就是Google所用的拍卖方法。看以下一个样例：

依照我们之前讲的GSP的规则，终于第一个投标者会得到第一个广告位，支付25美元；第二个投标者会得到第二个广告位，支付3美元；第三个投标者会得到第三个广告位，支付第四高的对第三个广告位的投标费用。可是我们之前讲到GSP并不能想单个物品的第二高价密封拍卖那样吸引买家Truth for bidding，它有漏洞，看以下这个样例：

三个拍卖者对每次（这和之前的每一个小时有点不一样，只是原理一样）点击的估值为12$, 8$, 4$，而两个广告位的点击率分别为400, 300。如果依照Truth for bidding 投标的话，三个拍卖者对每次点击的投标值应该为12$, 8$, 4$，此时第一个投标者得到第一个广告位，回报为：（12-8）*400= 1600$；而第一个投标者没有依照评估值投标（如果投标7$），其它两个依照估值投标，那么他将得到第二个广告位，回报为：（12-4）*300 = 2400$，大于依照评估值所得的回报。

由以上的样例说明，GSP并不能非常好的吸引买家依照评估值来竞标，而VCG可以，那为什么Google不採用VCG拍卖方案呢？

原因是：

1、影响拍卖效益的不只在于Truth for bidding。

2、还要可以将拍卖方案解释出来，Google面对各种各样的客户，可以让他们简单清楚的理解拍卖方案也非常重要，而VCG较复杂。

3、多个同一时候进行的拍卖。公开课里面提到了这一点，不是非常清楚。

4、非理性行为。虽然Google将拍卖方案从GSP转变为VCG，可是非常多用户还是会用GSP时候的投机手段，使得Google损失很多其它。详细不是非常理解。

參考资料：

1、《Network 20Q》, Princeton。

2、https://support.google.com/adsense/answer/160525?hl=en

3、http://en.wikipedia.org/wiki/Sealed_first-price_auction

4、http://baike.baidu.com/view/4421707.htm?fr=aladdin