On the Axiomatic Foundations of Ranking Systems∗Alon Altman and Moshe TennenholtzFaculty of Industrial Engineering and ManagementTechnion – Israel Institute of TechnologyHaifa 32000IsraelAbstractReasoning about agent preferences on a set ofalternatives, and the aggregation of such prefer-ences into some social ranking is a fundamentalissue in reasoning about uncertainty and multi-agent systems. When the set of agents and the setof alternatives coincide, we get the ranking sys-tems setting. A famous type of ranking systemsare page ranking systems in the context of searchengines. In this paper we present an extensiveaxiomatic study of ranking systems. In particu-lar, we consider two fundamental axioms: Tran-sitivity, and Ranked Independence of IrrelevantAlternatives. Surprisingly, we find that there isno general social ranking rule that satisfies bothrequirements. Furthermore, we show that ourimpossibility result holds under various restric-tions on the class of ranking problems consid-ered. Each of these axioms can be individuallysatisfied. Moreover, we show a complete axiom-atization of approval voting using one of theseaxioms. We also briefly consider the issue of in-centives in ranking systems.1 IntroductionThe ranking of agents based on other agents’ input is fun-damental to multi-agent systems (see e.g. [6, 15]). More-over, it has become a central ingredient of a variety of In-ternet sites, where perhaps the most famous examples areGoogle’s PageRank algorithm[13] and eBay’s reputationsystem[14].This basic problem introduces a new social choice model.In the classical theory of social choice, as manifested byArrow[2], a set of agents/voters is called to rank a set of∗Supported in part by grant number 53/03-10.5 from the IsraelScience Foundations.alternatives. Given the agents’ input, i.e. the agents’ indi-vidual rankings, a social ranking of the alternatives is gen-erated. The theory studies desired properties of the aggre-gation of agents’ rankings into a social ranking. In par-ticular, Arrow’s celebrated impossibility theorem[2] showsthat there is no aggregation rule that satisfies some minimalrequirements, while by relaxing any of these requirementsappropriate social aggregation rules can be defined. Thenovel feature of the ranking systems setting is that the setof agents and the set of alternatives coincide. Therefore, insuch setting one may need to consider the transitive effectsof voting. For example, if agent a reports on the impor-tance of (i.e. votes for) agent b then this may influence thecredibility of a report by b on the importance of agent c;these indirect effects should be considered when we wishto aggregate the information provided by the agents into asocial ranking.Notice that a natural interpretation/application of this set-ting is the ranking of Internet pages. In this case, theset of agents represents the set of Internet pages, and thelinks from a page p to a set of pages Q can be viewedas a two-level ranking where agents in Q are preferred byagent(page) p to the agents(pages) which are not in Q. Theproblem of finding an appropriate social ranking in thiscase is in fact the problem of (global) page ranking. Par-ticular approaches for obtaining a useful page ranking havebeen implemented by search engines such as Google[13].The theory of social choice consists of two complementaryaxiomatic perspectives:• The descriptive perspective: given a particular rule rfor the aggregation of individual rankings into a socialranking, find a set of axioms that are sound and com-plete for r. That is, find a set of requirements that rsatisfies; moreover, every social aggregation rule thatsatisfies these requirements should coincide with r. Aresult showing such an axiomatization is termed a rep-resentation theorem and it captures the exact essenceof (and assumptions behind) the use of the particularrule.• The normative perspective: devise a set of require-ments that a social aggregation rule should satisfy, andtry to find whether there is a social aggregation rulethat satisfies these requirements.Many efforts have been invested in the descriptive approachin the framework of the classical theory of social choice. Inthat setting, representation theorems have been presentedto major voting rules such as the majority rule[11] (see[12] for an overview). Recently, we have successfully ap-plied the descriptive perspective in the context of rankingsystems by providing a representation theorem[1] for thewell-known PageRank algorithm [13], which is the basisof Google’s search technology[4].An excellent example for the normative perspective is Ar-row’s impossibility theorem mentioned above. In [17],we presented some preliminary results for ranking systemswhere the set of voters and the set of alternatives coincide.However, the axioms presented in that work consist of sev-eral very strong requirements which naturally lead to animpossibility result.In this paper we provide an extensive study of ranking sys-tems. We introduce two fundamental axioms. One of theseaxioms captures the transitive effects of voting in rankingsystems, and the other adapts Arrow’s well-known inde-pendence of irrelevant alternatives(IIA) axiom to the con-text of ranking systems. Surprisingly, we find that no gen-eral ranking system can simultaneously satisfy these twoaxioms! We further show that our impossibility result holdsunder various restrictions on the class of ranking problemsconsidered. On the other hand, we show that each of theseaxioms can be individually satisfied. Moreover, we use ourIIA axiom to present a positive result in the form of a repre-sentation theorem for the well-known approval voting rank-ing system, which ranks the agents based on the number ofvotes received. This axiomatization shows that when ig-noring transitive effects, there is only one ranking systemthat satisfies our IIA axiom. Finally, we consider the issueof incentives in ranking systems, and demonstrate that theissue of incentive compatibility cannot be easily tackled.This paper is structured as follows: Section 2 formally de-fines our setting and the notion of ranking systems. Sec-tions 3 and 4 introduce our axioms of Transitivity andRanked Independence of Irrelevant Alternatives respec-tively. Our main impossibility result is presented in Sec-tion 5, and further strengthened in Section 6. Our positiveresult, in the form of an axiomatization for the ApprovalVoting ranking system in presented in