Finding Bidder-Optimal Core Points Quickly

Jason D. Hartline, Nicole Immorlica, Brendan Lucier, Rad Niazadeh

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) 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.

Introduction

Modern online advertising has evolved beyond simple text slots into "rich" environments where ads vary in size, layout, and decorative features. In these settings, the auction becomes combinatorial: the value of a specific ad placement depends heavily on the surrounding ads and the remaining screen real estate. While the Vickrey-Clarke-Groves (VCG) mechanism is theoretically elegant due to its truthfulness, it often fails in combinatorial settings by producing unacceptably low revenue and outcomes that appear "unfair" to losing bidders who would have willingly paid more than the winners.

Core-selecting auctions address these flaws by ensuring that the resulting payments lie within the "core." A payment is in the core if no coalition of bidders and the auctioneer can find an alternative outcome that improves their collective utility. However, calculating these payments has historically been a computational bottleneck, requiring iterative linear programming that is too slow for real-time systems like search engines, which must process thousands of auctions every millisecond.

The Water-Filling Algorithm

To overcome the speed limitations of traditional core-selecting methods, we propose a deterministic Water-Filling Algorithm. This approach finds an $\epsilon$-approximate bidder-optimal core point by navigating the geometry of the core polytope in utility space.

Intuition and Mechanism

The algorithm begins by assuming all bidders pay their full bids, resulting in zero utility. It then "pours" utility into a subset of bidders, increasing their gains uniformly until they hit a "facet" of the core polytope—a boundary where a core constraint becomes tight.

Crucially, the algorithm treats the underlying welfare-maximization problem (deciding which ads to display) as a black-box oracle, referred to as WIN-ORAC. By using binary search to identify tight constraints and "freezing" bidders as they hit these boundaries, the algorithm terminates in at most $n$ iterations (where $n$ is the number of bidders). This results in a query complexity of $O(n \log(n/\epsilon))$, a significant improvement over general-purpose cutting-plane methods.

Practical Advantages

Unlike previous heuristics that suffer from precision issues or "unstable behavior" in production environments, the water-filling approach is robust. It avoids the log-function overflows common in optimization-based methods and is significantly easier to implement within existing production codebases.

Experimental Evaluation

We evaluated the algorithm using a massive dataset from Microsoft Bing, comprising approximately 20,000 text ad auctions from early 2018. These auctions involved up to 23 advertisers with configurations ranging from 3 to 14 lines of text. The scale of this data reflects the high-pressure environment of Bing, which processes roughly 3.7 auctions every millisecond.

Key Results

  • Revenue Performance: The water-filling algorithm generated 26% more revenue than VCG on average. Furthermore, it outperformed existing core-pricing rules in the literature by approximately 9% and nearly matched the revenue of the standard (though ad-hoc) Generalized Second Price (GSP) auction.
  • Computational Efficiency: The algorithm is 6–10 times faster than previous core-pricing methods, such as those proposed by Day & Raghavan. In practice, it required only ~3.1 times the number of oracle calls as VCG, and its total running time was roughly 7.5 times that of VCG—well within the acceptable threshold for real-time deployment.
  • Fairness: While VCG is often considered the benchmark for fairness, our core-pricing algorithm significantly outperformed GSP variants in terms of utility distribution among winning bidders.

Conclusion

By achieving near-linear query complexity, the water-filling algorithm makes core-selecting auctions a viable reality for high-speed, combinatorial advertising markets. While core-selecting auctions do not guarantee the same dominant-strategy truthfulness as VCG, their revenue benefits and computational feasibility make them a compelling choice for modern ad platforms. Future work may extend this framework to even more complex, high-stakes environments, such as video ad auctions.

Summary updated

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) 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.
BibTeX
@inproceedings{hartline2016finding,
  author = {Jason D. Hartline and Nicole Immorlica and Brendan Lucier and Rad Niazadeh},
  title = {{Finding Bidder-Optimal Core Points Quickly}},
  booktitle = {Oper. Res},
  year = {2016},
  url = {https://openreview.net/forum?id=I5xxhhm7OIo},
}
Figure