Scoring of web pages and tournaments-axiomatizations. (English) Zbl 1132.91418
Summary: Consider a set of elements which we want to rate using information about their bilateral relationships. For instance sports teams and the outcomes of their games, journals and their mutual citations, web sites and their link structure, or social alternatives and the tournament derived from the voters’ preferences. A wide variety of scoring methods have been proposed to deal with this problem. In this paper we axiomatically characterize two of these scoring methods, variants of which are used to rank web pages by their relevance to a query, and academic journals according to their impact. These methods are based on the Perron-Frobenius theorem for non-negative matrices.
MSC:
| 91B14 | Social choice |
References:
| [1] | Arrow KJ (1963) Social Choice and Individual Values, 2nd ed, Yale University Press, New Haven |
| [2] | Brin S, Page L (1998) The anatomy of large-scale hypertextual web search engine. Computer Networks 30(1-7):107–117 |
| [3] | Chakrabarti S, Dom B, Gibson D, Kleinberg J, Kumar R, Raghavan P, Rajagopalan S, Tomkins A (1999) Hypersearching the web. Scientific American (June issue) |
| [4] | Conner GR, Grant CP (2000) An extension of Zermelo’s model for ranking by paired comparisons. Eur J Appl Math 11:225–247 · Zbl 1042.05022 · doi:10.1017/S0956792500004150 |
| [5] | Daniels HE (1969) Round-robin tournament scores. Biometrika 56:295–299 · doi:10.1093/biomet/56.2.295 |
| [6] | David HA (1987) Ranking from unbalanced paired-comparison data. Biometrika 74:432–436 · Zbl 0618.62077 · doi:10.1093/biomet/74.2.432 |
| [7] | David HA (1988) The Method of Paired Comparisons, 2nd ed, Charles Griffin and Company, London · Zbl 0665.62075 |
| [8] | Elo AE (1978) The Rating of Chess Players, Past and Present. Arco Publishing Inc |
| [9] | Freidlin MI, Wentzell AD (1998) Random Perturbations of Dynamical Systems, 2nd ed, Springer, Berlin Heidelberg New York · Zbl 0922.60006 |
| [10] | Henriet D (1985) The Copeland choice function: an axiomatic characterization. Social Choice and Welfare 2:49–63 · Zbl 0602.90010 · doi:10.1007/BF00433767 |
| [11] | Herings J-J, van der Laan G, Talman D (2001) Measuring the power of nodes in digraphs. Discussion paper · Zbl 1088.90505 |
| [12] | Kano M, Sakamoto A (1985) Ranking the vertices of a paired comparison digraph. SIAM Journal on Algebraic and Discrete Methods 6:79–92 · Zbl 0572.05030 · doi:10.1137/0606009 |
| [13] | Keener JP (1993) The Perron–Frobenius theorem and the ranking of football teams. SIAM Review 35:80–93 · Zbl 0788.62064 · doi:10.1137/1035004 |
| [14] | Kemeny JG, Snell JL (1976) Finite Markov chains. Springer, Berlin Heidelberg New York |
| [15] | Kendall MG (1955) Further contributions to the theory of paired comparisons. Biometrics 11:43–62 · doi:10.2307/3001479 |
| [16] | Kleinberg J (1999) Authoritative sources in a hyperlinked environment. J ACM 46:604–632 · Zbl 1065.68660 · doi:10.1145/324133.324140 |
| [17] | Laslier J (1997) Tournament solutions and majority voting. Springer, Berlin Heidelberg New York · Zbl 0948.91504 |
| [18] | Levchenkov VS (1995) Self-consistent rule for group choice. I: Axiomatic approach. Discussion Paper 95–3, Conservatoire National des Arts et Métiers |
| [19] | Merlin V, Saari DG (1996) Copeland method I: dictionaries and relationships. Economic Theory 8:51–76 · Zbl 0852.90044 |
| [20] | Moon JW (1968) Topics on tournaments. Holt, Rinehart and Winston, New York · Zbl 0191.22701 |
| [21] | Moon JW, Pullman NJ (1970) On generalized tournament matrices. SIAM Review 12:384–399 · Zbl 0198.03804 · doi:10.1137/1012081 |
| [22] | Moulin H (1988) Axioms of cooperative decision making. Cambridge University Press, Cambridge, UK · Zbl 0699.90001 |
| [23] | Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: Bringing order to the web. Technical report, Stanford University |
| [24] | Palacios-Huerta I, Volij O (2002) The measurement of intellectual influence · Zbl 1137.91582 |
| [25] | Pinski G, Narin F (1976) Citation influence for journal aggregates of scientific publications: theory, with applications to the literature of physics 12:297–312 |
| [26] | Rubinstein A (1980) Ranking the participants in a tournament. SIAM J Appl Math 38:108–111 · Zbl 0442.05028 · doi:10.1137/0138009 |
| [27] | Saari DG (2001) Decisions and elections: explaining the unexpected. Cambridge University Press · Zbl 1049.91037 |
| [28] | Saaty TL (1980) The analytic hierarchy process: planning, priority setting, resource allocation. McGraw Hill · Zbl 0587.90002 |
| [29] | Sen A (1970) Individual choice and social welfare. Holden Day · Zbl 0227.90011 |
| [30] | Thomson W (2000) Consistent allocation rules. Mimeo, University of Rochester |
| [31] | van den Brink, Gilles R (2000) Measuring domination in directed networks. Soc Networks 22:141–157 · doi:10.1016/S0378-8733(00)00019-8 |
| [32] | Wei T (1952) The algebraic foundation of ranking theory. Ph.D Thesis, Cambridge University |
| [33] | Zermelo E (1929) Die Berechnung der Turnier–Ergebnisse als ein Maximalproblem der Wahrscheinlichkeitsrechnung. Math Z 29:436–460 · JFM 54.0543.01 · doi:10.1007/BF01180541 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
