Fast Core Pricing for Rich Advertising Auctions

• 成果类型: Article
• 署名作者: Niazadeh, Rad; Hartline, Jason; Immorlica, Nicole; Khani, Mohammad Reza; Lucier, Brendan
• 署名单位: University of Chicago; Northwestern University; Amazon.com
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2104
• 发表日期: 2022
• 页码: 223-240
• 关键词: COMBINATORIAL; algorithm

摘要

Standard ad auction formats do not immediately extend to settings where multi-ple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementar-ities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) auction can yield unacceptably low revenue. We therefore study core-selecting auctions, which boost reve-nue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinato-rial algorithm that finds an approximate bidder-optimal core point with an almost linear number of calls to the welfare-maximization oracle. Our algorithm is faster than previously proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time-sensitive practical use cases such as real-time auctions for online advertising and can yield more revenue. We justify this claim experi-mentally usingMicrosoft Bing Ad Auction data, through which we show our core pricing algorithm generates almost 26% more revenue than the VCG auction on average, about 9% more revenue than other core pricing rules known in the literature, and almost matches the revenue of the standard generalized second price auction.