Axiomatic Foundations for Ranking Systems

Alon Altman, Moshe TennenholtzJAIR 2008 · DOI · OpenReview

Introduction

In classical social choice theory, such as the study of political elections, there is a clear distinction between the set of voters and the set of candidates. Arrow’s Impossibility Theorem famously demonstrated that no voting system can satisfy a specific set of fairness criteria simultaneously. However, the rise of the internet has introduced a new paradigm: systems where the voters and candidates are the same entities. In Google’s PageRank, a webpage "votes" for another via a hyperlink; in peer-to-peer networks, users rate each other to build reputations. This paper applies the rigorous axiomatic approach of social choice theory to these modern ranking systems to determine if a "perfect" ranking algorithm is mathematically possible.

The Axiomatic Framework

The authors define several formal mathematical requirements (axioms) that an ideal ranking system should follow. These axioms are designed to capture intuitive notions of fairness and consistency in a directed graph where nodes represent agents and edges represent votes.

  1. Transitivity: This axiom posits that if agent $A$’s voters are ranked higher than agent $B$’s voters, then $A$ should be ranked higher than $B$. This captures the "prestige" effect—the idea that a vote from a highly-ranked source should carry more weight than a vote from a low-ranked source.
  2. Ranked Independence of Irrelevant Alternatives (RIIA): This requires that the relative ranking of two agents should depend only on the ranks of the agents who voted for them, rather than the specific identities of those voters or other global graph properties.
Figure 1: A directed graph representing a ranking system where nodes act as both voters and candidates, illustrating the complex interdependencies in prestige-based ranking.

The Impossibility of Perfect Ranking

The central finding of this research is a surprising impossibility theorem. The authors prove that Transitivity and RIIA are mutually exclusive. Any system that attempts to account for the "quality" of voters (Transitivity) must necessarily sacrifice the property that rankings are determined solely by the ordinal rank of predecessors (RIIA).

This conflict explains why popular algorithms often fail one of these tests. For instance, Approval Voting (ranking agents simply by their total number of votes) satisfies RIIA but completely ignores the quality of the voters, thus failing Transitivity. Conversely, PageRank successfully captures the quality of voters but fails RIIA because its calculations are influenced by the out-degree of voters (how many other links a page provides), which is considered "irrelevant" information under the RIIA axiom.

Figure 2: A cyclic graph structure. Such cycles present significant challenges for maintaining consistent ordinal rankings in recursive systems like PageRank.

Key Results and Alternatives

Beyond the impossibility result, the paper provides several significant contributions to the field:

  • Theorem 5.1 (Impossibility): Formally proves that no general ranking system can satisfy even a weakened version of Transitivity alongside RIIA. This result is robust, persisting even in restricted environments like bipartite graphs.
  • Axiomatization of Approval Voting: The paper offers the first complete axiomatic characterization of Approval Voting using the RIIA property.
  • Recursive In-degree Algorithm: To address the impossibility, the authors propose a new algorithm. By relaxing the transitivity requirement, the "Recursive In-degree" system ranks agents first by their total votes, then breaks ties by recursively examining the ranks of their highest-ranked voters. This algorithm is computationally efficient, with a complexity of $O(|V| \cdot |E|)$.

Conclusion and Future Work

While the search for a "perfect" ranking system is constrained by mathematical impossibility, this work establishes the trade-offs inherent in algorithm design. Future research may expand this framework to include cardinal scores (rather than just ordinal rankings), dynamic systems where links change over time, and game-theoretic models to prevent strategic manipulation by agents seeking to artificially inflate their own ranks.

Summary updated

BibTeX
@article{altman2008axiomatic,
  author = {Alon Altman and Moshe Tennenholtz},
  title = {{Axiomatic Foundations for Ranking Systems}},
  journal = {J. Artif. Intell. Res.},
  year = {2008},
  doi = {10.1613/jair.2306},
}

Loading related content...

Figure