OxfordCroquet Logo

Dr Ian Plummer

Donation Button

http://oxfordcroquet.com/tech/knockout/index.asp
Technical
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:

AB    CD
AC   BD
AD   BC

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:

A     
46.71%
B  
26.98%
C  
14.40%
D  
7.02%
E  
3.09%
F  
1.23%
G  
0.44%
H  
0.14%

In addition we can see what the effect of "luck of the draw" is on each of the players

      Best     Worst
A   
61.89%
 
38.04%
B  
42.14%
 
19.18%
C  
29.08%
 
8.13%
D  
18.37%
 
3.11%
E  
10.69%
 
1.15%
F  
4.58%
 
0.41%
G  
1.90%
 
0.14%
H  
0.57%
 
0.04%

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:

A    
52.66%
B  
27.84%
C  
12.42%
D  
4.77%
E  
1.59%
F  
0.51%
G  
0.16%
H  
0.05%

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.

Dave

Author: David Maugham
All rights reserved © 2010


Updated 19.x.10
About, Feedback
oxfordcroquet.com/tech/knockout/index.asp
on www.oxfordcroquet.com
Hits: 2387