ITR: Axioms and Algorithms for Reputation

Stanford University, Stanford CA

Investigators

Abstract

The goal of this project is to design metrics of online reputation that are both robust to gaming agents and efficiently computable. This will be done through development of an axiomatic framework for reputation together with novel algorithms that make the framework useful. This work will be grounded in practical online reputation systems of contemporary interest, and issues arising in real systems will guide axiomatic and algorithmic developments. To navigate the complex web of information and agents on the Internet, society has increasingly come to rely on automated systems that assess reputation. Some prominent examples of such reputation systems are the PageRank mechanism used by the Google search engine, the feedback based rating scheme for the online auction site eBay, and the incentive scheme used by the popular file sharing system KaZaA. All these reputation systems are vulnerable to gaming by selfish agents trying to improve their own rating. Fundamentally, these reputation systems suffer from a misalignment between economic incentives of individual users and aggregate value to society. This research program will have a significant impact on several important problem domains such as ranking of web pages and blogs, online marketplaces, and peer-to-peer systems. Online services such as search engines and auction sites have become an important part of our national infrastructure and need to be protected against greedy or malicious tampering. This research will contribute to the robustness of such systems. Additionally, the purpose of reputation systems is to gather highly imperfect information from many sources, and to process it into a comprehensible prediction of outcomes (e.g., whether a vendor will be reliable). Certain national security needs could conceivably be met with variants of reputation systems. One of the great challenges of intelligence assessment is to determine what information is reliable and what is not. The proposed research should help in addressing this challenge. Elements of the research will be integrated into undergraduate and graduate courses on optimization, game theory, Markov chains, public policy, and Internet technology.