Win probability in a free-for-all of N players

[Norbo11]

Has anyone come up with an appropriate formula for calculating a win probability in a free-for-all match? I'm aware of the formula for a two-team matchup or a 1v1 matchup, but I haven't seen one for a free-for-all.

I've tried to devise my own formula by simply defining the win probability for a player as the average of all win probabilities in 1v1 matchups against all the other opponents. It seems to give reasonable results intuitively, but I'm not sure about the mathematical validity of this approach.

import itertools
import math
from itertools import combinations
from typing import List, Tuple, Dict

import trueskill
from trueskill import Rating


def win_probability(team1: List[Rating], team2: List[Rating]):
    delta_mu = sum(r.mu for r in team1) - sum(r.mu for r in team2)
    sum_sigma = sum(r.sigma ** 2 for r in itertools.chain(team1, team2))
    size = len(team1) + len(team2)
    denom = math.sqrt(size * (trueskill.BETA * trueskill.BETA) + sum_sigma)
    ts = trueskill.global_env()
    return ts.cdf(delta_mu / denom)


def win_probability_free_for_all(all_ratings: List[Rating]) -> List[float]:
    all_ratings_with_index: List[Tuple[int, Rating]] = [(i, rating) for i, rating in enumerate(all_ratings)]
    matchups: List[Tuple[Tuple[int, Rating], Tuple[int, Rating]]] = combinations(all_ratings_with_index, 2)
    total_probability: float = 0.0
    player_index_to_win_probabilities: Dict[int, List[float]] = {i: [] for i in range(len(all_ratings))}

    for rating_with_index_1, rating_with_index_2 in matchups:
        index1, rating1 = rating_with_index_1
        index2, rating2 = rating_with_index_2

        win_probability_1 = win_probability([rating1], [rating2])
        win_probability_2 = win_probability([rating2], [rating1])

        player_index_to_win_probabilities[index1].append(win_probability_1)
        player_index_to_win_probabilities[index2].append(win_probability_2)

        total_probability += win_probability_1 + win_probability_2

    win_probabilities = []

    for index, win_probabilities in player_index_to_win_probabilities.items():
        win_probability_for_player = sum(win_probabilities) / total_probability
        win_probabilities.append(win_probability_for_player)

    return win_probabilities


assert win_probability_free_for_all([Rating(mu=25, sigma=50 / 3) for _ in range(4)]) == [
    0.24999999999999997,
    0.24999999999999997,
    0.24999999999999997,
    0.24999999999999998
]

assert win_probability_free_for_all(
    [Rating(mu=30, sigma=50 / 3)] + [Rating(mu=25, sigma=50 / 3) for _ in range(3)]) == [
       0.2907628713511193,
       0.23641237621629355,
       0.23641237621629355,
       0.23641237621629355
]

assert win_probability_free_for_all([Rating(mu=30, sigma=0.1)] + [Rating(mu=25, sigma=0.1) for _ in range(3)]) == [
    0.40093001957080043,
    0.19968999347639982,
    0.19968999347639982,
    0.19968999347639982
]

Would anyone more familiar with the mathematics be able to verify these results, or give some insight as to why it might be correct/incorrect? Many thanks.

[vivekjoshy]

@Norbo11 We wrote one for openskill. When I originally wrote it I tested it with trueskill and it works at predicting n-player games fine.

Lines for predicting wins: https://github.com/OpenDebates/openskill.py/blob/fa0b3543f12a2d2cc6d222d27795b2e616187636/openskill/rate.py#L327-L361

Relevant Pull Request: vivekjoshy/openskill.py#48