An Axiomatic Approach to Personalized Ranking Systems

1 Introduction

Personalized ranking systems and trust systems are an essential tool for collaboration in a multi-agent environment. In these systems, agents report on their peers performance, and these reports are aggregated to form a ranking of the agents. This ranking may be either global, where all agents see the same ranking, or personalized, where each agent is provided with her own ranking of the agents. Examples of global ranking systems include eBay's reputation system[Resnick and Zeckhauser, 2001] and Google's PageRank[Page et al., 1998]. Examples of personalized ranking systems include the personalized version of PageRank[Haveliwala et al., 2003] and the MoleTrust ranking system[Avesani et al., 2005]. Furthermore, trust systems which provide each agent with a set of agents he or she can trust, can be viewed as personalized ranking systems which supply a two-level ranking over the agents. Many of these systems can be easily adapted to provide a full ranking of the agents. Examples of trust systems include OpenPGP(Pretty Good Privacy)'s trust system[Callas et al., 1998], the ranking system employed by Advogato[Levien, 2002], and the epinions.comweb of trust.

A central challenge in the study of ranking systems, is to provide means and rigorous tools for the evaluation of these systems. This challenge equally applies to both global and personalized ranking systems. A central approach to the evaluation of such systems is the experimental approach. In the general ranking systems setting, this approach was successfully applied to Hubs&Authorities[Kleinberg, 1999] and to various other ranking systems[Borodin et al., 2005]. In the trust systems setting, [Massa and Avesani, 2005] suggest a similar experimental approach.

A more analytical approach to the evaluation of ranking systems is the axiomatic approach. In this approach, one considers basic properties, or axioms, one might require a ranking system to satisfy. Then, existing and new systems are classified according to the set of axioms they satisfy. Examples of such study in the global ranking systems literature include [Cheng and Friedman, 2005; Borodin et al., 2005; Tennenholtz, 2004; Altman and Tennenholtz, 2006b]. Typical results of such study are axiomatizations of particular ranking systems, or a proof that no ranking system satisfying a set of axioms exists. For example, in [Altman and Tennenholtz, 2005b]we provide a set of axioms that are satisfied by the PageRank system and show that any global ranking system that satisfies these axioms must coincide with PageRank.

While the axiomatic approach has been extensively applied to the global ranking systems setting, no attempt has been made to apply such an approach to the context of personalized ranking systems. In this paper, we introduce an extensive axiomatic study of the personalized ranking system setting, by adapting known axioms we have previously applied to global ranking systems[Altman and Tennenholtz, 2005a; 2006a]. We compare several existing personalized ranking systems in the light of these axioms, and provide novel ranking systems that satisfy various sets of axioms. Moreover, we prove a characterization of the personalized ranking systems satisfying all suggested axioms.

We consider four basic axioms. The first axiom, self confidence, requires that an agent would be ranked at the top of his own personalized rank. The second axiom, transitivity, captures the idea that an agent preferred by more highly trusted agents, should be ranked higher than an agent preferred by less trusted agents. The third axiom, Ranked Independence of Irrelevant Alternatives, requires that under the perspective of any agent, the relative ranking of two other agents would depend only on the pairwise comparisons between the rank of the agents that prefer them. The last axiom, strong incentive compatibility, captures the idea that an agent cannot gain trust by any agent's perspective by manipulating its reported trust preference.

We show a ranking system satisfying all four axioms, and ranking systems satisfying every three of the four axioms (but not the fourth). Furthermore, we provide a characterization proving that any ranking system satisfying all four axioms must satisfy a strong property we call maximum-transitivity.

This paper is organized as follows. Section 2 introduces the setting of personalized ranking systems and discusses some known system. In section 3 we present our axioms, and classify the ranking systems shown according to these axioms. In section 4 we provide a characterization of the ranking systems satisfying all of our axioms, and in section 5 we study ranking systems satisfying every three of the four axioms. Section 6 presents some concluding remarks and suggestions for future research.

2 Personalized Ranking Systems

2.1 The Setting

Before describing our results regarding personalized ranking systems, we must first formally define what we mean by the words "personalized ranking system" in terms of graphs and linear orderings:

Definition 1. Let A be some set. A relation R ⊆ A × A is called an ordering on A if it is reflexive, transitive, and complete. Let L(A) denote the set of orderings on A.

Notation 2. Let ⪯ be an ordering, then ≃ is the equality predicate of ⪯, and ≺ is the strict order induced by ⪯. Formally, a ≃ b if and only if a ⪯ b and b ⪯ a; and a ≺ b if and only if a ⪯ b but not b ⪯ a.

Given the above we can define what a personalized ranking system is:

Definition 3. Let GsV be the set of all directed graphs G = (V,E) such that for every vertex v ∈ V , there exists a directed path in E from s to v. A personalized ranking system(PRS) F is a functional that for every finite vertex set V and for every source s ∈ V maps every graph G ∈ GsV to an ordering ⪯FG,s∈ L(V ).

We require that there is a path of trust from the source to every agent, because agents that have no path from s cannot be ranked, as no agent trusted by s to any level has any connection with these agents. This assumption is satisfied when G is strongly connected. As it turns out, in most practical trust systems and social networks, a large portion of the agents are part of a strongly connected component. Our study also applies in cases where such paths do not exist, however for the ease of exposition we elect to keep this assumption.

2.2 Some personalized ranking systems

We shall now give examples of some known PRSs. A basic ranking system that is at the basis of many trust systems ranks the agents based on the minimal distance of the agents from the source.

Notation 4. Let G = (V,E) be some directed graph and v1, v2 ∈ V be some vertices, we will use dG(v1, v2) to denote the length of the shortest directed path in G between v1 and v2.

Definition 5. The distance PRS FD is defined as follows: Given a graph G = (V,E) and a source s, v1 ⪯FD G,s v2 ⇔ dG(s, v1) ≥ dG(s, v2)

Another family of PRSs can be derived from the wellknown PageRank ranking system by modifying the so-called teleportation vector in the definition of PageRank[Haveliwala et al., 2003]. These system can be defined as follows:

Definition 6. Let G = (V,E) be a directed graph, and assume V = {v1, v2, . . . , vn}. The PageRank Matrix AG (of dimension n × n) is defined as:

where SG(v) is the successor set of v in G.

The Personalized PageRank procedure ranks pages according to the stationary probability distribution obtained in the limit of a random walk with a random teleportation to the source s with probability d; this is formally defined as follows:

Definition 7. Let G = (V,E) be some graph, and assume V = {s, v2, . . . , vn}. Let r be the unique solution of the system (1-d)·AG·r+d·(1, 0, . . . , 0)T = r. The Personalized PageRank with damping factor d of a vertex vi ∈ V is defined as PPRdG,s (vi) = ri. The Personalized PageRank Ranking System with damping factor d is a PRS that for the vertex set V and source s ∈ V maps G to ⪯PPRd G,s , where ⪯PPRd G,s is defined as: for all vi, vj ∈ V : vi ⪯PPRd G,s vj if and only if PPRdG,s (vi) ≤ PPRdG,s(vj ).

We now suggest a variant of the Personalized PageRank system, which, as we will later show, has more positive properties than Personalized PageRank.

Definition 8. Let G = (V,E) be some graph and assume V = {s, v2, . . . , vn}. Let BG be the link matrix for G. That is, [BG]i,j = 1 ⇔ (i, j) ∈ E. Let α = 1/n2 and let r be the unique solution of the system α · BG · r+ (1, 0, . . . , 0)T = r. The α-Rank of a vertex vi ∈ V is defined as αRG,s(vi) = ri. The α-Rank PRS is a PRS that for the vertex set V and source s ∈ V maps G to ⪯αR G,s, where ⪯αR G,s is defined as: for all vi, vj ∈ V : vi ⪯αR G,s vj if and only if αRG,s(vi) ≤ αRG,s(vj ).

The α-Rank system ranks the agents based on their distance from s, breaking ties by the summing of the trust values of the predecessors. By selecting α = 1/n2, it is ensured that a slight difference in rank of nodes closer to s will be more significant than a major difference in rank of nodes further from s.

Additional personalized ranking systems are presented in Section 5 as part of our axiomatic study.

3 Some Axioms

A basic requirement of a PRS is that the source - the agent under whose perspective we define the ranking system - must be ranked strictly at the top of the trust ranking, as each agent implicitly trusts herself. We refer to this property as self confidence.

Definition 9. Let F be a PRS. We say that F satisfies self confidence if for all graphs G = (V, E), for all sources s ∈ V and for all vertices v ∈ V \ {s}: v ≺FG,s s.

We have previously defined[Altman and Tennenholtz, 2005a] a basic property of (global) ranking systems called strong transitivity, which requires that if an agent a's voters are ranked higher than those of agent b, then agent a should be ranked higher than agent b. We adapt this notion to the personalized setting, and provide a new weaker notion of transitivity as follows:

Definition 10. Let F be a PRS. We say that F satisfies quasi transitivity if for all graphs G = (V, E), for all sources s ∈ V and for all vertices v1, v2 ∈ V \ {s}: Assume there is a 1-1 mappingf : P(v1) ↦→P(v2) s.t. for all v ∈ P(v1):v ⪯ f(v). Then, v1 ⪯ v2. F further satisfies strong quasi transitivity if for all v ∈ P(v1): v ≺ f(v), then v1 ≺ v2. F further satisfies strong transitivity if when either f is not onto or for some v ∈ P(v1): v ≺ f(v), then v1 ≺ v2.

This new notion of transitivity requires that agents with stronger matching predecessors be ranked at least as strong as agents with weaker predecessors, but requires a strict preference only when all matching predecessors are strictly stronger.

A standard assumption in social choice settings is that an agent's relative rank should only depend on (some property of) their immediate predecessors. Such axioms are usually called independence of irrelevant alternatives(IIA) axioms. In the ranking systems setting, we require that the relative ranking of two agents must only depend on the pairwise comparisons of the ranks of their predecessors, and not on their identity or cardinal value. Our IIA axiom, called ranked IIA, differs from the one suggested by [Arrow, 1963] in the fact that ranked IIA does not consider the identity of the voters, but rather their relative rank. We adapt this axiom of ranked IIA to the setting of PRSs, by requiring this independence for all vertices except the source.

To formally define this condition, one must consider all possibilities of comparing two nodes in a graph based only on ordinal comparisons of their predecessors. [Altman and Tennenholtz, 2005a] call these possibilities comparison profiles:

Definition 11. A comparison profile is a pair 〈a, b〉 where a = (a1, . . . , an), b = (b1, . . . , bm), a1, . . . , an, b1, . . . , bm ∈ N, a1 ≤ a2 ≤ · · · ≤ an, and b1 ≤ b2 ≤ · · · ≤ bm. Let P be the set of all such profiles.

Let PG(v) denote the predecessor set of v in a graph G. A PRS F, a graph G = (V,E), a source s ∈ V , and a pair of vertices v1, v2 ∈ V are said to satisfy such a comparison profile 〈a, b〉 if there exist 1-1 mappings f1 : P(v1) ↦→ {1 . . . n} and f2 : P(v2) ↦→ {1 . . .m} such that given f : ({1}×P(v1)) ∪ ({2}×P(v2)) ↦→N defined as:

f(i, x) ≤ f(j, y) ⇔ x ⪯FG,s y for all (i, x), (j, y) ∈ ({1} × P (v1)) ∪ ({2} × P (v2)).

We now require that for every such profile the personalized ranking system ranks the nodes consistently:

Definition 12. Let F be a PRS. We say that F satisfies ranked independence of irrelevant alternatives (RIIA) if there exists a mapping f : P ↦→ {0, 1} such that for every graph G = (V,E), for every source s ∈ V and for every pair of vertices v1, v2 ∈ V \ {s} and for every comparison profile p ∈ P that v1 and v2 satisfy, v1 ⪯FG,s v2 ⇔ f(p) = 1. We will sloppily use the notation a ≼ b to denote f 〈a, b〉 = 1.

This IIA axiom intuitively means that the relative ranking of agents must be consistent across all comparisons with the same rank relations.

Personalized ranking systems do not exist in empty space. Agents may wish to manipulate their reported preferences in order to improve their trustworthiness in the eyes of a specific agent. Therefore, the incentives of these agents should in many cases be taken into consideration. We have previously defined the notion of strong incentive compatibility[Altman and Tennenholtz, 2006a], which requires that agents will not be ranked better for stating untrue preferences, under the assumption that the agents are interested only in their own ranking, with a strong preference with regard to rank. This notion is also natural when adapted to the personalized setting, as follows:

Definition 13. Let F be a PRS. F satisfies strong incentive compatibility if for all true preference graphs G = (V, E), for all sources s ∈ V , for all vertices v ∈ V , and for all preferences Vv ⊆ V reported by v: Let E′ = E \ {(v, x)|x ∈ V } ∪ {(v, x)|x ∈ Vv} and G′ = (V, E′ ) be the reported preference graph. Then, |{x ∈ V |v ≺FG′ x}| ≥ |{x ∈ V |v ≺FG x}|; and if |{x ∈ V |v ≺FG′ x}| = |{x ∈ V |v ≺FG x}| then |{x ∈ V |v ≃FG′ x}| ≥ |{x ∈ V |v ≃FG x}|.

3.1 Satisfication

We will now demonstrate these axioms by showing which axioms are satisfied by the PRSs mentioned in Section 2.2.

Proposition 14. The distance PRS FD satisfies self confidence, ranked IIA, strong quasi transitivity, and strong incentive compatibility, but does not satisfy strong transitivity.

Proof. Self-confidence is satisfied by definition of FD. FD satisfies RIIA, because it ranks every comparison profile consistently according to the following rule:

That is, any two vertices are compared according to their strongest predecessor. FD satisfies strong quasi transitivity, because when the 1-1 relation of predecessors exists, then also the strongest predecessors satisfy this relation.

To prove that FD satisfies strong incentive compatibility, note the fact that an agent x cannot modify the shortest path from s to x by changing its outgoing links since any such shortest path necessarily does not include x (except as target). Moreover, x cannot change the shortest path to any agent y with d(s, y) ≤ d(s, x), because x is necessarily not on the shortest path from s to y. Therefore, the amount of agents ranked above x and the amount of agents ranked equal to x cannot change due to x's manipulations.

To prove FD does not satisfy strong transitivity, consider the graph in Figure 1a. In this graph, x and y are ranked the same, even though P(x) ⊊ P(y), in contradiction to strong transitivity.

Proposition15. The Personalized PageRank ranking systems satisfy self confidence if and only if the damping factor is set to more than 12 . Moreover, Personalized PageRank does not satisfy quasi transitivity, ranked IIA or strong incentive compatibility for any damping factor.

Proof. To prove the that PPR does not satisfy self-confidence for d ≤ 12 , consider the graph in Figure 1b. For any damping factor d, the PPR will be PPR(s) = d and PPR(x) = 1-d. If d ≤ 1 2 then PPR(s) ≤ PPR(x) and thus s ⪯PRd x, in contradiction to the self confidence axiom.

PPR satisfies self-confidence for d > 12 because then PPR(s) ≥ d > 12 , while for all v ∈ V \ {s}, PPR(v) ≤ 1-d < 1 2 .

To prove that PPR does not satisfy strong quasi transitivity and ranked IIA, consider the graph in Figure 1c. The PPR of this graph for any damping factor d is as follows: PPR(s) = d; PPR(a) = d(1-d) 2 ; PPR(b) = d(1-d)2 4 ; PPR(c) = d(1-d)2 2 . Therefore, the ranking of this graph is: b ≺ c ≺ a ≺ s. quasi transitivity is violated because b ≺ c even though P(b) = P(c) = a. This also violates ranked IIA because the ranking profile 〈(1), (1)〉 must be ranked as equal due to trivial comparisons such as a and a.

Strong incentive compatibility is not satisfied, because, in the previous graph, if any of the b agents b′ would have voted for themselves, they would have been ranked b ≺ b′ ≺ c ≺ a ≺ s, which is a strict increase in b′ rank.

Strong transitivity is also satisfied by a natural PRS - the α-Rank system:

Proposition 16. The α-Rank system satisfies self confidence and strong transitivity, but does not satisfy ranked IIA or strong incentive compatibility

4 ACharacterization Theorem

In order to characterize the systems satisfying the aforementioned axioms, we need to define some stronger properties that, as we will show, are implied by the combination of the axioms.

We start by defining stronger notions of transitivity:

Definition 17. Let F be a PRS. We say that F satisfies weak maximum transitivity if for all graphs G = (V,E), for all sources s ∈ V and for all vertices v1, v2 ∈ V \ {s}: Let m1,m2 be the maximally ranked vertices in P(v1), P(v2)

respectively. Assume m1 ⪯ m2. Then, v1 ⪯ v2. F further satisfies strong maximum transitivity if when m1 ≺ m2 then also v1 ≺ v2.

The distance PRS FD can be seen as a member in a family of PRSs that rank the agents first according to their distance from the source. We define this property below:

Definition 18. Let F be a PRS. We say that F satisfies the distance property if for all graphs G = (V, E), for all sources s ∈ V and for all vertices v1, v2 ∈ V \ {s}, if d(s, v1) < d(s, v2) ⇒ v1 ≻ v2.

The distance property and distance PRS are strongly linked to the new notions of strong quasi transitivity:

Proposition 19. Let F be a PRS that satisfies weak maximum transitivity and self confidence. Then, F satisfies the distance property. Furthermore, a PRS F satisfies strong maximum transitivity and self confidence if and only if F is the distance system FD.

We now claim that weak maximum transitivity is implied by the combination of the axioms presented above.

Theorem 20. Let F be a PRS that satisfies self confidence, strong quasi transitivity, RIIA and strong incentive compatibility. Then, F satisfies weak maximum transitivity.

The proof of Theorem 20 is involved, and thus we only supply a sketch of the proof.

Proof. (Sketch) In order to show that F satisfies weak maximum transitivity, we will show that for every comparison profile 〈(a1, a2, . . . , ak), (b1, b2, . . . , bl)〉 where ak ̸= bl the ranking must be consistent with weak maximum transitivity. We do this by building a special graph for each profile. Figure 2 contains such a graph for the profile 〈(1, 4), (2, 2, 3)〉.

We shall now demonstrate the proof for this graph. Assume for contradiction that (1, 4) ≼ (2, 2, 3). Note that by strong quasi transitivity and self confidence, 0 ≃ 0′ ≺ · · · ≺ 4 ≃ 4′ ≺ s. Therefore a and b satisfy this comparison profile, and from our assumption a ⪯ b. By strong quasi transitivity, a ⪰ 3, and thus from our assumption also b ⪰ 3. Now consider the point of view of agent 3. She can perform a manipulation by not voting for b. This manipulation must not improve her relative rank. As the relative ranks of the numbered agents and s are unaffected by this manipulation, it cannot affect the ranks of a and b relative to 3, and thus after the edge (3, b) is removed, we still have b ⪰ 3. The same is true for agent 2 with regard to the edge (2, b), maintaining b ⪰ 2. After removing these links, b is pointed to by only agent 2′ and thus is ranked b ≃ 1′ ≺ 2, in contradiction to b ⪰ 2.

The same idea could be applied to any comparison profile 〈(a1, a2, . . . , ak), (b1, b2, . . . , bl)〉 where ak ̸= bl, thus completing the proof.

Theorem 20 provides us with an important result where a set of simple and basic axioms lead us to the satisfication of a strong property. This theorem is especially important since this property limits our scope of PRSs to those that satisfy the distance property:

Corollary 21. Let F be a PRS that satisfies self confidence, strong quasi transitivity, RIIA and strong incentive compatibility. Then, F satisfies the distance property.

5 Relaxing the Axioms

We shall now prove the conditions in Theorem 20 are all necessary by showing PRSs that satisfy each three of the four conditions, but do not satisfy weak maximum transitivity. Some of these systems are quite artificial, while others are interesting and useful.

Proposition 22. There exists a PRS that satisfies strong quasi transitivity, RIIA and strong incentive compatibility, but not self confidence nor weak maximum transitivity.

Proof. Let F - D be the PRS that ranks strictly the opposite of

the depth system FD. That is, v1 ⪯F - D G,s v2 ⇔ v2 ⪯FD G,s v1. The proof F - D satisfies strong quasi transitivity, RIIA and strong incentive compatibility follows the proof of Proposition 14, with the following rule for ranking comparison profiles:

F - D does not satisfy self confidence, because, by definition s is weaker than all other agents, and does not satisfy weak maximum transitivity because in graph from Figure 1a, F - D ranks x and y equally even though the strongest predecessor of y, which is x, is stronger than the strongest predecessor of x, which is s.

This PRS is highly unintuitive, as the most trusted agents are the ones furthest from the source, which is by itself the least trusted. Relaxing strong quasi transitivity leads to a PRS that is almost trivial:

Proposition 23. There exists a PRS that satisfies self confidence, ranked IIA and strong incentive compatibility, but not strong quasi transitivity nor weak maximum transitivity.

Proof. Let F be the PRS which ranks for every G = (V, E), for every source s ∈ V , and for every v1, v2 ∈ V \ {s}: v1 ≃ v2 ≺ s. That is, F ranks s on the top, and all of the other agents equally. F trivially satisfies self confidence, RIIA and strong incentive compatibility, as s is indeed stronger than all other agents and every comparison profile is ranked equally. F does not satisfy strong quasi transitivity or weak maximum transitivity, because in a chain of vertices starting from s all except s will be ranked equally,

5.1 Relaxing Ranked IIA

When Ranked IIA is relaxed, we find a new ranking system that ranks according to the distance from s, breaking ties according to the number of paths from s. This system can be seen as a version of PGP's trust system, when manipulating certificate levels and trust ratings globally to convert the binary trust system to a PRS.

Notation 24. Let G = (V,E) be some directed graph and v1, v2 ∈ V be some vertices, we will use nG(v1, v2) to denote the number of simple directed paths in G between v1 and v2.

Definition 25. The Path Count PRS FP is defined as follows: Given a graph G = (V,E) and a source s, for all v1, v2 ∈ V \ {s}:

Proposition 26. The path count PRS FP satisfies self confidence, strong quasi transitivity and strong incentive compatibility, but not ranked IIA nor weak maximum transitivity.

5.2 Relaxing incentive compatibility

When we relax incentive compatibility we find an interesting family of PRSs that rank the agents according to their indegree, breaking ties by comparing the ranks of the strongest predecessors. These recursive in-degree systems work by assigning a rational number trust value for every vertex, that is based on the following idea: rank first based on the indegree. If there is a tie, rank based on the strongest predecessor's trust, and so on. Loops are ranked as periodical rational numbers in base (n + 2) with a period the length of the loop, only if continuing on the loop is the maximally ranked option.

The recursive in-degree systems differ in the way different in-degrees are compared. Any monotone increasing mapping of the in-degrees could be used for the initial ranking. To show these systems are well-defined and that the trust values can be calculated we define these systems algorithmically as follows:

Definition 27. Let r : {1, . . . , n} ↦→ {1, . . . , n} be a monotone nondecreasing function. The recursive in-degree PRS with rank function r is defined as follows: Given a graph G = (V, E) and a source s,

where value is the function defined in Algorithm 1, and 0 is the function V ↦→N that maps every vertex in G to zero.

Fact 28. The recursive in-degree PRS IDr with rank function r, when r is constant (r ≡ r0) is exactly equal to the distance PRS (IDr ≡ FD).

An example of the values assigned for a particular graph and source when r is the identity function is given in Figure 3. As n = 8, the values are decimal. Note that the loop (b, d) generates a periodical decimal value(b, r, 0) = 0.32 by the division in step 5 in Algorithm 1 (where h′ (b) = 32; m = 99).

Algorithm 1 The recursive in-degree algorithm

Procedure value(x, r, h) - returns numeric trust of node x under weight function r given previously seen nodes h:

1. If x = s: return n n+2 .
2. Let d := r(|P(x)|).
3. Let

1. If h(x) = 0:
2. (a) Return 1 n+2 [d + max{value(x, h′ , r)|p ∈ P (x)}]
3. Otherwise:
4. (a) Let m= min{(n+2)k - 1|(n + 2)k > h′ (x)}.
5. (b) Return h′ (x)/m.

Proposition 29. For every nondecreasing rank function r : {1, . . . , n} ↦→ {1, . . . , n} which is not constant, the recursive in-degree PRS IDr satisfies self confidence, strong quasi transitivity and ranked IIA, but not strong incentive compatibility nor weak maximum transitivity.

6 Concluding Remarks

We have presented a method for the evaluation of personalized ranking systems by using axioms adapted from the ranking systems literature, and evaluated existing and new personalized ranking systems according to these axioms. As most existing PRSs do not satisfy these axioms, we have presented several new and practical personalized ranking systems that satisfy subsets, or indeed all, of these axioms. We argue that these new ranking systems have a more solid theoretical basis, and thus may very well be successful in practice.

Furthermore, we have proven a characterization theorem that limits the scope of the search for ranking systems satisfying all axioms, and shows that any system which satisfies all these axioms, must have certain strong properties, and indeed must rank according to the distance rule.

This study is far from exhaustive. Further research is due in formulating new axioms, and proving representation theorems for the various PRSs suggested in this paper. An additional avenue for research is modifying the setting in order to accommodate for more elaborate input such as trust/distrust relations or numerical trust ratings, as seen in some existing personalized ranking systems used in practice.