The UEFA Champions League, UEFA Europa League, and UEFA Conference League draw A random two-sided matching occurs in the
UEFA Champions League Round of 16 and
UEFA Europa League Round of 32. After some games are done within 8 groups, the group winner and the group runner-up proceed to the champions league. The UEFA rules say that each winner should be paired with a runner-up. Without further constraints, this problem could easily be solved by finding a
random permutation of the winners. But UEFA rules impose two additional constraints: two teams from the same group cannot be paired, and two teams from the same
association cannot be paired. Thus, the goal is to choose a random matching in an incomplete
bipartite graph. The UEFA mechanism makes several draws from different bowls. At the beginning, there are: • Bowl 1, containing identical balls each of which represents one group runner-up; • Bowl 2, initially empty, to be filled and refilled later. • Bowls A to H, each of which represents a group winner and contains 7 balls with the winner's name on it. The draw proceeds as follows: • A ball is drawn from bowl 1, and the runner-up's name is displayed; • A computer program shows all winners that can — according to the UEFA rules — be paired with the drawn runner-up. This takes into account not only current constraints, but also constraints for future runners-up. • From some of the bowls A to H, representing the potential winners, a single ball is taken and put in bowl 2; • The balls in bowl 2 are shuffled. One ball is drawn, and it represents the winner matched to the previously drawn runner-up. • Bowl 2 is emptied, and the process repeats for 8 rounds. This procedure yields probabilities that are different than just choosing a matching at random; this creates a distortion in the matching probalities of different groups, which raises suspicion and
conspiracy theories. First, the runners-up are drawn in a random order. Then, each winner in turn is drawn, and it is matched to the first runner-up in the order, to which it can be matched according to the constraints. This draw, too, produces distorted probabilities relative to the uniform-random matching. == See also ==