0
$\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 at 22:23
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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