skip to main content
10.1145/1367497.1367525acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Trust-based recommendation systems: an axiomatic approach

Published: 21 April 2008 Publication History

Abstract

High-quality, personalized recommendations are a key feature in many online systems. Since these systems often have explicit knowledge of social network structures, the recommendations may incorporate this information. This paper focuses on networks that represent trust and recommendation systems that incorporate these trust relationships. The goal of a trust-based recommendation system is to generate personalized recommendations by aggregating the opinions of other users in the trust network.
In analogy to prior work on voting and ranking systems, we use the axiomatic approach from the theory of social choice. We develop a set of five natural axioms that a trust-based recommendation system might be expected to satisfy. Then, we show that no system can simultaneously satisfy all the axioms. However, for any subset of four of the five axioms we exhibit a recommendation system that satisfies those axioms. Next we consider various ways of weakening the axioms, one of which leads to a unique recommendation system based on random walks. We consider other recommendation systems, including systems based on personalized PageRank, majority of majorities, and minimum cuts, and search for alternative axiomatizations that uniquely characterize these systems.
Finally, we determine which of these systems are incentive compatible, meaning that groups of agents interested in manipulating recommendations can not induce others to share their opinion by lying about their votes or modifying their trust links. This is an important property for systems deployed in a monetized environment.

References

[1]
A. Altman and M. Tennenholtz. On the axiomatic foundations of ranking systems. In Proc. 19th International Joint Conference on Artificial Intelligence, pages 917--922, 2005.
[2]
A. Altman and M. Tennenholtz. Ranking systems: the pagerank axioms. In EC '05: Proceedings of the 6th ACM conference on Electronic commerce, pages 1--8, New York, NY, USA, 2005. ACM Press.
[3]
A. Altman and M. Tennenholtz. An axiomatic approach to personalized ranking systems. In Proc. 20th International Joint Conference on Artificial Intelligence, 2006.
[4]
A. Altman and M. Tennenholtz. Quantifying incentive compatibility of ranking systems. In Proc. of AAAI-06, 2006.
[5]
A. Altman and M. Tennenholtz. Incentive compatible ranking systems. In Proceedings of the 2007 International Conference on Autonomous Agents and Multiagent Systems (AAMAS-07), 2007.
[6]
K. Arrow. Social Choice and Individual Values (2nd Ed.). Yale University Press, 1963.
[7]
P. Avesani, P. Massa, and R. Tiella. A trust-enhanced recommender system application: Moleskiing. In SAC '05: Proceedings of the 2005 ACM symposium on Applied computing, pages 1589--1593, New York, NY, USA, 2005. ACM Press.
[8]
Y. Bakos and C. N. Dellarocas. Cooperation without enforcement? a comparative analysis of litigation and online reputation as quality assurance mechanisms. MIT Sloan School of Management Working Paper No. 4295-03, 2003.
[9]
A. Borodin, G. O. Roberts, J. S. Rosenthal, and P. Tsaparas. Link analysis ranking: algorithms, theory, and experiments. ACM Trans. Inter. Tech., 5(1):231--297, 2005.
[10]
A. Cheng and E. Friedman. Sybilproof reputation mechanisms. In P2PECON '05: Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, pages 128--132, New York, NY, USA, 2005. ACM Press.
[11]
R. Dash, S. Ramchurn, and N. Jennings. Trust-based mechanism design. In Proceedings of the Third International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 748--755, 2004.
[12]
R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In WWW '04: Proceedings of the 13th international conference on World Wide Web, pages 403--412, 2004.
[13]
T. Haveliwala. Topic-sensitive pagerank. In WWW '02: Proceedings of the 11th international conference on World Wide Web, pages 517--526, 2002.
[14]
T. Haveliwala, S. Kamvar, and G. Jeh. An analytical comparison of approaches to personalizing pagerank, 2003. Technical report, Stanford University.
[15]
D. Houser and J. Wooders. Reputation in auctions: Theory and evidence from ebay. Working Paper, University of Arizona, 2000.
[16]
J. M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5):604--632, 1999.
[17]
R. Levien. Attack Resistant Trust Metrics. PhD thesis, University of California, Berkeley, 2002.
[18]
P. Massa and P. Avesani. Controversial users demand local trust metrics: An experimental study on epinions.com community. In Proc. of AAAI-05, pages 121--126, 2005.
[19]
L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report, Stanford University, 1998.
[20]
Pennock D. M., Horvitz E., and Giles C. L. Social Choice Theory and Recommender Systems: Analysis of the Axiomatic Foundations of Collaborative Filtering. In Proceedings of the National Conference on Artificial Intelligence (AAAI-2000), pages 729--734. {AAAI Press}, {2000}.
[21]
P. Resnick and R. Zeckhauser. Trust among strangers in internet transactions: Empirical analysis of ebay's reputation system. Working Paper for the NBER workshop on empirical studies of electronic commerce, 2001.
[22]
P. Resnick, R. Zeckhauser, R. Friedman, and E. Kuwabara. Reputation systems. Communications of the ACM, 43(12):45--48, 2000.
[23]
A. P. Singh, A. Gunawardana, C. Meek, and A. C. Surendran. Recommendations using absorbing random walks. Manuscript under submission.
[24]
G. Slutzki and O. Volij. Ranking participants in generalized tournaments. International Journal of Game Theory, 33(2):255--270, 2005.
[25]
M. Tennenholtz. Reputation systems: An axiomatic approach. In Proceedings of the 20th conference on uncertainity in Artificial Intelligence (UAI-04), 2004.

Cited By

View all
  • (2024)Trust Exploitation in Graph based Social Recommender Systems : A Survey2024 Second International Conference on Emerging Trends in Information Technology and Engineering (ICETITE)10.1109/ic-ETITE58242.2024.10493384(1-9)Online publication date: 22-Feb-2024
  • (2024)Recognizing single-peaked preferences on an arbitrary graph: Complexity and algorithmsDiscrete Applied Mathematics10.1016/j.dam.2024.02.009348(301-319)Online publication date: May-2024
  • (2023)The Effect of Iterativity on Adversarial Opinion FormingInformation Processing Letters10.1016/j.ipl.2023.106453(106453)Online publication date: Oct-2023
  • Show More Cited By

Index Terms

  1. Trust-based recommendation systems: an axiomatic approach

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      WWW '08: Proceedings of the 17th international conference on World Wide Web
      April 2008
      1326 pages
      ISBN:9781605580852
      DOI:10.1145/1367497
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      In-Cooperation

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 21 April 2008

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. axiomatic approach
      2. recommendation systems
      3. reputation systems
      4. trust networks

      Qualifiers

      • Research-article

      Conference

      WWW '08
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)35
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 09 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Trust Exploitation in Graph based Social Recommender Systems : A Survey2024 Second International Conference on Emerging Trends in Information Technology and Engineering (ICETITE)10.1109/ic-ETITE58242.2024.10493384(1-9)Online publication date: 22-Feb-2024
      • (2024)Recognizing single-peaked preferences on an arbitrary graph: Complexity and algorithmsDiscrete Applied Mathematics10.1016/j.dam.2024.02.009348(301-319)Online publication date: May-2024
      • (2023)The Effect of Iterativity on Adversarial Opinion FormingInformation Processing Letters10.1016/j.ipl.2023.106453(106453)Online publication date: Oct-2023
      • (2023)Recommending on graphs: a comprehensive review from a data perspectiveUser Modeling and User-Adapted Interaction10.1007/s11257-023-09359-w33:4(803-888)Online publication date: 13-Mar-2023
      • (2022)Toward Fast and Scalable Random Walks over Disk-Resident Graphs via Efficient I/O ManagementACM Transactions on Storage10.1145/353357918:4(1-33)Online publication date: 11-Nov-2022
      • (2022)From Who You Know to What You Read: Augmenting Scientific Recommendations with Implicit Social NetworksProceedings of the 2022 CHI Conference on Human Factors in Computing Systems10.1145/3491102.3517470(1-23)Online publication date: 29-Apr-2022
      • (2022)Gauging node consistency in accusation–endorsement networksJournal of Complex Networks10.1093/comnet/cnac01110:3Online publication date: 25-Apr-2022
      • (2022)Recent advances of deep learning algorithms for aquacultural machine vision systems with emphasis on fishArtificial Intelligence Review10.1007/s10462-021-10102-355:5(4077-4116)Online publication date: 1-Jun-2022
      • (2022)Towards an axiomatic approach to truth discoveryAutonomous Agents and Multi-Agent Systems10.1007/s10458-022-09569-336:2Online publication date: 1-Oct-2022
      • (2022)A novel hybrid approach of ABC with SCA for the parameter optimization of SVR in blind image quality assessmentNeural Computing and Applications10.1007/s00521-021-06435-334:6(4165-4191)Online publication date: 1-Mar-2022
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media