[enhancement] add win probabilities
djcunningham0 opened this issue · 2 comments
Add a method to the MultiElo class to calculate the probabilities of each player coming in first place, second place, ..., last place.
To calculate these probabilities, we can assume each player gets a "score" sampled from a Gumbel distribution. For example, if we have two players with ratings RA and RB and we're using Elo parameter D = 400, then their scores would be SA ~ Gumbel(RA, 400) and SB ~ Gumbel(RB, 400). The difference in two Gumbel distributions with the same scale parameter is a logistic distribution, which aligns with how Elo calculates the win probability for pairwise matchups. See my answer here for more details.
There are probably two ways to do this:
- Simulate it. Sample scores for each player a bunch of times and then count how many times each player finishes in each place.
i. Pros: Easy. Probably scales reasonably well with number of players, but answers might get less exact.
ii. Cons: Possibly slow depending on number of simulations, doesn't return an exact answer, won't return the same answer every time - Calculate it analytically.
i. Pros: Exact answer. Faster (at least for small number of players).
ii. Cons: Need to figure out how to do it. Might not scale well for large number of players.
iii. Note: probably add a parameter to only return 1st place probability for each player rather than every possible place. This would probably save some computation time if that's all the user wants.
Probably going to need to use simulations. Fortunately, I was able to make the simulation pretty efficient (pull request coming soon).
Analytical answer would be difficult. In general, there's no easy way to calculate the probability that a random variable is the kth smallest (see my question here). And calculating all of the probabilities analytically would likely be very complicated because they'd all be conditional probabilities (I have a question posted on Cross Validated here but I'm not holding out much hope for an answer).
Fixed in #2