Mechanism Design for Personalized Recommender Systems

ABSTRACT

Strategic behaviour from sellers on e-commerce websites, such as faking transactions and manipulating the recommendation scores through artificial reviews, have been among the most notorious obstacles that prevent websites from maximizing the efficiency of their recommendations. Previous approaches have focused almost exclusively on machine learning-related techniques to detect and penalize such behaviour. In this paper, we tackle the problem from a different perspective, using the approach of the field of mechanism design. We put forward a game model tailored for the setting at hand and aim to construct truthful mechanisms, i.e. mechanisms that do not provide incentives for dishonest reputation-augmenting actions, that guarantee good recommendations in the worst-case. For the setting with two agents, we propose a truthful mechanism that is optimal in terms of social efficiency. For the general case of m agents, we prove both lower and upper bound results on the effciency of truthful mechanisms and propose truthful mechanisms that yield significantly better results, when compared to an existing mechanism from a leading e-commerce site on real data.

References

1. E. H. Clarke. Multipart pricing of public goods. Public Choice, 2:19--33, 1971.
2. B. Faltings. Using incentives to obtain truthful information. In Agents and Artificial Intelligence, pages 3--10. Springer, 2013.
3. T. Groves. Incentives in Teams. Econometrica, 41:617--631, 1973.
4. N. Jindal and B. Liu. Opinion spam and analysis. In Proceedings of the 2008 International Conference on Web Search and Data Mining, pages 219--230. ACM, 2008.
5. S. Johnson, J. W. Pratt, and R. J. Zeckhauser. Efficiency despite mutually payoff-relevant private information: The finite case. Econometrica: Journal of the Econometric Society, pages 873--900, 1990.
6. R. Jurca and B. Faltings. Obtaining reliable feedback for sanctioning reputation mechanisms. Journal of Artificial Intelligence Research (JAIR), 29:391--419, 2007.
7. R. Jurca and B. Faltings. Truthful opinions from the crowds. ACM SIGecom Exchanges, 7(2):3, 2008.
8. R. Jurca, B. Faltings, et al. Mechanisms for making crowds truthful. Journal of Artificial Intelligence Research, 34(1):209, 2009.
9. E. S. Maskin. Mechanism design: How to implement social goals. The American Economic Review, pages 567--576, 2008.
10. H. Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437--455, 1980.
11. A. Mukherjee, A. Kumar, B. Liu, J. Wang, M. Hsu, M. Castellanos, and R. Ghosh. Spotting opinion spammers using behavioral footprints. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 632--640. ACM, 2013.
12. R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
13. R. B. Myerson. Mechanism design. Center for Mathematical Studies in Economics and Management Science, Northwestern University, 1988.
14. N. Nisan, T. Roughgarden, Éva Tardos, and V. V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.
15. M. Ott, Y. Choi, C. Cardie, and J. T. Hancock. Finding deceptive opinion spam by any stretch of the imagination. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 309--319. Association for Computational Linguistics, 2011.
16. A. D. Procaccia and M. Tennenholtz. Approximate mechanism design without money. In Proceedings of the 10th ACM conference on Electronic commerce, pages 177--186. ACM, 2009.
17. Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game theoretic and Logical Fundations. Cambridge Uni. Press, 2009.
18. G. Swamynathan, K. C. Almeroth, and B. Y. Zhao. The design of a reliable reputation system. Electronic Commerce Research, 10(3--4):239--270, 2010.
19. W. Vickrey. Counterspeculation, Auctions and Competitive Sealed Tenders. Journal of Finance, pages 8--37, 1961.
20. H. Xu, D. Liu, H. Wang, and A. Stavrou. E-commerce reputation manipulation: The emergence of reputation-escalation-as-a-service. In Proceedings of the 24th International Conference on World Wide Web, pages 1296--1306. International World Wide Web Conferences Steering Committee, 2015.
21. K.-H. Yoo and U. Gretzel. Comparison of deceptive and truthful travel reviews. Information and communication technologies in tourism 2009, pages 37--47, 2009.
22. J. Zhang, R. Cohen, and K. Larson. Combining trust modeling and mechanism design for promoting honesty in e-marketplaces. Computational Intelligence, 28(4):549--578, 2012.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Recommender systems

  • World Wide Web

    • Web applications

      • Electronic commerce

        • E-commerce infrastructure

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Algorithmic mechanism design