Thinking Twice about Second-Price Ad Auctions

Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, C. Thach NguyenarXiv 2008 · arXiv

Abstract

Theoretical research on ad auctions often assumes a "first-price" model where winners pay their exact bid. However, real-world search engines predominantly use "second-price" mechanisms, such as the Generalized Second Price (GSP) auction. This paper demonstrates that this shift from theory to practice significantly increases algorithmic complexity, transforming a solvable matching problem into one that is NP-hard to even approximate. To address this, the authors propose a novel randomized algorithm, RankingSimulate, which achieves a 5.083 competitive ratio for online auctions, bridging the gap between theoretical models and industry reality.

Introduction: The Second-Price Headache

In sponsored search, engines must allocate ad slots to maximize revenue. While the "Adwords problem" has been extensively studied under the first-price auction model (pay-as-you-bid), the industry standard is the Generalized Second Price (GSP) auction. In a GSP auction, the winner pays the bid of the next-highest bidder.

This creates a fundamental dependency: to generate revenue, a search engine needs at least two interested bidders. If a keyword attracts only one bidder, the "second price" is zero, and no revenue is collected despite the bidder's high valuation. The authors formalize this as the Second-Price Ad Auctions (2PAA) problem and its simplified 0-1 version, Second-Price Matching (2PM).

Illustration of second-price matching scenarios and the impact of bidder selection on revenue.

Complexity and Hardness

The transition to second-price auctions introduces extreme computational hardness. The paper proves that for the general 2PAA problem, it is NP-hard to approximate the optimal revenue to any factor better than $m/R_{min}$ (where $m$ is the keyword count). This suggests that the problem is practically impossible to solve optimally in polynomial time.

Furthermore, in the online setting—where keywords arrive sequentially—the authors demonstrate that no deterministic algorithm can achieve a constant competitive ratio. An adversary can always construct a sequence that forces a fixed strategy to exhaust critical bidders, leading to zero revenue in subsequent steps.

Algorithmic Solutions

The paper explores both offline and online scenarios with new algorithmic frameworks:

  1. ReverseMatch (Offline): For the 0-1 matching case (2PM), this algorithm first identifies a standard maximum matching. It then processes keywords in the reverse order of their arrival to ensure that every "winner" is paired with a "second-price" partner, achieving a 2-approximation.
  2. RankingSimulate (Online): This randomized algorithm is the paper's primary contribution. It adapts the classic "Ranking" algorithm for bipartite matching by maintaining two distinct sets of bidders: "matched" and "reserved." By using a random permutation to decide which bidders are paired as the price-setters for incoming keywords, it maintains a stable competitive ratio of 5.083.

Key Insights

  • The "Second Bidder" Constraint: A bidder's value is capped not just by their own budget, but by the bid of the person behind them. This coupling makes the optimization landscape much more fragile than first-price models.
  • Budget Sensitivity: In second-price auctions, a minor budget reduction for a "second-price" bidder can cause the revenue from a "first-price" winner to drop to zero across multiple keywords, a phenomenon not seen in first-price auctions.
  • Robustness of Randomization: The success of RankingSimulate shows that randomizing the "reservation" of bidders can effectively mitigate the risks posed by adversarial keyword sequences.

Conclusion and Future Directions

While the 5.083 competitive ratio is a significant breakthrough compared to previous bounds (which were effectively infinite), a gap remains. Theoretical lower bounds suggest that no randomized online algorithm can do better than a ratio of 2. Future work involves refining the analysis of RankingSimulate or developing new algorithms to approach this theoretical limit. Additionally, extending these approximation techniques to multi-slot GSP auctions remains a critical open challenge for the field.

Summary updated

Abstract

Recent work has addressed the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions so as to maximize revenue, most of which assume that pricing is done via a first-price auction. This does not realistically model the Generalized Second Price (GSP) auction used in practice, in which bidders pay the next-highest bid for keywords that they are allocated. Towards the goal of more realistically modeling these auctions, we introduce the Second-Price Ad Auctions problem, in which bidders' payments are determined by the GSP mechanism. We show that the complexity of the Second-Price Ad Auctions problem is quite different than that of the more studied First-Price Ad Auctions problem. First, unlike the first-price variant, for which small constant-factor approximations are known, it is NP-hard to approximate the Second-Price Ad Auctions problem to any non-trivial factor, even when the bids are small compared to the budgets. Second, this discrepancy extends even to the 0-1 special case that we call the Second-Price Matching problem (2PM). Offline 2PM is APX-hard, and for online 2PM there is no deterministic algorithm achieving a non-trivial competitive ratio and no randomized algorithm achieving a competitive ratio better than 2. This contrasts with the results for the analogous special case in the first-price model, the standard bipartite matching problem, which is solvable in polynomial time and which has deterministic and randomized online algorithms achieving better competitive ratios. On the positive side, we provide a 2-approximation for offline 2PM and a 5.083-competitive randomized algorithm for online 2PM. The latter result makes use of a new generalization of a result on the performance of the "Ranking" algorithm for online bipartite matching.
BibTeX
@misc{azar2008thinking,
  author = {Yossi Azar and Benjamin E. Birnbaum and Anna R. Karlin and C. Thach Nguyen},
  title = {{Thinking Twice about Second-Price Ad Auctions}},
  year = {2008},
  eprint = {0809.1895},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0809.1895},
}
Figure