You're organizing a Swiss-style tournament with N players of a game.
The game is a two-player game, and it results in one winner and one loser. The players are totally ordered by skill, and whenever two players play against each other, the more skilled player always wins.
In each tournament round, each player can play only one game. Going into the tournament, nothing is known about the relative skill levels of the players. The pairings for each round are not decided until the previous round has finished, so you can use the results from previous rounds when you're deciding how to pair the players up. You are not required to follow any traditional pairing rules.
Your goal is to completely determine the ranking of all $N$ players. What is $Swiss(N)$, the number of rounds required in the worst case?
Results for small $N$:
- If $N$ is $0$ or $1$, the number of rounds required is $0$.
- For $N = 2$, the number of rounds required is $1$.
- For $N = 3$, it can be seen that $2$ rounds are not sufficient. If you use only $2$ rounds, then there must be at least two players who only play one game each. If these players both win their games, then their relative skill level is unknown. However, $3$ rounds are sufficient, because this is enough to play out all possible pairings (a round-robin tournament). So the number of rounds required is $3$.
- For $N = 4$, $3$ rounds are necessary (because they are necessary for $N = 3$) and sufficient (because this is enough for a round-robin tournament).
Some sub-questions:
- We can come up with a logarithmic lower bound for $Swiss(N)$ using information theory. The complete ranking of all $N$ players contains $\log_2(N!)$ bits of information, but each tournament round only gives you $\lfloor N/2 \rfloor$ bits of information, so at least $\log_2(N!) / \lfloor N/2 \rfloor$ rounds are required. Is there a better lower bound?
- We can come up with a linear upper bound for $Swiss(N)$ by simply pairing every player against every other player (a round-robin tournament). This gives us an upper bound of $N$ for odd $N$, and $N – 1$ for even $N$. Is there a better upper bound?
- In particular, is there an algorithm which uses $o(N)$ rounds?
- What is the asymptotic behavior of $Swiss(N)$? Is it logarithmic, linear, or something in between?
Best Answer
Just like you seem to have already realized, asking for the number of tournaments $Swiss(n)$ is the same as asking for the span of an optimal parallel sorting network.
I'll just point you to a simple sorting network, the Bitonic Sorter, which gives an $O(\log^2n)$ span.
There is a famous result by Ajtai, Kolmos and Szemeredi that gives the first $O(\log n)$ depth and $O(n \log n)$ work sorting network (implying that your $O(\log n)$ lower bound is tight).
See this link for more details.