A random two-sided matching is a process by which members of two groups are matched to each other in a random way. It is often used in sports in order to match teams in knock-out tournaments. In this context, it is often called a draw, as it is implemented by drawing balls at random from a bowl, each ball representing the name of a team.
A random two-sided matching occurs in the UEFA Champions League Round of 16.[1] [2] 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:
The draw proceeds as follows:
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.
Another two-sided matching occurs in the FIFA World Cup. 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.