The tournament problem

[tomtom2357]

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.

[jestingrabbit]

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?

[tomtom2357]

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.

[Лом]

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

[jestingrabbit]

Can't be done faster than n * log₂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 Ford-Johnson 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 Ford-Johnson 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 Ford-Johnson Algorithm that is more Space Efficient" and the authors are Ayala-Rincó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 Ford-Johnson.

[tomtom2357]

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:

Spoiler:

I will use P for the number of people, and f_p for the number of games needed. f₁=0, f₂=1, f₃, f₄=5, f₅=?8

[jestingrabbit]

The cost is the number of games, and you want to minimize the worst case, so the answer is Ford-Johnson for small n.

In particular, for n = 5, call the players A, B, C, D and E.

Spoiler:

Make A and B play, and C and D play. wlog A>B and C>D. Then make A and C play, and again wlog A>C. So, we've got A>C>D and A>B. Now, make E play C, if they win they play A, and if they lose they play D. So, then you've got a chain of 4 players, and you know B isn't better than A, so take the lowest 3 in the chain, X, Y, Z, compare B to Y. If they win, compare B to X, if they lose, compare B to Z. That gives you enough to put E in the chain.

Three initial comparisons, two each for E and B, comes to 7.

This is all explained on page 3 of the paper I linked to.

[douglasm]

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]

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)).

[tomtom2357]

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.

[jestingrabbit]

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?

[tomtom2357]

True, but isn't g(x)=Ceiling(f(x)/Ceiling(x/2))?

[WarDaft]

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.)

[douglasm]

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.

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 non-obvious.