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

详细信息    查看全文

• 作者：Raju Balakrishnan ; Subbarao Kambhampati
• 刊名：Journal of Intelligent Information Systems
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：46
• 期：3
• 页码：531-562
• 全文大小：801 KB
• 刊物类别：Computer Science
• 刊物主题：Data Structures, Cryptology and Information Theory
  Artificial Intelligence and Robotics
  Document Preparation and Text Processing
  Business Information Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-7675
• 卷排序：46

文摘

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.KeywordsAd rankingDocument rankingDiversityAuctionsClick models