| Abstrakt: |
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 natural equilibria. Prior work in economics has studied heuristics and algorithms for computing approximate bidder-optimal core points, given oracle access to the welfare optimization problem. Relative to prior work, our goal is to develop an algorithm with asymptotically fewer oracle calls while maintaining theoretical performance guarantees. 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 take a two-pronged approach to evaluating our core-pricing method. We first consider a theoretical treatment of the problem of finding a bidder-optimal core point in a general combinatorial auction setting. We then consider an experimental treatment of deploying our algorithm in a highly time-sensitive advertising auction platforms. [ABSTRACT FROM AUTHOR] |
