טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAlon Altman
SubjectThe Axiomatic Approach to Ranking Systems
DepartmentDepartment of Industrial Engineering and Management
Supervisor Full Professor Tennenholtz Moshe
Full Thesis textFull thesis text - English Version


Abstract

The ranking of agents based on other agents' input is fundamental to multi-agent systems and has become a central ingredient of a variety of Internet sites. The setting of ranking systems introduces a new social choice model where the set of agents and the set of alternatives coincide.


The theory of social choice consists of two complementary axiomatic perspectives: The descriptive perspective, where given a particular rule for the aggregation of individual rankings into a social ranking finds a set of axioms that are sound and complete for that rule; and the normative perspective, where a set of requirements is devised, and we and try and find whether there is a social aggregation rule that satisfies these requirements.


In this thesis, we apply both these approaches to the ranking systems setting. We begin by applying the descriptive approach and providing a representation theorem for the well-known PageRank algorithm. We show a set of five axioms which uniquely imply an idealized version of PageRank.


In the normative perspective, we begin by defining two important properties of ranking systems. We prove an impossibility result for satisfying these two properties together, but show that when the one of the axioms is weakened, both can be satisfied by an interesting ranking system. We formally define this ranking system and provide an efficient algorithm for its computation.


Still in the normative approach, we tackle the issue of incentives. We consider the case where a self-interested agent may try and manipulate its votes in order to improve its position in the ranking. We prove a full classification of the existence of incentive compatible ranking systems under four very basic axioms, each with a weak and a strong version. As this classification indicates that no reasonable ranking system can be fully incentive compatible, we expand our discussion to quantifying the level of incentive compatibility of ranking systems. In that setting we prove positive as well as negative results.


Finally, we present a variation of ranking systems where a personalized ranking is generated for every participant in the system. We adapt several axioms from the general ranking systems setting and prove a surprisingly positive result — a representation theorem for the systems which satisfy all of these axioms. We further show that all of the axioms are required for this proof, while relaxing any axiom leads to new personalized ranking systems.