Fast Core Pricing for Rich Advertising Auctions

Rad Niazadeh (), Jason Hartline (), Nicole Immorlica (), Mohammad Reza Khani () and Brendan Lucier ()
Additional contact information
Rad Niazadeh: Chicago Booth School of Business, University of Chicago, Chicago, Illinois 60637
Jason Hartline: Computer Science Department, Northwestern University, Evanston, Illinois 60208
Nicole Immorlica: Microsoft Research New England, Cambridge, Massachusetts 02142
Mohammad Reza Khani: Amazon, Seattle, Washington 98109
Brendan Lucier: Microsoft Research New England, Cambridge, Massachusetts 02142

Operations Research, 2022, vol. 70, issue 1, 223-240

Abstract: Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey–Clarke–Groves (VCG) auction can yield unacceptably low revenue. We therefore study core-selecting auctions, which boost revenue 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 combinatorial 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 experimentally 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.

Keywords: Revenue Management and Market Analytics; sponsored search auctions; core pricing; VCG auction; GSP auction; sale of ad space; combinatorial auction (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:1:p:223-240

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().