Draw System for League Phases of European Cups 2024 onwards

[simonk]

Hello, is there any Idea, how the draw will work technically? No matter, whether it is drawn with balls or digitally, there needs to be a system behind it. I have thought about it, one Idea is, that a computer generates an empty plan with placeholders #1 to 36, with 1 to 9 are from Pot 1, and every team is drawn one after the another, and will then be assigned to an number that avoids any country deadlocks.
Another Idea is, a team is selected and then it gets 8 possible opponents, which are possible for them, and avoiding deadlocks for other teams.
Any concrete Ideas?

[Tazmania]

Is the second way feasible though because while for clubs drawn early on it will be possible to avoid deadlocks as the draw progresses they might run into deadlocks with no scope to resolve them?

[Sagy]

We have had this discussion months ago.

I believe that UEFA will use a version of the first approach that you suggested. Need to add logic for country protection unless a country has more than 4 teams and no more than two games against teams from the same country (might be the same as your avoiding country deadlocks).

As I remember, a large group of people believe that a version of the second approach will be used.

[fabiomh]

IMHO it is a really complex problem, very very interesting from an algorithmic point of view.
Both methods might have some issue, because many constraints appear only while the draw will be progressing, and the deadlock risk is always behind the corner, expecially in the last steps of the draw.
I have no idea about which method can work.
Hope that UEFA have already some clear idea about to solve it.


EDIT:
Let me recap the constraints, please check and correct if needed:
1) each team have to play on each of 8 MDs
2) each team have to meet 2 teams from each pot
3) no matches between teams of the same association (*)
4) each team cannot meet more than 2 teams from the same association (*)

Home/Away & Pairings
5) (extension from constraint #2)
each team have to play 4 matches home and 4 matches away; each team have to meet 2 teams from each pot, one home and one away
6) each team cannot play three or more matches in a row home/away
7) teams of the same city/stadium or using the same airport cannot play home in the same MD (probably 48 hours gap is allowed)
8 ) teams in the same pairing: if one team play on Tuesday, the other one should play on Wednesday (exception for MD8: all the matches will be played same day-time)

(*) unless there is a deadlock

[Stadion]

Are there any draw simulators available online at this stage?

[FEPG]

Are there any draw simulators available online at this stage?

Mine is under construction.

[FEPG]

Hello, is there any Idea, how the draw will work technically? No matter, whether it is drawn with balls or digitally, there needs to be a system behind it. I have thought about it, one Idea is, that a computer generates an empty plan with placeholders #1 to 36, with 1 to 9 are from Pot 1, and every team is drawn one after the another, and will then be assigned to an number that avoids any country deadlocks.
Another Idea is, a team is selected and then it gets 8 possible opponents, which are possible for them, and avoiding deadlocks for other teams.
Any concrete Ideas?

Here is the article explaining how the draw will be conducted. In short, they will pick 36 teams one by one, and the computer will select their opponents.

[simonk]

In order to solve the problem of how fitting it into a match table with 8 matchdays having an odd number of 9 teams per pot might be resolved as follows:
pot 1 and 2, as well as pot 3 and 4 are paired.

Pairings between for example 1 and 3 are drawn in one inning, with home right for one pot, and in the second inning with home right for the other pot, and other opponents. Like in draws for the round of 16 earlier.
On pairings for example 1 and 2, it's a little more complex. The teams or placeholders of every single pot will be split in 3 groups of 3. For example 1-3, 4-6, 7-9, 10-12 etc.
It's like a circle, one one single matchdays, you have 3 matches between block a and b, c and d, and e and f.
This alternates 3 time, so on an other matchday, it's a against c, b against e, and d against f. etc.
In any case, it is not possible on the same matchday, to play every match against teams from the same pot, as one team would be left.

[simonk]

In my opinion to fullfill every detail, country protection, stadium clashes, balance of clubs of same country on the matchdays can really resolved by an blank computer generated plan with 1 to 36. Then with beginning in pot 1, every team is drawn from a pot, and then a computer decides on complex calculation, which positions are available, some might be impossible, and then a draw decides, which position it gets.
But I can only suggess.

[amirbachar]

Hello, is there any Idea, how the draw will work technically? No matter, whether it is drawn with balls or digitally, there needs to be a system behind it. I have thought about it, one Idea is, that a computer generates an empty plan with placeholders #1 to 36, with 1 to 9 are from Pot 1, and every team is drawn one after the another, and will then be assigned to an number that avoids any country deadlocks.
Another Idea is, a team is selected and then it gets 8 possible opponents, which are possible for them, and avoiding deadlocks for other teams.
Any concrete Ideas?

Here is the article explaining how the draw will be conducted. In short, they will pick 36 teams one by one, and the computer will select their opponents.

Thanks for the information!
I wonder how they are going to calculate everything, since I believ it is an NP-hard problem.
Perhaps they will do it hueristically and if they can't find a reasonable path in decent time, they will not consider that team as a possible opponent.
If they find one valid path it means this opponent is possible...

[Sagy]

Hello, is there any Idea, how the draw will work technically? No matter, whether it is drawn with balls or digitally, there needs to be a system behind it. I have thought about it, one Idea is, that a computer generates an empty plan with placeholders #1 to 36, with 1 to 9 are from Pot 1, and every team is drawn one after the another, and will then be assigned to an number that avoids any country deadlocks.
Another Idea is, a team is selected and then it gets 8 possible opponents, which are possible for them, and avoiding deadlocks for other teams.
Any concrete Ideas?

Here is the article explaining how the draw will be conducted. In short, they will pick 36 teams one by one, and the computer will select their opponents.

Thanks for the information!
I wonder how they are going to calculate everything, since I believ it is an NP-hard problem.
Perhaps they will do it hueristically and if they can't find a reasonable path in decent time, they will not consider that team as a possible opponent.
If they find one valid path it means this opponent is possible...

There is little doubt in my mind that the general solution is an NP-complete problem. However, UEFA doesn’t need to come up with the best solution. At any point they just need a solution (pick) that ensures that there is at least one path with no deadlocks remains. That can be done in linear time or better.

[amirbachar]

Here is the article explaining how the draw will be conducted. In short, they will pick 36 teams one by one, and the computer will select their opponents.

Thanks for the information!
I wonder how they are going to calculate everything, since I believ it is an NP-hard problem.
Perhaps they will do it hueristically and if they can't find a reasonable path in decent time, they will not consider that team as a possible opponent.
If they find one valid path it means this opponent is possible...

There is little doubt in my mind that the general solution is an NP-complete problem. However, UEFA doesn’t need to come up with the best solution. At any point they just need a solution (pick) that ensures that there is at least one path with no deadlocks remains. That can be done in linear time or better.

That's the point, the question whether a soultion exists is NP-hard. It is possible there is no valid solution, and I don't think it can be proven in less than exponential time.

[eye]

Picking a name and then computer decides the opponents it is not draw. There is no point to have the whole event if this is how they plan to do the draw. This can be done at their office and simply post the schedule.

There is a simple way to have draw. The procedure should as below:

1. There will be some complete schedules (10, 20 or more) based on the draw restrictions and they will draw one of them.
2. For countries that have more than one club in a pot the clubs will be named. eg at pot 1 there are Liverpool and City. At schedule their names will be eng1, eng 2 and there will be draw to determine if City will get the schedule of eng or of eng 2.
3. If there are more than 1 countries in a pot with only one club in competition there should also be draw as at 2.
4. If there are countries that have same club allocation at pots eg 2 countries have one club each at pot 2 and one club each at pot 3 again there will be draw as at 2.


This is probably the only possible way to have a draw in a simple way and not too much time

[Sagy]

Thanks for the information!
I wonder how they are going to calculate everything, since I believ it is an NP-hard problem.
Perhaps they will do it hueristically and if they can't find a reasonable path in decent time, they will not consider that team as a possible opponent.
If they find one valid path it means this opponent is possible...

There is little doubt in my mind that the general solution is an NP-complete problem. However, UEFA doesn’t need to come up with the best solution. At any point they just need a solution (pick) that ensures that there is at least one path with no deadlocks remains. That can be done in linear time or better.

That's the point, the question whether a soultion exists is NP-hard. It is possible there is no valid solution, and I don't think it can be proven in less than exponential time.

You can pre-create a list of valid matches for each team (both home and away). Yes, it will be a big list but nothing a modern computer will have a hard time with. Even if it takes a week to generate the needed combinations, it’s not an issue since it’s done before the draw. If needed, we can limit the number of combinations to be considered to no more than some arbitrary large number (let’s say 100M). At this point there are no checks just creating valid combination.

When we draw a team (A) the computer picks a valid team (X) for it to play against. At this point you go through all possible renaming combination and remove everything that doesn’t have that matchup (that can by done O(k) or better, k being the number of valid combinations available before the draw).

The computer now creates a list of all teams that have a valid path with a matchup vs team A. Worst case, the list of all teams eligible can be created in O(k) time. Now the computer select team Y from the list of valid teams (we know we will have at least 1 valid path after the selection) and remove all the combinations that don’t include that matchup (again, no worse than O(k) time).

When we remain with only 1 valid path, all matchups are determined and there is no need to continue with the draw, but there is nothing to stop the drawing on the remaining balls and showing the matchups for each of these teams.

If this process is followed, the draw itself is still in linear time. I think that worst case you have to traverse the list of valid matchups 72 times (might be wrong about 72).

Again, I fully agree that the general problem is NP-Complete, I’m just saying that for the purposes of the UEFA draw they don’t have to deal with the full complexity during the draw.

[eye]

You can pre-create a list of valid matches for each team (both home and away). Yes, it will be a big list but nothing a modern computer will have a hard time with. Even if it takes a week to generate the needed combinations, it’s not an issue since it’s done before the draw. If needed, we can limit the number of combinations to be considered to no more than some arbitrary large number (let’s say 100M). At this point there are no checks just creating valid combination.

If it takes a week to generate the needed combinations it is surely huge problem since 7 spots are still unknown in the league phase and will be decided just a day before the draw. Although to generate all the valid combinations for each club it requires only few mins. For each club there are 28 possible pairs of opponents from the same pot and 36 possible pairs of opponents from each of the other 3 pots. Totally there are 1.3M different lists of opponents and you only need to check how many of these are valid. To do this for all clubs you need to check 36*1.3=47M possible combinations which requires less than 5 mins at an average computer. I might create such lists.

The major problem is when you are combining these lists and try to calculate which solutions will not lead you to a deadlock situation.