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

摘要

Ranking of search results and ads has traditionally been studied separately. The probability ranking principle is commonly used to rank the search results while the ranking based on expected profits is commonly used for paid placement of ads. These rankings try to maximize the expected utilities based on the user click models. Recent empirical analysis on search engine logs suggests unified click models for both ranked ads and search results (documents). These new models consider parameters of (i) probability of the user abandoning browsing results (ii) perceived relevance of result snippets. However, current document and ad ranking methods do not consider these parameters. In this paper we propose a generalized ranking function—namely Click Efficiency (CE)—for documents and ads based on empirically proven user click models. The ranking considers parameters (i) and (ii) above, optimal and has the same time complexity as sorting. Furthermore, the CE ranking exploits the commonality of click models, hence is applicable for both documents and ads. We examine the reduced forms of CE ranking based upon different underlying assumptions, enumerating a hierarchy of ranking functions. Interestingly, some of the rankings in the hierarchy are currently used ad and document ranking functions; while others suggest new rankings. Thus, this hierarchy illustrates the relationships between different rankings, and clarifies the underlying assumptions. While optimality of ranking is sufficient for document ranking, applying CE ranking to ad auctions requires an appropriate pricing mechanism. We incorporate a second price based mechanism with the proposed ranking. Our analysis proves several desirable properties including revenue dominance over Vickrey Clarke Groves (VCG) for the same bid vector and existence of a Nash equilibrium in pure strategies. The equilibrium is socially optimal, and revenue equivalent to the truthful VCG equilibrium. As a result of its generality, the auction mechanism and the equilibrium reduces to the current mechanisms including Generalized Second Price Auction (GSP) and corresponding equilibria. Furthermore, we relax the independence assumption in CE ranking and analyze the diversity ranking problem. We show that optimal diversity ranking is NP-Hard in general, and a constant time approximation algorithm is not likely. Finally our simulations to quantify the amount of increase in different utility functions conform to the results, and suggest potentially significant increase in utilities.