The Champions League Problem

In the UEFA Champions League, 32 teams are divided into eight groups of four. The top two teams from each group qualify for the knockout stage. The qualified teams and their group stage standings are as follows:

Group A Winner: Porto (Portugal), Runner-up: Liverpool (England)
Group B Winner: Chelsea (England), Runner-up: Schalke (Germany)
Group C Winner: Real Madrid (Spain), Runner-up: Olympiacos (Greece)
Group D Winner: Milan (Italy), Runner-up: Celtic (Scotland)
Group E Winner: Barcelona (Spain), Runner-up: Lyon (France)
Group F Winner: Manchester United (England), Runner-up: Roma (Italy)
Group G Winner: Inter (Italy), Runner-up: Fenerbahce (Turkey)
Group H Winner: Sevilla (Spain), Runner-up: Arsenal (England)

The knockout stage will see each group winner facing a randomly drawn runner-up; however, teams from the same group or association (e.g. England) cannot be drawn together.

I am particularly interested in my favorite team, Inter. What is the probability of Inter playing against, say, Liverpool in the next stage?

According to the rules, Inter can face one of these six opponents: Liverpool, Schalke, Olympiacos, Celtic, Lyon, and Arsenal. (Other runners-up, i.e. Roma and Fenerbache, are ruled out.) It is tempting to say that Inter has a 1/6 chance of facing Liverpool, assuming each opponent has an equal chance.

From Liverpool's perspective, it can face Real Madrid, Milan, Barcelona, Inter, or Sevilla. Using the same logic as above, we will conclude that Liverpool has a 1/5 chance of facing Inter.

Since Inter vs. Liverpool and Liverpool vs. Inter are the same event, they must be associated with the same probability. But we arrive at a probability of 1/6 from Inter's perspective and 1/5 from Liverpool's. It must be that the assumption of equal chance is at fault.

Strange as it may seem, Inter's (and/or Liverpool's) potential opponents do not have the same chance of drawing Inter (Liverpool). To better understand this concept, imagine a hypothetical situation where UEFA imposes a stricter rule that reduces Liverpool's potential opponent to Inter only, and everything else is unchanged. Although Inter still has five other teams in the pot, it must now be drawn to Liverpool for the knockout stage to work. The probabilities assigned to the teams are then 1 for Liverpool and 0 for the five remaining teams.

The spirit of the draw is that it should be fair to every team under the UEFA's constraints. In the ideal case, a team should be drawn to its potential opponents with an equal probability; but we have just learned that it is not achievable. Now that some teams are more likely to play against each other under the current rule, how should the probabilities be adjusted? While the probabilities certainly depend upon the exact drawing mechanism, is there an "optimal scheme" that minimizes the probability differences?

I am not sure how UEFA handles this issue. The draw will be held on December 21, 2007.