Computer Science – Computer Science and Game Theory
Scientific paper
2011-07-08
Computer Science
Computer Science and Game Theory
Twenty Six Pages, Two Figures, Six Theorems. Initial Version Published in Workshop on Web and Databases 2008
Scientific paper
Traditionally the probabilistic ranking principle is used to rank the search results while the ranking based on expected profits is 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 a unified click models for both ranked ads and search results. The segregated view of document and ad rankings does not consider this commonality. Further, the used models consider parameters of (i) probability of the user abandoning browsing results (ii) perceived relevance of result snippets. But how to consider them for improved ranking is unknown currently. 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. To exploit its generality, we examine the reduced forms of CE ranking under different assumptions enumerating a hierarchy of ranking functions. Some of the rankings in the hierarchy are currently used ad and document ranking functions; while others suggest new rankings. 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 pricing mechanism with the proposed ranking. Our analysis proves several desirable properties including revenue dominance over 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. Further, 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 that a constant time approximation is unlikely.
Balakrishnan Raju
Kambhampati Subbarao
No associations
LandOfFree
Click Efficiency: A Unified Optimal Ranking for Online Ads and Documents does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Click Efficiency: A Unified Optimal Ranking for Online Ads and Documents, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Click Efficiency: A Unified Optimal Ranking for Online Ads and Documents will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-222487