搜索引擎的竞价排名是怎样实现的？
导读：在搜索引擎的搜索结果页面上一般有两类内容：一类是根据PageRank等算法得到的与你搜索的关键字有直接关联的源生链接，另一类是广告商付了费的广告链接。
每次你在搜索引擎上搜索一个关键字时，搜索引擎在背后都实时地运行了一场拍卖，通过这场拍卖来决定哪些广告商的链接能够被显示出来，这些链接以什么次序排列，以及向每个广告商收取多少钱。
那么这样的系统背后的模型是什么？是怎样设计的？本文带你一一了解。
作者：蒂姆·拉夫加登（Tim Roughgarden）
译者：郝东 李斌 刘凡
来源：大数据DT（ID：hzdashuju）
01 背景知识
关键字搜索拍卖创造了巨大的网络经济效益。相关的数据非常让人震撼：在2006年，来自关键字搜索拍卖的利润占据了谷歌总利润的98%。虽然在线广告现在有多种成熟的表现形式，但是关键字搜索拍卖产生的经济价值仍然是每年数百亿美元量级的。
进入正式讨论前，我们先看两个定义：
1. 占优策略激励相容（DSIC）
在一场拍卖中，如果对于每一个竞拍者按照自己的估值真实报价都是一个占优策略，并且真实报价的竞拍者的效用都非负，则称这个拍卖是占优策略激励相容（Dominant-Strategy Incentive Compatible，DSIC）的。
2. 社会福利
单物品拍卖结果的社会福利定义为
其中，如果竞拍者i赢得了拍卖，则xi为1，否则为0。因为只有一个物品，所以有一个可行性的约束条件
。所以，社会福利就是赢家的估值，或者如果没有赢家的话，社会福利就是0（物品的售价并没有包括在社会福利的计算中。我们将卖家视为一个独立的智能体，他的收益抵消了赢家由于支付而产生的收益损失）。
如果在一场拍卖中，在所有的竞拍者都说真话的情况下，拍卖的结果能导致最大的社会福利，就说这场拍卖是社会福利最大化（welfare maximizing）的。
02 关键字搜索拍卖的基本模型
下面我们针对关键字搜索拍卖，讨论一种简单、实用且很有影响的模型。需要销售的物品是某个搜索结果页面上的k个广告链接位置。竞拍者是一些想要在该关键字页面下显示自己广告链接的广告商。
例如，沃尔沃和斯巴鲁可以是“客货两用车”这个关键字的竞拍者，尼康和佳能可以是“单反相机”这个关键字的竞拍者，这样的拍卖形式比单物品拍卖要复杂。
其复杂体现在两个方面：一方面，一般来说，有多个物品待售（即k>1）；另一方面，这些物品是不同的。例如，如果广告是按顺序显示在页面上的，那么排在前面的广告比排在后面的广告就更有价值，因为人们一般遵循从前到后的顺序来浏览广告列表。
我们使用点击率（Click-Through Rate，CTR）来对不同广告位之间的差别进行量化。广告位j的点击率αj表示的是用户点击这个广告位链接的概率。如果广告位是从上到下排列的，那么一个合理的假设就是α1≥α2≥…≥αk。为了简化处理，我们现在做一个不太合理的假设，即广告位的点击率与该广告位的内容无关。
关键字搜索拍卖可以扩展到更一般化且符合实际的形式，即每个广告商i都有一个自己的质量分βi（越高越好），这样的话，广告商i在广告位j处的链接的点击率计算为βiαj。
我们假设广告商并不在乎广告的曝光量，而是对用户的每一次点击有一个估值vi。这样的话，广告商i在广告位j处的期望值就是viαj。
03 我们想要什么
是否存在理想化的关键字搜索拍卖呢？对于这样的拍卖，有以下几个关键的需求：
- DSIC。也就是按照真实估值报价是占优策略，而且效用不会为负。
- 社会福利最大化。对广告位的分配应该使得
最大化，其中xi是分配给i的广告位的点击率（如果该广告位没分配给任何广告商，则为0）。每个广告位只能分配给一个竞拍者，每个竞拍者只能得到一个广告位。
- 计算高效。拍卖的运行时间应该是输入（即v1,…,vn）的多项式级的（甚至是近线性的）。请注意，每天都有海量的这种拍卖在搜索引擎上运行。
04 我们的设计方法
拍卖问题的困难在于，我们要同时处理两个搅在一起的事情：决定谁赢得拍卖，以及决定每个人付多少钱。即使在单物品拍卖中，如果只做对了第一件事（比如把物品分给出价最高的竞拍者），也是不够的。因为如果没有好好设计支付，那么策略型参与者就会钻空子。
令人高兴的是，在许多应用（包括关键字搜索拍卖）中，我们可以同时解决这两个交织在一起的问题。
- 步骤1：假设所有的竞拍者都如实报价。那么，我们该如何将竞拍者分配到广告位上去，从而使得上面的性质2和3成立？
- 步骤2：在得到步骤1的解之后，我们该如何设定售价，从而使得上面的性质1成立？
如果能高效地解决以上两个步骤，那么我们就得到了一个理想的拍卖。步骤2保证了DSIC性质，这意味着竞拍者会如实报价（前提是如果竞拍者有占优策略，就会执行这个策略）。这样的话，步骤1中的假设就得到满足了，所以拍卖的结果就是社会福利最大化的。
最后，我们来看看在关键字搜索拍卖这个情境下步骤1是如何执行的。如果报价都是真实的，我们该如何将竞拍者分配到广告位上去才能实现社会福利最大化呢？自然的贪心算法是能实现最优的（而且是计算高效的），即对于所有的i=1,2,…,k，将报价第i高的竞拍者分配到点击率第i高的广告位上去。
关于作者：蒂姆·拉夫加登（Tim Roughgarden）， 哥伦比亚大学计算机科学系教授，之前曾任教于斯坦福大学，主要研究领域包括算法、博弈论以及微观经济学。他曾获得美国青年科学家与工程师总统奖（PECASE），ACM颁发的Grace Murray Hopper奖，Game Theory Society颁发的Kalai奖，Mathematical Programming Society颁发的Tucker奖，以及EATCS-SIGACT颁发的Gödel奖。
本文摘编自《斯坦福算法博弈论二十讲》，经出版方授权发布。