×

Bayesian locally optimal design of knockout tournaments. (English) Zbl 1134.62015

Summary: The elimination or knockout format is one of the most common designs for pairing competitors in tournaments and leagues. In each round of a knockout tournament, the losers are eliminated while the winners advance to the next round. Typically, the goal of such a design is to identify the overall best player. Using a common probability model for expressing relative player strengths, we develop an adaptive approach to pairing players each round in which the probability that the best player advances to the next round is maximized. We evaluate our method using simulated game outcomes under several data-generating mechanisms, and compare it to random pairings, to the standard knockout format, and to two variants of the standard format.

MSC:

62F15 Bayesian inference
62K05 Optimal statistical designs
90C27 Combinatorial optimization
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bradley, R. A.; Terry, M. E., The rank analysis of incomplete block designs. 1. The method of paired comparisons, Biometrika, 39, 324-345 (1952) · Zbl 0047.12903
[2] Cook, W. J.; Rohe, A., Computing minimum-weight perfect matchings, INFORMS J. Comput., 11, 138-148 (1999) · Zbl 1040.90539
[3] Critchlow, D. E.; Fligner, M. A., Paired comparison, triple comparison, and ranking experiments as generalized linear models, and their implementation in GLIM, Psychometrika, 56, 517-533 (1991) · Zbl 0850.62574
[4] Crouch, E. A.C.; Spiegelman, D., The evaluation of integrals of the form \(\int f(t) \exp(- t^2) d t\): application to logistic normal models, J. Amer. Statist. Assoc., 85, 464-469 (1990) · Zbl 0716.65137
[5] David, H. A., The Method of Paired Comparisons (1988), Chapman and Hall: Chapman and Hall London · Zbl 0665.62075
[6] Davis, P. J.; Rabinowitz, P., Methods of Numerical Integration (1975), Dover: Dover New York · Zbl 0154.17802
[7] Dellaportas, P.; Smith, A. F.M., Bayesian inference for generalized linear and proportional hazards models via Gibbs sampling, Appl. Statist., 42, 443-459 (1993) · Zbl 0825.62409
[8] Edmonds, J., Paths, trees and flowers, Canad. J. Math., 17, 449-467 (1965) · Zbl 0132.20903
[9] Edwards, C. T., Non-parametric procedure for knockout tournaments, J. Appl. Statist., 25, 375-385 (1998) · Zbl 0930.62048
[10] Gabow, H.N., 1973. Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. Thesis, Stanford University.; Gabow, H.N., 1973. Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. Thesis, Stanford University.
[11] Gabow, H. N.; Tarjan, R. E., Faster scaling algorithms for general graph matching problems, Journal of the ACM, 38, 815-853 (1991) · Zbl 0799.68145
[12] Genz, A., Numerical computation of multivariate normal probabilities, J. Comput. Graph. Statist., 1, 141-149 (1992)
[13] Glickman, M. E., Parameter estimation in large dynamic paired comparison experiments, Appl. Statist., 48, 377-394 (1999) · Zbl 0939.62071
[14] Glickman, M. E., Dynamic paired comparison models with stochastic variances, J. Appl. Statist., 28, 673-689 (2001) · Zbl 0991.62048
[15] Glickman, M. E.; Jensen, S. T., Adaptive paired comparison design, J. Statist. Plann. Inference, 127, 279-293 (2005) · Zbl 1083.62001
[16] Harris, W. P., A revised law of comparative judgment, Psychometrika, 22, 189-198 (1957)
[17] Herbrich, R., Graepel, T., 2006. TrueSkill™: a Bayesian skill rating system. Technical report MSR-TR-2006-80, Microsoft Research.; Herbrich, R., Graepel, T., 2006. TrueSkill™: a Bayesian skill rating system. Technical report MSR-TR-2006-80, Microsoft Research.
[18] Hwang, F. K., New concepts in seeding knockout tournaments, Amer. Math. Monthly, 89, 235-239 (1982) · Zbl 0486.05031
[19] Lindley, D. V., Bayesian Statistics—A Review (1972), SIAM: SIAM Philadelphia · Zbl 0246.62009
[20] Lovász, L.; Plummer, M. D., Matching Theory (1986), Akadémia i Kiadoó: Akadémia i Kiadoó Budapest · Zbl 0618.05001
[21] Marchand, E., On the comparison between standard and random knockout tournaments, The Statistician, 51, 169-178 (2002)
[22] McNemar, Q., Note of the sampling error of the difference between correlated proportions or percentages, Psychometrika, 12, 153-157 (1947)
[23] Mosteller, F., Remarks on the method of paired comparisons: I. The least squares solution assuming equal standard deviations and equal correlations, Psychometrika, 16, 3-9 (1951)
[24] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical Recipes in Fortran 77: The Art of Scientific Computing (1997), Cambridge University Press: Cambridge University Press New York
[25] Schwenk, A. J., What is the correct way to seed a knockout tournament?, Amer. Math. Monthly, 107, 140-150 (2000) · Zbl 0981.05054
[26] Thurstone, L. L., A law of comparative judgment, Psychol. Rev., 34, 273-286 (1927)
[27] Zellner, A.; Rossi, P. E., Bayesian analysis of dichotomous quantal response models, J. Econometrics, 25, 365-393 (1984) · Zbl 0575.62092
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.