搜索引擎的竞价排名是怎样实现的

　　01背景知识
　　关键字搜索拍卖创造了巨大的网络经济效益。相关的数据非常让人震撼：在2006年，来自关键字搜索拍卖的利润占据了谷歌总利润的98。虽然在线广告现在有多种成熟的表现形式，但是关键字搜索拍卖产生的经济价值仍然是每年数百亿美元量级的。
　　进入正式讨论前，我们先看两个定义：
　　1。占优策略激励相容（DSIC）
　　在一场拍卖中，如果对于每一个竞拍者按照自己的估值真实报价都是一个占优策略，并且真实报价的竞拍者的效用都非负，则称这个拍卖是占优策略激励相容（DominantStrategyIncentiveCompatible，DSIC）的。
　　2。社会福利
　　单物品拍卖结果的社会福利定义为
　　其中，如果竞拍者i赢得了拍卖，则xi为1，否则为0。因为只有一个物品，所以有一个可行性的约束条件。所以，社会福利就是赢家的估值，或者如果没有赢家的话，社会福利就是0（物品的售价并没有包括在社会福利的计算中。我们将卖家视为一个独立的智能体，他的收益抵消了赢家由于支付而产生的收益损失）。
　　如果在一场拍卖中，在所有的竞拍者都说真话的情况下，拍卖的结果能导致最大的社会福利，就说这场拍卖是社会福利最大化（welfaremaximizing）的。
　　02关键字搜索拍卖的基本模型
　　下面我们针对关键字搜索拍卖，讨论一种简单、实用且很有影响的模型。需要销售的物品是某个搜索结果页面上的k个广告链接位置。竞拍者是一些想要在该关键字页面下显示自己广告链接的广告商。
　　例如，沃尔沃和斯巴鲁可以是客货两用车这个关键字的竞拍者，尼康和佳能可以是单反相机这个关键字的竞拍者，这样的拍卖形式比单物品拍卖要复杂。
　　其复杂体现在两个方面：一方面，一般来说，有多个物品待售（即kamp；gt；1）；另一方面，这些物品是不同的。例如，如果广告是按顺序显示在页面上的，那么排在前面的广告比排在后面的广告就更有价值，因为人们一般遵循从前到后的顺序来浏览广告列表。
　　我们使用点击率（ClickThroughRate，CTR）来对不同广告位之间的差别进行量化。广告位j的点击率j表示的是用户点击这个广告位链接的概率。如果广告位是从上到下排列的，那么一个合理的假设就是12k。为了简化处理，我们现在做一个不太合理的假设，即广告位的点击率与该广告位的内容无关。
　　关键字搜索拍卖可以扩展到更一般化且符合实际的形式，即每个广告商i都有一个自己的质量分i（越高越好），这样的话，广告商i在广告位j处的链接的点击率计算为ij。
　　我们假设广告商并不在乎广告的曝光量，而是对用户的每一次点击有一个估值vi。这样的话，广告商i在广告位j处的期望值就是vij。
　　03我们想要什么
　　是否存在理想化的关键字搜索拍卖呢？对于这样的拍卖，有以下几个关键的需求：
　　DSIC。也就是按照真实估值报价是占优策略，而且效用不会为负。
　　社会福利最大化。对广告位的分配应该使得最大化，其中xi是分配给i的广告位的点击率（如果该广告位没分配给任何广告商，则为0）。每个广告位只能分配给一个竞拍者，每个竞拍者只能得到一个广告位。
　　计算高效。拍卖的运行时间应该是输入（即v1，，vn）的多项式级的（甚至是近线性的）。请注意，每天都有海量的这种拍卖在搜索引擎上运行。04我们的设计方法
　　拍卖问题的困难在于，我们要同时处理两个搅在一起的事情：决定谁赢得拍卖，以及决定每个人付多少钱。即使在单物品拍卖中，如果只做对了第一件事（比如把物品分给出价最高的竞拍者），也是不够的。因为如果没有好好设计支付，那么策略型参与者就会钻空子。
　　令人高兴的是，在许多应用（包括关键字搜索拍卖）中，我们可以同时解决这两个交织在一起的问题。
　　步骤1：假设所有的竞拍者都如实报价。那么，我们该如何将竞拍者分配到广告位上去，从而使得上面的性质2和3成立？
　　步骤2：在得到步骤1的解之后，我们该如何设定售价，从而使得上面的性质1成立？如果能高效地解决以上两个步骤，那么我们就得到了一个理想的拍卖。步骤2保证了DSIC性质，这意味着竞拍者会如实报价（前提是如果竞拍者有占优策略，就会执行这个策略）。这样的话，步骤1中的假设就得到满足了，所以拍卖的结果就是社会福利最大化的。
　　最后，我们来看看在关键字搜索拍卖这个情境下步骤1是如何执行的。如果报价都是真实的，我们该如何将竞拍者分配到广告位上去才能实现社会福利最大化呢？自然的贪心算法是能实现最优的（而且是计算高效的），即对于所有的i1，2，，k，将报价第i高的竞拍者分配到点击率第i高的广告位上去。