Generalized second price auction with probabilistic broad match

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

TL;DR

This paper introduces Probabilistic Broad-Match (PBM), a novel mechanism for Generalized Second Price (GSP) auctions that improves how search engines handle "broad match" queries. By randomly sampling a single keyword for each query rather than pooling all matched ads, PBM-GSP provides significantly better theoretical guarantees for social welfare and revenue compared to the standard industry approach.

What Problem Does This Paper Address?

In online advertising, search engines use Generalized Second Price (GSP) auctions to sell ad slots. Because users type billions of unique queries, advertisers cannot bid on every possible string. Instead, they use broad match, where a bid on a keyword (e.g., "shoes") can match many related queries (e.g., "running footwear").

The current industry standard, Standard Broad-Match (SBM-GSP), pools all ads that match a query and runs one big auction. However, this has a major theoretical flaw: it can lead to very poor social welfare (the total value generated for all parties). Specifically, the "Price of Anarchy" (a measure of efficiency loss in equilibrium) for SBM-GSP grows quadratically with the diversity of advertiser valuations. Furthermore, theoretical properties of SBM-GSP are poorly understood for multi-slot auctions or settings where advertisers have private, incomplete information (Bayesian settings).

Methods

The authors propose the Probabilistic Broad-Match (PBM-GSP) mechanism. Its core logic is simple but transformative:

  1. Probabilistic Sampling: When a user issues a query, the system doesn't pool every matching ad. Instead, it chooses one matching keyword based on a predefined probability distribution.
  2. Isolated Auction: It then runs a standard GSP auction using only the ads that specifically bid on that chosen keyword.

To analyze this, the authors introduce a new metric called Keyword-Level (KL) expressiveness ($\beta$), which measures how well a limited number of keywords can cover an advertiser's interests. They use the smoothness framework (a standard tool in algorithmic game theory) to prove upper bounds on the Price of Anarchy for both full-information and Bayesian settings.

Datasets

While primarily a theoretical paper, the authors validate their new expressiveness measure using:

  • Commercial Search Engine Logs: A one-week snapshot of query-keyword bipartite graphs and advertiser bid data.
  • Micro-market Simulations: They sampled 1,000 "micro-markets" (clusters of related keywords like "insurance" or "travel") to compare their new KL-expressiveness against older metrics.

Key Insights and Ideas

  • Decoupling Queries: By sampling a single keyword, PBM-GSP prevents the "mixing" of unrelated query valuations that plagues SBM-GSP. This keeps the auction "cleaner" and easier for advertisers to bid on truthfully.
  • Linear vs. Quadratic Scaling: The efficiency loss in SBM-GSP scales quadratically ($\Theta(c^2)$) with a "homogeneity" factor $c$ (representing valuation diversity). PBM-GSP improves this to a linear scaling ($O(c)$), making it much more robust in diverse markets.
  • Computational Efficiency: The authors show that their new KL-expressiveness metric can be computed in linear time, whereas the previous industry-standard metric (QL-expressiveness) is NP-Hard to calculate.
  • Revenue-Welfare Link: The paper proves that under certain conditions (Monotone Hazard Rate distributions), PBM-GSP can guarantee a specific fraction of the optimal social welfare as search engine revenue.

Key Results

The paper provides a comprehensive theoretical map of PBM-GSP performance (summarized in the paper's tables):

  • Social Welfare (Price of Anarchy): In the multi-slot Bayesian setting, the efficiency loss is bounded by approximately $e \cdot c \cdot \frac{\beta+1}{\beta}$. In simpler single-slot cases, this improves to $c/\beta$.
  • Revenue Guarantee: In Bayesian settings with a Myerson reserve price, PBM-GSP achieves a revenue of at least $\frac{\beta}{1+\beta} \cdot \frac{1}{2\eta(ce)^2}$ of the optimal social welfare (where $\eta$ is a distribution-specific constant).
  • Comparison: PBM-GSP consistently outperforms SBM-GSP in social welfare bounds under "mild conditions," particularly when the diversity of queries matched to a keyword is high.

Limitations and Future Work

  • Probability Tuning: The paper assumes the matching probabilities ($\pi_q(s)$) are predefined. A major area for future work is determining how to optimize these probabilities to maximize welfare or revenue dynamically.
  • Tightness of Bounds: While the authors provide upper bounds, they acknowledge that some bounds (especially for revenue) might be conservative and could be tightened in future research.
  • Transition Costs: The paper does not discuss the practical engineering overhead or the potential "voter frustration" of advertisers who might see their ads shown less frequently due to the sampling mechanism, even if the theoretical welfare is higher.

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 the broad match between queries and bid keywords when executing the GSP auctions, however, it has been revealed that the 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