2
$\begingroup$

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?
$\endgroup$
  • 2
    $\begingroup$ How is this different then a comparison based sorting algorithm, where when we attempt to compare two numbers then we let those two players play against one another? We know that for such algorithm there is a tight bound of theta of nlog(n) so that's an answer for the asymptomatic behavior $\endgroup$ – Belgi Dec 25 '16 at 6:38
  • 2
    $\begingroup$ @Belgi The difference is that multiple comparisons can be performed in parallel, and we are trying to minimize the amount of time taken rather than the total number of comparisons performed. $\endgroup$ – Tanner Swett Dec 25 '16 at 6:40
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your answer! Are you sure that $Swiss(n)$ is the same as the minimal depth of a sorting network? In the Swiss tournament, unlike in a sorting network, it's possible to change the pairings in substantial ways based on the results of previous rounds. In a sorting network, the pairings for each round depend on the results of the previous round, but only in a limited, predetermined way. Is it easy to show that the Swiss tournament has no advantage over the sorting network? $\endgroup$ – Tanner Swett Dec 26 '16 at 21:36
  • 1
    $\begingroup$ If anything, the swiss sorting should be more "powerful" than a plain sorting network (hence lower span) because it has more "degree of freedom". But this certainly isn't the case because the $O(\log n)$ information-theoretic lower bound matches the lower bound for sorting networks. Note that the $O(\log n)$ lower bound is also a lower bound for any parallel comparison based sort. $\endgroup$ – Obinna Okechukwu Dec 26 '16 at 23:55
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.