10
$\begingroup$

Elo rating system use a gradient descent minimization algorithm of the cross-entropy loss function between the expected and observed probability of an outcome in paired comparisons. We can write the general loss functions as

$$ E=-\sum_{n,i} p_i Log (q_i) $$

where the sum is performed over all outcomes $i$ and all opponents $n$. $p_i$ is the observed frequency of the event $_i$ and $q_i$ the expected frequency.

In the case of only two possible outcome (win or loose) and one opponent we have

$$ E=-p Log (q)-(1-p)Log(1-q) $$

If $\pi_i$ is the ranking of the player $i$ and $\pi_j$ is the ranking of the player $j$ we can built the expected probability as $$ q_i=\frac{e^{\pi_i}}{e^{\pi_i}+e^{\pi_j}} $$ $$ q_j=\frac{e^{\pi_j}}{e^{\pi_i}+e^{\pi_j}} $$ then the gradient descent update rule tell use

$$ \pi_i'=\pi_i-\eta (q_i-p_i) $$

$$ \pi_j'=\pi_j-\eta (q_j-p_j) $$

where $q_i$ and $p_i$ are the expected and observed probability of win of the player $i$ against the player $j$. This is the two outcomes update rules.

In the presence of draws we can generalize the above model including and third outcome with probability

$$ q(d)=\frac{\nu e^{\frac{\pi_i+\pi_j}{2}}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}} $$ $$ q_i(w)=\frac{ e^{\pi_i}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}} $$ $$ q_j(w)=\frac{ e^{\pi_j}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}} $$

And we can build the Loss function as

$$ E=-p(w)Log(q(w))-(1-p(w)-p(d))Log(q(l))-p(d)Log(q(d)) $$

where $p(w),p(l),p(d)$ are respectively the observed likelihood of win,loose and draw and $q(w),q(l),q(d)$ expected likelihood of win,loose and draw. In the latter case the update rule would be

$$ \pi_i'=\pi_i-\eta (q_i(w)+\frac{q_i(d)}{2}-p_i(w)-\frac{p_i(d)}{2}) $$

$$ \pi_j'=\pi_j-\eta (q_j(w)+\frac{q_j(d)}{2}-p_j(w)-\frac{p_j(d)}{2}) $$

where $q_j(w)$ and $q_j(d)$ are the expected probability of the player $i$ to win and to draw against the player $j$. And where $p_i(w)$ and $p_i(d)$ are the observed probability of the player $i$ to win and to draw against the player $j$. This is the three outcome update rule.

The question is, why do Elo rating system use the two outcomes update rules even in the presence of draws?

$\endgroup$
3
$\begingroup$

The probability of drawing, as opposed to having a decisive result, is not specified in the Elo system. Instead a draw is considered - both in expected performance and in match outcome - half a win and half a loss.

An example from Elo page in Wikipedia: "A player's expected score is his probability of winning plus half his probability of drawing. Thus an expected score of 0.75 could represent a 75% chance of winning, 25% chance of losing, and 0% chance of drawing. On the other extreme it could represent a 50% chance of winning, 0% chance of losing, and 50% chance of drawing."

The probability of drawing, as I said, is not specified, and it leads to a simple two outcome update rule, $R_A^\prime = R_A + K(S_A - E_A)$, in which $S_A=1 \cdot (n_w + 0.5 \cdot n_d ) + 0 \cdot (0.5 \cdot n_d + n_l)$, so, after a single match, $S_A=1$ (win), or $S_A=0.5$ (draw, as half a win), or $S_A=0$ (loss).

Like Elo, the Glicko system does not model draws but it makes an update as the average of a win and a loss (per player). Instead, in the TrueSkill ranking system, "draws are modelled by assuming that the performance difference in a particular game is small. Hence, the chance of drawing only depends on the difference of the two player's playing strength. However, empirical findings in the game of chess show that draws are more likely between professional players than beginners. Hence, chance of drawing also seems to depend on the skill level."

This approach requires different specific modeling for every games (and TrueSkill is applied to a few Microsoft Xbox games), so it's suitable in Elo and Glicko (designed just for chess), and it's not for rankade, our multipurpose ranking system.

$\endgroup$
  • $\begingroup$ 'A player's expected score is his probability of winning plus half his probability of drawing.' is exactly what i found in the formula above. Anyway in the Elo update formula the half of probability of draw is not specified as you are pointing out. The question remain, why in the Elo ranking system we do not care about draws? $\endgroup$ – emanuele Feb 15 '16 at 12:20
  • 1
    $\begingroup$ You can always express expected score as the chance of winning and the chance of losing (and zero chance of drawing - see first example from Wikipedia). In this case, 'a player's expected score is his probability of winning' (and anything more, because half probability of drawing is zero). After a single match, the outcome is a win, or a loss, or half a win. Even if you have a game in which draws are allowed, you can update Elo score using just a combination of a win and a loss, as if draws have no chance. $\endgroup$ – Tomaso Neri Feb 15 '16 at 20:52

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.