当前位置: 首页 > news >正文

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

导读:在搜索引擎的搜索结果页面上一般有两类内容:一类是根据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 我们想要什么

是否存在理想化的关键字搜索拍卖呢?对于这样的拍卖,有以下几个关键的需求:

  1. DSIC。也就是按照真实估值报价是占优策略,而且效用不会为负。

  2. 社会福利最大化。对广告位的分配应该使得最大化,其中xi是分配给i的广告位的点击率(如果该广告位没分配给任何广告商,则为0)。每个广告位只能分配给一个竞拍者,每个竞拍者只能得到一个广告位。

  3. 计算高效。拍卖的运行时间应该是输入(即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奖。

本文摘编自《斯坦福算法博弈论二十讲》,经出版方授权发布。

延伸阅读《斯坦福算法博弈论二十讲》

点击上方链接了解及购买

转载请联系微信:DoctorData

推荐语:本书源于斯坦福大学“算法博弈论”课程讲义,计算机科学+经济学的跨学科研究,涵盖重要模型与结论。

部分图书目前在京东满100减30,长按下方二维码去逛逛吧。

相关文章:

  • 掌握Java核心技术,看我!
  • 【新书速递】斯坦福算法博弈论二十讲
  • 【直播预告】「甦:知识蓄力2020」编辑讲书智慧接力行动
  • 【一周书讯】网络安全、云计算、人工智能、大数据一网打尽
  • 计算机仿真模拟告诉你,为什么现在还不能开学
  • 物联网领域新计算范式技术、架构、应用方面的前沿指南
  • 无处不在的流计算到底是什么?终于有人讲明白了(附导图)
  • 打破VR-AR的“神话” 揭开VR-AR的“现实”
  • 手绘 | 深入解析风控8大场景中的机器学习应用
  • 新时代的大数据处理方式:实时流计算
  • 中央定调,“新基建” 彻底火了!这七大科技领域要爆发
  • “程序媛”女神节,华章图书备厚礼,快来拿礼物
  • 【直播预告】3月7日|新时代的大数据处理方式——实时流计算
  • 世界上第一位程序员,竟然是诗人拜伦的女儿?
  • 一文读懂Docker及其对系统管理员的重要性
  • Fastjson的基本使用方法大全
  • GitUp, 你不可错过的秀外慧中的git工具
  • Git初体验
  • JavaScript新鲜事·第5期
  • java正则表式的使用
  • Js基础知识(四) - js运行原理与机制
  • Kibana配置logstash,报表一体化
  • LintCode 31. partitionArray 数组划分
  • magento 货币换算
  • spring学习第二天
  • SwizzleMethod 黑魔法
  • Travix是如何部署应用程序到Kubernetes上的
  • 关于 Linux 进程的 UID、EUID、GID 和 EGID
  • 记录一下第一次使用npm
  • 入手阿里云新服务器的部署NODE
  • 使用putty远程连接linux
  • 算法-图和图算法
  • 提醒我喝水chrome插件开发指南
  • 详解NodeJs流之一
  • [Shell 脚本] 备份网站文件至OSS服务(纯shell脚本无sdk) ...
  • CMake 入门1/5:基于阿里云 ECS搭建体验环境
  • hi-nginx-1.3.4编译安装
  • ​卜东波研究员:高观点下的少儿计算思维
  • #HarmonyOS:Web组件的使用
  • #QT(一种朴素的计算器实现方法)
  • (C语言)输入一个序列,判断是否为奇偶交叉数
  • (delphi11最新学习资料) Object Pascal 学习笔记---第2章第五节(日期和时间)
  • (八)Docker网络跨主机通讯vxlan和vlan
  • (附源码)springboot“微印象”在线打印预约系统 毕业设计 061642
  • (附源码)ssm考生评分系统 毕业设计 071114
  • (附源码)计算机毕业设计SSM在线影视购票系统
  • (一)eclipse Dynamic web project 工程目录以及文件路径问题
  • (转)编辑寄语:因为爱心,所以美丽
  • (转)菜鸟学数据库(三)——存储过程
  • **CI中自动类加载的用法总结
  • .helper勒索病毒的最新威胁:如何恢复您的数据?
  • .Net - 类的介绍
  • .net redis定时_一场由fork引发的超时,让我们重新探讨了Redis的抖动问题
  • .NET处理HTTP请求
  • [20161101]rman备份与数据文件变化7.txt