Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-30T19:13:54.750Z Has data issue: false hasContentIssue false

Some Monotone Almost Balanced Knockout Tournament Plans

Published online by Cambridge University Press:  27 July 2009

R. W. Chen
Affiliation:
Department of Mathematics and Computer Science, University of Miami, Coral Gables, Florida 33124
F. K. Hwang
Affiliation:
AT & T Bell Laboratories, Murray Hill, New Jersey 07974
Y. C. Yao
Affiliation:
Department of Statistics, Colorado State University, Fort Collins, Colorado 80523
A. Zame
Affiliation:
Department of Mathematics and Computer Science, University of Miami, Coral Gables, Florida 33124

Abstract

Knockout tournaments are often used in sports (or experiments where preferences are registered by comparisons instead of measurements) to determine the champion of an event. A knockout tournament plan (KTP) for n players is a rooted binary tree with n leaves to be labeled by the n players. Each subtree of two leaves represents a match between the two players labeling the two leaves; the winner of the match then moves on to label the root of the subtree. While there are many KTPs to choose from for a given number of players, in the real world an almost balanced KTP is usually chosen. One reason could be the perception that a balanced KTP is “fair” to the players, in the sense that, given a random labeling of leaves by players, a stronger player has a better chance to win the tournament. Surprisingly, it has been shown that not all KTPs have this property, and it is difficult to prove this property for any general class of KTPs. So far the property has been shown to hold only for balanced KTPs. In this paper we extend it to some classes of almost balanced KTPs.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1993

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.Chen, R. & Hwang, R.K. (1988). Stronger players win more balanced knockout tournaments. Graphs and Combinatorics 4: 9599.CrossRefGoogle Scholar
2.Chung, F.R.K. & Hwang, F.K. (1978). Do stronger players win more knockout tournament? Journal of the American Statistical Association 73: 593596.CrossRefGoogle Scholar
3.Hwang, F.K., Lin, C.C., & Yao, Y.C. (1991). Knockout tournaments with diluted Bradley-Terry preference schemes. Journal of Statistical Planning and Inference 28: 99106.CrossRefGoogle Scholar
4.Israel, R. (1982). Stronger players need not win more knockout tournaments. Journal of the American Statistical Association 76: 950951.CrossRefGoogle Scholar