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