The tournament problem
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
The tournament problem
Okay, I have a group of n people participating in a tournament. They are very competitive, and they each want to know what place they are in, so that they can brag to all the people who are ranked lower than that person. Each game in the tournament is a game between two people where there is a winner and a loser, and no chance of a draw. Also, the games take a while, and while they want to know their place, they have lives to get back to, so they need to know the minimum amount of games needed to decide the position each of them have. Also, the decision of who plays who in each of the games may depend on the outcome of the previous games.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5963
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The tournament problem
There seems to be an implicit assumption, that if A beats B and B beats C, then A would beat C and there is no need to play the game. Is this an assumption that you want people to make?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: The tournament problem
jestingrabbit wrote:There seems to be an implicit assumption, that if A beats B and B beats C, then A would beat C and there is no need to play the game. Is this an assumption that you want people to make?
Yes, that is an assumption that I want people to make, so here is my list of assumptions:
1. If a beats b, and b beats c, then a will beat c, and so there is no need to play that game. In other words, the tournament is transitive.
2. If a beats b, then there is no need for them to play again because a will always beat b.
3. If a beats b, then a ranks higher than b regardless of whatever else happens. Any contradictions that arise from this rule should be covered by assumption 1.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: The tournament problem
Well, look like this is simple sorting. Comparison = match.
Can't be done faster than n * log n.
How to? Read any article on sorting, for example: http://en.wikipedia.org/wiki/Sorting_algorithm
Can't be done faster than n * log n.
How to? Read any article on sorting, for example: http://en.wikipedia.org/wiki/Sorting_algorithm
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5963
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The tournament problem
Лом wrote:Can't be done faster than n * log_{2}n. How to? Read any article on sorting.
Whilst I agree that this is asking for the best possible sorting algorithm, the manner in which differing methods are compared is fairly uncommon: the cost of the algorithm is only the number of comparisons. In general, that's a very cheap part of the algorithm, and the memory usage, memory calls, function calls etc etc are the real issues.
Anyway, as is mentioned here
http://en.wikipedia.org/wiki/Comparison ... ort_a_list
the lower bound must be at least ceiling(log2(n!)), but that bound isn't always realised  you can need 34 comparisons to sort 13 things but log2(13!) < 33. Its known that a thing called the FordJohnson algorithm does the best possible for small groups (apparently provably up to n = 47), but the interwob seems to think that its suboptimal. I haven't read that stuff so I can't say whether its actually true. I wouldn't be surprised if it were suboptimal, but I'm not going to vouch for a proof I haven't given a good look at.
Anyway, you can read about how FordJohnson works here
http://www.google.com.au/url?sa=t&rct=j ... eg&cad=rja
I have no idea if that link will work for anyone but me. The article title is "A Variant of the FordJohnson Algorithm that is more Space Efficient" and the authors are AyalaRincón, Abreu, Siqueira (though I can't swear that that's the right accent on the o). Note though, that most articles on comparison sort don't mention FordJohnson.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: The tournament problem
Yes, but the cost of sorting is not my original problem. The best case for sorting might not be possible for my tournament, so I think that you should calculate the actual values before jumping to conclusions.
Here are my answers so far:
Here are my answers so far:
Spoiler:
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5963
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The tournament problem
The cost is the number of games, and you want to minimize the worst case, so the answer is FordJohnson for small n.
In particular, for n = 5, call the players A, B, C, D and E.
This is all explained on page 3 of the paper I linked to.
In particular, for n = 5, call the players A, B, C, D and E.
Spoiler:
This is all explained on page 3 of the paper I linked to.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: The tournament problem
Is it possible to run multiple games simultaneously between different players? For example, A vs B, and at the same time C vs D? If so, the goal should be to minimize the worst case number of rounds, and the optimal solution will be quite different.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5963
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The tournament problem
douglasm wrote:Is it possible to run multiple games simultaneously between different players? For example, A vs B, and at the same time C vs D? If so, the goal should be to minimize the worst case number of rounds, and the optimal solution will be quite different.
I think in that case you could get there in ceil(log2(n)).
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: The tournament problem
douglasm wrote:Is it possible to run multiple games simultaneously between different players? For example, A vs B, and at the same time C vs D? If so, the goal should be to minimize the worst case number of rounds, and the optimal solution will be quite different.
Okay then, that will be my next problem. However, I do not see how that will be different than the original problem though.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5963
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: The tournament problem
Well, at the moment, you are saying that f(4) = 5. But, if those four people are A, B, C and D, then you can play A and B whilst you also play C and D, so you get two comparisons, but it only costs you one time unit. If you use that concurrency, you can get g(4) = 3, where g is this other way of calculating cost, where we allow concurrent comparisons, but only cost them as one comparison.
btw, did I score my calculation for f(5) alright? or did I miss something?
btw, did I score my calculation for f(5) alright? or did I miss something?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: The tournament problem
True, but isn't g(x)=Ceiling(f(x)/Ceiling(x/2))?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: The tournament problem
Ironically, if score(a) < score(b) did not always imply that a lost to b, but simply lost more than 50% of their games, we could develop an asymptotically linear sort. Rank N people, using something like ELO, for X games played against other randomly chosen players where X approaches some finite Y as N approaches infinity. Use this to approximate player position via Flashsort, then you can refine positions to any desired confidence by choosing another constant number of games Z which we approach as the number of players increases. This will not require more than (Y+Z)*N games  and so be linear in the number of players.
If number crunching time is inconsequential relative to 'comparison' time, I should think we would simply be best off enumerating possible derangements of the players. Each game then eliminates possible derangements, and by simply taking all possible results of all game sequences, we can pick the game tree which is guaranteed to reduce the number of derangements to 1 in the fewest number of games in the worst case. This is probably at least factorial in the number of players, with horrible constants and multiplied terms, but we don't care about that for this problem. This can also just as easily solve every simple modification of the problem which does not make running time of the algorithm important (things like allowing parallel plays but not multiple games by one player, minimizing the difference in the number of games played between the players who play the most and least, etc.)
If number crunching time is inconsequential relative to 'comparison' time, I should think we would simply be best off enumerating possible derangements of the players. Each game then eliminates possible derangements, and by simply taking all possible results of all game sequences, we can pick the game tree which is guaranteed to reduce the number of derangements to 1 in the fewest number of games in the worst case. This is probably at least factorial in the number of players, with horrible constants and multiplied terms, but we don't care about that for this problem. This can also just as easily solve every simple modification of the problem which does not make running time of the algorithm important (things like allowing parallel plays but not multiple games by one player, minimizing the difference in the number of games played between the players who play the most and least, etc.)
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: The tournament problem
jestingrabbit wrote:douglasm wrote:Is it possible to run multiple games simultaneously between different players? For example, A vs B, and at the same time C vs D? If so, the goal should be to minimize the worst case number of rounds, and the optimal solution will be quite different.
I think in that case you could get there in ceil(log2(n)).
You could get the best and the worst in that time, yes, but I think sorting out the middle would take a lot longer.
tomtom2357 wrote:True, but isn't g(x)=Ceiling(f(x)/Ceiling(x/2))?
I very much doubt it. Later on in the tournament, you'll almost certainly (I think) run into situations where either A) you need the outcomes of some of the current round's games in order to decide which players should face off in some of the other games you'd like to do in the same round, or B) only a relatively small portion of the list remains undecided, and matching up all the undecided players leaves a lot left over so you have a lot of "wasted" games because the only players available to play them are ones where you already know what the outcome would be.
To the best of my knowledge it is conceivable that there might be an algorithm that will reliably avoid both of these problems, but the design of such an algorithm is extremely nonobvious.
Who is online
Users browsing this forum: Google Feedfetcher and 0 guests