×

To stay discovered: on tournament mean score sequences and the Bradley-Terry model. (English) Zbl 1492.60045

The authors give new proofs of two results on mean score sequences in random tournaments. Within an \(n\)-team tournament, write \(x_i\) for the expected number of wins by team \(i\). The mean score sequence is then \((x_i,1\leq i\leq n)\).
The first result, due to H. Joe [Ann. Stat. 16, No. 2, 915–925 (1988; Zbl 0721.62067)] is within the framework of the Bradley-Terry model, in which the probability that team \(i\) beats team \(j\) in a given match is given by \(L(\lambda_i-\lambda_j)\), where \(L(\cdot)\) is the standard logistic function, and \(\lambda_i\) and \(\lambda_j\) are parameters associated with teams \(i\) and \(j\), respectively. Joe’s result is that essentially all mean score sequences can be obtained from the Bradley-Terry model. More precisely, that the closure of the set of score sequences from the Bradley-Terry model in \(\mathbb{R}^n\) is the set of all score sequences. Here the authors give new, probabilistic proofs of this result.
Secondly, the authors give a new, constructive proof of a result due to J. W. Moon [Pac. J. Math. 13, 1343–1345 (1963; Zbl 0133.13303)] that an increasing sequence of \(n\) real numbers is a mean score sequence of some random tournament if and only if it is majorized by \((0,1,\ldots,n-1)\). The authors further use this as a starting point to discuss the construction of joint distributions in the representation theorem for convex ordering.

MSC:

60E15 Inequalities; stochastic orderings
60C05 Combinatorial probability
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D., Elo ratings and the sports model: a neglected topic in applied probability?, Statist. Sci., 32, 4, 616-629 (2017) · Zbl 1383.60057
[2] Bang, C. M.; Sharp Jr., H., An elementary proof of Moon’s theorem on generalized tournaments, J. Combin. Theory Ser. B, 22, 3, 299-301 (1977) · Zbl 0357.05048
[3] Brualdi, R. A.; Hwang, S.-G.; Pyo, S.-S., Vector majorization via positive definite matrices, Linear Algebra Appl., 257, 105-120 (1997) · Zbl 0874.15019
[4] Chao, K.-M.; Wong, C. S., Applications of \(M\)-matrices to majorization, Linear Algebra Appl., 169, 31-40 (1992) · Zbl 0757.15009
[5] Cruse, A. B., On linear programming duality and Landau’s characterization of tournament scores, Acta Universitatis Sapientiae, Informatica, 6, 21-32 (2014) · Zbl 1297.05097
[6] Fishburn, P. C., Binary choice probabilities: on the varieties of stochastic transitivity, J. Math. Psych., 10, 327-352 (1973) · Zbl 0277.92008
[7] Hirsch, F.; Profeta, C.; Roynette, B.; Yor, M., (Peacocks and Associated Martingales, with Explicit Constructions. Peacocks and Associated Martingales, with Explicit Constructions, Bocconi & Springer Series, vol. 3 (2011), Springer: Springer Milan; Bocconi University Press, Milan), xxxii+384 · Zbl 1227.60001
[8] Joe, H., Majorization, entropy and paired comparisons, Ann. Statist., 16, 2, 915-925 (1988) · Zbl 0721.62067
[9] Király, F. J.; Qian, Z., Modelling competitive sports: Bradley-Terry-Elo models for supervised and on-line learning of paired competition outcomes (2017), preprint available at arXiv:1701.08055
[10] Landau, H. G., On dominance relations and the structure of animal societies. III. The condition for a score structure, Bull. Math. Biophys., 15, 143-148 (1953)
[11] Marshall, A. W.; Olkin, I.; Arnold, B. C., (Inequalities: Theory of Majorization and Its Applications. Inequalities: Theory of Majorization and Its Applications, Springer Series in Statistics (2011), Springer, New York), xxviii+909 · Zbl 1219.26003
[12] Moon, J. W., An extension of Landau’s theorem on tournaments, Pacific J. Math., 13, 1343-1345 (1963) · Zbl 0133.13303
[13] Moon, J. W.; Pullman, N. J., On generalized tournament matrices, SIAM Rev., 12, 384-399 (1970) · Zbl 0198.03804
[14] Shah, N. B.; Balakrishnan, S.; Guntuboyina, A.; Wainwright, M. J., Stochastically transitive models for pairwise comparisons: statistical and computational issues, IEEE Trans. Inform. Theory, 63, 2, 934-959 (2017) · Zbl 1364.94253
[15] Shaked, M.; Shanthikumar, J. G., (Stochastic Orders and Their Applications. Stochastic Orders and Their Applications, Probability and Mathematical Statistics (1994), Academic Press, Inc.: Academic Press, Inc. Boston, MA), xvi+545 · Zbl 0806.62009
[16] Strassen, V., The existence of probability measures with given marginals, Ann. Math. Stat., 36, 423-439 (1965) · Zbl 0135.18701
[17] Thörnblad, E., Another proof of Moon’s theorem on generalised tournament score sequences (2016), preprint available at arXiv:1605.06407
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.