Refine Predictions Ad Infinitum?

Mukund Sundararajan, Inbal Talgam-CohenarXiv 2013 · OpenReview

TL;DR

This paper investigates how improving the accuracy of predicting ad relevance (click-through rates) impacts sponsored search auctions. The authors demonstrate that for mechanisms balancing revenue and efficiency, better predictions always improve performance, giving search engines a clear incentive to refine their prediction models. Under specific conditions, these refinements also improve market efficiency.

What Problem Does This Paper Address?

Sponsored search, like Google Ads or Bing Ads, is a massive market where search engines sell ad slots to advertisers. The core challenge for search engines is to maximize both revenue (from advertisers) and efficiency (by showing users the most relevant ads). This involves two key pieces of information: the advertiser's willingness to pay per click, and the predicted relevance of their ad for a given query (click-through rate, or CTR). While advertisers' bids are elicited through auctions, predicting relevance is a machine learning problem. The paper asks: what happens to auction performance (revenue and efficiency) as the accuracy of these relevance predictions improves? Does refining these predictions always help, or can it sometimes hurt?

Methods

The authors model sponsored search auctions using a standard framework, focusing on "Pareto optimal mechanisms" that optimize a convex combination of expected welfare (efficiency) and expected revenue. They introduce the concept of "prediction schemes," which are essentially ways of categorizing query-advertiser pairs to predict relevance. A "refinement" of a prediction scheme means using more granular categories, leading to potentially more accurate predictions. A key technical contribution is defining and analyzing "flip-spread refinements," a specific type of refinement where the relative relevances of advertisers either become more distinct or flip entirely. They then analyze how these refinements affect the ranking of advertisers by their "virtual values" (used for revenue optimization) versus their "realized values" (used for efficiency).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses examples to illustrate its points, rather than empirical evaluation on real-world datasets.

Key Insights and Ideas

  • No Disincentive to Refine: Search engines have no reason not to improve their relevance predictions, as it will always improve their chosen balance of revenue and efficiency. This is a strong practical takeaway.
  • Efficiency Gains Under Conditions: While refinements always help the revenue-efficiency trade-off, they only guarantee improvements in efficiency under specific assumptions, notably the "flip-spread" condition. This condition ensures that refinements don't make advertisers artificially more similar in a way that distorts rankings.
  • Ranking Convergence: Refinements tend to make the ranking of advertisers for revenue optimization (virtual value) converge towards the ranking for efficiency (realized value), especially under the flip-spread condition.
  • Signaling Connection: The problem of relevance prediction refinement is framed as a form of "signaling" in economics, where the seller (search engine) has private information (features of the query) that influences the value of the items (ads).

Key Results

  • Theorem 4.1: For any Pareto optimal mechanism, refining a prediction scheme always improves the mechanism's objective (the weighted sum of revenue and efficiency) in expectation. This holds without strong assumptions on value distributions or the nature of the refinement.
  • Theorem 3.1: Under i.i.d. and MHR (Monotone Hazard Rate) assumptions on advertiser values, and for "flip-spread" refinements, improving relevance predictions always increases market welfare (efficiency).
  • Examples: The paper provides examples demonstrating that non-flip-spread refinements can, in some cases, reduce efficiency, highlighting the importance of the flip-spread assumption for guaranteed efficiency gains.

Limitations and Future Work

  • Multiplicative Assumption: The core results rely on the assumption that seller information (relevance) affects realized values multiplicatively. Generalizing to additive or other forms of interaction is an open question.
  • Flip-Spread Generalization: The "flip-spread" condition is crucial for guaranteed efficiency gains. Exploring more general notions of refinement that might still lead to efficiency improvements is a direction for future work.
  • Other Mechanisms: The paper focuses on Pareto optimal mechanisms. Investigating whether other types of mechanisms also benefit from refinements, or under what conditions, is an open question.
  • Non-i.i.d. and Non-MHR: While Theorem 4.1 is robust, Theorem 3.1's efficiency guarantees require specific assumptions about value distributions. Exploring these guarantees under weaker assumptions is a natural extension.

Summary updated

Abstract

We study how standard auction objectives in sponsored search markets change with refinements in the prediction of the relevance (click-through rates) of ads. We study mechanisms that optimize for a convex combination of efficiency and revenue. We show that the objective function of such a mechanism can only improve with refined (improved) relevance predictions, i.e., the search engine has no disincentive to perform these refinements. More interestingly, we show that under assumptions, refinements to relevance predictions can only improve the efficiency of any such mechanism. Our main technical contribution is to study how relevance refinements affect the similarity between ranking by virtual-value (revenue ranking) and ranking by value (efficiency ranking). Finally, we discuss implications of our results to the literature on signaling.
BibTeX
@misc{sundararajan2013refine,
  author = {Mukund Sundararajan and Inbal Talgam-Cohen},
  title = {{Refine Predictions Ad Infinitum?}},
  year = {2013},
  eprint = {1302.6700},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1302.6700},
}
Figure