Consider a fair symmetric game between two players that always results in exactly one of the players winning, i.e. there are no ties.
When two players $P$ and $Q$ play each other, $P$ wins with a fixed but unknown probability $W_{PQ}$.
In a collection $n$ players, each player $P$ has an unknown score $S_P = \frac{1}{n - 1}\sum_{Q \neq P} W_{PQ}$. It is the arithmetic mean of $P$'s win probability over all other players. Assume that no two players have the same score.
I want to rank all players in the collection by their score, using the minimum number of games. Since the outcome of each game is based on a probability, I can never be fully confident of the ranking. However, I am interested in finding two particular tournament strategies:
- A strategy which returns a ranking with confidence $c$ (e.g. 90%) using the fewest number of games.
- A greedy strategy which increases confidence by as much as possible with each game.
I feel like this is a known and solved problem, but I haven't been able to find the solution. Some of my terminology might be off or clumsy. I'd welcome edits in those cases.