Chances of player A winning a chess tournament?

Tags:
1. Sep 3, 2016

TheSodesa

1. The problem statement, all variables and given/known data
4 Players (A, B, C, and D) enter a chess tournament. The probabilities of them winning each other have been calculated based on their previous games. The results are in the below table:

\begin{array}{|c|cccc|}
\hline\\ \\
& \text{A wins} & \text{B wins} & \text{C wins} & \text{D wins} \\
\hline\\
A & - & 0.4 & 0.6 & 0.7\\
B & 0.6 & - & 0.2 & 0.3\\
C & 0.4 & 0.8 & - & 0.4\\
D & 0.3 & 0.7 & 0.6 & -\\
\hline
\end{array}

What is the probability of A winning the tournament, assuming no games will end in a tie?

2. Relevant equations

Combinations:

{n \choose k} = \frac{n!}{k!(n-k)!}

Permutations:

p(k) = k!

Independent probability:

P(A \cap B) = P(A)P(B)

P(A \cup B) = P(A) + P(B) - P(A \cap B)

The multiplicative rule:

P(A \cap B) = P(B)P(A|B)

3. The attempt at a solution

Since the rules were not specified in the problem statement, I'm assuming everybody will play against everybody, meaning each player has 3 opponents. Therefore the total number of games, $N$, will be
$$N = 3! = 6$$

For A to win, he has to win the most games. If A wins all of his games, he is sure to win the tournament. If he loses 1 game, he still has a chance of winning, assuming the other players don't reach 2 victories. He is certainly not going to win if he loses more than 1 game.

Now let's denote $A$ = "Player A wins", and let $X$ denote the number of victories player A has.
The number of ways $X = 3$ is ${3 \choose 3} = 1$.For $X = 2$ the number is ${3 \choose 2} = 3$

Then
\begin{align*}
P(X = 3) &= (0.6)(0.4)(0.3) = 0.072\\
P(X = 2) &= \stackrel{\text{Loses against B}}{(0.4)(0.4)(0.3)}
+ \stackrel{\text{Loses against C}}{(0.6)(0.6)(0.3)}
+ \stackrel{\text{Loses against D}}{(0.6)(0.4)(0.7)}\\
&= 0.324
\end{align*}

Now the total probability (there's another formula for this, but I don't think it applies here since, I don't know the probabilities of the partitions of the sample space $\Omega$):
\begin{align*}
P(A)
&= P((X = 3) \cup (X = 2))\\
&= P(X=3) + P(X=2) - P((X =3) \cap (X=2))
\end{align*}

This is where I'm stuck (And I'm not sure my approach is "the" correct one in the first place.) I can't seem to get rid of that last probability of the intersections by using $(5)$, because none of the events seem to be dependent on each other.

What to do?

2. Sep 3, 2016

TomHart

As you stated, there are a total of 6 games. That means there are a total of 6 wins and 6 losses. If player A only wins 2 games, is it possible for all other players to win less than 2 games so that player A will have the most wins?

3. Sep 3, 2016

TheSodesa

We have 4 players. If A wins two times, that automatically means 2 other players have lost 1 game and 1 player has won 1 game. At this stage player A has played all of the games he's going to play.

Then, if we proceed in order, player B plays his 2 other games. He has now either lost 1 game or won 1 game. Since he still has 2 games left, it is possible for him to win against A (or reach a tie) if he wins both of those games. Therefore the only chance of A winning at this point is if B loses both games.

That would mean that C, who has now played 2 games (against A and B) has 1 victory (against B, since B had to lose both remaining games) and 1 loss (against A). He can still reach A if he wins the last game against D. Therefore D has to win, but then D would also have 2 victories (because he would have had to defeat B).

Therefore the only way of A winning is for him to win all of his games?

4. Sep 3, 2016

Staff Emeritus
Suppose A defeats B and C but loses to D. B defeats C and D but loses to A.. C defeats D and loses to A and B. D defeats A and loses to B and C. Who wins?

5. Sep 3, 2016

TheSodesa

Nobody?

I mean, A and B would have tied, right? Here's a table of the situation you described:

6. Sep 3, 2016

TomHart

So if 2 players each won 2 matches, then you have to decide how to work this problem. The way I see it, there are 3 possibilities: 1) Like you said, nobody wins. 2) The player who won the head-to-head match-up between the two players with 2 wins is awarded the tournament victory. 3) The two players are both awarded the tournament victory - kind of like when they give 2 gold medals in the olympics (on rare occasions).

I suppose the right method is whatever gives a result of p=0.196.

7. Sep 3, 2016

TheSodesa

Ok, but...

My mind is absolutely racing right now. There are so many possibilities (permutations) and I don't have a systematic approach to this sort of problem. Even in the case of A winning all three games, the other players could have different arrangements of victories and losses.

I don't really even know where to begin.

8. Sep 3, 2016

SammyS

Staff Emeritus
I think it's unlikely that the tournament would be Round-Robin, i.e. everyone plays everyone else. If it were Round-Robin, there would be the possibility of ties for the overall tournament, either a three way tie or three ways to get a two way tie.

I expect that the tournament would be set up in brackets. For this,three possible pairings.

9. Sep 3, 2016

TheSodesa

I was just about to correct the problem description. It actually says (I don't know how I missed this), that at first pairs are randomly selected, after which the 2 survivors will play against each other for the 1st place. This means there are 2 rounds/tiers to the tournament. One winner, one second place and two dropouts.

In the first round A has a 1/3 chance of ending up playing against each of the other players. After winning this round, the probability of him winning the first position is based on the statistics given in the OP and who won the other match.

10. Sep 3, 2016

TheSodesa

Now the number of ways A can play against the others is ${3 \choose 2} = 3$. These are (A vs B and C), (A vs B and D) and finally (A vs C and D). The order doesn't matter as much, these are the possible combinations.

Now the probabilities of A winning in these 3 match-ups are:

\begin{align*}
P(\text{B and C}) &= (0.6)(0.4) = 0.24\\
P(\text{B and D}) &= (0.6)(0.3) = 0.18\\
P(\text{C and D}) &= (0.4)(0.3) = 0.12
\end{align*}

But now I'm stuck again. The events seem to be mutually exclusive, which would lead me to just sum the probabilities together to come up with the final probability, but that would be too much.

EDIT: Dividing 0.54 by 3 yields 0.18, which is just a little too little.

11. Sep 3, 2016

TheSodesa

Alright. I got a little help from someone on Reddit. Apparently the problem was just as simple as I feared, although quite annoying. I just had to go through all of the possible cases of e.g. A winning B while C defeated D, and then A defeating C in the following manner:

(P(A wins vs B) * P(C wins vs D) * P(A wins vs C) + ||(A wins B) and (C wins D) and (A wins C)

P(A wins vs B) * P(D wins vs C) * P(A wins vs D) +

P(A wins vs C) * P(D wins vs B) * P(A wins vs D) +

P(A wins vs C) * P(B wins vs D) * P(A wins vs B) +

P(A wins vs D) * P(B wins vs C) * P(A wins vs B) +

P(A wins vs D) * P(C wins vs B) * P(A wins vs C)) = 0.588

Then all I had to do was divide the result by three to get rid of the repeating cases and end up with the result of 0.196. This was the intuitive approach, but I'm still having a little trouble thinking about this in terms of set theory.

I'm also wondering, whether there would have been a cleaner approach. Inserting that expression into my calculator was a pain in the butt.

12. Sep 4, 2016

haruspex

I don't claim cleaner, but fewer keystrokes. Writing ab for P(A beats B) etc.,