第 1 章 绪 论
本章将主要介绍关键词拍卖的研究背景，并分析现有研究的不足之处，确立以带预算约束的关键词拍卖作为本文主要的研究对象。在此研究背景下，简要介绍本文的研究意义、研究中遇到的难点、研究思路以及解决问题使用的基本方法。最后给出本文的研究内容与各章节的具体安排，并指出本文的创新点。
1.1 研究背景
近年来随着经济社会的快速发展，人们获取资讯的方式和手段也发生了巨大变化。早期人们主要通过传统媒体获取信息，如：电视、广播、杂志、报纸等。这些媒体覆盖面广，信息获取成本低，但是传播方式较为被动，信息精确度低，缺乏针对性，有效信息难以及时获取。随着互联网与信息技术的迅猛发展，以及传统媒体自身存在的缺陷，使得网络成为人们获取信息的最佳途径。但从浩如烟海的网络资源中寻找所需的信息仍然十分困难，用户迫切希望出现某种工具可以解决这个问题，所以搜索引擎就应运而生。该系统使用相应的计算机程序搜集互联网中的信息，并基于关键词匹配技术进行组织和协调处理，进而为用户提供各项检索服务。1990年，加拿大麦吉尔大学计算机学院的Alan Emtage、Peter Deutsch和 Bill Wheelan 开发了世界上第一个搜索引擎 Archie，它可以搜索 FTP 服务器上的文件；1993 年 6 月，世界上第一个网页搜索引擎 World Wide Web Wandere 发布，该系统仅仅可以检索网址；同年 10 月，Kosterc 创建了第二个网页搜索引擎ALIWEB，在之前系统的基础上进行了改进，相当于 Archie 的 HTTP 升级版本，能够检索网站的标题标签等索引信息1。之后随着雅虎、谷歌、百度等互联网公司的相继成立，搜索引擎技术也取得了长足的进步。由于操作的便捷性（用户仅需要在搜索栏中输入关键词就可以获得相应的海量资讯）和内容的精准性，越来越多的人将搜索引擎作为获取网络信息的首选工具。而且近年来凭借智能手机与移动互联网的深入普及与发展，各行各业的用户都可以随时随地使用移动设备通过搜索引擎检索方便快捷地获取自己所需的信息。
.......
1.2 研究意义
拍卖理论是经济学理论的一个重要分支，也是微观经济学的一个成功应用。而关键词拍卖是将拍卖理论应用于互联网广告领域的典范。作为一种新型的在线广告拍卖模式，它应用到经济学、管理学、数学与计算机科学等众多交叉学科的理论知识，具体涉及到博弈论、信息经济学、机制设计理论与优化理论等众多领域，相互促进，共同发展。其中带预算约束的关键词拍卖的理论研究更加符合实际情况，有助于将理论知识应用到实际中。关键词拍卖以出售搜索引擎的广告位为目的，与传统拍卖模式存在一些差别。首先，所有交易由计算机后台操作进行，从而交易时间很短，近似于实时完成。其次，由于同一时间用户检索量巨大，服务器必须同时将大量广告匹配到相应关键词，所以对拍卖机制和效率有着很高的要求。再次，广告主的最优竞价以及广告位的分配问题都是由计算机来实现，这使得机制设计和预算分配策略的制定变得非常关键。最后，关键词广告与传统消费品有很大不同。它的价值体现在占有广告位后，对自家品牌的传播与推广，而不在于拥有广告位；能否获得经济效益，取决于广告推广效果，具有一定的未知风险；占有广告位具有时效性，预算一旦耗尽，就无法获得广告位，若闲置也会浪费资源。一些可再生性资源也具有类似特征，因此关键词拍卖的研究对其他相似资源的分配也具有一定的借鉴意义。2002 年 5 月，著名经济学权威 Varian 加入 Google，受聘为该公司首席经济学家，利用拍卖理论优化 Google 的广告拍卖系统，并参与了数据查询、广告行为、收入预测、广告有效性、IPO 拍卖等项目，创造了庞大利润。2014 年 6 月，微软宣布任命著名经济学家 McAfee 为该公司首席经济学家，他曾担任 Google的战略技术主管，在 2007 年至 2012 年担任 Yahoo!的首席经济学家，负责研究市场和分析数据的工作。这些学者都针对关键词拍卖进行了大量的理论研究工作。在关键词拍卖研究方面，学者们已做出很多研究成果。Varian(2007)的论文在《International Journal of Industrial Organization》发表，以及 Edelman et al.(2007)、Edelman and Schwarz(2010)的论文两次发表于顶级经济学期刊《The AmericanEconomic Review》上，说明关键词拍卖问题已引起学术界的广泛关注。综上所述，关键词拍卖是一个新兴的研究领域。对于带预算约束的关键词拍卖问题的理论研究，一方面可以促进关键词广告行业健康有序发展，为搜索引擎企业提供理论指导；另一方面也为广告商们制定预算及报价策略，提高经济效益，增加整体社会福利，提供了理论依据。因此，该问题的研究对丰富和完善关键词拍卖理论起着非常重要的作用。
.........
第 2 章 文献综述
本文主要探讨搜索引擎通过拍卖机制出售关键词广告位，所以首先有必要简要介绍一下拍卖。大多数人或多或少都听说过拍卖这个概念，它是一种可以决定物品价格和配置的规则。拍卖行为随时随地都在发生着，苏富比、佳士得、中国保利、中国嘉德等国内外知名拍卖行拍卖艺术品、古董的新闻常常占据媒体的显要位置。2009 年 2 月 25 日法国佳士得拍卖行举办专场拍卖会，包括在战争时期被英法联军窃走并流失海外多年的我国圆明园流失文物十二生肖兽首中的鼠首和兔首铜像，当时引起国内的强烈反响。2015 年 5 月 11 日，在美国纽约举行的佳士得拍卖会上，西班牙著名画家毕加索的油画作品《阿尔及尔的女人（O 版）》以超过 1.79 亿美元的天价成交，创下全球艺术品拍卖的新高。还有如油气田的开采权、俄罗斯手机 1800MHz 频段、英国运输设施、伐木权等公共财产都是通过拍卖方式进行出售的。一些军事装备、建筑设施等政府合同也是通过拍卖竞标获得的。因此，拍卖可以处理各种商品的交易，体现出应用范围的广泛性；并且拍品的归属只取决于报价，与投标人的身份无关，也体现出拍卖的非歧视性。而拍卖理论作为经济学的一个分支，虽然起步较晚，但也有众多学者参与研究且取得很大进展。而近年来，随着信息技术与互联网高速发展，搜索引擎已成为人们最主要的检索工具。而随之兴起的网络广告模式——关键词广告，也成为众多广告主推广产品的重要途径之一。由于搜索引擎网站每天都会产生的庞大访问量，而搜索结果页面上的展示关键词广告很大程度上会影响用户的行为。关键词拍卖作为拍卖理论的一个重要应用，也已成为学术界的研究热点之一。本章中，我们首先对拍卖的起源、发展及不同拍卖方式进行介绍，然后回顾了关键词拍卖的发展历程，最后对关键词拍卖的相关文献进行分类，梳理并总结了国内外学者关于关键词拍卖问题的研究情况。
2.1 拍卖
2.1.1 拍卖发展历程
拍卖作为一种商品交易手段，对人类文明的发展起到了重要作用。据记载，拍卖最早出现于公元前 500 年左右，古希腊著名历史学家希罗多德曾纪录了古巴比伦的婚姻市场中出现过拍卖新娘的行为。直到罗马共和国时期，拍卖活动首次出现了高峰情况，除了继续保留拍卖奴隶的基础外，还出现了各种商品和战利品拍卖的交易行为。比如：罗马士兵向一些跟随军队的商人以拍卖方式出售他们使专门从事各类商品拍卖的拍卖行也由此诞生，代替早期由财产拥有者自行组织举行的拍卖活动。到了 17、18 世纪，拍卖已经成为一个行业。1744 年 3 月，英国人塞缪尔·贝克在伦敦的科芬园举办了一场书籍拍卖会，标志着世界上最古老的拍卖行——苏富比拍卖行诞生；1766 年，与苏富比齐名的另一大著名拍卖行——佳士得拍卖行由詹姆斯·佳士得在伦敦创立，并于当年的 12 月 5 日进行了首次拍卖。两家拍卖行在各自擅长的领域相互竞争，成绩斐然。当时的伦敦拍卖行可谓十分盛行，共有拍卖会 60 多家，拍卖业蓬勃发展，相关法规逐步建立与完善。我国的拍卖行最早出现在清末时期，1874 年，英国远东公司在上海开办鲁意斯摩洋行，在此之后，丹麦、法国、日本等国分别在上海建立拍卖行。而北京出现最早的拍卖行是光绪末年的鲁麟洋行。当时东郊民巷的外国人在回国前会将不便带走的家具、衣物等物品送去洋行，洋行采用拍卖方式进行出售。而在新中国成立之后，由于当时国家实行计划经济政策，所有物资都需要按照计划分配，所以商品交易价格受到严格管控，从而导致具有商品经济色彩的拍卖行业无法继续存在下去。1958 年，当时我国最后一家拍卖行在上海停业。这之后的 20 多年，我国的拍卖业完全销声匿迹。直到 1984 年中共十二届三中全会通过《关于经济体制改革的决议》，提出我国要建立具有中国特色的社会主义市场经济体制。在该决议正式实施后，拍卖业才逐步恢复起来。1986 年，我国第一家拍卖企业在广州创建。1995 年 6 月，中国拍卖行业协会正式挂牌成立。1994 年起，上海市为解决交通严重拥堵的状况，首次对新增客车的牌照实行拍卖，现已有一些城市如：天津、广州、深圳、杭州等效仿上海机动车牌照拍卖制度。据报道，2017年 2 月的沪牌拍卖数据显示，上海车牌拍卖平均成交价已达到 88240 元，比上月增加 555 元，中标率约为 4%9。1996 年 7 月 5 日，第八次全国人民代表大会第二十次会议审议通过我国第一部《拍卖法》，并于 1997 年 1 月 1 日起正式实施。自此，我国拍卖业已取得长足的发展。
..........
2.2 关键词拍卖的发展历程
1994 年，最早的互联网广告诞生。早期采取的定价方式是双方进行谈判，网站与每个有意向的广告主一对一单独进行谈判，综合考虑各方面因素确定是否同意在该平台投放广告。广告平台通常采用每千次点击支付(Cost Per Mille, CPM)向广告主收费，一些大企业广告主可以接受这种谈判定价方式，但是对众多小企业广告主也采取同样方式，费时费力且效果很差，并不适合高效率的互联网平台，还对互联网广告的发展造成了一定的阻碍。1997 年，一家名为 GoTo.com 的搜索引擎公司（2001 年正式更名为 Overture，2003 年 Yahoo!公司以 16.3 亿美元的价格收购该公司）最先使用拍卖的方式出售其搜索结果页面上的广告位，他们使用的是广义第一价格（Generalized FirstPrice，GFP）拍卖机制。广告主根据自身产品或服务具备的特点，对感兴趣的关键词的相关度和搜索频率进行综合考量后，给出用户每次点击后广告主应支付的费用。一旦搜索引擎用户检索该关键词时，搜索引擎将所有对此关键词进行过报价的广告主全部从其数据库中调出，按照报价大小由高到低进行排序，然后按照该顺序将搜索结果页面上的广告位从上到下依次分配给相对应的广告主。在 GSP机制中，若用户点击了某位广告主的关键词广告链接，则该广告主需要向搜索引擎支付等于自己报价的广告费。相比早期的互联网广告模式，GoTo.com 公司采用的关键词广告交易机制有以下几点特征：首先，关键词广告属于定向发布广告，广告主可以选择不同的关键词控制投放广告的受众群体，如性别、年龄、教育背景、职业、收入等因素，避免在非自身目标群体上浪费广告预算；其次，关键词广告是按点击支付的，只有用户点击广告链接后，广告主才需要向搜索引擎付费。相比按照展示次数付费的模式，按照点击付费更容易被广告主所接受。而与一对一谈判的模式相比，关键词广告的交易效率也因为自主运行的拍卖机制而大幅提升，还能够提供详尽的统计数据报告供广告主参考调整；最后，相较投放传统广告的高昂成本，关键词广告的费用相对较低，多数中小微广告主也可以参与投放。由于具备上述这些特征，GoTo.com 公司推出的关键词广告拍卖模式获得巨大成功。不过系统经过一段时间的运行实践后，GFP 机制存在的缺陷也逐渐暴露出来，为获取更多的收益，广告主需要时刻关注竞争对手的情况，还要根据对手的反应随时调整报价，导致形成价格战的态势，对拍卖效率造成一定的损失。因此，GFP 拍卖机制存在效率低、不稳定的缺点。
........
第 3 章 关键词拍卖相关理论 ..........35
3.1 非合作博弈理论中的基本概念 .....35
3.2 关键词拍卖基本假设及概念 .........38
3.2.1 关键词拍卖中的基本假设...........38
3.2.2 关键词拍卖中的基本概念...........39
3.3 三种常见的关键词拍卖机制 .........40
3.4 广告位拍卖的利益相关方及其目标和策略选择 ....42
3.5 本章小结 .....43
第 4 章 基于纳什均衡的带预算约束的广告主均衡报价研究............44
4.1 引言....44
4.2 关键词拍卖模型 ...........45
4.3 纳什均衡下广告主报价的上下界 ..........47
4.4 带预算约束的纳什均衡 ........49
4.5 搜索引擎收益 ......59
4.6 不同均衡报价集的关系 ........66
4.7 本章小结 .....67
第 5 章 基于 VCG 机制的带预算约束关键词拍卖研究....69
5.1 引言....69
5.2 关键词拍卖模型描述 ............70
5.3 广告主均衡报价 ...........73
5.4 本章小结 .....81
第 6 章 展示时间对广告主收益的影响
本章针对 Koh(2013)论文中带预算约束的关键词拍卖模型中最长广告展示时间设置为单位时间 1 的假设进行拓展，根据广告主自身情况，将最长展示时间调整为不再固定不变。在之前两章中，若广告主预算耗尽的时间小于等于拍卖时间，则提前退出拍卖；若某广告主预算充足，则他不会提前耗尽退出拍卖，而始终占据广告位，直到拍卖结束。本章假设关键词广告展示不再设置统一的结束时间，只有当广告主预算耗尽时才会退出拍卖。在此假设下，广告主 i 的预算在整个拍卖过程中的总支付值就等于预算值，即i i i iP = p t = B。而广告主的收益由自身估价、报价、预算、所占据广告位的点击率与广告展示时间共同决定。下面将讨论在展示时间不固定的条件下，当报价向上偏离与向下偏离时，广告主收益会如何变化，是否有利可图，以及能否达到均衡状态等问题。
6.1 引言
搜索引擎可以使人们更方便地获取所需信息，很多网民将搜索引擎作为上网的重要入口。根据权威研究公司 Forrester 的调查数据表明，2015 年底，全球搜索引擎用户达到 18.57 亿，并且每年仍以 10%的速度增长，稍高于全球网络用户每年 8%的增长速度，市场规模约为 815.9 亿美元。报告还显示，大部分网民只会关注或点击搜索结果页面排在前十位左右的网页链接，仅有不到 1%的搜索用户会浏览排在 30 位之后的搜索结果，该结论普遍适用于使用不同语言及国籍的网民。每个广告商都希望自己的产品获得更高的关注度，自己的网站得到更多用户的有效点击。而搜索引擎营销可以帮助广告主在搜索引擎网站上取得好的排名，进而提高自身收益。在搜索引擎营销领域，关键词广告始终是最重要的组成部分。而预算分配并不是一个独立的问题，它与广告推广效果、广告主报价策略及搜索引擎的收益等因素密切相关。预算分配状况将直接影响广告主参与拍卖的时间。由于规则的灵活性，广告主可根据自身预算选择随时进入或退出拍卖过程。若广告主对一个关键词分配的预算过多，则在这个时间段结束后，该预算将继续进行投放，直到耗尽为止。因此，分析在预算约束广告展示时间不固定情况下的相关结论有助于关键词拍卖理论的进步与完善。
.........
结论
（1）从广告主角度考虑，为了控制成本以及防止支付过高，广告主投放关键词广告需要事先给定每天的预算。而此前多数关键词拍卖的文献由于复杂性的原因，没有在研究中引入预算约束进行考虑。首先，构建带预算约束的关键词拍卖模型，并给出带预算约束的纳什均衡概念，推导出满足纳什均衡条件的广告主报价的上界和下界，并与 Varian(2007)给出的满足对称纳什均衡广告主报价的上下界进行比较。其次，试图找出广告主们的报价向量达到带预算约束的纳什均衡条件，即每位广告主都满意自己现在所处的广告位，在该位置的收益最大。给出广告主报价向上偏离无利可图的条件，并用数值实例说明了广告主报价向下偏离后收益变化的不同情况。再次，给出广告主报价上界构成的报价向量不是带预算约束的纳什均衡的条件，并证明报价上界组成的向量是对称纳什均衡（同时也是纳什均衡）。综合上述结论，利用广告主的报价上界，给出并证明广告主报价向量是带预算约束的纳什均衡的充要条件。相比对称纳什均衡，由于应满足的条件不同，达到带预算约束的纳什均衡的情形要更复杂一些。最后，建立一个简单的带预算约束的二人博弈关键词拍卖模型，并给出此模型中报价向量达到带预算约束的纳什均衡应满足的条件以及预算与两人估价在不同范围下搜索引擎的收益大小。本研究的结论可以有效帮助广告主制定预算和报价策略，有效控制成本，也为搜索引擎采用何种拍卖机制能够提高利润提供一些参考。
（2）本文基于 VCG 机制研究了带预算约束的关键词广告拍卖问题，广告主在 VCG 机制中的支付取决于排在他之后的广告主占据广告位的点击率和其报价组成的线性组合，所以广告主的报价变化会对其他广告主的支付及收益造成影响。采用带有预算约束的全局无嫉妒纳什均衡条件，分析了广告主报价向上偏离后自身收益应如何变化，并找到广告主报价向上偏离无利可图的充要条件。之后还给出广告主的报价都取上界时，所组成的向量不是带预算约束的全局无嫉妒均衡的充要条件，并证明报价上界组成的向量是全局无嫉妒均衡的。最后综合上述结论，给出 VCG 机制中广告主报价向量是带预算约束的全局无嫉妒均衡的充要条件。该结论扩展了 Koh(2013)的研究结论，将预算约束和全局无嫉妒均衡应用到 VCG 机制中。
（3）上述研究都是在广告展示时间设定为 1 的条件下得出的。假设广告展示时间不固定时，广告主只有在预算耗尽后才会退出拍卖。这种情况下，广告主的收益由自身预算、估价、报价、所在广告位点击率等因素共同决定。建立展示时间不固定的关键词拍卖模型，并给出广义点击率的概念。判断报价向量能否达到带预算约束的纳什均衡，通过研究发现，在给定预算的情况下，广告主报价向上偏离是无利可图的，而报价向下偏离是有利可图的。因此，在预算确定的情形下，广告主报价构成的报价向量无法达到带预算约束的纳什均衡。
..........
参考文献（略）