Trust-based Recommendation Systems: An Axiomatic Approach

High-quality, personalized recommendations are a key fea-
ture in many online systems. Since these systems often have
explicit knowledge of social network structures, the recom-
mendations may incorporate this information. This paper
focuses on networks which represent trust and recommen-
dations which incorporate trust relationships. The goal of
a trust-based recommendation system is to generate per-
sonalized recommendations from known opinions and trust
relationships.
In analogy to prior work on voting and ranking systems,
we use the axiomatic approach from the theory of social
choice. We develop an natural set of five axioms which we
desire any recommendation system exhibit. Then we show
that no system can simultaneously satisfy all these axioms.
We also exhibit systems which satisfy any four of the five
axioms. Next we consider ways of weakening the axioms,
which can lead to a unique recommendation system based on
random walks. We consider other recommendation systems
(personal page rank, majority of majorities, and min cut)
and search for alternative axiomatizations which uniquely
characterize these systems.
Finally, we determine which of these systems are incen-
tive compatible. This is an important property for systems
deployed in a monetized environment: groups of agents in-
terested in manipulating recommendations to make others
share their opinion have nothing to gain from lying about
their votes or their trust links.