A Faster Algorithm for Bidder-Optimal Core Points

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

Abstract

In complex combinatorial markets with complementary valuations, truthful auctions can yield low revenue. Core-selecting auctions attempt to 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 expensive convex programs. Our main result is a combinatorial algorithm that finds an approximate bidder-optimal core point in a quasi-linear number of calls to the welfare maximization oracle.

Introduction: The Complexity of Modern Ad Auctions

Traditional search auctions, such as those for simple text links, typically rank ads in a straightforward list. However, modern digital advertising has evolved to include "rich" ads with varying shapes, sizes, and decorations like site links or images. This evolution transforms the auction into a complex combinatorial problem characterized by complementarities: displaying one large ad might prevent two smaller ads from appearing, even if the combined value of the smaller ads exceeds that of the single large one.

In these settings, the standard Vickrey-Clarke-Groves (VCG) auction—long considered the gold standard for truthful bidding—often fails. It can result in "unacceptably low revenue" and outcomes that appear unfair to losing bidders who were willing to pay significantly more than the winners. Core-selecting auctions offer a solution by ensuring that no group of bidders, including the auctioneer, can find a better outcome for themselves by renegotiating. The primary challenge is that finding these "core" prices is computationally expensive, often requiring complex linear or convex programming that is too slow for real-time advertising environments where decisions must be made in milliseconds.

The Water-Filling Algorithm

This research introduces a new "water-filling" algorithm designed to find an approximate bidder-optimal core point with high efficiency. The algorithm is built on a geometric intuition: it treats the bidders' utilities as containers and the core as a polytope.

Starting from a "pay-your-bid" state where all bidders have zero utility, the algorithm "pours water" into these containers, increasing the utilities of a subset of bidders uniformly. As utilities increase, the algorithm eventually hits a "facet" of the core polytope—a point where increasing a bidder's utility further would violate a core constraint, allowing a coalition of other bidders to "block" the outcome.

To navigate this space, the algorithm relies on a Winner Determination Oracle (WIN-ORAC). Rather than solving the entire pricing problem at once, it makes a series of probes to this oracle using truncated bids. By utilizing binary search to identify exactly when a constraint becomes "tight," the algorithm requires only $O(n \log(n/\epsilon))$ calls to the oracle. This quasi-linear complexity represents a massive improvement over previous cutting-plane or heuristic methods.

Empirical Evaluation and Key Results

The researchers evaluated the algorithm using a massive real-world dataset consisting of approximately 20,000 auctions sampled from Microsoft Bing in January 2018. Each auction involved up to 23 advertisers with configurations ranging from 3 to 14 lines of ad space. The algorithm was benchmarked against VCG, variants of the Generalized Second Price (GSP) auction, and several state-of-the-art core-pricing rules.

Performance Highlights:

  • Revenue Generation: The algorithm generated 26% more revenue than VCG on average and approximately 9% more revenue than other known core-pricing rules. It nearly matched the revenue of the standard GSP auction while maintaining better economic properties.
  • Computational Speed: In numerical experiments, the water-filling rule was 6–10 times faster than previous core-pricing methods. It proved to be only about 3x slower than VCG in terms of oracle calls, making it a viable candidate for production systems.
  • Stability: The algorithm demonstrated significantly better stability than interior-point methods, which were found to be highly sensitive to precision parameters in practice.

Economic Insights

The study confirms that complementarity is a salient feature of modern ad space. The "knapsack" nature of fitting ads into fixed line limits is why VCG revenue is often low; the "externality" a bidder imposes on others is frequently small compared to their actual value. By viewing the core as a geometric polytope, the authors realized they could "walk" the boundary of the core without needing to define all exponential constraints upfront.

While the mechanism is not "dominant-strategy truthful"—meaning bidders may have incentives to shade their bids—the authors argue it possesses a natural full-information Nash equilibrium that remains welfare-optimal. This makes it a robust "middle ground" for complex combinatorial markets.

Future Directions

Future work may explore whether this path-based approach can be adapted to optimize for specific global objectives, such as minimizing the distance to VCG prices. Additionally, while this study uses bids as a proxy for true values, further research is needed to model how sophisticated, learning-based bidders might adapt their strategies to this pricing rule over time. Beyond search auctions, these techniques could potentially be applied to other complex markets, such as auctions for video advertisements.

Summary updated

Abstract

In complex combinatorial markets with complementary valuations, truthful auctions can yield low revenue. Core-selecting auctions attempt to 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 expensive convex programs. Our main result is a combinatorial algorithm that finds an approximate bidder-optimal core point in a quasi-linear number of calls to the welfare maximization oracle.
BibTeX
@inproceedings{hartline2016faster,
  author = {Jason D. Hartline and Nicole Immorlica and Brendan Lucier and Rad Niazadeh},
  title = {{A Faster Algorithm for Bidder-Optimal Core Points}},
  booktitle = {Oper. Res},
  year = {2016},
  url = {https://openreview.net/forum?id=I5xxhhm7OIo},
}
Figure