PageRank as a Weak Tournament Solution
We observe that ranking systems—a theoretical framework for web page ranking and collaborative filtering introduced by Altman and Tennenholtz—and tournament solutions—a well-studied area of social choice theory—are strongly related. This relationship perm
- PDF / 366,323 Bytes
- 6 Pages / 430 x 660 pts Page_size
- 96 Downloads / 211 Views
stract. We observe that ranking systems—a theoretical framework for web page ranking and collaborative filtering introduced by Altman and Tennenholtz—and tournament solutions—a well-studied area of social choice theory—are strongly related. This relationship permits a mutual transfer of axioms and solution concepts. As a first step, we formally analyze a tournament solution that is based on Google’s PageRank algorithm and study its interrelationships with common tournament solutions. It turns out that the PageRank set is always contained in both the Schwartz set and the uncovered set, but may be disjoint from most other tournament solutions. While PageRank does not satisfy various standard properties from the tournament literature, it can be much more discriminatory than established tournament solutions.
1
Introduction
The central problem of the literature on tournament solutions is as appealing as it is simple: Given an irreflexive, asymmetric, and complete binary relation over a set, find the “maximal” elements of this set. As the standard notion of maximality is not well-defined in the presence of cycles, numerous alternative solution concepts have been devised and axiomatized [see, e.g., 14, 12]. In social choice theory, the base relation, which we call dominance relation, is usually defined via pairwise majority voting, and many well-known tournament solutions yield attractive social choice correspondences. Recently, a number of concepts have been extended to the more general setting of incomplete dominance relations [9, 17, 6, 5]. These generalized dominance relations are commonly referred to as weak tournaments. Motivated by the problem of ranking web pages based solely on the structure of the underlying link graph, Altman and Tennenholtz [3] introduced the notion of a ranking system, which maps each (strongly connected) directed graph to a complete preorder on the set of vertices. Obviously, this notion is strongly related to that of a tournament solution. In fact, Moulin [14] identifies “ranking the participants of a given tournament” as an important open problem. While little effort has been made so far to solve this problem, this is precisely what ranking systems achieve for strongly connected weak tournaments.
This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/3-1.
X. Deng and F.C. Graham (Eds.): WINE 2007, LNCS 4858, pp. 300–305, 2007. c Springer-Verlag Berlin Heidelberg 2007
PageRank as a Weak Tournament Solution
301
Altman and Tennenholtz do not refer to the vast literature on tournament solutions, and their recent work on ranking systems does not seem to be well known in the tournament community. This is regrettable for two reasons. For one, ranking systems address a problem that has long been neglected in social choice theory. Secondly, both research areas could benefit from a mutual transfer of concepts and axioms. We take a first step in this direction by formally analyzing a tournament solution that is based on Google’s PageRank ranking system.
Data Loading...
