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高的广告位上去。
