Algorithms and incentives for robust ranking
Published 7 January 2007
Rajat Bhattacharjee, Ashish Goel
Citations24
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper makes a case for sharing with users the revenue generated by ranking and reputation systems as incentive to provide useful feedback and presents an incentive based ranking scheme in a realistic model of user behavior which addresses the above problems.
Abstract
Spam in the form of link spam and click spam has become a major obstacle in the effective functioning of ranking and reputation systems. Even in the absence of spam, difficulty in eliciting feedback and self-reinforcing nature of ranking systems are known problems. In this paper, we make a case for sharing with users the revenue generated by such systems as incentive to provide useful feedback and present an incentive based ranking scheme in a realistic model of user behavior which addresses the above problems. We give an explicit ranking algorithm based on user feedback. Our incentive structure and ranking algorithm ensure that there is a profitable arbitrage opportunity for the users of the system in correcting the inaccuracies of the ranking. The system is oblivious to the source of inaccuracies (benign or
Keywords
Computer ScienceDecision Sciences
The PageRank Citation Ranking : Bringing Order to the Web
12,645 Citations1999Lawrence M. Page, Sergey Brin +2 more
This paper describes PageRank, a mathod for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them, and shows how to efficiently compute PageRank for large numbers of pages.
IEEE Transactions on Knowledge and Data EngineeringToward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions
10,115 Citations2005Gediminas Adomavičius, Alexander Tuzhilin
This paper presents an overview of the field of recommender systems and describes the current generation of recommendation methods that are usually classified into the following three main categories: content-based, collaborative, and hybrid recommendation approaches.
Journal of the ACMAuthoritative sources in a hyperlinked environment
9,060 Citations1999Jon Kleinberg
This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.
Journal of the American Statistical AssociationInequalities: Theory of Majorization and its Applications.
4,984 Citations1981Barry C. Arnold, Albert W. Marshall +1 more
Communications of the ACMReputation systems
2,153 Citations2000Paul Resnick, Ko Kuwabara +2 more
Systems T he Internet offers vast new opportunities to interact with total strangers, but these interactions can be fun, informative, even profitable, but they also involve risk.
Europhysics Letters (EPL)Competition and multiscaling in evolving networks
1,056 Citations2001Ginestra Bianconi, Albert-Ĺaszló Barabási
This work finds that competition for links translates into multiscaling, i.e. a fitness-dependent dynamic exponent, allowing fitter nodes to overcome the more connected but less fit ones.
Journal of the ACMMulticommodity max-flow min-cut theorems and their use in designing approximation algorithms
813 Citations1999Tom Leighton, Satish Rao
This paper establishes max-flow min-cut theorems for several important classes of multicommodity flow problems and uses the result to design the first polynomial-time (polylog n-times-optimal) approximation algorithms for well-known NP-hard optimization problems.
Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior
660 Citations2000Chrysanthos Dellarocas
A set of mechanisms are proposed, which eliminate, or significantly reduce the negative effects of such fraudulent behavior, and can be easily integrated into existing online reputation systems in order to safeguard their reliability in the presence of potentially deceitful buyers and sellers.
SSRN Electronic JournalThe Digitization of Word-of-Mouth: Promise and Challenges of Online Feedback Mechanisms
618 Citations2003Chrysanthos Dellarocas
Online feedback mechanisms harness the bi-directional communication capabilities of the Internet in order to engineer large-scale word-of-mouth networks and are poised to have a much wider impact on organizations.
Journal of Economics & Management StrategyThe Social Cost of Cheap Pseudonyms
547 Citations2001Eric J. Friedman, Paul Resnick
Management ScienceEliciting Informative Feedback: The Peer-Prediction Method
528 Citations2005Nolan Miller, Paul Resnick +1 more
A scoring system is devised that induces honest reporting of feedback and proves to be a Nash equilibrium, which can be scaled to induce appropriate effort by raters and can be extended to handle sequential interaction and continuous signals.
Information Systems FrontiersCombinatorial Information Market Design
486 Citations2003Robin Hanson
This work introduces market scoring rules, and considers several design issues, including how to represent variables to support both conditional and unconditional estimates, how to avoid becoming a money pump via errors in calculating probabilities, and how to ensure that users can cover their bets, without needlessly preventing them from using previous bets as collateral for future bets.
Impact of search engines on page popularity
285 Citations2004Junghoo Cho, Sourashis Roy
This paper analytically estimates how much longer it takes for a new page to attract a large number of Web users when search engines return only popular pages at the top of search results and shows that search engines can have an immensely worrisome impact on the discovery of new Web pages.
Link spam alliances
169 Citations2005Zoltán Gyöngyi, Héctor García-Molina
This paper studies how web pages can be interconnected in a spam farm in order to optimize rankings and shows that alliances can be synergistic and improve the rankings of all participants.
Duplicate detection in click streams
137 Citations2005Ahmed Metwally, Divyakant Agrawal +1 more
The problem of finding duplicates in data streams is considered, and a solution based on Bloom Filters is developed, demonstrating that the proposed solution yields extremely low error rates.
Page quality
128 Citations2005Junghoo Cho, Sourashis Roy +1 more
The proposed quality estimator has the potential to alleviate the rich-get-richer phenomenon and help new and high-quality pages get the attention that they deserve and is derived through a careful analysis of a reasonable web user model.
Lecture notes in computer scienceMaking Eigenvector-Based Reputation Systems Robust to Collusion
112 Citations2004Hui Zhang, Ashish Goel +3 more
The efficacy of, and countermeasures for, collusions designed to improve user rating in eigenvector based systems and Google’s PageRank algorithm for rating web pages are studied.
ComputerSpam: it's not just for inboxes anymore
88 Citations2005Zoltán Gyöngyi, Héctor García-Molina
E-mail spam is a nuisance that every user has come to expect, but Web spammers prey on unsuspecting users and undermine search engines by subverting search results to increase the visibility of their pages.
Avoiding ballot stuffing in eBay-like reputation systems
86 Citations2005Rajat Bhattacharjee, Ashish Goel
A simplified model is used to give an explicit relation between the reputation premium and the transaction cost that needs to hold in order to avoid ballot stuffing and bad mouthing and draws attention to the necessity of transaction costs for a well functioning reputation system.
Computer NetworksOn the security of pay-per-click and other Web advertising schemes
72 Citations1999Vinod Anupam, Alain Mayer +3 more
A hit inflation attack on pay-per-click Web advertising schemes is presented, which is virtually impossible for the program provider to detect conclusively, regardless of whether the provider is a third-party ‘ad network’ or the target of the click itself.
Evolution of page popularity under random web graph models
13 Citations2006Rajeev Motwani, Ying Xu
The preferential attachment model is extended with page quality, where the probability of a page getting new links depends not only on its current degree but also on its quality, and it is proved that under discrete quality distributions, the degree sequence still follows a power law distribution.