Contents ↑

• The laws of the game
  • Matching up
• How FIFA didn’t do it
  • It’s not random
  • It’s not lexicographic
  • It’s not greedy
  • It’s not rest days
• How FIFA did it
• This is not a coincidence
  • The key idea
  • A two-dimensional illustration
  • Numerics
• Where’d they come from?
  • Was the fix in?
  • Why weren’t they public?
• Appendix: better bounds
  • Improving d
  • Improving m

Reverse-engineering FIFA's giant World Cup lookup table

INT. FIFA HEADQUARTERS - ZURICH, SWITZERLAND - NIGHT

An INTERN enters, clutching a printout.

            INTERN
“Sir, we have the score from Algeria vs. Austria. Somehow, it’s a tie: 3-3.”

GIANNI INFANTINO’s chair turns slowly, revealing him first in side profile and then head-on.

            GIANNI INFANTINO
“The time has come. Execute option six-seven.”

---

I’m not quite sure that’s how it actually played out, but at some point on June 27, 2026, somebody at FIFA finalized the standings of the twelve third-place teams at the 2026 World Cup. The top eight third-place teams, which came from groups B, D, E, F, I, J, K, and L, would continue into the knockout stage. But who would their opponents be?

To answer that, we had to turn to Annexe C of the 2026 FIFA World Cup regulations. In that eighteen-page appendix, FIFA laid out which third-place team would fill each of the eight slots in the 32-team knockout bracket depending on which set of eight groups produced qualifying third-place teams. (FIFA calls these sets options; we’ll use the term scenarios.) Since there were twelve groups, but only eight slots, FIFA had to specify slot assignments in $\binom{12}{8} = 495$ different scenarios, explaining the absurd length of Annexe C.

Once we knew which eight groups produced a qualifying third-place team (i.e., which scenario we were in), we could look through Annexe C to figure out which matchups we were going to get. Despite the ten thousand articles and videos apparently required to explain it to sports fans, this procedure is pretty straightforward: it’s just a lookup table. But nobody seemed to be able to figure out how the lookup table was generated.

“Two-thirds of the 12 first-place finishers are scheduled to face a grab bag of third-place teams based on what’s literally an indecipherable algorithm.” (Nate Silver)

To be fair, Silver’s use of “indecipherable” may refer not just to the lookup table but also to the placement of the third-place slots in the 32-team knockout bracket. We don’t tackle the latter problem here at all. That said, @me, Nate.

“It’s unclear exactly how the permutations were decided.” (Sportico)

“I’m guessing from the distinct lack of success at that exact task from the online tools, there is no such algorithm. […] if there was a set of rules that would produce that table and only that table, they wouldn’t need the table.” (Sports StackExchange)

“No-one seems to have been able to reverse-engineer the table to work out exactly why the combinations are determined this way. There is no simple explanatory rule.” (Reddit, r/Aleague subreddit)

Today, we’ll do just that.

---

The laws of the game

Let’s get started by making sure we understand what Annexe C actually tells us. For each group winner (1E, 1A, 1I, 1D, 1G, 1L, 1B, 1K) that was to face a third-place team, FIFA prescribed five possible groups that the third-place team might come from: the shaded cells in the table below.

It’s not completely clear how FIFA chose the allowable groups for each slot. Some matchups seem to be forbidden for easily-explainable reasons:

• No round-of-32 rematches of group stage games (red ● circles).
• No potential round-of-16 rematches (orange ● circles).
• No games where one team has fewer than four days of rest (purple ● circles).

Other exclusions have murkier explanations:

• Games where the rest disparity would be three days or more (blue ● circles) seem to be mostly excluded. The only exception to this rule is the potential 1B-3J matchup.
• Potential quarterfinals rematches (yellow ● circles). These clearly aren’t completely excluded, but around half of the otherwise-inexplicably-excluded matchups could give rise to potential quarterfinals matchups.

Whatever FIFA’s logic, the table above tells us which matchups could happen. Annexe C tells us which matchups would happen.

Matching up

For every scenario, FIFA had to choose pairings between the first-place teams and third-place teams. Some scenarios offered few choices: for example, scenario ABCDGJKL offered only three.

It turns out that this is the minimum number of possible choices of pairings across all scenarios. Other scenarios, however, offered far more: scenario BCDEFHIJ offered 214 different choices of pairings, the maximum of any scenario.

This is the entirety of the data contained in Annexe C: for every one of the 495 possible scenarios, a choice of pairings—what computer scientists would call a perfect matching—between the eight group winners and the eight third-place teams.

We can count how many perfect matchings there are in each scenario. Multiplying these counts together tells us that there were

$$\left. \begin{array}{l} 167{,}757{,}057{,}085{,}640{,}477{,}975{,}149{,}600{,}620{,}947{,}010{,}751{,}043{,}006{,}477{,}670{,}791{,} \\ 982{,}287{,}050{,}837{,}234{,}444{,}257{,}384{,}780{,}085{,}706{,}075{,}639{,}277{,}408{,}101{,}051{,}690{,} \\ 905{,}654{,}122{,}717{,}067{,}025{,}651{,}670{,}949{,}622{,}241{,}051{,}775{,}029{,}354{,}642{,}125{,}370{,} \\ 187{,}921{,}884{,}728{,}446{,}264{,}180{,}870{,}595{,}366{,}847{,}713{,}485{,}539{,}260{,}342{,}302{,}211{,} \\ 650{,}765{,}289{,}097{,}763{,}907{,}529{,}896{,}412{,}634{,}969{,}420{,}419{,}400{,}913{,}528{,}169{,}798{,} \\ 851{,}523{,}245{,}434{,}355{,}168{,}549{,}374{,}442{,}953{,}394{,}765{,}351{,}656{,}026{,}674{,}744{,}304{,} \\ 721{,}126{,}125{,}655{,}488{,}700{,}817{,}875{,}346{,}143{,}719{,}081{,}249{,}967{,}806{,}650{,}064{,}212{,} \\ 004{,}288{,}054{,}850{,}237{,}325{,}855{,}601{,}887{,}079{,}651{,}302{,}827{,}954{,}317{,}831{,}713{,}992{,} \\ 226{,}530{,}987{,}599{,}278{,}065{,}271{,}438{,}760{,}186{,}098{,}264{,}950{,}799{,}706{,}911{,}216{,}280{,} \\ 532{,}242{,}931{,}509{,}977{,}883{,}154{,}820{,}033{,}896{,}724{,}185{,}188{,}958{,}312{,}971{,}589{,}505{,} \\ 777{,}664{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,} \\ 000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000{,}000 \end{array} \right\} \approx 2^{2130}$$

possible ways to choose one perfect matching per scenario. So how did FIFA do it?

---

How FIFA didn’t do it

Before we explain how FIFA did choose the 495 perfect matchings, let’s rule out some plausible-but-wrong explanations. (If you want to skip to the actual explanation, click here.) This will help us better understand the shape of the problem before we present the actual procedure FIFA used.

It’s not random

Anybody who’s spent time staring at Annexe C knows instinctively that it isn’t random. But how can we actually argue that it isn’t?

Let’s assign each third-place team (3A-3L) a color. Then we’ll pick a random matching per scenario, and plot the eight qualifying third-place team colors in a column ordered by the first-place team each was matched with. Finally, we’ll join together all 495 such columns. When we do that, we get plots that look like this:

There’s some structure here, like the mostly-purple bar at the bottom, but not much. The bar is there because whenever 3L qualifies, it can only be paired with 1K, whose opponent occupies the bottom row in the image above.

Now let’s do the same procedure for the choice of matchings that Annexe C makes:

It should be visually obvious that the plot for Annexe C is far from random, even granting that the random plot has structure of its own. But visually obvious and quantitatively rigorous aren’t quite the same thing, so let’s do some statistics.

Consider the natural null model: in each scenario, FIFA picked uniformly at random among that scenario’s valid matchings, independently across scenarios. Under this null, let’s examine the assignment-frequency table, which counts, given a choice of matchings for every scenario, how many of the 495 scenarios prescribe each matchup. Here’s the table from the random choice of matchings we used to produce the plot above:

Fix a particular matchup: say 1I-3F. In each of the $\binom{11}{7} = 330$ scenarios where team 3F qualifies, we can calculate exactly what fraction of the valid matchings pair 1I and 3F. That fraction is the null model’s probability of prescribing the matchup in that scenario, which makes the total count of 1I-3F matchups under the null model a sum of 330 independent Bernoulli variables with known, unequal probabilities: that is, a Poisson-binomial distribution. We can calculate the expected value (56.4) of this Poisson-binomial distribution by adding up these probabilities, and can exactly compute tail probabilities via dynamic programming.

When we do the tail-probability calculations for every matchup in the random choice of matchings above, we get pretty reasonable numbers. The table below shows, for each possible matchup, the negative base-2 logarithm of the smaller of the two tail probabilities.

The biggest value here is a 7, which corresponds to a tail probability of roughly $2^{-7} = 1/128$. That’s barely even a surprise among a selection of eighty tail probabilities.

Now let’s look at Annexe C. Here’s the assignment-frequency table:

Here are the analogous tail-probability logarithms for Annexe C.

Let’s look again at the 1I-3F matchup. The expected number of times this matchup occurs under the null model is 56.4. Annexe C prescribes the 1I-3F matchup 276 times. The tail probability here is $2^{-539}$. That’s ridiculous. $2^{-539}$ is barely even an actual number. No $2^{-539}$ event has ever happened in the history of the observable universe.

Annexe C isn’t random.

It’s not lexicographic

The lone concrete conjecture I found in the wild is from an answer on Sports StackExchange: namely, that the table can be generated by

“a simple exercise of filling up a table by picking the first available possibility for each match, going from left to right.”

It’s worth being explicit about how the post’s proposed procedure works. We start by picking a scenario. We then make all forced pairings—e.g., if 3L qualifies it has to play 1K—in the given scenario. Next, we work through the remaining slots by match number from §12.6 of the regulations. For each slot, we simply pick the first available third-place team alphabetically.

This procedure may not always produce a complete pairing, as it’s possible that earlier choices could leave us with no choices at some later step. If we backtrack appropriately, however, we’ll just end up choosing the lexicographically minimal valid matching. So let’s call that our procedure. Does it match FIFA’s?

The StackExchange post’s author checked this procedure against Options 1 and 2 in Annexe C, found it produced the correct matchings, and noted that checking the other 493 would require a script. I wrote a script. It did not go well for the conjecture.

To give the poster some credit, the first seven options in Annexe C agree with the output of this procedure, even though they only checked the first two. The chances of getting Options 3-7 correct if you picked matchings at random are one in 3.9 million, so the poster’s proposed procedure is really, really good! It’s also wrong.

The procedure first fails on Option 8, where the lexicographic rule matches 1L-3H, 1D-3I, and 1G-3J. FIFA, on the other hand, matches 1L-3I, 1D-3J, and 1G-3H, which no “grab the first thing available” rule could produce.

Of course, it’s possible that FIFA processes the slots in some other order. Happily, this is checkable: for each of the $8! = 40320$ slot orderings, we can ask whether FIFA’s matching is the lexicographically-minimal valid matching with respect to that processing order in all 495 options. No lexicographic rule made it past the first ten options of Annexe C.

It’s not greedy

A slightly-more-sophisticated version of the lexicographic conjecture above is to let the preference order vary per slot. As an example, perhaps for slot 1A’s opponent we prefer 3C to 3F (in order to equalize rest days), but for slot 1I’s opponent we prefer 3F to 3C (which would also minimize rest-day discrepancy). Then the procedure would proceed over slots in some order, with each slot taking its most-preferred still-available qualified third-place team (with look-ahead so nobody gets stranded). The search space here is enormous: $8!$ match-processing orders times $(5!)^8$ preference profiles is about 1.7 sextillion such procedures, which is way too many to enumerate. It turns out that we don’t have to enumerate, though: we can show that no such procedure can work by looking at revealed preferences.

Here’s the idea. Let’s fix a processing order for slots: say EAIDGLBK, as in our tables. In every one of the 495 scenarios, slot 1E gets its first choice of the qualified third-place teams. Now slot 1E can be paired with 3A, 3B, 3C, 3D, or 3F. Looking at Option 4 of Annexe C tells us that slot 1E prefers 3D to 3F, because 3F was available but slot 1E was paired with 3D. Similarly, Option 18 tells us that slot 1E prefers 3C to 3D. Unfortunately, Option 19 tells us that slot 1E prefers 3D to 3C. Hence there can be no consistent global preference for slot 1E if it is processed first.

We’ve just ruled out one-eighth of the $8!$ possible slot-processing orders with a few lines of logic. With a fair few lines of code, we can build up preference graphs for each slot and check to see if any have cycles (which would mean no consistent global preference order).

In fact, every slot’s preferences have cycles which could easily have been found by hand:

• Slot 1A can’t be processed first: it prefers 3F to 3I in Options 327, but prefers 3I to 3F in Options 56.
• Slot 1B swaps 3E/3F preferences between Options 33 and 487.
• Slot 1D swaps 3E/3F preferences between Options 31 and 270.
• Slot 1E swaps 3C/3D preferences between Options 18 and 19.
• Slot 1G swaps 3A/3I preferences between Options 166 and 286.
• Slot 1I swaps 3C/3G preferences between Options 82 and 397.
• Slot 1K swaps 3E/3J preferences between Options 42 and 362.
• Slot 1L swaps 3H/3J preferences between Options 126 and 246.

So no slot has consistent global preferences, which means no slot can be processed first. No such greedy algorithm exists. We can run the same trick to verify that FIFA doesn’t go column-by-column either.

This is perhaps our most important negative result, so let’s make sure we understand exactly what it says. FIFA’s choice of opponent for a slot cannot be a function of just that slot’s options. The same slot, facing the same available third-place teams, picks differently depending on what the other slots face. No procedure that fills in the bracket one match at a time can generate Annexe C. Local optimization is ruled out.

It’s not rest days

We know FIFA cares a great deal about rest days, so it’s worth ruling out a couple of simple algorithms that use that information. Local optimization is out, but perhaps some sort of global optimization survives?

First, let’s note that it makes no sense to maximize total rest. This is because total rest is determined entirely by which scenario we’re in: the number of rest days for the group winner is known, and the number of rest days for the third-place team is simply the date of the match minus the date of that group’s finale. Add these up and we get the sum of the dates of the knockout matches minus the sum of the dates of the qualifying groups’ finales, which clearly depends only on which groups qualified. So every single possible matching maximizes (and minimizes!) total rest.

But there are other ways to account for rest. Here are two reasonable possibilities:

• We could try to pick a matching that maximizes the minimal number of rest days. For example, suppose one of the three matchings in scenario ABCDGJKL gives every third-place team at least five days’ rest, and the other two give one third-place team four days’ rest. Then we’d pick the one with minimum rest five days.
• We could penalize games with four days’ rest a lot, penalize games with five days’ rest a little less, and so on up to eight days’ rest, then try to minimize the sum of these rest penalties.
  Importantly, we could perhaps penalize games with eight days’ rest more, not less: aren’t commentators always complaining about rust too?

Unfortunately, neither possibility works:

• Only 394 of the 495 prescribed matchings maximize the minimal number of rest days. Even this large number is mostly due to team 3K being forced to play 1L whenever they qualify, which forces the minimal number of rest days to be 4 no matter what valid matching we choose. If we instead considered trying to lexicographically maximize the sorted list of rest days, which tends to equalize rest across the qualified third-place teams, FIFA’s chosen matching gives the best possible list of rest days in only 35 of 495 scenarios.
• There’s no set of meaningful rest penalties $r_4, r_5, r_6, r_7, r_8$ such that FIFA’s chosen matching minimizes the sum of the rest penalties in every scenario. For every scenario, the chosen matching $M$ gives some inequality of the form $$\sum_{d=4}^8 m_dr_d \le \quad\min_{\substack{\text{matchings }M' \\ \text{in the scenario}}} \quad\sum_{d=4}^8 m'_dr_d,$$ where $M'$ ranges over the other valid matchings in the scenario and $m_d$, $m'_d$ count how many games the matchings $M$, $M'$ have with $d$ rest days. When we write down all these inequalities, we get a linear program whose only solutions are $r_d = a\cdot d + b$. The $b$-term is meaningless—it’s just a constant extra penalty—and the $a\cdot d$ term is meaningless because $\sum_d m_d d$ is just the total rest, which (as we saw above) is constant once we’ve fixed a scenario. So these degenerate solutions don’t separate any matchings: they tell us nothing at all.

So it’s not rest days—or, at least, it’s not just rest days. What could it be?

---

How FIFA did it

The greedy-algorithm refutation above showed that however FIFA picked matchings, it wasn’t purely a local optimization procedure. The rest-days refutation showed that it wasn’t a global optimization procedure based solely on rest days. So let’s enlarge our space of hypotheses.

Not all of the forty FIFA-allowed pairings in our table are created equal. Not only are there rest-day discrepancies, there’s also travel distance to consider. Most groups’ third-place matches took place in cities that were close to one another, allowing us to assign a consistent “third-place team travel penalty” to each potential pairing of third-place team and venue. We might also assign some sort of “rematch penalty” to pairings that could produce quarterfinals or semifinals rematches.

This is starting to look like a per-pairing penalty—or, with the opposite sign, a per-pairing score. So perhaps FIFA’s matchings are just the ones with the best possible sum of scores. Let’s ask the question:

Is there some set of numbers we can put in the forty potential pairings so that every matching prescribed by Annexe C maximizes the total score of its pairings (among all valid matchings for that scenario)?

This question, finally, has a positive answer. Here’s one such set of numbers:

It may seem like we pulled these numbers out of thin air. They’re actually the result of a complicated mix of linear programming and alternating projection. Rather than get side-tracked, though, let’s see how these numbers get used in scenario ABCDGJKL, the three-matching example from earlier.

When we sum up the red weights, we get 162. The green weights give us a sum of 160, and the blue weights give us a sum of 167. And indeed, scenario ABCDGJKL corresponds to option 431 in Annexe C, which prescribes the blue matching. The weights in the table above give rise to a unique maximum-weight matching for every one of the 495 possible scenarios, and every single maximum-weight perfect matching agrees with Annexe C.

So that’s it. That’s the problem solved, right? Not so fast, my friend!

---

This is not a coincidence

We should be a little bit suspicious of this solution: forty arbitrary weights is a lot of freedom. Perhaps no matter what choices of matchings FIFA made, it would always be possible to find a set of forty weights that explain the matchings via maximum-weight perfect matching?

This turns out to be very, very, very false. Almost no choices of matchings admit weights that do this, and there’s some really neat math that explains why.

Here’s how to think about it. Let’s consider an arbitrary weight vector $$\mathbf{w} = \left(w_1, w_2, \cdots, w_{40}\right)$$ where we number the potential pairings 1-40 from top-to-bottom then left-to-right in the table above. As a concrete example, our valid weight vector from the table above has $w_1 = 3$, $w_2 = 1$, $w_{21} = 23$, and $w_{40} = 37$.

Let’s also form matching vectors, which have ones in the positions corresponding to the eight pairings in the matching and zeroes elsewhere. As a concrete example, the red matching vector $\mathbf{m}_{red}$ has ones at positions 1, 6, 12, 16, 25, 30, 33, and 40, and zeroes everywhere else.

Then the sum of weights for a particular matching is simply the dot product of its matching vector with the weight vector. So the fact that the blue matching has maximal sum is equivalent to the two inequalities $$\langle \mathbf{w}, \mathbf{m}_{red} \rangle < \langle \mathbf{w}, \mathbf{m}_{blue} \rangle, \qquad \qquad \langle \mathbf{w}, \mathbf{m}_{green} \rangle < \langle \mathbf{w}, \mathbf{m}_{blue} \rangle,$$ which we’ll rearrange to read $$\langle \mathbf{w}, \mathbf{m}_{blue} - \mathbf{m}_{red} \rangle > 0, \qquad \qquad \langle \mathbf{w}, \mathbf{m}_{blue} - \mathbf{m}_{green} \rangle > 0.$$

So scenario ABCDGJKL, which has three valid matchings, gives us two half-space constraints (i.e., inequalities of the form $\langle \mathbf{w}, \mathbf{x}\rangle > 0$) on the weight vector. Similarly, scenario BCDEFHIJ, which has 214 valid matchings, gives us 213 half-space constraints coming from differences between the maximal matching and the other 213 non-maximal matchings. Across all 495 scenarios, there are a total of 13,939 possible valid matchings, so we get 13,444 half-space constraints in $\mathbb{R}^{40}$ of the form $$\langle \mathbf{w}, \mathbf{m}_1-\mathbf{m}_2 \rangle > 0.$$

Any other choice of matchings also gives us 13,444 half-space constraints. Unfortunately, the new constraints will not use the exact same set of 13,444 hyperplanes. To see this, let’s suppose that FIFA had instead chosen the green matching in scenario ABCDGJKL. In that case, we’d get the half-space constraints $$\langle \mathbf{w}, \mathbf{m}_{green} - \mathbf{m}_{red} \rangle > 0, \qquad \qquad \langle \mathbf{w}, \mathbf{m}_{green} - \mathbf{m}_{blue} \rangle > 0.$$ We still get information about the hyperplane normal to $\mathbf{m}_{green} - \mathbf{m}_{blue}$, but we don’t get information about the hyperplane normal to $\mathbf{m}_{red} - \mathbf{m}_{blue}$: instead, we get information about the hyperplane normal to $\mathbf{m}_{red} - \mathbf{m}_{green}$.

The key idea

Let’s step back for a second and figure out where we’re going. We’re trying to argue that a random choice of matchings admitting a valid weight vector is a very unlikely event. To do so, we’re going to want to count, or at least upper-bound, the number of choices of matchings that do admit a weight vector.

Now, given a choice of matchings admitting a weight vector, we get a bunch of half-space constraints on said weight vector, so it has to live in the nonempty region in $\mathbb{R}^{40}$ cut out by those half-space constraints.

A different choice of matchings coming from a weight vector gives us different half-space constraints along a different set of hyperplanes. Importantly, the two regions cut out by the constraints are disjoint. This is because the two choices of matchings must disagree in some scenario. If the first choice of matchings has $M_1$ as the maximum-weight matching in that scenario, and the second choice of matchings has $M_2$, the two matchings disagree about the sign of the dot product $\langle \mathbf{w}, \mathbf{m}_1 - \mathbf{m}_2 \rangle$ coming from the matching-difference vector. Hence the corresponding regions must be disjoint.

This means that we’ve transformed the problem of counting choices of matchings into the problem of counting regions of high-dimensional space cut out by hyperplanes. Believe it or not, this transformation is actually really helpful, because mathematicians have put a lot of work into the latter problem! Now, despite all that work, I don’t know how to calculate the exact number of regions cut out by these particular (joint!) choices of signs and 13,444 hyperplanes. But we don’t need the exact number; we just need a useful upper bound.

Our one saving grace in writing down a useful upper bound is that there aren’t that many hyperplanes in total: letting $N_i$ be the number of valid matchings in scenario $i$, the total number of hyperplanes involved in any constraint for any choice of matchings coming from a weight vector is $$\sum_{i=1}^{495} \binom{N_i}{2} = 390,596,$$ because every hyperplane involved in a constraint is of the form $\mathbf{m}_i - \mathbf{m}_j$ for matchings $M_i$, $M_j$ for the same scenario.

These arguments let us write down the very-loose-but-still-very-useful upper bound

$$\begin{aligned} &\#\left\{\text{choices of matchings coming from a weight vector}\right\} \\[1em] =\ &\#\left\{\begin{array}{l} \text{nonempty regions of }\mathbb{R}^{40}\text{ coming from particular signs on} \\ \text{a particular choice of 13,444 hyperplanes among 390,596} \end{array}\right\} \\[1em] \le\ &\#\left\{\begin{array}{l} \text{nonempty regions of }\mathbb{R}^{40}\text{ coming from} \\ \text{any signs on all 390,596 hyperplanes} \end{array}\right\}. \end{aligned}$$

The equality here is our disjointness argument above; the inequality comes from forgetting the unnecessary signs.

A two-dimensional illustration

This is a pretty abstract argument, so let’s try to make it a little bit more concrete. Instead of there being 495 scenarios, let’s pretend that there’s just one: scenario ABCDGJKL above, with three matchings (red/green/blue). Let’s also pretend that the red/green/blue matching vectors live in $\mathbb{R}^2$, not $\mathbb{R}^{40}$, as depicted below:

Here the red-shaded region is all weight vectors that give the red matching, and likewise for the green- and blue-shaded regions. Each of these comes from a particular choice of signs on only two of the three hyperplanes. But choosing signs on all of the three hyperplane constaints divides $\mathbb{R}^2$ into six nonempty regions. So the two-dimensional analogue of our region-counting inequalilty above reads

$$\begin{aligned} &\#\left\{\text{choices of matchings coming from a weight vector}\right\} \\[1em] =\ &\#\left\{\begin{array}{l} \text{nonempty regions of }\mathbb{R}^{2}\text{ coming from particular signs on} \\ \text{a particular choice of two hyperplanes among three} \end{array}\right\} \\[1em] \le\ &\#\left\{\begin{array}{l} \text{nonempty regions of }\mathbb{R}^{2}\text{ coming from} \\ \text{any signs on all three hyperplanes} \end{array}\right\}. \end{aligned}$$

Namely, there are fewer different shaded regions (just three) than regions chopped up by hyperplanes (six). In high dimensions, we lose more than just a factor of two; thankfully, we’ve got factors of two to spare.

Numerics

The final quantity in our high-dimensional region-counting inequality above—the nonempty-region count coming from all 390,596 hyperplanes—is easy to upper-bound via the theory of hyperplane arrangements: namely, an inequality due to Schläfli. For a central hyperplane arrangement, Schläfli’s inequality gives $$\#\left\{\begin{array}{l} \text{nonempty regions of }\mathbb{R}^{d}\text{ cut out by} \\ m\text{ hyperplanes through the origin} \end{array}\right\} \le 2\sum_{k=0}^{d-1} \binom{m-1}{k}.$$

In our case, we get the numerical bound

$$\#\left\{\text{choices of matchings coming from a weight vector}\right\} \le 2\sum_{k=0}^{39} \binom{390595}{k} \approx 2^{572}.$$

Now, that’s a lot of possible choices of matchings that might come from weight vectors. But earlier, we saw that there were about $2^{2130}$ possible choices of matchings in total. So the chance that a random choice of matchings comes from a weight vector (via taking the maximum-weight matchings) is something like $2^{-1560}$. In other words, there’s a billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion to one odds against this happening by random.

I don’t think a sportsbook would entertain such a wager. This is, to my eyes, the smoking gun: the choice of matchings bears a ridiculously unmistakable mathematical signature. So we can finally claim to have solved the mystery of Annexe C:

FIFA assigned some weights to each of the forty possible pairings, and then recorded in Annexe C the perfect matching in each scenario with the maximum possible sum of weights.

---

Where’d they come from?

The one remaining question is where these forty free parameters came from. Were they in turn generated from some smaller set? What nefarious deeds—it’s FIFA, after all—are concealed within those still-somewhat-mysterious numbers?

I’m not sure that there’s going to be a satisfying answer to this question. For one, we can’t determine exactly what the weights are. The example we gave above is one weight vector that produces the matchings of Annexe C, but there are lots of others. So we can’t even try to isolate how much FIFA weighted various factors like rest days, travel distance, or potential rematches.

The only satisfying answer would be FIFA themselves saying how they weighted the matches, and that doesn’t seem very likely to happen, does it?

Was the fix in?

Forty parameters of unknown origin also invite the question of whether they could be chosen to favor certain teams. This isn’t all that far-fetched: it was known well before Annexe C was published that Mexico, Canada, and the United States were going to be assigned to groups A, B, and D, respectively. As hosts, they had weaker groups, so were widely expected to end up as teams 1A, 1B, and 1D. So were these teams favored in, say, expected rest differential?

We tested this hypothesis: namely, we compared each slot’s expected opponent rest under FIFA’s table against the uniform-random baseline. There is no consistent host signal: 1B does get slightly more-tired opponents than chance (by about ten hours, on average), as does 1A (by four hours), but 1D gets fresher ones (about eight hours). So, while FIFA could perhaps have chosen to give the hosts a very slight advantage here, they don’t seem to have done so.

Why weren’t they public?

Setting aside FIFA’s general tendency to be unaccountable, opaque, and corrupt, are there any good arguments against making the weights public?

I actually think there are decent arguments for not making the weights public if you’re FIFA. First and foremost, you’re just inviting further criticism of whatever weights you assigned: maybe you decided that flying from Guadalajara to Vancouver wasn’t that bad, or some other sin. Second, you’re inviting people to screw up math, rather than just screw up a table lookup. Finally, maybe you screwed up the math or the algorithms. I’ve certainly written incorrect implementations of the Hungarian algorithm, so who’s to say FIFA wouldn’t?

That said, it would be neat to have them. So if that FIFA intern who actually generated Annexe C is out there, let me know.

---

Comments? Questions? Corrections? Just want to let me know you enjoyed this? You’re the FIFA intern I mentioned? Interested in having me do nonsense with numbers for you? Email me at [email protected].

---

Appendix: better bounds

There are a few fun ways to improve the quantities in the Schläfli bound that actually give us pretty substantial wins.

Improving $d$

The first trick is to reduce the dimension $d$ of the weight vectors, since there’s actually a fair bit of degeneracy. There are two forms of degeneracy, plus an overlap between them that we have to make sure not to double-count.

First, we can increase all the weights in a given column (i.e., a fixed third-place team) by a constant amount and not change which matchings the weight vector produces. The only matchings we affect are matchings where that team qualified, and all of those see their sum of weights increased by a constant, hence this won’t affect the maximum-weight matching in any scenario. So we can quotient our weight vectors and half-space constraints by the 12-dimensional span of the column vectors.

Second, we can do the same thing in a given row. Increasing all the weights in a single row by a constant increases every matching’s total score by that constant, so it again has no effect on the matchings we choose. This lets us quotient by the 8-dimensional span of the row vectors.

Unfortunately, these two subspaces intersect in a one-dimensional space spanned by the sum of all weights. So we don’t get a 20-dimensional cutdown, only a 19-dimensional one. But dropping to dimension $d = 21$ still helps us enormously, as our Schläfli numerics now become $$2\sum_{k=0}^{20} \binom{390595}{k} \approx 2^{311}.$$

Improving $m$

There are two tricks to improve $m$, the number of hyperplanes: deduplication, and single-cycle reduction. Neither buys us too much, but they’re still neat.

Recall that our earlier $m = 390,596$ figure came from summing $\binom{N_s}{2}$ across all scenarios to count the number of vectors of the form $\mathbf{m}_{i} - \mathbf{m}_{j}$ where matchings $M_i$, $M_j$ come from the same scenario. It turns out that not all of these $\mathbf{m}_{i} - \mathbf{m}_{j}$ vectors are distinct (up to sign): when we deduplicate, we find that we only have 89,203 distinct matching-difference vectors. That takes us down to $$2\sum_{k=0}^{20} \binom{89202}{k} \approx 2^{269}.$$

We started at Schläfli numerics of $2^{572}$, so we’ve already found an extra $2^{-300}$ basically just lying on the floor. We’ve still got one final trick up our sleeves.

Let’s consider a matching-difference vector $\mathbf{m}_{i} - \mathbf{m}_{j}$. Now, since $M_i$, $M_j$ are matchings under the same scenario, there’s some permutation $\sigma$ of the slots that takes $M_i$ to $M_j$. This permutation, like all permutations, can be decomposed into disjoint cycles. It turns out that the hyperplane constraint coming from $\mathbf{m}_{i} - \mathbf{m}_{j}$ is always redundant if $\sigma$ has more than one cycle. This is because we know we don’t care about the constraint unless either $M_i$ or $M_j$ is the maximal matching. If $M_i$ is the maximal matching, then we know that $$\langle \mathbf{w}, \mathbf{m}_i - \tau(\mathbf{m}_{i}) \rangle > 0$$ for any single cycle $\tau$ (where the action of permutations on matching vectors abuses notation slightly). But if $\sigma$ is the composition of disjoint cycles $\tau_j$, then $$\langle \mathbf{w}, \mathbf{m}_i - \sigma(\mathbf{m}_{i}) \rangle = \sum_j \langle \mathbf{w}, \mathbf{m}_i - \tau_j(\mathbf{m}_{i}) \rangle > 0$$ precisely because the cycles are disjoint.

So it suffices to only consider matching-difference vectors coming from matchings that differ by a single cycle. This takes us down to $m = 42,097$, which gives the best Schläfli numerics I’ve got: the number of choices of matchings that can arise from weight vectors is at most $$2\sum_{k=0}^{20} \binom{42096}{k} \approx 2^{247},$$ which makes the odds of a coincidence at most $2^{-1883}$. My intuition is that this is still a massive overcount, but I don’t know how to push these techniques any further.