Single elimination tournament probabilities

[CraigD]

Here’s a probability problem, inspired by the one in the thread 22087:

 

4 players, Alice, Bob, Carol, and Don, are in a single elimination tournament. The tournament begins with a semifinal round where each player is randomly assigned one of the others as an opponent. The winners of the semifinal round games oppose one another in the final round. The winner of the final round game gets 1st place. The loser gets 2nd. The two losers of the semifinal round oppose one another in a loser round. The winner of the loser round game gets 3rd place. The loser gets 4th.

 

The probabilities of a given player beating another are:

Alice beats Bob = .65

Alice beats Carol = .65

Alice beats Don = .8

Bob beats Carol = .5

Bob beats Don = .71

Carol beats Don = .71

 

What are the probabilities of each player finishing 1st, 2nd, 3rd, or 4th in the tournament?

[A23]

Hi again,

 

I tried like this :

 

the semi-finals are : a) (A-B & C-D) b) (A-C & B-D) and c) (A-D & B-C) the different semi-finals.

 

the finals happens after, for example,

 

A

B - A,B --

 

C

D - C, D --

 

-----------------------

 

A

C---A,C

 

B---B,D

D

 

------------------

 

A

D----A,D----

 

B----B,C----

C

 

------------------

 

those possibilities have the same prob. to happen.

 

then, letting (i,j)=prob(i wins vs. j) :

 

(for example PA1 : A beats B and A beats C and C beats C, and all other possibilities : summarized by sums over every possible semi-final

 

P(A1)=1/3[(A,B)*(A,C)*(C,D)+(A,B)*(A,D)*(D,C)]+1/3[...]=1/3[math]\sum_{j\neq 1}\sum_{k\neq 1,j}\sum_{l\neq 1,j,k}(1,j)*(1,k)*(k,j)[/math]

 

for 2nd : P(i,2nd)=1/3[math]\sum_{j\neq i}\sum_{k\neq i,j}\sum_{l\neq i,j,k}(i,j)*(k,i)*(k,j)[/math]

 

for 3rd : P(i,3rd)=1/3[math]\sum_{j\neq i}\sum_{k\neq i,j}\sum_{l\neq i,j,k}(j,i)*(k,l)*(i,l)[/math]

 

for 4th : P(i,4th)=1/3[math]\sum_{j\neq i}\sum_{k\neq i,j}\sum_{l\neq i,j,k}(j,i)*(k,j)*(k,l)[/math]

 

I made a program to sum out these, getting :

 

Probwin 0-1 0.650000 rev : 0.350000

Probwin 0-2 0.650000 rev : 0.350000

Probwin 0-3 0.800000 rev : 0.200000

Probwin 1-2 0.500000 rev : 0.500000

Probwin 1-3 0.710000 rev : 0.290000

Probwin 2-3 0.710000 rev : 0.290000

 

Prob A be 1st : 0.473850 2nd 0.226150 3rd : 0.219850 4th 0.080150

Prob B be 1st : 0.231030 2nd 0.288970 3rd : 0.290230 4th 0.189770

Prob C be 1st : 0.231030 2nd 0.288970 3rd : 0.290230 4th 0.189770

Prob D be 1st : 0.064090 2nd 0.195910 3rd : 0.199690 4th 0.540310

 

I don't know if you got these results too.

 

I then checked the other formula, from "Probability Question" thread : we should have : A2=A1*(B1(1-B1)+C1/(1-C1)+D1/(1-D1))~0.317

 

But I got another result from the calculation I did here, namely 0.226 ?

[A23]

It's not very clear, I noticed. Since I changed A,B,C,D in 1,2,3,4 in the sums, for the program.

 

For example the prob A1st were, completely :

 

(1st possible semifinal) : (A,:)(A,C)(C,D)+(A,:)(A,D)(D,C)

(2nd possible semifinal) : (A,C)(A,;)(B,D)+(A,C)(A,D)(D,B)

(3rd possible semifinal) : (A,D)(A,B)(B,C)+(A,D)(A,C)(C,B)

 

for A2nd : (A,B)(C,A)(C,D)+...

 

A3rd : (B,A)(C,D)(A,D)+....

 

A4th : (B,A)(C,B)(C,D)+....

 

which i wrote in term of sums over integer, to put in a C code.

[CraigD]

Prob A be 1st : 0.473850 2nd 0.226150 3rd : 0.219850 4th 0.080150

Prob B be 1st : 0.231030 2nd 0.288970 3rd : 0.290230 4th 0.189770

Prob C be 1st : 0.231030 2nd 0.288970 3rd : 0.290230 4th 0.189770

Prob D be 1st : 0.064090 2nd 0.195910 3rd : 0.199690 4th 0.540310

 

I don't know if you got these results too.

I got exactly the same results. :thumbs_up You're good at this stuff, A23! :)

 

Here’re the chunk of MUMPS code (MUMPS may need a lot of parenthesis, and look like somewhat like line noise, but you can get a lot of math in just a little code ;)) I used:

s E1="(CD*AB*AC)+((1-CD)*AB*AD)+(BD*AC*AB)+((1-BD)*AC*AD)+(BC*AD*AB)+((1-BC)*AD*AC)/3"
s E2="(CD*AB*(1-AC))+((1-CD)*AB*(1-AD))+(BD*AC*(1-AB))+((1-BD)*AC*(1-AD))+(BC*AD*(1-AB))+((1-BC)*AD*(1-AC))/3"
s E3="((1-CD)*(1-AB)*AC)+(CD*(1-AB)*AD)+((1-BD)*(1-AC)*AB)+(BD*(1-AC)*AD)+((1-BC)*(1-AD)*AB)+(BC*(1-AD)*AC)/3"
s E4="((1-CD)*(1-AB)*(1-AC))+(CD*(1-AB)*(1-AD))+((1-BD)*(1-AC)*(1-AB))+(BD*(1-AC)*(1-AD))+((1-BC)*(1-AD)*(1-AB))+(BC*(1-AD)*(1-AC))/3"
s (AB,AB0)=.65,(AC,AC0)=.65,(AD,AD0)=.80,(BC,BC0)=.50,(BD,BD0)=.71,(CD,CD0)=.71 w @E1," ",@E2," ",@E3," ",@E4
s AB=(1-AB0),AC=BC0,AD=BD0,BC=AC0,BD=AD0,CD=CD0 w @E1," ",@E2," ",@E3," ",@E4
s AB=(1-BD0),AC=(1-CD0),AD=(1-AD0),BC=BC0,BD=(1-AB0),CD=(1-AC0) w @E1," ",@E2," ",@E3," ",@E4

I think your common notation math expression

P(A1) = ... = 1/3 [math]\sum_{j\neq 1}\sum_{k\neq 1,j}\sum_{l\neq 1,j,k}(1,j)*(1,k)*(k,j)[/math]

should read

P(A1) = ... = 1/3 [math]\sum_{j\neq 1}\sum_{k\neq 1,j}\sum_{l\neq 1,j,k}(1,j)*(1,k)*(k,l)[/math]

or

P(A1) = ... = 1/3 [math]\sum_{j\neq 1}\sum_{k\neq 1,j}\sum_{l\neq 1,j,k}(1,j)*(1,k)*(j,l)[/math]

but as the actual code you’re using in your program works, writing it in pretty LaTeX isn’t terribly important, IMHO. In this case, since even with this notation, the expression is not general (that is, it works only for the described tournament of exactly 4 players), IMHO it’s more readable just to give the probabilities as something like this:

 

[math]A_1=\frac{AB \cdot AC \cdot BD+AB \cdot AC \cdot CD+AB \cdot AD \cdot BC+AB \cdot AD \cdot DC+AC \cdot AD \cdot CB+AC \cdot AD \cdot DB}3[/math]

 

[math]A_2=\frac{AB \cdot CA \cdot CD+AB \cdot DA \cdot DC+AC \cdot BA \cdot BD+AC \cdot DA \cdot DB+AD \cdot BA \cdot BC+AD \cdot CA \cdot CB}3[/math]

 

[math]A_3=\frac{AB \cdot CA \cdot DB+AB \cdot CB \cdot DA+AC \cdot BA \cdot DC+AC \cdot BC \cdot DA+AD \cdot BA \cdot CD+AD \cdot BD \cdot CA}3[/math]

 

[math]A_4=\frac{BA \cdot CA \cdot DB+BA \cdot CA \cdot DC+BA \cdot CB \cdot DA+BA \cdot CD \cdot DA+BC \cdot CA \cdot DA+BD \cdot CA \cdot DA}3[/math]

 

Where [imath]A_1[/imath] is the probability of A winning the tournament, AB is the probability of A beating B, etc.

I then checked the other formula, from "Probability Question" thread : we should have : A2=A1*(B1(1-B1)+C1/(1-C1)+D1/(1-D1))~0.317

 

But I got another result from the calculation I did here, namely 0.226 ?

That’s to be expected, as in answering the question in 22087, we made an assumption about how we could get probabilities such as “Alice beats Bob (in a contest of just Alice vs. Bob)” that, while simple seeming, don’t work exactly as the simple given “A beats B” probabilities and precise definition of a “tournament” given in this thread.

 

That’s in large part why I started this thread – to show that the precise design of an algorithm (a “tournament” in this case) that generates outcomes from probabilities has a critical effect on the probabilities of those outcomes. You can have great fun with this, designing tournaments that seem “fair”, but where the probability of a player winning has little, or even an inverse, correlation to his probability of beating the other players. :evil:

 

Anybody want to try generalizing the probabilities of a player finishing 1st, 2nd, etc in a tournament of this design with any number of players that’s a power of 2 (8 players, 16, 32, 64, etc)? It’s not very hard programming, but trying to write it in a nice notations is a challenge – I’m not even sure what sort of notation, other than some computer programming language, this can be done in. :shrug:

[A23]

Thanks.

 

Yes, I made a mistake in the formula.

 

Then, I thought, we could also choose other probabilities than 1/3, for the random choices for the starting teams, and get other results for this set of probabilities. But these should be more logically uniform, since we have no data on the choosing method.