Pure-Strategy Nash Equilibria of GSP Keyword Auction

CORC > 自动化研究所 > 中国科学院自动化研究所 > 复杂系统管理与控制国家重点实验室 > 互联网大数据与安全信息学研究中心

	Pure-Strategy Nash Equilibria of GSP Keyword Auction
	Li, Linjing1 ; Zeng, Daniel; Zhao, Huimin 2
刊名	JOURNAL OF THE ASSOCIATION FOR INFORMATION SYSTEMS
	2012
卷号	13 期号:2 页码:57-87
关键词	Keyword Advertising Stability Generalized Second-Price Sponsored Search Nash Equilibrium
英文摘要	Despite the tremendous commercial success of generalized second-price (GSP) keyword auctions, it still remains a big challenge for an advertiser to formulate an effective bidding strategy. In this paper, we strive to bridge this gap by proposing a framework for studying pure-strategy Nash equilibria in GSP auctions. We first analyze the equilibrium bidding behaviors by investigating the properties and distribution of all pure-strategy Nash equilibria. Our analysis shows that the set of all pure-strategy Nash equilibria of a GSP auction can be partitioned into separate convex polyhedra based on the order of bids if the valuations of all advertisers are distinct. We further show that only the polyhedron that allocates slots efficiently is weakly stable, thus allowing all inefficient equilibria to be weeded out. We then propose a novel refinement method for identifying a set of equilibria named the stable Nash equilibrium set (STNE) and prove that STNE is either the same as or a proper subset of the set of the well-known symmetrical Nash equilibria. These findings free both auctioneers and advertisers from complicated strategic thinking. The revenue of a GSP auction on STNE is at least the same as that of the classical Vickrey-Clarke-Groves mechanism and can be used as a benchmark for evaluating other mechanisms. At the same time, STNE provides advertisers a simple yet effective and stable bidding strategy.
WOS标题词	Science & Technology ; Technology
类目[WOS]	Computer Science, Information Systems ; Information Science & Library Science
研究领域[WOS]	Computer Science ; Information Science & Library Science
关键词[WOS]	SPONSORED SEARCH
收录类别	SCI ; SSCI
语种	英语
WOS记录号	WOS:000307843600001
内容类型	期刊论文
源URL	[http://ir.ia.ac.cn/handle/173211/3670]
专题	自动化研究所_复杂系统管理与控制国家重点实验室_互联网大数据与安全信息学研究中心
作者单位	1.Chinese Acad Sci, State Key Lab Management & Control Complex Syst, Inst Automat, Beijing, Peoples R China 2.Univ Wisconsin Milwaukee, Sheldon B Lubar Sch Business, Milwaukee, WI USA
推荐引用方式 GB/T 7714	Li, Linjing,Zeng, Daniel,Zhao, Huimin. Pure-Strategy Nash Equilibria of GSP Keyword Auction[J]. JOURNAL OF THE ASSOCIATION FOR INFORMATION SYSTEMS,2012,13(2):57-87.
APA	Li, Linjing,Zeng, Daniel,&Zhao, Huimin.(2012).Pure-Strategy Nash Equilibria of GSP Keyword Auction.JOURNAL OF THE ASSOCIATION FOR INFORMATION SYSTEMS,13(2),57-87.
MLA	Li, Linjing,et al."Pure-Strategy Nash Equilibria of GSP Keyword Auction".JOURNAL OF THE ASSOCIATION FOR INFORMATION SYSTEMS 13.2(2012):57-87.