Fast Core Pricing for Rich Advertising Auctions

As online ad offerings become increasingly complex, with multiple size configurations and layouts available to advertisers, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities. Standard ad auction formats do not immediately extend to these settings, and truthful combinatorial auctions, such as the Vickrey-Clarke-Groves auction, can yield unacceptably low revenue. Core selecting auctions, which apply to combinatorial markets, boost revenue by setting prices so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different allocation and payments. Among outcomes in the core, bidder-optimal core points have been the most widely studied due to their incentive properties, such as being implementable at equilibrium. Prior work in economics has studied heuristics and algorithms for computing approximate bidder-optimal core points given oracle access to the welfare optimization problem, but these solutions either lack performance guarantees or are based on prohibitively slow convex programs. Our main result is a combinatorial algorithm that finds an approximate bidder-optimal core point with almost linear number of calls to the welfare maximization oracle. Our algorithm is faster than previously-proposed heuristics, it has theoretical guarantees, and it reveals some useful structural properties of the core polytope. We conclude that core pricing is implementable even for very time sensitive practical use cases such as realtime auctions for online advertising and can yield more revenue. We justify this claim experimentally using the Microsoft Bing Ad Auction platform, which allows advertisers to have decorations with a non-uniform number of lines of text. We find that core pricing generates almost 100% more revenue than VCG on average, and almost 20% more revenue than the standard Generalized Second Price (GSP) auction.