How many rounds are required in a "Swiss tournament sorting algorithm"?

Question

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?

Answer 1

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.

Answer 2

I enjoyed this exchange, an eloquently posed question and an answer that also seems correct to me.

At first, the relationship between a tournament and a sorting network was unclear to me, but then I considered the definition of the depth of a sorting network: the largest number of comparators that any input value can encounter on its way through the network and see that it is equivalent to the number of rounds in a tournament.

So, for each sorting network of depth D, there exists a corresponding tournament of pairwise comparisons, which has D rounds which determines the full ordering of the players.

Therefore, the result of Ajtai, Komlos, Szemeredi concerning the asymptotic depth of sorting networks applies to tournaments of pairwise matches also.

Note, however, that whilst this is a strong asymptotic result, because the constant is quite large, there may well exist algorithms which are more optimal for "smaller" values of n.

I recently published a paper which explores this and the more general problem of partial sorting (i.e. determining only the top k players) which you can find here or here. All comments are most welcome!

Norbert