Big O of Swiss Tournament

[Ambeco]

The Swiss Tournament (http://en.wikipedia.org/wiki/Swiss-system_tournament) was created as a parellel sort, like a Sorting Network (http://en.wikipedia.org/wiki/Sorting_network). I've been trying to deduce the average and maximum number of rounds for n players. (assuming they are strictly ordered: if A beats B, and B beats C: A will always beat B and C, and that B will always beat C.)
It's easy to show that the top and bottom ranked players are found in log2(n) rounds. However, it's not so easy to show when the second top and bottom ranked players are guaranteed, but I think it's log2(n)+1, and I think the third top and bottom ranked players are log2(n)+1 as well. However, my methods are sloppy and my math-fu is weak. Any tips or answers?
I wrote a program to do these, I'll have to re-run it and measure average and worst cases as best I can, see if that gives any ideas.

[freakish777]

Uhm, Swiss tournaments aren't particularly interested in second, third, fourth, or n ranked players.

You should end up with a bell curvish distribution of players based on their win loss records.

Almost every swiss tournament I've ever attended has been floor(log2(n))+1 (unless n is a power of 2, in which case you don't add the 1) rounds and then optionally cut to top X competitors for an elimination portion.

Finding distinct n ranked players isn't really feasible, you may think "well we just add a round to find the second ranked player." This would necessitate that players are allowed to be paired against each other more than once (not a big deal), but more importantly, now your first ranked player with his/her/it's X-0 record can lose, and no longer be ranked in first. And then you need to add yet another round to get another first ranked player (also it's more than 1 round you need to add)... hence cutting to top X and having an elimination portion.

Let's take an 16 person tournament like this. After 4 rounds:

A 4-0
B 3-1
C 3-1
D 3-1
E 3-1
F 2-2
G 2-2
H 2-2
I 2-2
J 2-2
K 2-2
L 1-3
M 1-3
N 1-3
O 1-3
P 0-4

To find a distinct second, you need to add 2 more rounds at least (and this assumes A always wins, which obviously is a poor assumption in the real world).

Anyways, coding this shouldn't be that difficult, you just need to add a check after each round that determines "is there a distinct n ranked player? no? play another round." Allowing players to be paired multiple times would also be easier to code.

[Ambeco]

Uhm, Swiss tournaments aren't particularly interested in second, third, fourth, or n ranked players.

Actually, I started studying them because it's a fast way to find all the rankings. Maybe nobody cares so they stop early, but the algorithm can do it. Otherwise, it'd be no better than a single-elimination tournament, and far less exciting.

You should end up with a bell curvish distribution of players based on their win loss records.

True, unless players skills are strictly ordered. As players with similar scores play, they flatten out until it's a line.

Almost every swiss tournament I've ever attended...

is only concerned with first place, and so they stop at log2(n)+1.

...now your first ranked player with his/her/it's X-0 record can lose.

Not if the players skills are strictly ordered.

Let's take an 16 person tournament like this. After 4 rounds:

[edit] Corrected, that's a possible setup[/edit]

[EvanED]

This is sort of not on the main thrust of the thread, but...

Uhm, Swiss tournaments aren't particularly interested in second, third, fourth, or n ranked players.

Actually, I started studying them because it's a fast way to find all the rankings. Maybe nobody cares so they stop early, but the algorithm can do it. Otherwise, it'd be no better than a single-elimination tournament, and far less exciting.

Hmm, I'm not sure I agree with "less exciting", except perhaps for the final couple rounds. And it has the benefit that it's way more fun to participate in a swiss tournament than a single-elimination one. (Unless you just add additional games onto the backbone of a single-elimination one.)

Almost every swiss tournament I've ever attended...

is only concerned with first place, and so they stop at log2(n)+1.

Unlikely... more likely to be concerned with the top few places, but not below that.

[Ambeco]

You should end up with a bell curvish distribution of players based on their win loss records.

True, unless players skills are strictly ordered. As players with similar scores play, they flatten out until it's a line.

Ah darn, I just realized in a standard Swiss Sort (players get a point per win), the bubble moves up, requiring first place to play several "middling" players while they flatten. In my coded version, I made an optimization where if A beats B, then A will always be above B (which forces a strict ordering where one wouldn't normally exist), and also greatly reduces the number of rounds required (similar to organizing by win/loss ratio instead of number of wins). Otherwise freakish777 is right that it would take n^2/2 rounds to guarantee a complete ordering. That optimization makes the math much harder. Darn. Nevermind then xkcd. The math is far too hard with that optimization. (and the algorithm without it is too slow to care about.)

[freakish777]

Let's say you do just have A always win, B beats everyone but A, etc and being paired against the same player multiple times isn't allowed.

16 players, 0 rounds, you have all at 0-0 records.
16 players, 1 rounds, you have half at 1-0 records and half at 0-1 records.
16 players, 2 rounds, you have 1/4th at 2-0 records, 1/2 at 1-1 records, and 1/4 at 0-2 records.
16 players, 3 rounds, you have 1/8 at 3-0 records, 6/16 at 2-1, 6/16 at 1-2, 1/8th at 0-3 records.
16 players, 4 rounds, you have 1/16 at 4-0 records, 1/4 at 3-1, 6/16 at 2-2, 1/4th at 1-3, 1/16th at 0-4 records.

You're looking to crush that your N players with one record, 0-0, (a big vertical line) into n players with n distinct records (a big horizontal line) instead of trying to just find the first ranked player (which results in the bell curvish shape). So to get all n players distinctly ranked, you need n-1 rounds (which is a round robin tournament, assuming of course player A being the best can never lose, and the second best player can only lose to the best, and so on, and no draws, otherwise you can have RR tournaments where players A B and C each Rock Paper Scissor each other and beat everyone else). To get just the second ranked player, you need to add 2 rounds (when n is a power of 2, there should be 1 player at X-0 and 4 players at X-1 after log2(n) rounds always, assuming no draws are allowed).

16 players, 5 rounds, you have 1 at 5-0 records (A), 2 at 4-1 (in my paperwork its B and E), 5 at 3-2 (C,D,G,H,K), 5 at 2-3 (F, I, J M, N), 2 at 1-4 (L, O), 1 at 0-5 records (P).

16 players, 6 rounds, you have A at 6-0 (wins all the rest of it's matches), B at 5-1 (wins all the rest of it's matches), C, D and E at 4-2, F, G, H, I, J, K at 3-3 (notice that this is the same number of players at 50% w/l records as two rounds ago), L, M, N at 2-4, O at 1-5 (losses all the rest), and P at 0-6 (loses all the rest).

3rd place? Add two more rounds... Eventually that "mountain" of 6 players in the middle with 50% w/l will go down, but it's going to be there a while.



Also, as far as the "They stop at log2(n) + 1 because they only care about first" is completely wrong. Most tournaments award prizes to the top X competitors, and so there will be a Top 8, Top 16, or Top 32 single elimination rounds. This is why most tournaments do Tie Breakers of some sort (the first is usually Opponent Match Win Percentage, if you went 4-2 and your opponents combined for 26-10, your tie breakers are going to be incredible compared to everyone else at 4-2, if the first isn't OMW% you're doing it wrong).

The best tournaments I've seen have payouts down to 32nd, and then to save time, the cut offs are Top 8 (they play a 3 round single elim tournament), 9-16th (they play a 3 round single elim tournament), 17-24th (they play a 3 round single elim tournament), 25th-32nd (you get the idea).


One final point, your assumption that A always wins is only applicable in 100% skill games (even Chess isn't 100% skill) with no draws and perfect information where once a player has learned to avoid mistake X, they never make mistake X ever again. So not very useful for real world modeling.


EDIT: Bolded most relevant part if you want to tl;dr

[Ambeco]

the cut offs are Top 8 (they play a 3 round single elim tournament

Single elimination only finds first place accurately though. What if the best plays the second best in the first round of the single elim? (Still assuming strictly ordered, as of course, as you say, in the real world, there's chance involved)

Other than that, Wow! you actually worked out all the numbers for exactly what I asked for, and made it easy to understand. Props for that! :shock:
Unfortunately, What I asked for isn't what I was thinking, and I don't think that what I was thinking can be done. My experiments show that if you hold that (if A beats B, then A will at all points be ranked above B and never play B again), then the times are far faster than worst case, but I had forgotten that this is not normal for Swiss Tournaments. I created this algorithm to sort N players such that each player beat the next player down in ranking once, in as few rounds as possible.

Here were my measurements from my tests, where I sorted N (strictly ordered) players 100 times. I am fully aware that 100 is hardly enough to accurately measure maximums, but even so, I expected those measured to be higher. My current test setup is one program saving a file with relative scores, then my algorithm sorts, and saves the results, which the "tester" program reads and verifies. This file IO and double-checking is the reason I'm only doing each test 100 times instead of 1000 or so. (Also, it crashes between 332 and 415 players, I'll look into that.)

Spoiler:

PLAYERS:2 ROUNDS:max:1 avg:1.000
PLAYERS:4 ROUNDS:max:3 avg:2.740
PLAYERS:6 ROUNDS:max:5 avg:4.180
PLAYERS:8 ROUNDS:max:6 avg:5.210
PLAYERS:10 ROUNDS:max:8 avg:6.140
PLAYERS:12 ROUNDS:max:9 avg:6.890
PLAYERS:14 ROUNDS:max:10 avg:7.510
PLAYERS:16 ROUNDS:max:10 avg:7.970
PLAYERS:18 ROUNDS:max:11 avg:8.570
PLAYERS:20 ROUNDS:max:12 avg:9.230
PLAYERS:22 ROUNDS:max:16 avg:9.570
PLAYERS:24 ROUNDS:max:14 avg:9.870
PLAYERS:26 ROUNDS:max:15 avg:10.530
PLAYERS:28 ROUNDS:max:15 avg:10.930
PLAYERS:30 ROUNDS:max:16 avg:11.470

PLAYERS:37 ROUNDS:max:19 avg:12.900
PLAYERS:46 ROUNDS:max:26 avg:14.550
PLAYERS:57 ROUNDS:max:24 avg:16.260
PLAYERS:71 ROUNDS:max:31 avg:20.050
PLAYERS:88 ROUNDS:max:43 avg:23.570
PLAYERS:110 ROUNDS:max:45 avg:26.520
PLAYERS:137 ROUNDS:max:55 avg:32.870
PLAYERS:171 ROUNDS:max:64 avg:42.950
PLAYERS:213 ROUNDS:max:89 avg:49.770
PLAYERS:266 ROUNDS:max:115 avg:61.410
PLAYERS:332 ROUNDS:max:147 avg:84.280

[KnightExemplar]

Assuming perfect information, and perfect play from everyone, single elimination finds the winner in log_2(n) battles.

However, it is easy to see that single-elimination fails in any situation with probabilities. For example, if you have 31 players, all equal in skill, and the "best player" has such significant skill advantage that he has a 80% chance of winning against everyone... There is only a 32% chance that he wins the Swiss Tournament.

[EvanED]

Assuming perfect information, and perfect play from everyone, single elimination finds the winner in log_2(n) battles.

However, it is easy to see that single-elimination fails in any situation with probabilities. For example, if you have 31 players, all equal in skill, and the "best player" has such significant skill advantage that he has a 80% chance of winning against everyone... There is only a 32% chance that he wins the Swiss single-elimination Tournament.

Typo.

(I don't want to compute the probability for the swiss tourney, so theoretically it's the same.)