Algorithms and incentives for robust ranking

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 malicious), thus making it robust to spam as well as the problems of eliciting feedback and self-reinforcement.

REFERENCES

• 1: Gediminas Adomavicius , Alexander Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.734-749, June 2005 [doi>10.1109/TKDE.2005.99]
• 2: Vinod Anupam , Alain Mayer , Kobbi Nissim , Benny Pinkas , Michael K. Reiter, On the security of pay-per-click and other Web advertising schemes, Proceedings of the eighth international conference on World Wide Web, p.1091-1100, May 1999, Toronto, Canada
• 3: Rajat Bhattacharjee , Ashish Goel, Avoiding ballot stuffing in eBay-like reputation systems, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080203]
• 4: R. Bhattacharjee, A. Goel. Incentive based ranking mechanisms. First workshop on the economics of networked systems, June 2006.
• 5: G. Bianconi, A-L. Barbasi. Competition and multiscaling in evolving networks. Europhysics letters, 54(4), 436--442, 2001
• 6: G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev. Ser. A, vol. 5 pp. 147--151, 1946.
• 7: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 8: Junghoo Cho , Sourashis Roy, Impact of search engines on page popularity, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988676]
• 9: Junghoo Cho , Sourashis Roy , Robert E. Adams, Page quality: in search of an unbiased web ranking, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066220]
• 10: Chrysanthos Dellarocas, Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior, Proceedings of the 2nd ACM conference on Electronic commerce, p.150-157, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352889]
• 11: Chrysanthos Dellarocas, The Digitization of Word of Mouth: Promise and Challenges of Online Feedback Mechanisms, Management Science, v.49 n.10, p.1407-1424, October 2003 [doi>10.1287/mnsc.49.10.1407.17308]
• 12: L. Dumalge, I. Halperin. On a theorem of Frobenius-König and J. von Neumann's game of hide and seek. Trans. Roy. Soc. Canada III(3), vol. 49, pp. 23--29, 1955.
• 13: E. Friedman, P. Resnick. The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 10(2):173--199. 2001.
• 14: Zoltán Gyöngyi , Hector Garcia-Molina, Link spam alliances, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: Zoltan Gyongi , Hector Garcia-Molina, Spam: It's Not Just for Inboxes Anymore, Computer, v.38 n.10, p.28-34, October 2005 [doi>10.1109/MC.2005.352]
• 16: Robin Hanson, Combinatorial Information Market Design, Information Systems Frontiers, v.5 n.1, p.107-119, January 2003 [doi>10.1023/A:1022058209073]
• 17: G. H. Hardy, J. E. Littlewood, G. Pólya. Inequalities. 2nd edition, 1952, Cambridge University Press, London.
• 18: http://www.amazon.com
• 19: http://www.google.com
• 20: http://www.yahoo.com
• 21: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 22: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 23: A. W. Marshall, I. Olkin. Inequalities: Theory of Majorization and Its Applications, 1979, Academic Press, New York.
• 24: Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Duplicate detection in click streams, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060753]
• 25: Nolan Miller , Paul Resnick , Richard Zeckhauser, Eliciting Informative Feedback: The Peer-Prediction Method, Management Science, v.51 n.9, p.1359-1373, September 2005 [doi>10.1287/mnsc.1050.0379]
• 26: Rajeev Motwani , Ying Xu, Evolution of page popularity under random web graph models, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142372]
• 27: J. von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. In Contributions to the optimal assignment problem to the Theory of Games. Princeton Univ. Press, 1953, vol. 2, pp.5--12.
• 28: B. Null. A discussion of click-through algorithms for web page ranking. Available at http://www.stanford.edu/~null/ClickThroughAlg_Tutorial.pdf.
• 29: L. Page, S. Brin, R. Motwani, T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Stanford Digital Library Technologies Project, 1998.
• 30: Paul Resnick , Ko Kuwabara , Richard Zeckhauser , Eric Friedman, Reputation systems, Communications of the ACM, v.43 n.12, p.45-48, Dec. 2000 [doi>10.1145/355112.355122]
• 31: D. Vise. Clicking to steal. Washington Post Magazine, F01, April 17 2005.
• 32: H. Zhang, A. Goel, R. Govindan, K. Mason, B. Van Roy. Making eigenvector-based reputation systems robust to collusion. Workshop on Algorithms and Models for the Web Graph (WAW) 2004.