3
$\begingroup$

In a multiplayer game up to 10 players can play against each other and only 1 player can win. There can be no collaboration between players.

Let's assume that the 10 players are called: A, B, C, D, E, F, G, H, I and J.

They play various games:

1) A, B, C, D where A wins,

2) D, E where D wins,

3) A, G, H where G wins,

4) A, B, C, D, E, F, G, H where H wins,

...

300) C, D, E, F where F wins.

How can I know the probability of a given player, let's say A, winning when playing against an arbitrary set of players, let's say: C, D, E, F and J?

Shall I use some sort of Elo rating? Or apply in some way the Bayes Theorem?

$\endgroup$
2
  • 1
    $\begingroup$ In general you can't without making some assumption (usually based on the way the game is played - in particular the roles of luck and skill in determining the outcome of the game). To get you started you could look at TrueSkill, which is used in online matchmaking for Xbox. You can google the word or read about it here: mbmlbook.com/TrueSkill.html $\endgroup$
    – Maurits M
    May 16, 2020 at 7:47
  • $\begingroup$ @MauritsM the question is: how can I infer it from only knowing the results of prior games? $\endgroup$
    – Newbie
    May 18, 2020 at 18:07

2 Answers 2

2
$\begingroup$

If A plays a tournament with B, C, D and A wins then this can be coded as A beats B, A beats C and A beats D. In your example this gives the following tournament matrix:

P N A B C D E F G H
1 A . 1 1 1 . . 0 0
2 B 0 . . . . . . 0
3 C 0 . . . . 0 . 0
4 D 0 . . . 1 0 . 0
5 E . . . 0 . 0 . 0
6 F . . 1 1 1 . . 0
7 G 1 . . . . . . 1
8 H 1 1 1 1 1 1 1 .

To establish a meaningful win probability between players x, y, a winning path between x to y and y to x is needed.

Update-1 Add the folowing tournaments to the example to make the tournament matrix connected.

 5) H, B where B wins,
 6) B, C where C wins,
 7) C, E where E wins,

The resulting tournament matrix will be:

P N |1 2 3 4 5 6 7 8 |Pts| Rrtg
1 A |. 1 1 1 . . 0 0 | 3 | 104.87
2 B |0 . 0 . . . . 1 | 1 |-157.99
3 C |0 1 . . 0 0 . 0 | 1 |-290.67
4 D |0 . . . 1 0 . 0 | 1 |-178.03
5 E |. . 1 0 . 0 . 0 | 1 |-276.60
6 F |. . 1 1 1 . . 0 | 3 | 142.96
7 G |1 . . . . . . 1 | 2 | 360.54
8 H |1 1 1 1 1 1 1 . | 7 | 294.91

Let Rrtg be the relative Elo ratings so that the expected score equals the actual score (Pts). See also: Obtain ranking from pairwise comparison with continuous outcome.

Derived from the relative ratings (Rrtg):

Pr(A beats C) = pnorm(104 - -290.67,0, 2000 / 7) = 92%
Pr(A beats D) = pnorm(104 - -178.03,0, 2000 / 7) = 84%
Pr(A beats E) = pnorm(104 - -276.60,0, 2000 / 7) = 91%
Pr(A beats F) = pnorm(104 -  142.96,0, 2000 / 7) = 45%

The probability that A defeats all of his opponents in a single tournament is equal to
Π Pr(A beats x) = 31%, where x in (C, D, E, F)

Update-2 An alternative approach is to replace the normal distribution by a linear function: p800(D) = D / 4C + 0.5,
where C=200 is the Elo class interval, 1/4 the slope of the logistic function at x=0.

Solving the Elo ratings for all games simultaneously equates solving a system of linear equations. In the previous example the solution becomes:
Rrtg = c(84.31, -126.40, -225.99, -150.88, -212.94, 107.06, 306.80, 218.04)

This gives:

Pr(A beats C) = p800(84.31 - -225.99) = 89%
Pr(A beats D) = p800(84.31 - -150.88) = 79%
Pr(A beats E) = p800(84.31 - -212.94) = 87%
Pr(A beats F) = p800(84.31 -  107.06) = 47%

A's overall probability equals 89% * 79% * 87% * 47% = 29%.

Note that these ratings are equivalent to least squares ratings.
$\endgroup$
1
$\begingroup$

You might use an elo rating, but whether it is a good model depends on your game.

An elo rating relates to an underlying latent variable similar to a probit model where each player has some performance score distributed according to a normal distribution (or a logistic distribution when we use the approximate logistic regression model) and a game is modelled as each player drawing a performance for the particular game from those individual normal distributions, and the player with the highest performance wins.

This approach becomes problematic when the performance is not independent from the opponent, for instance whether there is some asymmetric rock paper scissors effect. In Chess it works reasonable, you have chess players with different styles but it works out reasonably, there is not too much variation in the game. In other games, for instance card trading games, players may have startegies with large variations that work out vary different depending on the opponent.

If an elo-system makes sense for your game, then you can apply it also for games with multiple players. You could apply an elo rating updating scheme. But also, you could solve the model for all games at once. In the case of chess this would be a binomial regression model. In your case with multiple players this becomes a multinomial regression model.

Potentially you could add additional variables for

  • Cases when specific players encounter each other (to get a rock paper scissors effect) with few players and many games you can include parameters for individual interaction, for many players with few games you could try to define categories of playing styles.

    Some sort of PCA could be interesting here. Based on the matrix of wins against other players you can consider the principle components of that matrix as a model for the win probability.

  • other variables that may influence the game. Possibly some players are better at games with many players and other players are better at games with few players.

$\endgroup$
1
  • $\begingroup$ I wondering whether we could change the latent variable model underlying elo rating and probit regression into a multidimensional latent variable model. Have people tried this before? I imagine a neural network with a latent feature space could potentially do this. $\endgroup$ Mar 11, 2023 at 12:14

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.