Single elimination tournament design using dynamic programming algorithm

yusri ikhwani; As`ary Ramadhan; Muhammad Bahit; Taufik Hidayat Faesal

doi:10.30812/matrik.v23i1.3290

yusri ikhwani Universitas Islam kalimantan Muhammad Arsyad Al Banjari, Banjarmasin, Indonesia
As`ary Ramadhan Universitas Islam kalimantan Muhammad Arsyad Al Banjari, Banjarmasin, Indonesia
Muhammad Bahit Politeknik Negeri Banjarmasin, Banjarmasin, Indonesia
Taufik Hidayat Faesal Universiti Tun Hussein Onn, Johor, Malaysia

DOI: https://doi.org/10.30812/matrik.v23i1.3290

Keywords: Algorithm, Dynamic Programming, Optimization, Single Elimination, Tournament

Abstract

Finding the best single-elimination tournament design is important in scientific inquiry because it can have major financial implications for event organizers and participants. This research aims to create an optimal single-elimination tournament design using binary tree modeling with dummy techniques. Dynamic programming algorithms have been used to compute optimal single-elimination designs to overcome this effectively. This research method uses various implementations of sub-optimal algorithms and then compares their performance in terms of runtime and optimality as a solution to measure the comparison of sub-algorithms. This research shows that the difference in relative costs produced by various sub-algorithms with the same input is quite low. This is expected because quotes are generated as integer values from a small interval 1, ≤ 9, whereas costs tend to reach much higher values. From the comparison of these sub-algorithms, the best results among the sub-optimal algorithms were obtained in the Sub Optimal algorithm 3. We present the experimental findings achieved using the Python implementation of the suggested algorithm, with a focus on the best single-elimination tournament design solution.

Downloads

Download data is not yet available.

References

[1] P. Manurangsi and W. Suksompong, “Fixing Knockout Tournaments With Seeds,” IJCAI International Joint Conference on
Artificial Intelligence, pp. 412–418, 2022.
[2] M. P. Kim, W. Suksompong, and V. V. Williams, “Who Can Win a Single-Elimination Tournament?” pp. 1–13, 2018.
[3] L. Csat´o, “A simulation comparison of tournament designs for theWorld Men’s Handball Championships,” International Transactions
in Operational Research, vol. 28, no. 5, pp. 2377–2401, 2021.
[4] E. C. Olymphic, “New Study on the Economic impact of Sport released by the European Commission,” 2020.
[5] R. Hulett, “Single-elimination brackets fail to approximate Copeland winner,” Leibniz International Proceedings in Informatics,
LIPIcs, vol. 145, no. 13, pp. 1–13, 2019.
[6] Y. Ikhwani, K. Marzuki, and A. Ramadhan, “Automated University Lecture Schedule Generator based on Evolutionary Algorithm,”
vol. 22, no. 1, pp. 127–136, 2022.
[7] J. Kuo and J. W. Sheppard, “Tournament Topology Particle Swarm Optimization,” 2021 IEEE Congress on Evolutionary Computation,
CEC 2021 - Proceedings, pp. 2265–2272, 2021.
[8] F. Spieksma, R. Pendavingh, and R. Lambers, “How to Design a Stable Serial Knockout Competition,” 2022.
[9] K. Gokcesu and H. Gokcesu, “Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament
Design,” pp. 1–6, 2022.
[10] D. B˘adic˘a, A., B˘adic˘a, C., Buligiu, I., Ciora, L.I., Logoftu, “Optimal Knockout Tournaments: Definition and Computation,” in
International Conference on Large-Scale Scientific Computing, 2022.
[11] F. Della Croce, G. Dragotto, and R. Scatamacchia, “On fairness and diversification in WTA and ATP tennis tournaments generation,”
Annals of Operations Research, vol. 316, no. 2, pp. 1107–1119, 2022.
[12] J. Guyon, “Choose your opponent: A new knockout design for hybrid tournaments,” Journal of Sports Analytics, vol. 8, no. 1,
pp. 9–29, 2021.
[13] H. Aziz, S. Gaspers, S. Mackenzie, N. Mattei, P. Stursberg, and T. Walsh, “Fixing balanced knockout and double elimination
tournaments,” Artificial Intelligence, vol. 262, no. May, pp. 1–14, 2018.
[14] A. Karpov, “Generalized knockout tournament seedings,” International Journal of Computer Science in Sport, vol. 17, no. 2,
pp. 113–127, 2018.
[15] P. Bhumipol, N. Makaje, T. Kawjaratwilai, and R. Ruangthai, “Match analysis of professional Muay Thai fighter between
winner and loser,” Journal of Human Sport and Exercise, vol. 18, no. 3, pp. 657–669, 2023.
[16] B. R. Sziklai, P. Bir´o, and L. Csat´o, “The efficacy of tournament designs,” Computers and Operations Research, vol. 144, no.
February, 2022.
[17] T. Stojadinovi´c, “On catalan numbers,” Teaching of Mathematics, vol. 18, no. 1, pp. 16–24, 2015.
[18] O. Banias, “Test case selection-prioritization approach based on memoization dynamic programming algorithm,” Information
and Software Technology, vol. 115, no. June, pp. 119–130, 2019.
[19] A. B˘adic˘a, C. B˘adic˘a, I. Buligiu, L. I. Ciora, and D. Logoftu, “Dynamic programming algorithms for computing optimal
knockout tournaments,” Mathematics, vol. 9, no. 19, 2021.
[20] D. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, part 1 ed. Boston: Addison-Wesley
Professional, 2011.