Algorithm for least required matches to rank players in tournament

algorithmscombinatoricsdiscrete mathematicsgraph theoryoptimization

Assuming the following conditions:

  1. A higher skill level always beats a lower skill level.
  2. Given n players, each have a distinct skill level compared to the other (n-1).
  3. If player A has beat player B, and player B has beat player C, then player A is better than player C and no match need to occur.
  4. The skill level of each player can only be used to determine if it is complete (It cannot use the skill level to help the algorithm, it must only use the match history)
  5. The algorithm is only considered complete when each player is correctly ranked according to their skill level

What matching algorithm would rank the n players in the least number of matches?

Notice I state matches, and not rounds. So concurrent matches occurring does not help. Although I am curious of the algorithm that would do it in the least number of rounds as well.

If there is no clear obvious answer, what methods/techniques are worth considering?

The answer may (probably?) be a well known tournament style.

If not I have a feeling the answer is very simple and is related to some graph traversal problem, or even related to sorting algorithms on random integers.

As an example, I will use a basic algorithm for 4 players:

Player A (skill 4)
Player B (skill 3)
Player C (skill 2)
Player D (skill 1)

Matches

Round 1 (Match-making is random in round 1 as per condition 4)
A vs C: A wins
B vs D: B wins

Known: (A > C), (B > D)

Round 2
A vs B: A wins
C vs D: C wins

Known: (A > BCD), (B > D), (C > D)

Round 3
B vs C: B wins

Known: (A > BCD), (B > CD), (C > D)

So given 4 players, I was able to find the rank for all players in 5 matches.

Best Answer

If we are optimizing the number of matches, then this problem is exactly equivalent to the problem of finding a good sorting algorithm. Since $m$ matches have $2^m$ different possible outcomes, and we want to distinguish $n!$ possible orders between the players, we must have $2^m \ge n!$ or $m \ge \log_2 (n!) = O(n \log n)$ matches. Algorithms like quicksort or mergesort achieve this many matches, at least asymptotically.

(So just run quicksort, for example, and every time it asks you to compare two elements, have the corresponding players play a match to decide the outcome of the comparison.)

It's more interesting to optimize the number of rounds. Since each round can include up to $\frac n2$ matches, the lower bound on the number of rounds is only $\frac{\log_2 (n!)}{n/2} = O(\log n)$.

We can borrow some constructions from sorting networks to achieve this bound, at least asymptotically. A sorting network can be thought of as a tournament of this type with some restrictions:

  1. Initially, the players are given an arbitrary ranking from $1$ to $n$.
  2. When a game is played between players ranked $i$ and $j$, if $i<j$ but the $i^{\text{th}}$ player loses, the two players exchange ranks.
  3. The games have to be prearranged in advance - but in terms of ranks. (So the instructions for one round with 6 players might be "players ranked 1 and 4 play, players ranked 2 and 5 play, players ranked 3 and 6 play".)

The depth of a sorting network is precisely the number of rounds required in the resulting tournament.

There are many sorting networks, such as the bitonic sorter, that have depth $O(\log^2 n)$. This is good, but not optimal. The AKS network is a sorting network with depth $O(\log n)$, which is optimal up to a (huge) constant; it's not useful in practice.

Related Question