International Journal of Scientific & Engineering Research, Volume 6, Issue 1, January-2015 102

ISSN 2229-5518

Scheduling the fixtures for the African Cup of Nations Football Tournament: A “no seeding” approach

Oluwaseun A. Otekunrin, Charles O. Aminobiren

Abstract—In this study, we designed an alternative schedule, which excludes seeding, for the African Cup of Nations (AFCON) Football

Tournament. Assuming all other constraints and factors are as arranged by AFCON tournament organizers, a simple random sampling without replacement technique was used to randomly allocate the 16 qualified teams to n = 4 preliminary groups: A, B, C, D; 4 teams per

group. The concept of symmetric Latin square design was used to schedule the teams’ preliminary stage group matches. The quarter-final, semi-final and final stage matches were scheduled using tournament designs. In the resulting schedule which excludes seeding, the teams have equal probability of being assigned to any of the preliminary groups in the tournament. This is an advantage over the schedule being used by AFCON presently.

Index Terms— Seeding, Simple random sampling without replacement, Symmetric Latin square, Tournament Designs, Tournament scheduling.

1 INTRODUCTION

——————————  ——————————
ournament scheduling has become an important area of research in recent years. According to [1], professional sporting activities have become a lucrative business and
the quality of the schedules greatly determines the amount of revenue accruable to sport organizations. The design of a schedule is determined by many factors. This includes facility availability, time, number of entries and other special con- straints. These factors contribute to the level of complexity involved in the construction of the schedules. Different meth- ods, which include combinatorial, constraint and integer pro- gramming and so on are used for constructing tournament schedules. Some of these methods can be found in [2], [3], [4], [5], [6], [7], [8]. The major types of tournament scheduling, including round-robin and single elimination tournament scheduling types, are discussed in [9].
Tournament scheduling using combinatorial designs have received a lot of attention in literature. Orthogonal Latin squares were applied to the scheduling of golf tournaments in [10]-[12]. Orthogonal Latin squares were also applied in [13] to the scheduling of a round robin for mixed doubles table tennis (MDTT) tournament of order n where a team of n men and n women opposes another team of n men and n women, equivalent to two orthogonal Latin squares. Constructions on self-orthogonal Latin squares with symmetric orthogonal ma- tes (SOLSSOMs) were used to provide schedules for spouse avoiding mixed double round robin (SAMDRR) tournaments

————————————————

• Oluwaseun A. Otekunrin is with the Department of Statistics, University of Ibadan, Nigeria. All correspondences should be directed to her at oa.alawode@mail.ui.edu.ng or seramide2003@yahoo.co.uk

• Charles O. Aminobiren is currently pursuing a masters degree program in

Statistics at the University of Ibadan, Nigeria.

of order 4 ≤ n ≤ 20 in [14]. Latin square was used to sched- ule a SAMDRR tennis tournament of order n ≠ 2, 3, 6 in [15]. A whist tournament was scheduled by [16] using a resolvable balanced incomplete block design RBIBD. A motor speedway

tournament for 4 riders competing in a 20 heat competition was scheduled by [17] using a balanced incomplete block de- sign. Balanced tournament designs (BTD) for all orders were constructed by [18] using recursive constructions and some other techniques from combinatorial design theory. Graph theory was used to design some tournament schedules in [19].
Canonical patterns on a round robin tournament for 2n
teams were constructed by [20].
Seeding is an important aspect of most tournament sched-
ules. According to [21], tournaments can either be seeded or
randomly drawn. Seeding ensures that stronger teams face
weaker teams early in the competition thereby maximizing the
probability that the strongest teams will survive to the end of
the tournament. This leads to a very interesting final match and
huge financial gains for the organizers of the tournament [22]. But this is a major disadvantage for the so called “weaker teams” because they are not given equal opportunity like their “stronger teams” counterparts to display their relative
strengths. On the other hand, in random draws, all teams have equal probability of being allocated to groups for the games. This implies that two highly rated teams can meet early in the competition. It has been shown by [23] that expected effort and win-probabilities in any two-player contest do not rest on the absolute strength (win valuations) of the respective players alone, but also on their relative strengths. Thus, this may lead to more effort and thrill that can produce better performance in the so-called “weaker teams”. Lately, this has come into play as various cases of “upsets” have occurred in international and local tournaments, thereby discouraging the usage of seeding.
In the AFCON tournament presently, seeding is used in the allocation of the 16 qualified teams to preliminary groups. Therefore, the main objective of this study is to design an al-

IJSER © 2015 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 6, Issue 1, January-2015 103

ISSN 2229-5518

ternative schedule, which excludes seeding, for the AFCON tournament that allocates all 16 qualified teams randomly to preliminary groups and then apply the concept of symmetric

3 ROUND ROBIN TOURNAMENTS

A round robin tournament, according to [25] is defined as fol- lows:
Latin square design to schedule the teams’ preliminary group
Given the set Ζ

= {0,1,2, 2n − 1}

(the elements of
matches. Also, we will schedule the quarter-final, semi-final
and final stage matches by using the Single elimination format

2n

which are called teams), a round-robin tournament of or-
coupled with Berger Tables, a round robin algorithm. The

der 2n is a partition into 2n − 1

parts (called rounds) of
constraints, as provided by the organizers, which governed

Ζ , each consisting of 2-subsets (called matches) so that

( 2)

the 2013 AFCON tournament included the following:
each unordered pair in

Ζ 2 n

(the set of all 2-subsets of
• Participating Teams: 16
• Dates: 19 January 2013 to 10 February 2013

Ζ 2 n ) occurs in exactly one part.

This implies that if n is the number of teams, a pure round
• Number of matches: 32 Matches
robin tournament requires

n(n −1)

2 games. If n is even,
•24 Group Stages (6 matches in each group)
then, in each of

(n − 1) rounds, it is possible to play n 2

•8 Knock-out matches

games involving all the n teams. If n is odd, there will be
• Match Days: 17 match days

n rounds, each with (n −1) 2

games, and each team would
• Match Sites: 24 match sites
•2 Matches per day for 16 matches (Group Stages) in
same venue in the same city. The remaining 8 matches
will be played 2 per day but not necessarily the same city.
• Host Cities / Stadiums: 5 Cities, 5 stadiums
• Training Sites
•1 per team (4 per Host City)
•1 for Referees
This present work is however only concerned with the
method for scheduling the fixtures, and assumes that all con-
straints on organizing a successful competition are satisfied.
This paper is divided into five sections. Section 1 contains
the introduction while sections 2 and 3 contain the description
of the AFCON football tournament and round robin tourna-
ments. The methodology is presented in section 4 and the con- clusion is in section 5.

2 AFRICAN CUP OF NATIONS (AFCON) FOOTBALL TOURNAMENT

This tournament is organized by the Confederation of African Football (CAF) and it is held biennially. Sixteen teams, includ- ing the host nation, participate in the tournament. The tour- nament has two stages: the preliminary and the single elimina- tion stages. The teams are seeded into four groups A, B, C, and D, each containing four teams. According to the rules that governed the 2013 edition of the tournament, for instance, the host nation is assigned the first slot in group A while the title holder from the previous edition of the tournament is as- signed the first slot in group C. The remaining 14 teams are ranked based on their performance in the last three editions of the tournament (2008, 2010 and 2012 editions) and points are awarded. Then, random draws are made based on the group- ings of the points to determine the particular group for each of the teams. The top two teams from each group advance to the knockout stage. In this stage, the winner of each group plays against the runner-up of another group. This is followed by the semi-finals, the third-place match (contested by the losing semi-finalists), and the final. The details can be found in [24].
have no game in a particular round.
Generally, a round robin tournament is a tournament
where all teams meet all other teams a fixed number of times.
The fixed number of times may be single, double, triple and quadruple. The AFCON tournament is a combination of round robin and single elimination tournaments. The single round robin tournament pattern is exhibited in its preliminary
stage group matches while the single elimination tournament pattern is exhibited in the Quarter-final, the Semi-final and the Final stage matches of the tournament.
Round robin tournaments can be constructed using tour- nament designs. A starter in a cyclic group is selected as the first column and other columns are derived from it cyclically [26]. Possible schedules of play for 4 and 8 teams respectively are presented in Table I.

TABLE I (a)

A TOURNAMENT DESIGN FOR 4 TEAMS

TABLE I (b)

A TOURNAMENT DESIGN FOR 8 TEAMS

4 METHODOLOGY

We assumed that none of the qualified 16 teams is a “football minnow” since they all emerged from a strict qualifying series of matches played across the continent. Therefore, the teams should have equal chance of being assigned to any of the groups in the preliminary stage. So, there was no seeding of teams according to status as host or according to previous per- formance of the teams. We also assumed that all other con- straints and factors, as determined by the AFCON tournament

IJSER © 2015 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 6, Issue 1, January-2015 104

ISSN 2229-5518

organizers are satisfied.
From the rules governing the 2013 AFCON, sixteen teams
are to participate in the tournament. The steps for designing
the schedules are discussed as follows:

4.1 Preliminary Stage

Step 1: For the 16 teams, use a simple random sampling with- out replacement technique, for instance, a random number generator, to select one team at a time. Place the first team se- lected in group A. Repeat the process placing the second, third and fourth teams selected respectively in Groups B, C and D respectively. Repeat the process until all the teams are allocat- ed to the 4 groups, 4 teams per group. A possible random allo- cation of the team is presented in Table II. This technique en- sures that each possible sample (of equal size) from the popu- lation of teams has exactly the same probability of selection [27].

TABLE II

RANDOM ALLOCATION OF THE 16 TEAMS TO GROUPS

Step 2: Use a symmetric Latin square format [28] to schedule the preliminary stage group matches. Recall that a symmetric Latin square is equivalent to a single round robin tournament

[29]. For each group, the entry in row i and column j gives
the team that opposes i in round j . Each group has n −1 = 3

rounds consisting of (n / 2) = 2 matches each. These are pre- sented in Tables III(a) and (b).

4.2 Single Elimination Stages

The Single Elimination stages comprise the Quarter-final, the
Semi-final and the Final stage matches of the tournament.

(i) Quarter and semi-final Stages:

From the rules governing AFCON tournament, two teams
with the highest number of points from each group in the pre-
liminary stage proceed to the next stage of the competition
which is the quarter-final stage. Then, the winners from the
quarter final stage participate in the semi-final stage.
Let GRPAW1, GRPBW3, GRPCW5, and GRPDW7 represent
the winner in each of Groups A, B, C and D respectively. Simi-
larly, let GRPAR2, GRPBR4, GRPCR6, and GRPDR8 represent
the runner-up in each of Groups A, B, C and D respectively.
Also, let the winner of each of the 1st, 2nd, 3rd and 4th Quarter
final matches be represented by QF1W, QF2W, QF3W and

QF4W respectively. The schedules are drawn using round I of

the tournament designs for 8 and 4 teams respectively. These
are presented in Tables IV and V.

(ii) Final Stage:

Step 3: The losers in the semi-final matches play the third

place match (losers’ final) and the winners play the final match
where the overall winner of the competition emerges. This is
presented in Table VI.

TABLE III (a)

SYMMETRIC LATIN SQUARES FOR EACH OF THE 4 GROUPS

TABLE III (b)

IJSER © 2015 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 6, Issue 1, January-2015 105

ISSN 2229-5518

COMPLETE SCHEDULE FOR THE 16 TEAMS FOR PRELIMINARY STAGE GROUP ROUNDS

TABLE IV

SCHEDULE OF MATCHES FOR THE QUARTER- FINAL STAGE

c. Scheduling of the quarter-final, semi-final and final stage matches using the Berger tables, a round robin algorithm.
In the schedule designed, the teams have equal probability of being assigned to any of the preliminary groups in the tourna- ment. This is an advantage when compared to the schedule be-

ing used by AFCON presently.

1st Quarter final match GRPAW1 vs GRPDR8

TABLE V

SCHEDULE OF MATCHES FOR THE SEMI-FINAL STAGE

TABLE VI

SCHEDULES FOR THE THIRD PLACE AND FINAL MATCHES

5. CONCLUSION

In this study, we designed an alternative schedule, which ex- cludes seeding, for the African Cup of Nations (AFCON) Foot- ball Tournament. We assumed all other constraints and factors are as arranged by AFCON organizers. The following methods were used:
a. Random allocation of the 16 qualified teams to preliminary groups using simple random sampling without replacement (SRSWOR) technique. This ensures that each possible sample (of size 1) from the population of teams has exactly the same probability of selection.
b. Scheduling of the teams’ preliminary stage group matches using the concept of symmetric Latin square design.

REFERENCES

[1] R.V. Rasmussen and M.A. Trick, “Round robin scheduling: A survey,”

European Journal of Operational Research, vol. 188, pp. 617-636, 2008.

[2] A. Bar-Noy and D. Moody, “A Tiling Approach for Fast Implementation of the Travelling Tournament Problem,” PATAT 2006, pp. 351-358, 2006.

[3] M. Henz, T. Muller, and S.Thiel, “Global Constraints for Round Robin Tournament Scheduling,” European Journal of Operational Research, vol. 153, pp. 92-101, 2004.

[4] H. Zhang, “Generating College Conference Basketball Schedules by a Sat Solver,” Proceedings of the Fifth International Symposium on the Theory and Ap- plications of Satisfiability Testing, pp. 281-291, 2002.

[5] F. Della and D. Oliveri, “Scheduling the Italian football league: an ILP –

based approach,” Computers & Operations Research, vol. 33, pp. 1963-74,

2006.

[6] G. Durán, M. Guajardo, J. Miranda, D. Sauré, S. Souyris, and A. Wein- traub, “Scheduling the Chilean soccer league by integer programming,” In- terfaces, vol. 37, pp. 539–52, 2007.

[7] J. Dinitz and D. Froncek, “Scheduling the XFL,” Congressus Numerantium, vol. 147, pp. 5–15, 2000.

[8] T. Bartsch, A. Drexl, and S. Kroger, “Scheduling the professional soccer leagues of Austria and Germany,” Computers & Operations Research, vol. 33, pp. 1907-37, 2006.

[9] J. Byl, Organizing Successful Tournaments. 4th ed. Leeds: Human Kinetics

Publishers; 2014.

[10] D.F. Robinson, “Constructing an annual round-robin tournament played on neutral grounds,” Mathematical Chronicle, vol. 10, pp. 73–82, 1981.

[11] W.D. Wallis, “The Problem of Hospitable Golfers,” Ars Combinatoria, vol.

15, pp. 149 –152, 1983.

[12] J.H. Dinitz, “Designing schedules for leagues and tournaments,” Mathe- matics and Statistics, University of Vermont, Burlington VT, USA, 2004.

[13] W.R. Pulleyblank, “Mixed doubles table tennis tournaments,” Proceedings of the fifth Manitoba Conference on Numerical Mathematics, Utilitas Mathematica Publishing Inc., Winnipeg, pp. 593 – 598, 1975.

[14] P. Burger, J.H. van Vuuren, “Skedulering van gade-vermydende gemeng-

de- dubbels rondomtalie-tennistoernooie,” Die Suid-Afrikaanse Tydskrif vir

Natuurwetenskap en Tegnologie, vol. 28, no. 1, pp. 35–63, 2009. Afrikaans.

[15] R.K. Brayton, D. Coppersmith, and A.J. Hoffman, “Self Orthogonal Latin

Squares of all orders n ≠ 2, 3, 6 ,” Bulletin of the American Mathematical

Society, vol. 80, no. 1, pp. 116 –118, 1974.

[16] D. Anderson and N.J. Finizio, “Whist Tournaments,” Handbook of Combina- torial Designs, C. J. Colbourn and J. H. Dinitz, eds., Boca Raton: CRC Press, pp. 663-668, 2007.

IJSER © 2015 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 6, Issue 1, January-2015 106

ISSN 2229-5518

[17] S.L. Buhl, “Balanced incomplete block designs: Construction of a BIBD,” Department of Mathematical Sciences, Aalborg University, http://www.math.aau.dk/_slb, 2009.

[18] P.J. Schellenberg, G.H.J. van Rees, and S.A.Vanstone, “The existence of

Balanced Tournament Designs,” Ars Combinatoria, vol. 3, pp. 303–318, 1977. [19] D. Froncek, “Scheduling a Tournament,” University of Minnesota, Duluth,

http://www.mathaware.org/mam/2010/essays/FroncekTournament.pdf,

2010.

[20] D. De Werra, “Minimizing irregularities in sports scheduling using graph theory,” Discrete Applied Mathematics vol. 4, pp. 217-226, 1982.

[21] R.G. Noll, “The Organization of Sports Leagues,” SIEPR Discussion Paper No. 02-43, Stanford Institute for Economic Policy Research, Stanford Uni- versity, 2003.

[22] C. Groh, B. Moldovanu, A. Sela, and U. Sunde, “Optimal Seedings in Elim- ination Tournaments,” http://www.econ2.uni bonn.de/pdf/seed- final.pdf, 2008.

[23] M. Baye, D. Kovenock, C. de Vries, “Rigging the Lobbying Process,” Ameri- can Economic Review vol. 83, pp. 289-294, 1993.

[24] Confederation of African Football, “Procedure for the drawing of lots of the

final tournament of the Orange Africa Cup of Nations – South Africa 2013”, http://www.cafonline.com/userfiles/file/comp/CAN2013/procedure_draw_

2013_E.pdf.

[25] M.P.Kidd, “A tabu-search for minimizing the carry-over effects value of a round robin tournament,” Orion, vol. 26, no. 2, pp. 125-141, 2010.

[26] J.H. Dinitz, D. Froncek, E.R. Lamken, and W.D. Wallis, “Scheduling a tour- nament,” Handbook of Combinatorial Designs, C. J. Colbourn and J. H. Dinitz, eds., Boca Raton: CRC Press, pp. 591–606, 2007.

[27] R. Banning, A. Camstra, and P. Knottnerus, Sampling theory-Sampling design and estimation methods, Statistics Netherlands, The Hague/Heerlen, 2012.

[28] C.F. Laywine and G.L. Mullen, Discrete Mathematics using Latin squares.

John Wiley & Sons, New York (NY), 1998.

[29] D. Anderson, “Factorizations of Graphs,” Handbook of Combinatorial Designs,

C. J. Colbourn and J. H. Dinitz, eds., Boca Raton: CRC Press, pp. 740-755,

2007.

IJSER © 2015 http://www.ijser.org