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

编辑:麦格网络-

广告

导读:在搜索引擎的搜索结果页面上一般有两类内容:一类是根据PageRank等算法得到的与你搜索的关键字有直接关联的源生链接,另一类是广告商付了费的广告链接。

每次你在搜索引擎上搜索一个关键字时,搜索引擎在背后都实时地运行了一场拍卖,通过这场拍卖来决定哪些广告商的链接能够被显示出来,这些链接以什么次序排列,以及向每个广告商收取多少钱。

那么搜索引擎竞价排名系统背后的模型是什么?是怎样设计的?本文带你一一了解。

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

来源:,欢迎分享本文!

本文链接:https://www.029ppyy.com/SEOyouhua/429.html

你会喜欢下面的文章? You'll like the following article.