1
$\begingroup$

Suppose there is a game with three participants: Player A, Player B, and Player C. One player will finish in first place, another in second place, and another in third place (no ties allowed). I know the probability of all pairwise outcomes. For example, let's assume that Player A beats Player B 75% of the time, Player A beats Player C 90% of the time, and Player B beats Player C 75% of the time.

Given those pairwise probabilities, how can I calculate the probability of each possible outcome? With three players there are six possible outcomes: (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), or (C, B, A). I need to generalize to $N$ players for any $N \ge 3$. I'm ideally looking for an analytical answer, not a simulation.

If it helps, we can assume that the pairwise probabilities are derived from Elo ratings using a logistic distribution (description on Wikipedia if you're unfamiliar with Elo). This ensures that the pairwise probabilities are consistent (e.g., if A is likely to beat B and B is likely to beat C, then A is even more likely to beat C).

$\endgroup$
1
  • $\begingroup$ I think that in general there isn't a unique answer. e.g. if each player has a 50% chance of beating each other player, that would be consistent with all 6 outcomes having equal probability, but also with ABC and CBA each having 50% probability. $\endgroup$
    – fblundun
    Apr 9, 2021 at 22:23

2 Answers 2

1
$\begingroup$

Here's what I ended up doing. My original question may have been a little ambiguous, but this solution gave me what I needed.

Rather than using the probabilities that Player A would beat Player B and so on, I assumed each player would have a "score" $S_i$ sampled from some distribution $D_i$. So $S_A \sim D_A$, $S_B \sim D_B$, and $S_C \sim D_C$, all independent, and then we sort the scores in descending order to see who gets first place, second place, and so on. Each of $D_i$ is the same type of distribution but with different parameters. The challenge is to select a distribution and parameters that are consistent with the pairwise probabilities. That is, if we take the example pairwise probabilities from my original question, we want to select distribution parameters such that $P(S_A > S_B) = 0.75$, $P(S_A > S_C) = 0.9$, and $P(S_B > S_C) = 0.75$.

In my case, the Gumbel distribution was the answer. That's because the difference of two Gumbel random variables follows a logistic distribution (see Wikipedia), and my pairwise probabilities are derived from the logistic function according to the standard Elo rating formula. (Technically, I used a modified version of the Gumbel distribution where I replaced the natural logs with log base 10).

To demonstrate, suppose I have three players with Elo ratings $R_A$, $R_B$, and $R_C$. Then according to Elo the probability of Player A beating Player B is $$ \frac{1}{1 + 10^{-(R_A - R_B) / D}} $$ for some constant $D$ (often $D = 400$) and the other pairwise probabilities are defined similarly. Now, look at what happens when we sample the "scores" for each player $S_A \sim \text{Gumbel}(R_A, D)$, $S_B \sim \text{Gumbel}(R_B, D)$, and $S_C \sim \text{Gumbel}(R_C, D)$. We want to calculate $P(S_A > S_B) = P(S_A - S_B > 0)$. Since $S_A$ and $S_B$ are drawn from Gumbel distributions with the same scale parameter, $S_A - S_B \sim \text{Logistic}(R_A - R_B, D)$. Using the CDF of the (base 10) logistic distribution, $$ P(S_A - S_B > 0) = \frac{1}{1 + 10^{-(R_A - R_B) / D}} $$ which is the same win probability that Elo predicted. This scales to any number of players $N \ge 2$.

In conclusion, we can simulate multi-player outcomes that are consistent with the pairwise win probabilities. My next goal is to calculate the "distribution" of where each player will finish. For example, Player A will finish in first place with probability $p_{1A}$, second place with probability $p_{2A}$, and so on. It's simple to do with a simulation, but if anyone has a way to derive those probabilities analytically I would be interested.

$\endgroup$
-1
$\begingroup$

The ELO ratings apply to chess. If player 1 has the rating R1 and player 2 has the rating R2 then the probability of player 1 beating player 2 is as you suggest above. They also apply to soccer, despite soccer matches frequently ending in a draw. You can use archives of past soccer results in which the respective elos before the match are included to work out a formula for P(home win), P(draw), P(away win). In soccer the team playing at home is usually awarded a bonus. I have a ready reckonner somewhere in java. But in chess also draw is a possibility, so that too can be worked out.

However what you are really interested in is multiplayer events. Such as discus throwing. A discus throwing event between 3 athletes can be arranged without loss of generality by making it into a series of 2 person contests. So if the three guys are A,B and C, we can for example ask C to wait and then face the winner of the contest between A and B. So with this rule you can work out the probabilities of A,B an C for the three way event. Then as there are 3 possibilities of doing that you take the averages.

What happens when there are N contestants though ? It's N! orderings and N! can get big. Is there some simplification ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.