Generalized Second Price Auction with Probabilistic Broad Match

Wei Chen, Di He, Tie-Yan Liu, Tao Qin, Yixin Tao, Liwei Wang

Abstract

Generalized Second Price (GSP) auctions are the industry standard for selling ad slots in search engines. While search engines typically employ "broad match" to connect queries with relevant bid keywords, the standard mechanism (SBM-GSP) suffers from significant theoretical drawbacks, including poor social welfare guarantees and a lack of robust analysis for multi-slot or Bayesian settings. This paper introduces the Probabilistic Broad-Match (PBM) mechanism. Unlike the standard approach of pooling all matching ads, PBM-GSP randomly samples a single keyword according to a predefined distribution and conducts the auction solely among ads bidding on that keyword. Our theoretical analysis demonstrates that PBM-GSP provides superior social welfare and revenue guarantees compared to SBM-GSP, particularly in complex, multi-slot environments.

Introduction

In the multi-billion dollar online advertising market, search engines must efficiently map user queries to advertiser bids. Because the space of possible queries is virtually infinite, advertisers bid on "keywords" rather than specific queries. A "broad match" system then bridges the gap, allowing a bid on "running shoes" to apply to a query for "marathon footwear."

Currently, most search engines use Standard Broad-Match GSP (SBM-GSP), which aggregates all advertisers whose keywords match a query into a single auction. However, this pooling mechanism introduces significant inefficiencies. The "Price of Anarchy"—a measure of how much social welfare is lost due to selfish bidding—can grow quadratically with the diversity of advertiser valuations in SBM-GSP. Furthermore, the theoretical properties of SBM-GSP are largely unknown for multi-slot auctions or settings with incomplete information (Bayesian settings).

The Probabilistic Broad-Match (PBM) Mechanism

To address these limitations, we propose Probabilistic Broad-Match (PBM-GSP). The mechanism shifts the complexity of the match from the auction itself to a pre-auction sampling step:

  1. Probabilistic Sampling: When a query is issued, the system selects exactly one keyword from the set of all keywords matching that query, based on a predefined probability distribution.
  2. Isolated Auction: The system then runs a standard GSP auction involving only the advertisers who placed bids on that specific sampled keyword.

By decoupling the queries through sampling, PBM-GSP prevents the "valuation mixing" that occurs in SBM-GSP. This isolation makes the auction more predictable for advertisers and easier to analyze theoretically.

Theoretical Framework and Metrics

To evaluate PBM-GSP, we introduce a new metric: Keyword-Level (KL) expressiveness (denoted as $\beta$). This metric quantifies how effectively a limited set of keywords can represent an advertiser's true valuation across various queries.

Using the smoothness framework from algorithmic game theory, we analyzed the Price of Anarchy for PBM-GSP. A critical finding is the difference in scaling: while the efficiency loss in SBM-GSP scales quadratically ($\\Theta(c^2)$) relative to valuation diversity ($c$), PBM-GSP scales linearly ($O(c)$). This suggests that PBM-GSP is significantly more robust in markets where advertiser valuations vary widely.

Key Results

Our study provides the first comprehensive theoretical map for broad-match mechanisms in multi-slot and Bayesian settings:

  • Social Welfare: In multi-slot Bayesian settings, we proved that the efficiency loss is bounded by approximately $e \cdot c \cdot \frac{\beta+1}{\beta}$. In simpler single-slot cases, this bound improves to $c/\beta$. Under most realistic conditions, PBM-GSP yields higher social welfare than the standard SBM-GSP.
  • Revenue Guarantees: We established that PBM-GSP can guarantee a specific fraction of the optimal social welfare as revenue. In Bayesian settings with a Myerson reserve price, the revenue is at least $\frac{\beta}{1+\beta} \cdot \frac{1}{2\eta(ce)^2}$ of the optimal social welfare.
  • Computational Efficiency: We demonstrated that our KL-expressiveness metric can be computed in linear time. This is a significant improvement over previous metrics like QL-expressiveness, which are NP-Hard to calculate, making PBM-GSP more practical for real-world implementation.

Empirical Validation

While the focus of the work is theoretical, we validated the underlying assumptions using commercial search engine logs. By analyzing a one-week snapshot of query-keyword graphs and advertiser bids, and simulating 1,000 "micro-markets" (e.g., clusters for "travel" or "insurance"), we confirmed that the KL-expressiveness metric accurately reflects market dynamics and that the conditions required for PBM-GSP's superiority are commonly met in practice.

Conclusion

PBM-GSP represents a significant step forward in the design of ad auctions. By replacing the complex pooling of SBM-GSP with a simpler probabilistic sampling step, we provide search engines with a mechanism that is not only more theoretically sound but also more efficient in terms of social welfare and revenue. Future research will focus on dynamically optimizing the sampling probabilities to further maximize market performance and exploring the practical transition costs for advertisers moving to a sampling-based system.

Summary updated

Abstract

Generalized Second Price (GSP) auctions are widely used by search engines today to sell their ad slots. Most search engines have supported broad match between queries and bid keywords when executing GSP auctions, however, it has been revealed that GSP auction with the standard broad-match mechanism they are currently using (denoted as SBM-GSP) has several theoretical drawbacks (e.g., its theoretical properties are known only for the single-slot case and full-information setting, and even in this simple setting, the corresponding worst-case social welfare can be rather bad). To address this issue, we propose a novel broad-match mechanism, which we call the Probabilistic Broad-Match (PBM) mechanism. Different from SBM that puts together the ads bidding on all the keywords matched to a given query for the GSP auction, the GSP with PBM (denoted as PBM-GSP) randomly samples a keyword according to a predefined probability distribution and only runs the GSP auction for the ads bidding on this sampled keyword. We perform a comprehensive study on the theoretical properties of the PBM-GSP. Specifically, we study its social welfare in the worst equilibrium, in both full-information and Bayesian settings. The results show that PBM-GSP can generate larger welfare than SBM-GSP under mild conditions. Furthermore, we also study the revenue guarantee for PBM-GSP in Bayesian setting. To the best of our knowledge, this is the first work on broad-match mechanisms for GSP that goes beyond the single-slot case and the full-information setting.
BibTeX
@inproceedings{chen2014generalized,
  author = {Wei Chen and Di He and Tie-Yan Liu and Tao Qin and Yixin Tao and Liwei Wang},
  title = {{Generalized Second Price Auction with Probabilistic Broad Match}},
  booktitle = {EC},
  year = {2014},
  doi = {10.1145/2600057.2602828},
}

Loading related content...

Figure