From a discussion in our Magic group…
You can think of a tournament as a sorting algorithm for ordering the players by skill, where each match is a comparison.
There are a couple of differences:
- Many tournaments only determine a partial ordering – for example, if it’s only looking for a winner.
- Comparisons between two players aren’t guaranteed to be consistent. One player could beat another in one match and lose to the same player in another match; or you could have a scissors-paper-rock type of cycle between three or more players.
For current purposes, we can ignore the first difference and only talk about tournaments where the goal is to rank all the players.
The second point is more interesting. A sorting algorithm assumes that there’s a complete order over the elements, which there isn’t in this case. We could either make it somehow resilient to noise, or find some way to break cycles, all of which is complicated. Or we could let the algorithm do whatever comparisons it does, and if it happens to be inconsistent with previous results then hopefully it’ll be resilient to it somehow. (In the worst case, a dumb-ass algorithm like a naive bubble sort might not terminate.)
Or – and this is why I’ve been thinking about it since this afternoon – we could only make comparisons for which we can’t already infer an answer.
This has some advantages. It means that we can never reach a contradiction where one player beat another but ended up ranked lower than them. It puts a natural limit on the length of the tournament, because the more matches you play, the more potential match-ups become redundant, until there are none left. It might mean that a player can get an unusually low ranking from a bad match-up early on, but that will tend to happen in a scissors-paper-rock sort of situation where no ranking is going to be consistent anyway, so one solution will be as good as any.
So, some solutions that came to mind…
A quicksort tournament would start by choosing one person as the pivot. Everyone plays a match against that person. Then the other players split off into two pools – those who beat the person, and those who didn’t. (Let’s assume there are no draws.) Each of those pools chooses another pivot and repeats until everyone is either a pivot or in a pool by themselves.
There’s an obvious downside to this in, for example, Friday night Magic – the first pivot has to play at least two matches (if those two players either both win or both lose) before anyone else can do anything. Another downside is that there’s a lot of variation in how many matches each person plays – the first pivot plays n-1 matches, but someone else could potentially only play one match (if they’re the only one who beats or is beaten by the first pivot).
(Actually this isn’t necessarily a bad thing for our Magic tournaments – the conversation started with someone pointing out that we have different amounts of free time to play with – but it would be nice the variation wasn’t too big. It would be even nicer if you could direct the extra matches towards people with more time to play.)
A merge sort tournament would avoid some of the first problem – players would pair off at the start of the night, and bottlenecks only start happening at the end of the first round. It still has the varying number of matches problem though. So our ideal sorting algorithm for a tournament would:
- be able to do lots of comparisons in parallel,
- do about the same number of comparisons on each element, and
- not compare elements if it could infer their order.
The first and third constraints are tricky once it gets going – you can’t have multiple matches running in parallel that could potentially give contradictory results. One approach for small numbers of players might be to brute-force it – keep a directed graph of players and schedule matches for which (a) there currently isn’t a path in either direction and (b) there won’t be a path in either direction for any of combination of outcomes of the games currently running. I actually started coding this when I got home, but was quickly distracted by something less confusing.
I gotta break out my Knuth vol. 2…1 comment