Football Group Draw Methods and Probabilities

by Gareth O. Roberts and Jeffrey S. Rosenthal, March 2022

[To skip straight to the World Cup draw simulations, click here. See also this Toronto Star article and UofT News Q&A and CBC article and the actual 2022 draw.]

Introduction:

This web page discusses the probabilities when drawing groups for the FIFA World Cup between national football (i.e. soccer) teams. It explains how traditional draws do not give equal probabilities to all valid group assignments. It also provides several methods of implementing draws with equal probabilities, while still keeping them transparent and entertaining.

Football draws are very important and popular, and are even televised. They are also challenging to conduct, and have sometimes had major problems, as in this 1982 video or the blunder which arose in the (different) 2021 UEFA draw. But what is less well known is that even when no major problems arise, the draws still do not give equal probabilities to all possible valid configurations. This can lead to various changes (see below) in the probabilities for which teams are matched up with which other teams.

World Cup Draw Rules:

The World Cup takes place every four years. A total of 32 teams qualify, from around the world. They are put into 4 different pots of 8 teams each, based on ranking. The 32 teams then have to be assigned to 8 different groups, each consisting of one team from each of the 4 pots, to determine the matches in the initial round. The host team is always put in Pot 1 and in Group A. The other 31 teams are then assigned randomly, subject to restrictions based on which world region they are located in, as follows:

The FIFA Sequential Method:

Assigning the 32 teams to the 8 groups while following the above restrictions is not such a simple task. FIFA accomplishes the draw using a sequential algorithm of their own invention, which is described in detail this video for the 2018 draw, and in this document (pdf) for the 2022 draw which will be held on 1 April 2022. In brief, the FIFA sequential algorithm selects teams one at a time randomly from the four pots in order, and assigns each new team to the next available group, i.e. the first group which will not conflict with the above restrictions. This assignment must be done carefully, since putting a team in a seemingly available group might lead to unavoidable conflict later on.

In addition, the FIFA method leads to different probabilities, since not all valid assignments are equally likely to occur (as noted here and here and here and here). For example, we compute that in the 2018 World Cup, the probability that England would be in the same group as Germany should have been 9.2%, but increased to 9.5% using the FIFA method. And in the 2022 World Cup (now updated with the final pots as of 31 March 2022), the probability that England is in the same group as Germany should be 10.6%, but increases to 11.8%; that Germany is in the same group as Qatar should be 13.6%, but decreases to 12.5%; that Canada is with Qatar should be 15.4%, but increases to 16.5%; and that USA is with Qatar should be just 9.0% (since the many European teams in Pot 2 would tend to be placed with non-European teams from Pot 1), but increases to 12.5% (a relative increase of 39%).

To deal with this problem of unequal probabilities, we now present three different ways to get uniform draws in which every valid configuration has the exact same chance of occuring.

Our Rejection-Sampler Single Draw Solution:

To obtain football draws with equal probabilities, the simplest way is to use a "rejection sampler", which assigns the teams completely randomly, but then rejects that assignment and starts again if any restriction is violated. When it finally produces an assignment in which all restrictions are satisfied, then it outputs that assignment as a valid equal-probability single draw.

Click here (and then 'Single Draw') to try out our World Cup 2018 or 2022 rejection-sampler draw.

Since this algorithm provides perfect uniform samples, it also allowed us to compute the above probability changes in FIFA's sequential algorithm. We did so by running the C computer program drawprobs.c to generate many random simulations of each method -- the perfect uniform draws and the FIFA sequential draws -- and compare the frequency of different matchups under the two different methods.

Our Multiple-Balls Solution:

The above Rejection-Sampler solution works perfectly, but it is not exciting to watch, and it requires viewers to "trust" the computer to sample correctly. As an alternative, we propose another method which still provides perfect uniform draws, but does so by selecting balls at random for each position in a sequential manner which could be viewed or televised like the usual FIFA draws.

This method fills in the groups one team at a time. At each step, the computer generates a collection of "balls" corresponding to all the teams who could potentially occupy the next spot. One of those balls is then chosen at random, either manually or by computer. Once all spots are filled, it provides a complete draw with the correct uniform probabilities.

Click here (and then 'Balls Update') to try out our World Cup 2018 or 2022 multiple-balls draw.

Our Swapping Solution:

Finally, we present an entirely different method of generating a draw with uniform probabilities. This method begins with a Rejection Sampler uniform sample as above. Then, it repeatedly chooses two teams at random, and "swaps" their group assignments if that swap does not violate any of the restrictions. (This is in fact a Metropolis algorithm.) As more swaps are performed, the overall group assignment continues to change randomly, with probabilities that are uniform over all valid assignments.

If desired, a large number of initial swaps could be performed quickly by a computer. Then, a certain fixed number of final swaps could be performed manually, by physically selecting balls from urns to determine which two teams are selected next for possible swap. The final assignment would then be whatever configuration remains after the final manual swap has been performed.

Click here (and then 'one' or '+') to try out our World Cup 2018 or 2022 swapping draw.

Summary:

The FIFA sequential method of generating football draws does not give the correct probabilities. As an alternative, we have presented three different methods (Rejection-Sampler, Multiple-Balls, and Swapping), which can all be tried interactively, to create football draws with equal probabilities for all valid draws. We hope that FIFA will consider adopting one of our methods in the future.

This web page is by Gareth O. Roberts and Jeffrey S. Rosenthal, March 2022.