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