Football World Cup Finals
I've been told the football world cup finals (FWCF) are in progression in Germany at the moment. Haven't followed them as I'm less interested in watching football played by others than the one I play myself with Konami's Pro Evolution Soccer 4 on my PS2.
The FWCF to some degree relates to an interesting algorithmic problem: the selection problem in which an algorithm must select the i'th largest element of n values with as few pairwise comparisons as possible. Author, mathematician, and reverend Lewis Carroll, officially Charles Dodgson, became puzzled over the same problem while following tennis tournaments. Barring luck (randomness in individual game outcomes), the common knockout tournament is obviously the best tournament system for selecting the winner. I've previously studied some specific selection problems, but never ones which involve unreliable comparisons.
The FWCF employs first a stage of eight parallel round-robin tournaments, each containing four teams. The two best teams of each group proceed to a knock-out tournament. The winning team has played seven games, and it is possible that two teams play against each other twice.
The Swiss tournament system was introduced in chess tournaments in the late 18'th century. As in round-robin tournaments, each player/team accumulates a score based on its wins, draws and losses. On each round players with equal scores are pitted against each other, but with additional rules that prevent same players meeting again. The Swiss tournament has nice advantages, such as rapid convergence and high entertainment value to players, but your average football fan might find it perplexing and, more importantly, the tournament doesn't necessarily end in a final climax.
Naturally I wouldn't be writing this blog entry unless I would be suggesting some wise-ass tournament schemes of my own. But first, as a basis for estimating the tournament systems I choose the probability of a win for player A against player B to follow the logistic curve, 1/(1+c^(a-b)), where c I choose to be 1.4, and a and b are the positions of players A and B if all players were ordered "correctly". Hence, the best player wins the second best player with probability 1/(1+1.4^(1-2)) = 0.5833... and the tenth best player with probability 0.9538...
A full round-robin tournament among all thirty-two FWCF finalists sounds fair albeit somewhat lengthy, lasting at least three months. Simulating such a round-robin tournament one million times on a computer with the above game outcome probabilities shows that the best player would be awarded the gold medal only with approximately a 47.5% probability, silver with 26.7% probability, and bronze with 14.5% probability. Adding a second round increases the likelihood of correct winner to approximately 58%.
The standard knockout tournament fares even worse: the correct winner is chosen only with approximately 38.5% probability. But there is a simple remedy to improve it: playing the final best-of-three improves the best player's chances to 42.3%, playing also the semifinals best-of-three yields 45.2%. The next improvement would be to play the final best-of-five, resulting in almost 47.6% chances of finding the best player, but such a lengthy final may already lead to loss of concentration in the audience and tolerance in the native inhabitants of the hosting cities. Furthermore, any best-of-N system implies uncertainty of when the final decisive game will be played, which in turn may be troublesome to broadcasting companies and organizers who would like to schedule everything well in advance.
The FWCF system is not particularly good, only slightly more reliable than the basic knockout tournament and it requires seven rounds of games - two more than the straight-forward knockout tournament. Exchanging the order of group and knockout stage would make the tournament more reliable, but that wouldn't ensure all teams have at least three occasions to play and that there's a final climax at a predetermined date.
For my tournament system proposal I chose the simple sorting network as the basic computational device. I decided to add an eighth round of games, and as the comparator function I use not only the result of the played game but the number of wins accumulated in all played games so far, with emphasis on later wins. Only the final round is played as earlier - winners of those games are honored with gold and bronze regardless of their game history - thus ensuring the final climax. I wrote an elementary genetic algorithm and a fitness function which tries to maximize the likelihood of also the dimmer medals for the best player and avoid same players meeting twice. A nightful of CPU cycles later I obtained the following network which I have post-processed and visualized:
The above tournament system would award gold to the best player with a 44.6% probability. There are duplicate games, such as players 1 and 5 meeting on the semifinal and quarter-final round, but this was an elective trade-off. On average slightly over five games are duplicates. The role of maintaining a score sheet of wins is interesting, because if the comparator function replaced with the traditional - winner moves to the upper line - the tournament still produces the best winner with 42.5% probability. The most significant drawback of the above tournament is that the chance of winning is not entirely independent of which line the player is initially placed on. On the other hand, the best player is better off in my tournament than in the current FWCF regardless of which line he is placed on.
There's one remaining question: how to deal with draws. FWCF employs extra time and penalty shootouts, the latter of which undoubtably brings an additional element of randomness to the results. The tournament system I proposed above might allow draws in some places, but if draws are easy to achieve, the player which considers a draw more beneficial may adjust his playing style accordingly. As this is generally considered dull for spectators I propose a few solutions amenable for football: instead of the penalty shootout, the winning team is the one granted more corner kicks when the ball was passed outside by the defending goal keeper, but not field player. Should also that statistic be drawn, during the first three and the last rounds ties are broken by penalty kicks, during the latter half a variant of the away goals rule is used: a zero-zero in goals is considered a win for the team on the lower line, otherwise the team on the upper line wins.
Should a FWCF follow my suggestions some day (yeah, right, chances are even worse than Finland winning the Eurovision Song Contest), I promise I'll buy a ticket and eat it.
The FWCF to some degree relates to an interesting algorithmic problem: the selection problem in which an algorithm must select the i'th largest element of n values with as few pairwise comparisons as possible. Author, mathematician, and reverend Lewis Carroll, officially Charles Dodgson, became puzzled over the same problem while following tennis tournaments. Barring luck (randomness in individual game outcomes), the common knockout tournament is obviously the best tournament system for selecting the winner. I've previously studied some specific selection problems, but never ones which involve unreliable comparisons.
The FWCF employs first a stage of eight parallel round-robin tournaments, each containing four teams. The two best teams of each group proceed to a knock-out tournament. The winning team has played seven games, and it is possible that two teams play against each other twice.
The Swiss tournament system was introduced in chess tournaments in the late 18'th century. As in round-robin tournaments, each player/team accumulates a score based on its wins, draws and losses. On each round players with equal scores are pitted against each other, but with additional rules that prevent same players meeting again. The Swiss tournament has nice advantages, such as rapid convergence and high entertainment value to players, but your average football fan might find it perplexing and, more importantly, the tournament doesn't necessarily end in a final climax.
Naturally I wouldn't be writing this blog entry unless I would be suggesting some wise-ass tournament schemes of my own. But first, as a basis for estimating the tournament systems I choose the probability of a win for player A against player B to follow the logistic curve, 1/(1+c^(a-b)), where c I choose to be 1.4, and a and b are the positions of players A and B if all players were ordered "correctly". Hence, the best player wins the second best player with probability 1/(1+1.4^(1-2)) = 0.5833... and the tenth best player with probability 0.9538...
A full round-robin tournament among all thirty-two FWCF finalists sounds fair albeit somewhat lengthy, lasting at least three months. Simulating such a round-robin tournament one million times on a computer with the above game outcome probabilities shows that the best player would be awarded the gold medal only with approximately a 47.5% probability, silver with 26.7% probability, and bronze with 14.5% probability. Adding a second round increases the likelihood of correct winner to approximately 58%.
The standard knockout tournament fares even worse: the correct winner is chosen only with approximately 38.5% probability. But there is a simple remedy to improve it: playing the final best-of-three improves the best player's chances to 42.3%, playing also the semifinals best-of-three yields 45.2%. The next improvement would be to play the final best-of-five, resulting in almost 47.6% chances of finding the best player, but such a lengthy final may already lead to loss of concentration in the audience and tolerance in the native inhabitants of the hosting cities. Furthermore, any best-of-N system implies uncertainty of when the final decisive game will be played, which in turn may be troublesome to broadcasting companies and organizers who would like to schedule everything well in advance.
The FWCF system is not particularly good, only slightly more reliable than the basic knockout tournament and it requires seven rounds of games - two more than the straight-forward knockout tournament. Exchanging the order of group and knockout stage would make the tournament more reliable, but that wouldn't ensure all teams have at least three occasions to play and that there's a final climax at a predetermined date.
For my tournament system proposal I chose the simple sorting network as the basic computational device. I decided to add an eighth round of games, and as the comparator function I use not only the result of the played game but the number of wins accumulated in all played games so far, with emphasis on later wins. Only the final round is played as earlier - winners of those games are honored with gold and bronze regardless of their game history - thus ensuring the final climax. I wrote an elementary genetic algorithm and a fitness function which tries to maximize the likelihood of also the dimmer medals for the best player and avoid same players meeting twice. A nightful of CPU cycles later I obtained the following network which I have post-processed and visualized:
The above tournament system would award gold to the best player with a 44.6% probability. There are duplicate games, such as players 1 and 5 meeting on the semifinal and quarter-final round, but this was an elective trade-off. On average slightly over five games are duplicates. The role of maintaining a score sheet of wins is interesting, because if the comparator function replaced with the traditional - winner moves to the upper line - the tournament still produces the best winner with 42.5% probability. The most significant drawback of the above tournament is that the chance of winning is not entirely independent of which line the player is initially placed on. On the other hand, the best player is better off in my tournament than in the current FWCF regardless of which line he is placed on.
There's one remaining question: how to deal with draws. FWCF employs extra time and penalty shootouts, the latter of which undoubtably brings an additional element of randomness to the results. The tournament system I proposed above might allow draws in some places, but if draws are easy to achieve, the player which considers a draw more beneficial may adjust his playing style accordingly. As this is generally considered dull for spectators I propose a few solutions amenable for football: instead of the penalty shootout, the winning team is the one granted more corner kicks when the ball was passed outside by the defending goal keeper, but not field player. Should also that statistic be drawn, during the first three and the last rounds ties are broken by penalty kicks, during the latter half a variant of the away goals rule is used: a zero-zero in goals is considered a win for the team on the lower line, otherwise the team on the upper line wins.
Should a FWCF follow my suggestions some day (yeah, right, chances are even worse than Finland winning the Eurovision Song Contest), I promise I'll buy a ticket and eat it.
posted by cessu at 3:07 AM
2 Comments:
This comment has been removed by a blog administrator.
This comment has been removed by a blog administrator.
Post a Comment
<< Home