Editing Elo rating system (section)

=== Formal derivation for win/draw/loss games ===

Since the very beginning, the Elo rating has been also used in chess where we observe wins, losses or draws and, to deal with the latter a fractional score value, <math>S_{\mathsf{A}}=0.5</math>, is introduced. We note, however, that the scores  <math>S_{\mathsf{A}}=1</math> and <math>S_{\mathsf{A}}=0</math> are merely indicators to the events when the player  <math>\mathsf{A}</math> wins or loses the game. It is, therefore, not immediately clear what is the meaning of the fractional score. Moreover, since we do not specify explicitly the model relating the rating values <math>R_{\mathsf{A}}</math> and <math>R_{\mathsf{B}}</math> to the probability of the game outcome, we cannot say what the probability of the win, the loss, or the draw is.

To address these difficulties, and to derive the Elo rating in the ternary games, we will define the explicit probabilistic model of the outcomes. Next, we will minimize the log loss via stochastic gradient.

Since the loss, the draw, and the win are [[Ordinal data|ordinal variables]], we should adopt the model which takes their ordinal nature into account, and we use the so-called adjacent categories model which may be traced to the Davidson's work<ref>{{Cite journal |last=Davidson |first=Roger R. |date=1970 |title=On Extending the Bradley-Terry Model to Accommodate Ties in Paired Comparison Experiments |url=https://www.jstor.org/stable/2283595 |journal=Journal of the American Statistical Association |volume=65 |issue=329 |pages=317–328 |doi=10.2307/2283595 |jstor=2283595 |issn=0162-1459}}</ref>

:<math> 
\Pr\{\mathsf{A}~\textrm{wins}\} = \sigma(r_{\mathsf{A,B}}; \kappa),
</math>

:<math> 
\Pr\{\mathsf{B}~\textrm{wins}\} = \sigma(-r_{\mathsf{A,B}}; \kappa),
</math>

:<math> 
\Pr\{\mathsf{A}~\textrm{draws}\} = \kappa\sqrt{\sigma(r_{\mathsf{A,B}}; \kappa)\sigma(-r_{\mathsf{A,B}}; \kappa)},
</math>

where

:<math> 
\sigma(r; \kappa) = \frac{10^{r/s}}{10^{-r/s}+\kappa + 10^{r/s}}
</math>

and <math>\kappa\ge 0</math> is a parameter. Introduction of a free parameter should not be surprising as we have three possible outcomes and thus, an additional degree of freedom should appear in the model. In particular, with <math>\kappa=0</math> we recover the model underlying the logistic regression

:<math> 
\Pr\{\mathsf{A}~\textrm{wins}\} = \sigma(r_{\mathsf{A,B}};0)=\frac{10^{r_{\mathsf{A,B}}/s}}{10^{-r_{\mathsf{A,B}}/s}+ 10^{r_{\mathsf{A,B}}/s}}=\frac{1}{1+ 10^{-r_{\mathsf{A,B}}/s'}},
</math>

where <math>s' = s/2</math>.

Using the ordinal model defined above, the [[log loss]] is now calculated as

:<math>
 \ell = 
\begin{cases}
-\log \sigma(r_{\mathsf{A,B}};\kappa) & \textrm{if}~ \mathsf{A}~\textrm{wins},\\
-\log \sigma(-r_{\mathsf{A,B}};\kappa) &  \textrm{if}~ \mathsf{B}~\textrm{wins},\\
-\log \kappa -\frac{1}{2}\log\sigma(r_{\mathsf{A,B}};\kappa) - \frac{1}{2}\log\sigma(-r_{\mathsf{A,B}};\kappa) &  \textrm{if}~ \mathsf{A}~\textrm{draw},
\end{cases}
</math>

which may be compactly written as

:<math>
 \ell = 
-(S_{\mathsf{A}} +\frac{1}{2}D)\log \sigma(r_{\mathsf{A,B}};\kappa)
-(S_{\mathsf{B}} +\frac{1}{2}D) \log \sigma(-r_{\mathsf{A,B}};\kappa)
-D\log \kappa 
</math>

where <math>S_{\mathsf{A}}=1</math> [[If and only if|iff]]  <math>\mathsf{A}</math> wins, <math>S_{\mathsf{B}}=1</math> iff  <math>\mathsf{B}</math> wins, and <math>D=1</math> iff  <math>\mathsf{A}</math> draws.

As before, we need the derivative of <math>\log\sigma(r;\kappa)</math> which is given by

:<math> 
\frac{\textrm{d}}{\textrm{d} r}\log\sigma(r; \kappa)  
=\frac{2\log 10}{s} [1-g(r;\kappa)] 
</math>,

where

:<math> 
g(r;\kappa)=
\frac{10^{r/s}+\kappa/2 }
{10^{-r/s}+\kappa + 10^{r/s}}.
</math>

Thus, the derivative of the log loss with respect to the rating <math>R_{\mathsf{A}}</math> is given by

:<math> 
\begin{align}
\frac{\textrm{d}}{\textrm{d} R_{\mathsf{A}}}\ell
&=
-\frac{2\log 10}{s}
\left( 
(S_{\mathsf{A}} +0.5D)[1-g(r_{\mathsf{A,B}};\kappa)]
-(S_{\mathsf{B}} +0.5D)g(r_{\mathsf{A,B}};\kappa)
\right)\\
&=
-\frac{2\log 10}{s}
\left(S_{\mathsf{A}} + 0.5D-g(r_{\mathsf{A,B}};\kappa)\right),
\end{align}
</math>

where we used the relationships <math>S_{\mathsf{A}} + S_{\mathsf{B}} + D=1</math> and <math> 
g(-r;\kappa)=1-g(r;\kappa)
</math>.

Then, the stochastic gradient descent applied to minimize the log loss yields the following update for the rating <math>R_{\mathsf{A}}</math>

:<math> 
R_{\mathsf{A}}\leftarrow R_{\mathsf{A}} + K (\hat{S}_{\mathsf{A}}-  g(r_{\mathsf{A,B}};\kappa)) 
</math>

where <math>K=2\eta\log10/s</math> and <math> 
\hat{S}_{\mathsf{A}}= S_{\mathsf{A}} + 0.5D 
</math>. Of course, <math> 
\hat{S}_{\mathsf{A}}= 1 
</math> if <math> 
\textsf{A} 
</math> wins, <math> 
\hat{S}_{\mathsf{A}}= 0.5 
</math> if <math> 
\textsf{A} 
</math> draws, and <math> 
\hat{S}_{\mathsf{A}}= 0 
</math> if <math> 
\textsf{A} 
</math> loses. To recognize the origin in the model proposed by Davidson, this update is called an Elo-Davidson rating.<ref name=":0" />

The update for <math>R_{\mathsf{B}}</math> is derived in the same manner as

:<math> 
R_{\mathsf{B}}\leftarrow R_{\mathsf{B}} + K (\hat{S}_{\mathsf{B}}-  g(r_{\mathsf{B,A}};\kappa)) 
</math>,

where <math> 
r_{\mathsf{B,A}}=R_{\mathsf{B}}-R_{\mathsf{A}}=-r_{\mathsf{A,B}} 
</math>.

We note that

:<math> 
\begin{align}
E[\hat{S}_{\mathsf{A}}]
&=\Pr\{\mathsf{A}~\text{wins}\}+0.5\Pr\{\mathsf{A}~\text{draws}\}\\
&=\sigma(r_{\mathsf{A,B}};\kappa)+0.5\kappa\sqrt{\sigma(r_{\mathsf{A,B}};\kappa)\sigma(-r_{\mathsf{A,B}};\kappa)}\\
&=g(r_{\mathsf{A,B}};\kappa)
\end{align} 
</math>

and thus, we obtain the rating update may be written as

:<math> 
R_{\mathsf{A}}\leftarrow R_{\mathsf{A}} + K (\hat{S}_{\mathsf{A}}-  E_{\mathsf{A}}) 
</math>,

where <math> 
E_{\mathsf{A}}=E[\hat{S}_\mathsf{A}] 
</math> and we obtained practically the same equation as in the Elo rating except that the expected score is given by <math> 
E_{\mathsf{A}}=g(r_{\mathsf{A,B}};\kappa) 
</math> instead of <math> 
E_{\mathsf{A}}=\sigma(r_{\mathsf{A,B}}) 
</math>.

Of course, as noted above, for <math>\kappa=0</math>, we have <math> 
g(r;0) = \sigma(r)
</math> and thus, the Elo-Davidson rating is exactly the same as the Elo rating. However, this is of no help to understand the case when the draws are observed (we cannot use <math> 
\kappa=0
</math> which would mean that the probability of draw is null). On the other hand, if we use <math> 
\kappa=2
</math>, we have

:<math> 
g(r;2)=
\frac{10^{r/s}+1 }
{10^{-r/s}+2 + 10^{r/s}}=\frac{1}
{1+10^{-r/s}}=\sigma(r)
</math>

which means that, using  <math> 
\kappa=2
</math>, the Elo-Davidson rating is exactly the same as the Elo rating.<ref name=":0" />