  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) 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 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 realtime auctions for
online advertising and can yield more revenue. We justify this claim
experimentally using the Microsoft Bing Ad Auction data, through which we show
our core pricing algorithm generates almost 26% more revenue than VCG 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 (GSP) auction.
