Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-18T21:13:12.097Z Has data issue: false hasContentIssue false
  • English
  • Français

WINNER PLAYS STRUCTURE IN RANDOM KNOCKOUT TOURNAMENTS

Published online by Cambridge University Press:  05 December 2018

Yang Cao  and
Sheldon M. Ross
Yang Cao
Affiliation:
Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA E-mail: [email protected]; [email protected]
Sheldon M. Ross
Affiliation:
Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA E-mail: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Suppose there are n players, with player i having value vi > 0, and suppose that a game between i and j is won by i with probability vi/(vi + vj). In the winner plays random knockout tournament, we suppose that the players are lined up in a random order; the first two play, and in each subsequent game the winner of the last game plays the next in line. Whoever wins the game involving the last player in line, is the tournament winner. We give bounds on players’ tournament win probabilities and make some conjectures. We also discuss how simulation can be efficiently employed to estimate the win probabilities.

Keywords

negatively associatedrandom knockout tournamentwinner plays
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 33 , Issue 4 , October 2019 , pp. 500 - 510
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Adler, I., Cao, Y., Karp, R., Pekoz, E. & Ross, S.M. (2016). Random knockout tournaments. arXiv preprint arXiv:1612.04448, Accepted for publication on Operations Research.Google Scholar
2.Chung, F.R.K. & Hwang, F.K. (1978). Do stronger players win more knockout tournaments? Journal of the American Statistical Association 73(363): 593–596.Google Scholar
3.Joag-Dev, K. & Proschan, F. (1983). Negative association of random variables with applications. The Annals of Statistics 11(1): 286–295.Google Scholar
4.Marchand, , É, . (2002). On the comparison between standard and random knockout tournaments. Journal of the Royal Statistical Society: Series D (The Statistician) 51(2): 169–178.Google Scholar
5.Maurer, W. (1975). On most effective tournament plans with fewer games than competitors. The Annals of Statistics 3(3): 717–727.Google Scholar
6.Ross, S. & Ghamami, S. (2008). Efficient simulation of a random knockout tournament. Journal Industrial and Systems Engineering 2: 88–96.Google Scholar