Is a Knock-Out Fair?
David Maugham argues as to why a seeded draw is an approximation to a 'fair draw' for a knock-out.
OK, word of warning, this may get a bit technical, and it's based on a spread sheet that I last used over 5 years ago, but the figures should all be correct.
Anyhow, for a given number of players (I'll always use a power of two for simplicity) there will be a fixed number of unique draws. E.g. for 4 players, there are 3:
There are a number of equivalent draws (e.g. AB CD is the same as DC AB), but they are all equally likely, so can be essentially ignored.
It turns out that there are 315 unique draws for an 8-player knockout, 638 million 16-player draws, and 1.2x1026 32-player draws.
Right, so, if we give each of the players a "grade" we can work out the probability that each player will win any given draw. Going back to the 4-player draw, the probability that A wins, is equal to P(A bt B)*(P(A bt C)*P(C bt D)+P(A bt D)*P(D bt C)). We can repeat this calculation for each of B, C & D to give them all a probability of winning that particular draw. Then we can repeat the whole process for each of the other 2 unique draws.
Since, in a random draw, each of these possible unique draws is equally likely we can average out each player's probability of winning. A draw which gave these exact probabilities would be the ideal "fair" draw, since it would be equivalent to running the knockout with each of the possible arrangements of players. It would avoid all the problems with random draws, where all (or all but one) of the best players are in the same half.
With the computer, I can work out the probabilities for an 8-player draw (315 combinations) but a 16-player event (638 million combinations) was out of the range of an Excel spread sheet ...
Some actual numbers for an 8-player draw where the players (A-H) have grades 180, 170, 160, ..., 120, 110 :
Average probability of winning:
In addition we can see what the effect of "luck of the draw" is on each of the players
So in this instance A's probability can vary by about 23%, which seems like a lot to leave to random chance.
Now in the real world, the problem arises that we don't know which of our 315 draws is the one which is closest to the ideal without running a probability simulation for each of them. This may be possible for an 8-player event, but would be prohibitive for a 16-player event, and is likely to take many centuries (or until quantum computing becomes a reality) to calculate any one set of 32-player draws for any particular group of players.
But we know we have a draw that we now we can easily reproduce, and it will scale easily, and requires no special computing power to produce:
1v8 5v4 3v6 7v2
how does this compare? Well:
It's not perfect - the better players do get a slight advantage over the ideal average draw (and the worse players are at a slight disadvantage), but all in all it's not bad. Obviously the probabilities and the difference between the ideal and the seeded draws are completely dependent on the respective grades of all of the players, these figures are just indicative of the principle.
This basically means that the seeded draw is a reasonable approximation to the ideal "fair" draw which is the average of all the possible draws.
Also, for what it is worth, this is why you don't seed each round. Doing that gives the best players a massive advantage, and it does not approximate to the "fairest" draw.
Paul Billings adds (x.2014):
The "standard" knockout draw is fairer than Dave indicates. I submit that the round robin in which everyone tries to win is the fairest format and should be the metric by which "fairness" is judged.
We can estimate the probability of winning the round robin by running it multiple times and counting the number of times each player wins. For the players in Dave's example, the column "Round Robin" gives the probability of each winning the round robin and the column Knockout gives the probability of winning a standard seeded knockout (the latter copied from Dave's article above):
Note the effectively identical probabilities. In my opinion, we play knockouts because we don't have the time or space for a full round robin. The fact that the probability of winning remains unchanged would indicate the standard seeded knockout is every bit as fair as the round robin and does NOT advantage or disadvantage anyone.
All rights reserved © 2010