WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security

Beijing, China

Trust-Based Recommendation Systems: an Axiomatic Approach
Reid Andersen Abraham Flaxman Christian Borgs Jennifer Chayes Uriel Feige Adam Kalai§  Vahab Mirrokni Moshe Tennenholtz¶ 

ABSTRACT
High-quality, p ersonalized recommendations are a key feature in many online systems. Since these systems often have explicit knowledge of social network structures, the recommendations may incorp orate this information. This pap er focuses on networks that represent trust and recommendation systems that incorp orate these trust relationships. The goal of a trust-based recommendation system is to generate p ersonalized 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 trustbased recommendation system might b e exp ected 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 p ersonalized PageRank, ma jority of ma jorities, 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 ab out their votes or modifying their trust links. This is an imp ortant prop erty for systems deployed in a monetized environment.

General Terms
Algorithms, Theory, Economics

Keywords
Recommendation systems, Reputation systems, Axiomatic approach, Trust networks

1. INTRODUCTION
Ranking, reputation, recommendation, and trust systems have b ecome essential ingredients of web-based multi-agent systems (e.g. [16, 22, 8, 25, 11]). These systems aggregate agents' reviews of products, services, and each other, into valuable information. Notable commercial examples include Amazon and E-Bay's recommendation and reputation systems (e.g. [21]), Google's page ranking system [19], and the Epinions web of trust/reputation system (e.g. [18]). This pap er is concerned particularly with the setting where there is a single item of interest (e.g., a product, service, or p olitical candidate). A subset of the agents have prior opinions ab out this item. Any of the remaining agents might desire to estimate whether or not they would like the item, based on the opinions of others. In the offline world, a p erson might first consult her friends for their recommendations. In turn, the friends, if they do not have opinions of their own, may consult their friends, and so on. Based on the cumulative feedback the initial consulter receives, she might form her own sub jective opinion. An automated trust-based recommendation system aims to provide a similar process to produce high-quality personalized recommendations for agents. We model this setting as an annotated directed graph in which some of the nodes are lab eled by votes of + and -. Here a node represents an agent, and an edge directed from a to b represents the fact that agent a trusts agent b. A subset of the nodes are lab eled by + or - votes, indicating that these nodes have already formed opinions ab out the item under question. Based on this input, a recommendation system must output a recommendation for each unlab eled node. We call such an abstraction a voting network b ecause it models a variety of two-candidate voting systems, where the candidates are + and -. For an example, consider a directed star graph where a single root node p oints to n agents with lab els, which models a committee making a recommendation to the root node. In that setting, ma jority and consensus are two common voting rules. For another example, The U.S. presidential voting system can b e modeled as a more complicated digraph, where the root p oints

Categories and Subject Descriptors
F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity; J.4 [Computer Applications]: Social and Behavioral Sciences--Economics Microsoft Research, Redmond, WA. Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel.  Part of this research conducted while visiting MSR. § School of Computer Science, Georgia Institute of Technology, Atlanta, GA. Partly supp orted by NSF SES-0734780. ¶ Faculty of Industrial Engineering and Management, Technion­Israel Institute of Technology, Haifa, Israel.
 

Copyright is held by the International World Wide Web Conference Committee (IW3C2). Distribution of these papers is limited to classroom use, and personal use by others. WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04.

199


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security
to nodes representing the memb ers of the electoral college, and the electoral college nodes p oint to nodes representing the voters in the state or congressional district that they represent. A multitude of recommendation systems have b een prop osed and implemented, and many fit in to the networkbased framework describ ed ab ove. This raises the question of how to determine the relative merits of alternative approaches to providing trust-based recommendations. The task of comparing recommendation systems is complicated by the difficulty of producing an ob jective measure of recommendation quality. We b egin with an imp ossibility theorem: for a small, natural set of axioms, there is no recommendation system simultaneously consistent with all axioms in the set. However, for any prop er subset of the axioms there exists a recommendation system that satisfies all axioms in the subset. We consider two ways past this negative result, b oth by replacing the transitivity axiom (defined b elow). We prove that there are recommendation systems consistent with b oth new sets of axioms. We also show that when one of these new sets is augmented with an additional axiom, the resulting set of axioms is uniquely satisfied by a recommendation system based on random walks. We also consider the descriptive approach, in which we characterize existing (acyclic) systems, like simple committees and the U.S. presidential elections, by a simple ma jority axiom. We generalize this to an axiom that leads to a unique "minimum cut" system on general undirected (p ossibly cyclic) graphs. Prior work on p ersonalized ranking systems has produced a ranking system called personalized PageRank [13]. This system can b e translated into a recommendation system by augmenting it to handle votes, creating a natural hybrid of a ranking and recommendation system. The details are discussed in Section 3.4. We define a notion of incentive compatibility for recommendation systems. This is imp ortant when designing systems for deployment in monetized settings, b ecause, as exp erience has shown, self-interested agents will not resp ect the rules of the system when there is money to b e made by doing otherwise. We find that all of the recommendation systems for which we provide a characterizing set of axioms turn out to b e incentive compatible, including the random walk system, ma jority of ma jorities system, and minimum cut system. In contrast, the p ersonalized PageRank system and various other natural systems are not incentive compatible. For simplicity, this pap er focuses on the case of unweighted multigraphs and binary votes. Most of our observations carry over to the more general cases of weighted graphs and fractional votes. The rest of this pap er is organized is follows. The next section contains related work. Section 1.2 is a brief summary of our axioms, algorithms, and results. Some formal definitions and notations app ear in Section 2, and in Section 3 we present some recommendation systems. In Section 4 we formally define our axioms. Section 5 provides the outline of the proofs of our results. Section 6 shows that our systems are incentive compatibility.

Beijing, China

Standard evaluation tools include simulations and field exp eriments (e.g. [7, 21, 15]). In addition, one may also consider computational prop erties of suggested systems. Our work builds on previous work on axiomatizations of ranking systems. The literature on the axiomatic approach to ranking systems deals with b oth global ranking systems [1, 2, 24, 9, 25, 4, 5] and p ersonalized ranking systems [7, 10, 3, 17]. Personalized ranking systems are very close to trustbased recommendation systems. In such systems, agents rank some of the other agents. Then an aggregated ranking of agents, p ersonalized to the p ersp ective of a particular agent, is generated based on that information. However, previous studies on the axiomatic approach have not b een concerned with situations where the participants share reviews or opinions on items of interest which are not the other agents in the system. Many existing recommendation system are based on collab orative filtering (CF), which is a completely different approach than the trust-based systems considered in this pap er. An axiomatic approach to analyzing CF systems app ears in [20]. Combining trust-based and CF approaches is a direction of current research [23].

1.2 Overview of Results
We model a voting network by a partially lab eled directed multigraph whose nodes represent agents. A subset of the nodes, called voters, is lab eled with votes of + and -. The remaining nodes are nonvoters. The recommendation system must assign, to each source nonvoter, a recommendation in {-, 0, +}.1 Below we informally summarize our axioms. Many of them are illustrated in Figure 1. We caution that our aim is only to succinctly convey the spirit of the axioms; formal definitions are found in Section 2. 1. Symmetry. Isomorphic graphs result in corresp onding isomorphic recommendations (anonymity), and the system is also symmetric with resp ect to + and - votes (neutrality). 2. Positive response. If a node's recommendation is 0 and an edge is added to a + voter, then the former's recommendation b ecomes +. 3. Independence of Irrelevant Stuff (IIS). A node's recommendation is indep endent of agents not reachable from that node. Recommendations are also indep endent of edges leaving voters. 4. Neighborhood consensus. If a nonvoter's neighb ors unanimously vote +, then the recommendation of other nodes will remain unchanged if that node instead b ecomes a + voter. If, in a particular graph, a source node is recommended +, then we say that the source trusts the set of agents that voted + more than those that voted -. The following axiom states that this relation should b e transitive, as we imagine varying the votes of various subsets of agents. 5. Transitivity. For any graph (N , E ) and disjoint sets A, B , C  N , for any source s, if s trusts A more than B , and s trusts B more than C , then s trusts A more than C .
1 It is easy to see, e.g., a three-node network, that symmetry (Axiom 1) is imp ossible with ± recommendations alone.

1.1 Related Work
There are several ways to study recommendation systems.

200


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security

Beijing, China

­ +

+

u v

­ +

­

­

v s s d) e) f)
­

s a) b) c)

Figure 1: Illustrative voting networks. Labels ± indicate votes, not recommendations. a) IIS: Node s's recommendation does not depend on any of the dashed node or dashed edges, since we ignore unreachable nodes as well as edges out of voters. b) Neighborhood consensus: Node v can be assigned + vote. c) If the recommendation for s is + then we say s trusts {v } more than {u}. d) Trust propagation: The dashed edges the upper part can be removed and replaced by dashed edges in the lower part. e) Scale invariance: Edges leaving s are tripled without consequence. f ) No groupthink: The three nonvoting nodes cannot all be given + recommendations. Theorem 1. Axioms 1-5 are inconsistent. Any proper subset of these axioms is satisfied by some recommendation system. Instead of transitivity, we consider the following two axioms. Similar axioms have b een used in the axiomatization of PageRank in the context of ranking systems [2]. 6. Trust propagation. Supp ose node u trusts nonvoter v . Supp ose that u has k edges to v and v has k edges to other nodes. Then the edges from u to v can b e replaced directly by edges from u to the nodes that v trusts without changing any resulting recommendations. 7. Scale invariance. Duplicating the outgoing edges of a node does not change recommendations. We sp ecify a random walk algorithm, a (deterministic) algorithm that computes a recommendation for node s by considering a (hyp othetical) random walk in the directed graph that starts at node s and follows outgoing edges, uniformly at random, until the first voter is reached. Its recommendation for s is based on whether it is more likely that the first voter reached votes + or -. The system computed by the random walk algorithm is called the Random Walk recommendation system (RW). Theorem 2. Axioms 1-4 and 6-7 are satisfied uniquely by RW. As we will see in the proof of Theorem 1, the transitivity axiom and the I IS axiom are hard to reconcile b ecause I IS implies the edges out of the voting nodes do not matter while transitivity implies that the sets in the trust graph must ob ey a certain relation regardless of who is voting. A weaker version of transitivity which does not conflict with I IS is the following: 5 . Sink Transitivity. For any graph (N , E ) and any disjoint sets A, B , C  N for which A, B , C contain only vertices with out-degree 0, for any source s, if s trusts A more than B and s trusts B more than C , then s trusts A more than C . Theorem 3. Axioms 1-4 and 5
a

re satisfied by RW.

We also consider axioms which lead uniquely to known recommendation systems: 8. Ma jority. The recommendation of a node should b e equal to the ma jority of the votes and recommendations of its trusted neighb ors. 9. No groupthink. Supp ose a set of nonvoters unanimously have the same nonzero recommendation. Then their recommendation should equal the ma jority of their trusted (external) neighb ors' votes and recommendations. The ma jority axiom represents a reasonable semantics -- an agent might like to wait for its trusted neighb ors to receive a recommendation and then take a simple ma jority. However, this axiom alone still p ermits a large clique of nonvoters to all have p ositive recommendations when they only p oint to external agents with negative recommendations (see Figure 1f ). The no-groupthink axiom is a natural extension to larger sets. It implies the ma jority axiom when one considers just singleton sets. Unfortunately, on general directed graphs axiom 9 is inconsistent. However, it is a statement ab out a single graph G, so we can consider it on limited classes of graphs. Two interesting classes of graphs are directed acyclic graphs and undirected graphs,where axioms 8 and 9 lead uniquely to two interesting solutions. These are the ma jority-of-ma jorities and minimum-cut systems are defined in Section 3. Theorem 4. (a) Axiom 8 on a rooted DAG implies the majority-of-majorities system. (b) Axiom 9 on an undirected graph implies the min-cut recommendation system.

2. NOTATION AND DEFINITIONS
Following the motivation provided in the previous section, we now formally define the basic setting of a trust-based recommendation system. In the remainder of the pap er, we refer to such systems simply as recommendation systems, for brevity.

201


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security
Definition 1. A voting network is a directed annotated multigraph G = (N , V+ , V- , E ) where N is a set of nodes, V+ , V-  N are disjoint subsets of positive and negative voters, and E  N 2 is a multiset of edges with paral lel edges al lowed but no self-loops. When V+ and V- are clear from context, we denote the set of voters by V = V+  V- and the set of nonvoters by V = N \V. Definition 2. A recommendation system R takes as input a voting network G and source s  V and outputs recommendation R(G, s)  {-, 0, +}. For convenience, we will use R+ (G), R- (G), and R0 (G) to denote the set of sources to which R gives a particular recommendation, i.e. R+ = {s  V | R(G, s) = +}. Also, we define R(G) = R+ (G), R- (G), R0 (G) . We denote by sgn : R  {-, 0, +} the function that computes the sign of its input. We denote by PredE (v ) and SuccE (v ) the multisets of nodes that p oint to v and that v p oints to, resp ectively (where, for example, u app ears in PredE (v ) with multiplicity equal to the numb er of arcs (u, v ) in multiset E ). Given a multiset of recommendations, S  {-, 0, +}, we define the majority MAJ(S ) to b e: + if more than half the elements of S are +; - if more than half of S are -; and 0 otherwise. I n p u t : G = (N , V + , V - , E ), s  V . Output: recommendation  {-, 0, +}.

Beijing, China

1. Let S  V b e the set of nonvoters that cannot reach any voter. 2. For each v  N , create a variable rv  R. Solve the following from rv :  if v  S 0,   1, if v  V+ rv = if v  V- -1, w   SuccE (v) rw , otherwise |SuccE (v )| 3. Output sgn(rs ). Figure 2: The random walk algorithm. (Recall that V = V+  V- is the set of voters and V = N \ V is the set of nonvoters.)

3.2 Majority-of-Majorities (MoM)
The system in this section and in the next seem quite different at first glance, but b oth derive from the same single axiom. In this section, we present a system that is well defined only when the graph underlying the voting network is a Directed Acyclic Graph (DAG). Nodes in a finite DAG can always b e partitioned into a finite numb er of levels. In level 0, nodes have out-degree 0. In each level i  1, nodes have edges only to nodes in level j < i. The Ma jority-of-ma jorities system assigns a recommendation as follows: each nonvoter that is a sink (i.e. in level 0) receives recommendation 0; each voter in level i receives a recommendation equal to the ma jority of the recommendations and votes of its outgoing neighb ors (where multiple edges are counted multiple times). This can b e computed recursively by an efficient algorithm. Recall that we use the definition of Ma jority from Section 2, which is conservative in the sense that in order to have a non-zero recommendation, there must b e a strict ma jority of matching recommendations. As stated in Theorem 4a, the ma jority-of-ma jorities recommendation system is the unique system which satisfies axiom 8 when the voting network is a DAG. The proof of Theorem 4 is sketched in Section 5 and provided in full in App endix C.

3.

SYSTEMS AND ALGORITHMS

3.1 Random Walk System (RW)
We first describ e a recommendation system based on random walks. Given a voting network G = (N , V+ , V- , E ) and a source s  V , the random walk system simulates the following: start a walker at node s and, at each step, choose an outgoing edge uniformly at random and follow it to the destination node. Continue this random walk until a node with a ± vote is reached, or until a node with no outgoing edges is reached (note this walk may reach a node whose strongly connected comp onent contains no voters, and thus never terminate). Let ps b e the probability that the random walk terminates at a node with p ositive vote and qs b e the probability that the random walk terminates at node with negative vote. Let rs = ps - qs . The random walk recommendation system recommends sgn(rs ) to s. The algorithm given in Figure 2 correctly computes recommendations as defined by the RW system. To see this, first note that, for any node that cannot reach a voter, the recommendation must b e 0 in b oth the RW system and the RW algorithm. Next, probabilistic arguments show that the equations defined must b e ob eyed by the random walk. Finally, the uniqueness of the solution follows from the fact that, with probability 1, the random walk will reach a vertex in S  V+  V- . Also note that the algorithm can b e implemented efficiently and in p olynomial time. As stated in Theorem 2 (Section 1.2), the RW recommendation system is the unique system which satisfies axioms 1-4 and 6-7. The formal definitions of these axioms app ear in Section 4 and the proof of Theorem 2 is sketched in Section 5 and provided in full in App endix B. Theorem 3 states that RW satisfies 1-4 and 5 . The proof of this is omitted.

3.3 Minimum Cut System (min-cut)
Let G = (N , V+ , V- , E ) b e a voting network. Let E  E b e the set of edges in E that originate at nonvoters, i.e., eliminate edges out of voters. We say that cut C  E is a (V+ , V- )-cut of G if there is no path from V+ to V- using edges in E \ C . We say that C is a min-cut of G if its size |C | is minimal among all (V+ , V- )-cuts. The minimum cut system can b e defined as follows. The recommendation of a source s is + if in al l min-cuts there is a path from s to V+ among edges in E \ C . The recommendation is - if all min-cuts leave a path from s to V- . Otherwise, the recommendation is 0. This may b e computed as follows: first, compute a mincut C in G. Next, consider network G+ which is formed

202


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security
from G by adding an edge from source s to a + voter, and compute C+ in G+ . If |C | < |C+ | then the recommendation is -. Otherwise, consider network G- , formed from G by adding an edge from s to a - voter. For a min-cut C- of G- , if |C | < |C- | then the recommendation for s is +. Otherwise, the recommendation for s is 0. This can b e computed in p olynomial time by rep eatedly using a p olynomial-time algorithm for (s, t)-minimum cut. To see that it correctly computes the min-cut recommendation, note that if s is connected to V+ in all min-cuts then adding an edge from s to a - voter will create a path from V- to V+ in all min-cuts. This will increase the min-cut cost by 1. On the other hand, if there is a cut of G where s is not connected to V+ , then this edge set will still b e a cut in G- so the min-cut cost will not increase. Similarly, |C | < |C+ | if and only if s is connected to V- in all min-cuts of G. In the remaining case, the sizes of all three min-cuts will b e the same b ecause there are some min-cuts in which s is connected to V- and some in which s is connected to V+ . As stated in Theorem 4b, the min-cut recommendation system is the unique system which satisfies axiom 8 on undirected graphs. The proof of Theorem 4 is sketched in Section 5 and provided in full in App endix C.

Beijing, China

4. AXIOMS
We are now ready to consider various prop erties of recommendation systems as candidate axioms. These prop erties are motivated by related literature on social choice and ranking systems, and also by the machinery used in practical recommendation systems. Similar to other axiomatic studies, the choice of axioms is to some extent arbitrary, and other sets of axioms are p ossible. Nevertheless, we b elieve that any one of our axioms by itself does capture a desirable prop erty for recommendation systems, and that the study of the combination of these axioms leads to informative insights and interesting algorithms. The first prop erty, symmetry, is purely structural. The symmetry axiom contains two parts, anonymity and neutrality. Anonynmity means that the names of the agents do not matter for the source node; all that matters is the structure of the trust graph and the votes provided. Neutrality means that the values +/- are arbitrary. Axiom 1. (Symmetry) Let G = (N , V+ , V- , E ) be a voting network. Anonymity: For any permutation  : N  N , let G , be the isomorphic voting network under  . Then R+ (G ) =  (R+ (G)) and R- (G ) =  (R- (G)). Neutrality: Also, let G = (N , V- , V+ , E ) be the voting network where the sets of voters V- and V+ have been interchanged. Then R+ (G) = R- (G ) and R- (G) = R+ (G ). The next axiom is a classic social choice axiom. It states that if a node s has recommendation 0 (or +) and an additional +-voter is added to the network along with an edge from s to the new node, then s's new recommendation should b e +. It reflects a razor's-edge view of a 0 recommendation. The axiom "pushes" the systems towards strict recommendations. (Without such an axiom, systems may almost always recommend 0.) Axiom 2. (Positive response) Let w  N , s  V , G { = (N , V+ ,V- , E ), and G = (N  {w}, V+  {w}, V- , E (s, w)}). If s  R- (G) then s  R+ (G ). / Note that the ab ove axiom is presented asymmetrically in terms of ± votes and recommendations. In combination with the Symmetry axiom, the corresp onding version with - votes and recommendations follows directly. We use an asymmetric presentation for readability in several of the axioms. The next axiom, Indep endence of Irrelevant Stuff (I IS) captures the semantics of recommendation systems discussed in the introduction: a source node is viewed as consulting neighb oring agents in the trust graph, who consult their neighb ors etc., while agents who have formed opinions just vote according to their opinion. This means that when considering the recommendation for a particular source node in a particular trust graph, where part of the agents vote (p erhaps based on first-hand exp erience), feedback from these agents is indep endent of who they trust (i.e., they trust themselves infinitely more than others) and the recommendation system should consider only reachable nodes and ignore links out of voters. While one may consider other typ es of semantics, something similar to this axiom app ears in many previously designed systems. Axiom 3. (IIS) Let G = (N , V+ , V- , E ) and e  V × N be an edge leaving a voter. Then for the subgraph G =

3.4 Personalized PageRank System
In designing a recommendation system, we can consider systems based on aggregating the level of trust a node has for other nodes. The idea is to define a trust level wuv for any two nodes u and v in the network, and to compute the recommendav ion for a nonvoter u by comparing two values: t v W+ (u) = V+ wuv and W- (u) = V- wuv . A natural way to capture the level of trust in a network is to apply a p ersonalized ranking system such as p ersonalized PageRank (as introduced by Haveliwala in [13]). The p ersonalized PageRank of node v for a node u is denoted by ppr (u  v ), and is defined to b e the probability mass at node v in the stationary distribution of a biased random walk R (u) with restart probability   (0, 1). The random walk R (u) is defined as follows: at each step, with probability , we restart the random walk at node u; and with probability 1 - , we go uniformly to one of the outgoing neighb ors, i.e, from a node w we go to one of the neighb ors 1- ; if there are no outgoing of w with probability out-degree(w) neighb ors, we restart the walk at node u . Note that, unlike the RW system in Section 3.1, this random walk continues regardless of whether the vertex it is currently visiting is a voter or nonvoter. The p ersonalized PageRank values can b e computed efficiently by simulating this random walk. For details of computation and extensions, see [13, 14]. Using this notation, the p ersonalized PageRank recommendation system is as follows: Given a voting network G = (N , V+ , V- , E ), and a parameter , we compute the p ersonalized PageRank ppr (u  v ) for v ll pairs of nodes. a For a nonvoter s, we compute W+ (s) = V+ ppr (s  v ), v ppr (s  v ), and we set R(G, s) = and W- (s) = V- sgn(W+ - W- ). It is not hard to see that the p ersonalized PageRank system satisfies the axioms symmetry, p ositive resp onse, and transitivity, but it does not satisfy the axioms I IS, and neighb orhood consensus. The proofs of these statements are omitted due to space constraints.

203


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security
(N, V+ , V- , E \ {e}) in which e has been removed, R(G) = R(G ). Similarly, if v  N is a node not reachable from s  V , then for the subgraph G in which node v (and its associated edges) have been removed, R(G, s) = R(G , s). When we write R(G) = R(G ), as in the ab ove, it means that the recommendations on the two voting networks are identical. The following requirement deals with some minimal rationality we wish to attribute to the agents; as in the classical theory of choice we are willing to assume something ab out the vote of an agent who has no a priori opinion only in extreme cases. The neighb orhood-consensus axiom does just that: if all the agents trusted by a node v vote +, and no other nodes touch v 's neighb ors, then the recommendation of any other nonvoter u will remain unchanged if v instead b ecomes a + voter. Axiom 4. (Neighborhood Consensus) Fix a voting network G = (N , V+ , V- , E ), and let s, u  V be distinct nonvoters. Suppose u has at least one outgoing edge, and suppose that each outgoing edge (u, v )  E points to v such that v  V+ and v has no (incoming or outgoing) neighbors other than u. Let G = (N , V+  {u}, V- , E ). Then R(G, s) = R(G , s).

Beijing, China

Axiom 6. (Trust propagation) Let voting network G = (N , V+ , V- , E ), u = v  V , and suppose that the edges leaving v (besides those to u) are (v , w1 ), . . . , (v , wk ), (wi = u) for some integer k. Suppose that E contains exactly k copie\ s E {(u, w1 ), . . . , (u, wk )} of (u, v ). Then, for E = {(u, v )  k} and G = (N , V+ , V- , E ), we have that R(G) = R (G ). Another natural axiom is scale invariance. Loosely sp eaking, this means that the amount of trust placed in a node is relative. Axiom 7. (Scale invariance) In voting network G = E (N , V+ , V- , E ), u  V , and k  1. Let G = (N , V+ , V- , E ) , where E is the multiset containing k copies of each of the edges leaving v . Then R(G) = R(G ). It states that we can duplicate all edges leaving a node an arbitrary numb er of times without changing recommendations.

4.3 Majority and Groupthink
The ma jority axiom states that a node's recommendation should equal the ma jority of the recommendations and votes of its trusted neighb ors. We say the sign of an edge is positive, negative, or neutral if it p oints to a node with p ositive vote or recommendation, negative vote or recommendation, or 0 recommendation, resp ectively. Axiom 8. (Ma jority) Let G = (N , V+ , V- , E ) be a voting network, and let let s  V be any nonvoter. Then, the recommendation of s should be equal to the majority of the signs of the edges leaving s. We are using the strict notion of ma jority as defined in Section 2. This choice is somewhat arbitrary, though it fits well with the next axiom. Also note that one can further axiomatize ma jority itself, but we leave it as is for the sake of brevity. Unfortunately, the ma jority axiom by itself does not imply unique recommendations on cyclic graphs (think ab out a graph with two nonvoters that p oint to each other). Instead, we consider the following prop erty. Groupthink refers to a social phenomenon in which an entire group of p eople arrive at a ridiculous conclusion through self-reinforcing interactions. The no-groupthink axiom rules this out and imp oses strong semantics on the system. There are two parts to this axiom. First, we consider the case that an entire group of nonvoters are all recommended +. This strong p osition should b e based on something external, since no memb er voted. The requirement is that, among the edges leaving the group, a ma jority must p oint to nodes with + votes or recommendations. Furthermore, if a ma jority of the edges leaving the group p oint to nodes with + votes or recommendations, then the group must contain at least one node with + recommendation. Since no-groupthink is inconsistent for general directed graphs, we define it for sp ecific graphs. We say that a recommendation system R avoids groupthink for G if the following holds: Axiom 9. (No groupthink) Let S  V be a nonempty set of nonvoters. Let E be the multiset of edges in E from S to N \ S . (a) If S  R+ (G), then a strict majority of the edges in E must point to nodes in R+ (G)V+ . (b) If a strict majority of the edges in E point to nodes in R+ (G)  V+ , then S  R+ (G) = .

4.1 Transitivity
Transitivity is a central concept in the axiomatization of voting [6]. In our context, we consider the case where the underlying trust graph is fixed, but the system needs to deal with more than one item, and different subsets of nodes vote on different items. The definition of transitivity is based on the following binary relation, which describ es whether a sp ecified source node trusts a set of nodes A more than another set of nodes B . Definition 3. Let G = (N , V+ , V- , E ) be a voting network. If s  R+ (G), then we say that s trusts V+ more than V- relative to multigraph (N , E ). For each source node, a binary relation is generated. The transitivity axiom stipulates that each of these binary relations must b e transitive. Axiom 5. (Transitivity) For al l multigraphs (N , E ), s  V , and disjoint A, B , C  N , if, relative to (N , E ), s trusts A more than B and s trusts B more than C , then s trusts A more than C .

4.2 Trust Propagation
In this section, we consider propagation of trust. Intuitively, if u trusts v and v trusts w, then u should trust w, at least to some extent. Much has b een written ab out trust propagation within social networks (see, e.g., [12]) and the axiom b elow is a conservative interpretation that agrees with much of the literature. One would like to say that if u trusts nonvoter v , and v trusts w, then we can simply add an edge from u to w without changing anything. However, our system is supp osed to reflect degrees of trust, and this would falsely inflate such trust. Instead, we count edges as follows. Supp ose there are k edges leaving v (that don't p oint to u). Supp ose that there happ en to b e k edges from u to v . Then we can remove k edges from u to v and replace them by k new edges from u to the k nodes that v trusts (b esides u), and no recommendations should change.

204


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security

Beijing, China

(i)

(ii) u s v

an individual implies directly that its vote will equal the ma jority of its outgoing neighb ors' recommendations. This can b e applied from the sinks upwards to get uniquely the MoM system. For part (b), our proof is by contradiction. We b egin by assuming that the recommendations do not match those of the min-cut system and use a case analysis to show that, in each case, some set of nodes engages in groupthink.

A

s

B

C

w

6. INCENTIVE COMPATIBILITY
Incentive compatibility is a desirable prop erty for voting systems. In our context, it not only means that an agent will have incentive to vote according to its prior opinion, but it means that an agent (or a set of agents) cannot b e more effective by creating false edges (or even false nodes). To discuss incentive compatibility, one needs to discuss preferences. We say an agent has positive preferences if an agent prefers a set of recommendations that is, node by node, larger than or equal to another set of recommendations (where + is larger than 0 and -, and 0 is larger than -). Similarly, for negative preferences. We say a recommendation system is incentive compatible if (1) every set of agents with p ositive preferences is at least as happy with the outcomes when they all vote + and rep ort trust honestly, as they would b e in any other scenario that they can collude to create; and (2) the same is true for every set of agents with negative preferences when they all vote -. For example, supp ose a set of agents T have p ositive preferences, and node s  T receives a 0 or - when all agents in S vote +. Incentive compatibility implies that s cannot receive a greater recommendation when agents in T take any of the following strategic actions (sometimes called Sybil attacks ): · T creates an arbitrarily large set of fictitious agents F . · T and F create arbitrary edges b etween themselves, and arbitrary outgoing edges from themselves to other agents. (They are not allowed to alter edges which start at non-malicious agents.) · Arbitrary subsets of S  F vote +, vote -, and do not vote. This implies that the set S will never strictly prefer any outcome (under their control) other than that achieved when they all vote +. It is relatively straightforward to see that RW satisfies incentive compatibility, as the b est strategy for a group of agents to maximize another node's vote is to maximize the probability that the first voting node encountered votes +. Before a random walk reaches that malicious agents, it is out of their control. Once it reaches them, they might as well terminate the walk with a + vote. It is similarly straightforward to verify that the MoM system also satisfies incentive compatibility if we enforce the fact that the cheating agents cannot create any cycles in the graph. Lastly, the min-cut system also ob eys the ab ove typ e of incentive compatibility. Note that p ersonalized PageRank does not satisfy incentive compatibility, since a voting node with p ositive preferences might have an incentive to alter its outlinks. Incentive compatibility is closely linked to axiom 3 (I IS), but they are not equivalent.

Figure 3: (i) Example demonstrating the impossibility of axioms 1-5. (ii) In this example, s trusts {u} more than {v }, {v } more than {w} and {w} more than {u}. The details are described in the text. When S is a singleton the no-groupthink axiom reduces to the ma jority axiom. Hence no-groupthink can b e interpreted as a generalization of the ma jority axiom to larger sets. Note that the no-groupthink axiom is incompatible with the scaleinvariance axiom.

5.

ANALYSIS SKETCH

In this section, we give intuition underlying the proofs of the three theorems from Section 1.2. Formal proofs are deferred to the App endix. For Theorem 1, the example in Figure 3(i) is used to demonstrate imp ossibility. Relative to the depicted graph, one can show that s trusts set A more than B , B more than C , and C more than A, contradicting transitivity. To show that the set of axioms is a minimal imp ossible set, we construct five recommendation systems, each one satisfying all but one of the axioms. For example, the RW recommendation system satisfies axioms 1-4 but does not satisfy axiom 5 (transitivity). Figure 3(ii) gives another example worthy of discussion. When u votes +, v votes -, and w does not vote, it is reasonable that s should b e + due to its extra path to u through w and the fact that multiple edges in our system reflect additional trust. However, continuing along these lines, symmetry leads to a cycle in the transitivity relation. While this argument does not follow from axioms 1-5, it is suggestive of problems due to transitivity. For Theorem 2, we first apply a sequence of transformations to the graph, to get the graph to a p oint in which all edges lead to voters. Each of these transformations can b e shown, by the axioms, not to change any recommendations. Moreover, none of these transformations change the recommendations computed by RW. Thus, the problem is reduced to showing that the theorem holds when all edges p oint to voters. The transformation process iterates through the nonvoters, and, for each non-voter, it removes all incoming edges by a combination of edge duplication and trust propagation. When we are left with edges only to voters, axioms 1-4 are still not sufficient to determine the recommendations of nodes due to p ossible multiple edges. However, by applying the trust propagation axiom again (in some sense in reverse), we complete the argument. For Theorem 4, part (a) on rooted trees is much simpler than part (b). For part (a), the no-groupthink axiom on

205


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security

Beijing, China

7.

CONCLUSIONS
[12]

In this pap er, we initiated the axiomatic study of trustbased recommendation systems. This allows for rigorous evaluation of recommendation systems. Our work deals b oth with a normative approach, where the ramifications of natural p ostulates are considered, and with the descriptive approach where we aim at fully characterizing particular systems. In particular, we have found five basic axioms that cannot b e satisfied simultaneously, for which any prop er subset can b e satisfied. In addition, we have given a sharp characterization of the random walk recommendation system. This was obtained by replacing an axiom capturing a notion of transitivity with ones capturing trust propagation and duplication. Acknowledgments. We thank the attendees of the "DIMACS Workshop on the Boundary b etween Economic Theory and Computer Science" for their many helpful comments.

[13]

[14]

[15]

[16]

[17]

8.

REFERENCES
[18]

[1] A. Altman and M. Tennenholtz. On the axiomatic foundations of ranking systems. In Proc. 19th International Joint Conference on Artificial Intel ligence, 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 p ersonalized ranking systems. In Proc. 20th International Joint Conference on Artificial Intel ligence, 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. Coop eration without enforcement? a comparative analysis of litigation and online reputation as quality assurance mechanisms. MIT Sloan School of Management Working Pap er No. 4295-03, 2003. [9] A. Borodin, G. O. Rob erts, J. S. Rosenthal, and P. Tsaparas. Link analysis ranking: algorithms, theory, and exp eriments. 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

[19]

[20]

[21]

[22]

[23]

[24]

[25]

International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 748­755, 2004. 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. T. Haveliwala. Topic-sensitive pagerank. In WWW '02: Proceedings of the 11th international conference on World Wide Web, pages 517­526, 2002. T. Haveliwala, S. Kamvar, and G. Jeh. An analytical comparison of approaches to p ersonalizing pagerank, 2003. Technical rep ort, Stanford University. D. Houser and J. Wooders. Reputation in auctions: Theory and evidence from ebay. Working Pap er, University of Arizona, 2000. J. M. Kleinb erg. Authoritative sources in a hyp erlinked environment. Journal of the ACM (JACM), 46(5):604­632, 1999. R. Levien. Attack Resistant Trust Metrics. PhD thesis, University of California, Berkeley, 2002. P. Massa and P. Avesani. Controversial users demand local trust metrics: An exp erimental study on epinions.com community. In Proc. of AAAI-05, pages 121­126, 2005. L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Rep ort, Stanford University, 1998. Pennock D. M., Horvitz E., and Giles C. L. Social Choice Theory and Recommender Systems: Analysis of the Axiomatic Foundations of Collab orative Filtering. In Proceedings of the National Conference on Artificial Intel ligence (AAAI-2000), pages 729­734. AAAI Press, 2000. P. Resnick and R. Zeckhauser. Trust among strangers in internet transactions: Empirical analysis of ebay's reputation system. Working Pap er for the NBER workshop on empirical studies of electronic commerce, 2001. P. Resnick, R. Zeckhauser, R. Friedman, and E. Kuwabara. Reputation systems. Communications of the ACM, 43(12):45­48, 2000. A. P. Singh, A. Gunawardana, C. Meek, and A. C. Surendran. Recommendations using absorbing random walks. Manuscript under submission. G. Slutzki and O. Volij. Ranking participants in generalized tournaments. International Journal of Game Theory, 33(2):255­270, 2005. M. Tennenholtz. Reputation systems: An axiomatic approach. In Proceedings of the 20th conference on uncertainity in Artificial Intel ligence (UAI-04), 2004.

APPENDIX A. PROOF OF THEOREM 1
First, we show that there exists a recommendation that satisfies any prop er subset of the axioms. In the following cases, we consider a voting network G = (N , V+ , V- , E ) and source s  N . 1. System without symmetry. Consider the trivial recommendation system that always recommends +. This system trivially satisfies the remaining axioms. 2. System without positive response. Consider the

206


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security
trivial recommendation system that always recommends 0. This system trivially satisfies the remaining axioms. (Recall that axiom 4, neighb orhood consensus, refers only to distinct non-voters.) 3. System without neighborhood-consensus. Consider the recommendation system which assigns to each nonvoter u the recommendation equal to sgn(a - b) where a is the numb er of edges from u to p ositive voters and b is the numb er of edges to negative voters. It is symmetric, neutral, and ob eys p ositive resp onse. It ob eys I IS since immediate neighb ors of s are reachable and can not b e removed. Transitivity is implied by the fact that this "local ma jority" system simply counts the numb er of edges leading to a set of nodes; since the numb er of edges connecting to X  Succ(s) is fixed, it ob eys transitivity. 4. A System Without IIS. In order to design a recommendation system that satisfies all axioms except I IS, define S+ to b e the set of nodes u  N that have at least one outgoing neighb or, and all of whose outgoing neighb ors are in V+ and have no neighb ors other than u. (These are essentially the nodes describ ed in the consensus axiom, except that it applies to voters as well, e.g., S+  V- is not necessarily empty.) Similarly define S- . For any nonvoter s  V , the recommendation to s is + if s  S+ , - if s  S- . For al l of the remaining nonvoters, the recommendation is sgn(|S+  V+ | - |S-  V- |). It is easy to see that this recommendation system satisfies symmetry. The p ositive resp onse axiom follows from the fact that the recommendation 0 for s can b e generated only when |S+  V+ | = |S-  V- |. Adding a new p ositive voting node w that is p ointed to by only s must increase |S+  V+ | and cannot increase |S-  V- |, since s  S-  S+  V-  V+ . To see that the system satisfies neighb orhood consensus, note that moving a nonvoter from S+ to V+ doesn't change any the sets in any other way. Finally, to see that the system satisfies transitivity, consider disjoint A, B , C  N and s  N such that s trusts A more than B and B more than C . Note that S+ dep ends only on V+ and is indep endent of V- . Also note that switching the sign of the votes switches the sets S+ and S- due to the symmetry of the algorithm. Next consider two cases. In case 1, supp ose that s  S+ when V+ = A. This means that s will receive a p ositive recommendation when V- = C so s trusts A more than C . In case 2, s  S+ when V+ = A. Since s trusts A more than B and B more than C , this means in particular that s  S+ when V+ = B nor when V+ = C (and s  S- when V- = B or V- = C ). Hence, in all cases, s's vote will equal sgn(|S+  V+ | - |S-  V- |). Thus |S+  V+ | is a measure of trust of s in a set V+ , and hence the system ob eys transitivity. 5. A System Without Transitivity. Theorem 2 implies that RW, the random walk recommendation system, satisfies axioms 1-4. 6. Inconsistency Now we prove that there is no recommendation system satisfying axioms 1-5. Consider the graph (V , E ) depicted in Figure 3(i). We claim that s trusts A more than B and s trusts B more than C , but s does not trust A more than C . This will prove imp ossibility. To see that s trusts A more than B , consider the voting network G = (V , A, B , E ). By the I IS axiom, we can ignore the edges from B to C without changing the recommendation to s, to get voting network G . Next imagine removing one of the nodes in A (and its associated edge) to get voting

Beijing, China

network G . Since G is a star graph with three + votes, three - votes, and 2 nonvoters aside from s, the recommendation for s has to b e 0 by the symmetry axiom. By p ositive resp onse, therefore, the recommendation for s in G has to b e + and hence s trusts A more than B . To see that s trusts B more than C , consider the voting network G = (V , B , C, E ). Again by the I IS axiom, we can ignore the edges from B to C without changing the recommendation to s. We are now again in a star graph with 3 + votes, 2 - votes, and 4 0 votes. By symmetry and p ositive resp onse, as ab ove, the recommendation to s must b e +, which is what we needed. Finally, to see that s does not trust A more than C , consider the voting network G = (V , A, C, E ). By three applications of neighb orhood consensus we can take the votes of B to b e all -. By I IS we can transform the graph yet again into a star graph, this time with 5 - votes and 4 + votes. As reasoned ab ove, the recommendation to s must b e -, and hence s does not trust A more than C .

B.

PROOF OF THEOREM 2

We first apply a sequence of transformations to the graph, to get the graph to a p oint in which all edges lead to voters or sink nonvoters. Each of these transformations can b e shown, by the axioms, not to change any recommendations. Moreover, none of these transformations change the recommendations computed by RW. Hence, it suffices to show the theorem for the case where all edges p oint to voters or sink nonvoters. The transformation removes all edges p ointing to any single nonvoter (that is not a sink), as follows. Take a node v which is a nonvoter but has out-degree k > 0. Take any other node u that p oints to v > 0 times. We will apply trust propagation to remove these edges to v , without adding other edges to v . To do this, we apply -fold edge duplication (scale invariance) to v and k-fold edge duplication (scale invariance) to u without changing any recommendations. This makes the numb er of edges from u to v equal to k and the out-degree of v also equal to k. Hence, we can apply trust propagation to remove all edges from u to v . This can b e applied in turn to each node that p oints to v , to get a graph where all edges p oint to voters or sink nonvoters. Note that each of these transformations does not change the recommendations of the RW system, either. The reason is that RW ob eys scale invariance and trust propagation, which can b e seen easily from the random walk definition. When the random walk reaches a non-sink nonvoter, it continues on a random edge out of that nonvoter. The trust propagation simply provides a "shortcut" which exactly simulates two steps of the random walk at this p oint. So, without loss of generality, it suffices to show the RW system is correct for a graph with only edges p ointing to voters and sink nonvoters. Consider any source s and the subgraph reachable from that source via directed edges through nonvoters. If no voter had multiple edges p ointing to it, then the theorem would follow from p ositive resp onse and symmetry. The reason is that when there were an equal numb er of + and - voters, by symmetry the recommendation of s would have to b e 0, regardless of the structure of edges to nonvoter sinks. By p ositive resp onse, adding any numb er of edges from s to more new + voters would cause the recommendation of s to b ecome p ositive (similarly for - voters).

207


WWW 2008 / Refereed Track: Internet Monetization - Recommendation & Security
The case that remains is where there are multiple parallel edges to voters. Say we have a +-voter v with k incoming edges (and, without loss of generality, no outgoing edges). By neighb orhood consensus, we can change such a voter to a nonvoter and add a numb er of outgoing edges to k new, distinct + voters that have no other neighb ors. Now we can apply trust propagation to v to get a new graph where all edges p ointing to v have b een replaced by edges p ointing directly to new nonvoters, without changing recommendations or the b ehavior of RW. In addition, we can remove v without changing s's recommendation, since there is no path from s to v . We can apply this procedure to each + and - voter with more than one incoming edge, until all voters have in-degree 1. The result for this case then follows from the argument in the ab ove paragraph.

Beijing, China

C.

PROOF OF THEOREM 3

Without loss of generality, we assume there are no edges b etween pairs of voters. Part (a) follows trivially from the ma jority axiom and the fact that any directed acyclic graph can b e partitioned into levels, where each edge is from a node in a higher level to a node in a lower level. For Theorem 4(b), we first state an interesting prop erty of the min-cut system. Lemma 1. Let G = (N , V+ , V- , E ) be a voting network and R(G) be the recommendations of the min-cut system. Let C the multiset of edges between nodes in R+ (G) and nodes in V-  R- (G)  R0 (G) plus with those between nodes in R- (G)  R0 (G) and nodes in V+ . Then C is a min-cut. Note that this lemma is asymmetric, we have essentially put all 0 recommendations with the negative recommendations. Proof. Given cuts C and C define the max of the two min-cuts as follows. For any cut C , let the node-set C+ b e the set consisting of +-voters and also nonvoters that can reach any + voter after C has b een removed. Given min-cuts C and C , and their corresp onding node sets C+ and C+ , the max of the two min-cuts is defined to b e the cut that cuts any edges b etween nodes in C+  C+ and N \ (C+  C+ ). (Note that the node-set corresp onding to the max of the two cuts is simply C+  C+ .) By rep eated application of this observation, we get the lemma, b ecause the intersection of all node-sets corresp onding to min-cuts gives exactly the cut describ ed by the lemma. It remains to show that the max of C and C is a min-cut by itself. To do this, it is helpful to define the min of two min-cuts, which is the completely symmetric notion to the max. Let the max b e A and the min b e B . It is not hard to see that multisets A B  C C , where denotes multiset union. The reason is that the numb er of times a given edge is cut by C and C (0, 1, or 2) is at least as great as the numb er of times it is cut by A and B (those edges b etween C+ \ C+ and C+ \ C+ are not cut at all by A or B ). Thus |A| + |B |  |C | + |C |. Furthermore, A and B are b oth cuts. Hence, at least one of them, say A, must no larger than C and C , which have the same size. But |A| = |C | = |C | since C and C are min-cuts. Hence, |B | = |A| and they are all min-cuts. We first argue that the min-cut system satisfies the groupthink axiom. Consider first part (a) of groupthink. Supp ose

S  R+ (G) is a subset of the nonvoters that are all given p ositive recommendations. These nodes are all connected to p ositive voters in every min-cut. Take the min-cut defined in the ab ove lemma. Now, for the purp oses of contradiction, supp ose S does not have a ma jority of p ositive edges leaving it. Then we claim that we could find another min-cut C in which no node in S is connected to a + voter, which violates the definition of the min-cut system. In particular, we would take C to b e the cut which is equal to C , except that it also cuts all p ositive edges leaving S and does not cut any negative or neutral edges leaving S . This is a cut b ecause C was a cut and no new paths b etween p ositive and negative voters have b een created ­ they would have to go through S but S has no p ositive edges and thus is disconnected from the p ositive voters. Furthermore, C would not b e larger than C b ecause we have assumed that S does not have a ma jority of p ositive edges leaving it. Hence, we have a min-cut and the desired contradiction. The argument for the case where S all has negative recommendations follows by symmetry of the system. We next argue that the min-cut system satisfies Groupthink (b). For the purp oses of contradiction, supp ose we have a set S  R- (G)  R0 (G) such that S has a majority of p ositive outgoing edges. (The other case, where S  R+ (G)  R0 (G) such that S has a ma jority of negative outgoing edges, is similar.) Again, take the min-cut C defined by the ab ove Lemma. Consider the cut C which is the same as C but where we have also cut all negative and neutral edges from S and haven't cut any p ositive edges. As in the previous argument, this remains a cut and is smaller than C , giving us the desired contradiction. It remains to show that the min-cut system is the unique system implied by the groupthink axiom. Supp ose not. Supp ose that on some undirected graph, different recommendations R (G) satisfy the groupthink axiom. Case 1: The set S = (R- (G)R0 (G))R+ (G) is nonempty. Since we have shown that the min-cut system satisfies groupthink and S  R+ (G), this means that a strict ma jority of edges b etween S and N \ S are b etween a node in S and a node in V+  (R+ (G) \ S ). However, by definition of S , (R+ (G) \ S )  (R- (G)  R0 (G)) is the empty set, or in other words R+ (G) \ S  R+ (G) since every nonvoter has either a -, 0, or + recommendation in R . This gives us the desired contradiction b ecause we have more than half of the edges leaving S p ointing to nodes in R+ (G)  V+ , which contradicts Groupthink (a). Case 2: The set (R+ (G)  R0 (G))  R- (G) = . This follows from the previous case by symmetry. Case 3: The sets (R- (G)  R0 (G))  R+ (G) = (R+ (G)  R0 (G))  R- (G) = , but T = R+ (G)  R0 (G) = . Again, b ecause the min-cut system satisfies groupthink, the set T which is unanimously 0 under R cannot have a strict ma jority of its edges p ointing to nodes in (R+ (G)  V+ ) \ T . However, it is unanimously p ositive under R , so it must have a strict ma jority of edges p ointing to nodes in (R+ (G)V+ )\T . However, by our choice of T , these two sets are equal. Case 4: The sets (R- (G)  R0 (G))  R+ (G) = (R+ (G)  R0 (G))  R- (G) = , but R- (G)  R0 (G) = . This follows from the previous case by symmetry. The ab ove four cases cover all p ossibilities in which R = R.

208