Efficient Simulation of a Random Knockout Tournament

Document Type : Research Paper

Authors

Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA, USA

Abstract

We consider the problem of using simulation to efficiently estimate the win probabilities for participants in a general random knockout tournament. Both of our proposed estimators, one based on the notion of “observed survivals” and the other based on conditional expectation and post-stratification, are highly effective in terms of variance reduction when compared to the raw simulation estimator. For the special case of a classical 2n -player random knockout tournament, where each survivor of the previous round plays in the current round, a second conditional expectation based estimator is introduced. At the end, we compare our proposed simulation estimators based on a numerical example and in terms of both variance reduction and the time to complete the simulation experiment. Based on our empirical study, the method of “observed survivals” is the most efficient method.

Keywords

Main Subjects

References

[1] Chung F.R.D., Hwang F.K. (1978), Do stronger players win more knockout tournaments?; J.
Am. Statist. Ass. 73; 593-596.
[2] David H.A. (1959), Tournaments and Paired comparisons; Biometrika 46; 139-149.
[3] Edwards C.T. (1996), Double-elimination tournaments: Counting and calculating; Amer.
Statistician 50; 27-33.
[4] Glasserman P. (2004), Monte Carlo Methods in Financial Engineering; Springer.
[5] Glenn W.A. (1960), A comparison of the effectiveness of tournaments; Biometrika 47; 253-
262.
[6] Horen J., Riezman R. (1985), Comparing draws for single elimination tournaments;
Operations Research 33; 249-262.
[7] Hwang F.K. (1982), New concepts in seeding knockout tournaments; Am. Math. Monthly
107; 140-150.
[8] Marchand E. (2002), On the comparison between standard and knockout tournaments; The
Statistician 51(2); 169-178.
[9] Ross and Schechner (1985) Ross S.M., Schechner Z. (1985), Using Simulation to
Estimate First Passage Distribution; Management Science 31(2).
[10] Ross S.M. (2006), SIMULATION; fourth ed.; Academic Press.
[11] Searls D.T. (1963), On the probability of winning with different tournament procedures; J.
Amer. Stat. Assoc.58; 1064-1081.

Files

History

  • Receive Date: 30 July 2006
  • Revise Date: 02 March 2007
  • Accept Date: 30 April 2007

Share

How to cite

Statistics