Click efficiency: a unified optimal ranking for online Ads and documents

Raju Balakrishnan, Subbarao KambhampatiJ. Intell. Inf. Syst 2016 · DOI

TL;DR

This paper introduces "Click Efficiency" (CE), a unified ranking framework for both online advertisements and search results. By modeling user behavior with a generalized click model that accounts for abandonment and perceived relevance, CE offers an optimal ranking strategy that unifies existing approaches and suggests new ones, with significant implications for ad auctions and search engine revenue.

What Problem Does This Paper Address?

Traditionally, ranking search results and online advertisements have been treated as separate problems. Search results are ranked based on relevance (e.g., Probability Ranking Principle), aiming to maximize user satisfaction. Online ads, on the other hand, are ranked to maximize profit, often using expected profit (bid * Click-Through Rate). This segregation overlooks the common underlying user behavior: users browse ranked lists from top to bottom, and their decision to click or abandon is influenced by perceived relevance and the likelihood of giving up. Recent research suggests a unified click model for both scenarios, but existing ranking functions don't fully leverage this commonality or incorporate crucial parameters like abandonment probability and perceived relevance in a unified, optimal way. This paper aims to bridge this gap by proposing a generalized ranking function that can optimally handle both document and ad ranking, considering these key user behavior aspects.

Methods

The core of this paper is the introduction of Click Efficiency (CE), a unified optimal ranking function. CE is derived from a generalized click model that incorporates three key parameters:

  1. Click Probability (C(e)): The perceived relevance of an entity (document snippet or ad impression).
  2. Abandonment Probability (γ(e)): The probability a user will stop browsing the list after viewing an entity.
  3. Utility (U(e)): The value of an entity, which can be relevance for documents or cost-per-click (CPC) for ads.

The CE ranking function is defined as the ratio of an entity's utility to the sum of its click and abandonment probabilities: $CE(e) = \frac{U(e)C(e)}{C(e) + \gamma(e)}$. The paper proves that ranking entities in descending order of CE maximizes the expected utility.

To demonstrate the generality of CE, the authors derive a taxonomy of ranking functions by substituting different utilities and making assumptions about the parameters. This taxonomy shows how CE reduces to existing ranking functions (like PRP for documents and GSP for ads) under specific conditions and also suggests new optimal rankings.

For ad auctions, CE ranking is combined with a second-price based pricing mechanism. The authors analyze the properties of this mechanism, proving the existence of a Nash Equilibrium that is socially optimal and maximizes search engine profit. They also demonstrate revenue dominance over VCG for equivalent bid vectors.

Finally, the paper relaxes the assumption of parameter independence to analyze diversity ranking, showing that even basic formulations are NP-Hard, and constant-ratio approximation algorithms are unlikely.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unified User Behavior: The most significant insight is that user click behavior for search results and ads can be modeled using a single, generalized framework, allowing for a unified ranking approach.
  • Importance of Abandonment: Explicitly modeling user abandonment probability is crucial for optimal ranking, especially in longer lists, and existing methods often ignore this.
  • Perceived vs. Actual Relevance: The distinction between perceived relevance (what the user sees in a snippet) and actual relevance is vital, and the CE framework incorporates this.
  • CE as a General Framework: The CE ranking function acts as a unifying principle, encompassing many existing ranking strategies as special cases under specific assumptions. This provides a clear hierarchy and understanding of their underlying conditions.
  • Ad Auction Optimality: Combining CE ranking with a second-price auction leads to a mechanism that achieves simultaneous social optimality and search engine profit maximization, with desirable equilibrium properties.
  • Inherent Hardness of Diversity: The analysis of diversity ranking reveals that even simple versions of the problem are computationally intractable, suggesting fundamental challenges in optimizing for diversity.

Key Results

  • Optimal Ranking Function: The paper introduces the Click Efficiency (CE) ranking function, $CE(e) = \frac{U(e)C(e)}{C(e) + \gamma(e)}$, which is proven to yield optimal expected utility for ranked lists.
  • Ranking Taxonomy: A hierarchy of ranking functions is presented, showing how CE reduces to:
  • Sort by Relevance (PRP) for documents under assumptions of infinite patience or abandonment probability negatively proportional to relevance.
  • Ranking by Bid Amount for ads when abandonment is zero.
  • Ranking by Expected Profit for ads when abandonment is negatively proportional to CTR.
  • Ad Auction Mechanism: A generalized ad auction mechanism based on CE ranking and second-price auctions is proposed.
  • It guarantees a Nash Equilibrium that is socially optimal and maximizes search engine profit.
  • It demonstrates revenue dominance over VCG for equivalent bid vectors.
  • The equilibrium revenue is revenue equivalent to truthful VCG equilibrium.
  • Diversity Ranking Hardness: The paper proves that diversity ranking is NP-Hard, and even constant-ratio approximation algorithms are unlikely.

Limitations and Future Work

  • Parameter Independence Assumption: The core CE ranking assumes that the parameters (utility, click probability, abandonment probability) of an entity are independent of other entities in the list. While the paper explores the implications of relaxing this for diversity ranking, it acknowledges that this assumption might not always hold and leads to NP-Hardness.
  • Empirical Validation: While the paper presents theoretical results and connections to existing work, it mentions that simulation studies suggest significant improvement, but large-scale empirical validation on real click logs is suggested as future work.
  • Approximation Algorithms for Diversity: The paper proves the hardness of diversity ranking but leaves the formulation of approximation algorithms (beyond constant-ratio) for future research.
  • Learning and Prediction: Learning and prediction of abandonment probability from click logs and parametric learning are identified as interesting future research directions.
  • Extension to Other Scenarios: The authors suggest that the CE ranking framework could be extended to other web ranking scenarios with similar click models, such as product recommendations and friend recommendations.

Summary updated

BibTeX
@article{balakrishnan2016click,
  author = {Raju Balakrishnan and Subbarao Kambhampati},
  title = {{Click efficiency: a unified optimal ranking for online Ads and documents}},
  journal = {J. Intell. Inf. Syst.},
  year = {2016},
  doi = {10.1007/s10844-015-0366-3},
}
Figure