Football Group Draw Methods and Probabilities
[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:
- Eu: UEFA (Europe) -- either 1 or 2 teams in each group
- SA: CONMEBOL (South America) -- maximum 1 team per group
- NA: CONCACAF (North/Central America) -- maximum 1 team per group
- As: AFC (Asia) -- maximum 1 team per group
- Af: CAF (Africa) -- maximum 1 team per group
- Oc: OFC (Oceana) -- maximum 1 team per group
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 a
computer program
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.