How should teams be paired for first round of Champions League?

Question

In the draw for the round of 16 of the Champions League football tournament, the eight group winners are seeded, and the eight group runners-up are unseeded. The seeded teams are drawn against the unseeded teams, with the seeded teams hosting the second leg. Teams from the same group or the same association cannot be drawn against each other.

Unfortunately, this is not the description of an algorithm. I have seen draws, but it didn't make it clear to me what exactly their mechanism is. So, to translate it to a more combinatorial problem.

Suppose that we are given a bipartite graph that contains at least one perfect matching. What is the algorithm that they use to pick a perfect matching?

This related question (mysteriously also asked in December!) seems to suppose implicit that the generated distribution is uniform on the matchings. This is very unlikely from the way the draws are conducted, where teams are drawn against each other from urns.

Answer 1

See the answers of "Nom Prenom" in december 2012, in the thread you mention above (and the answers to the different people who wrotes in this thread, including somebody named Igor). Teams pairing are selected one after the other: a team which finished second is selected first, then all valid opponents who finished first (valid in the sense that they have not been selected yet, and if selected, this choice will not lead to an unfeasible pairing for the remaining teams, this is precomputed by a computer) are placed in a bowl and one is selected. Doing so indeed leads to a NON-UNIFORM probability of draws. In particular all probabilities of team pairing that are given on the web are incorrect, reproduced blindly. To get the right probability, you need to emulate all possible draws and do the adequate counting. But this is doable (40 sec on my computer to get the probability of each possible draw and order in which it is generated).

Answer 2

Define a matching algorithm as "uniform" if and only if every allowable set of pairings is equally likely.

The following mechanism is practical, but not uniform, in the sense that matchings of the type $Aa, Bb, Cc, Dd$ are all validly matched against each other and same for the other eight teams, have different probabilities than matchings not satisfying that property:

Draw a seeded team at uniform random. Pair that seeded team with a randomly drawn non-seeded team; if the teams are from the same group, repeat the non-seeded team draw, then replace the first-drawn non-seeded team. Repeat on the remaining balls in the two collections, until there is only one left in each collection. If those last two are from the same group, discard the entire draw and repeat.

Here is a method which is uniform in all allowable match arrangements, and at average, requires about the same number of draws:

Draw the parings for teams $A,B, \ldots,H$ sequentially from the bag containing $a, b, \ldots, h$, ignoring possible disallowed matchups. Then examing the resulting pairings and if there is an unallowed pairing, discard the entire draw and try again. The expected value of the number of tries required will be very close to $e$.

So this method is "better", but I will guess that the actual committee either uses a less "perfect" method or, more likely, refuses to disclose its method because it takes bribes or assigns more desirable pairings, and would be vulnerable to this being detected by statistical examination if the purported pairing method were revealed.