Weng and Lin 2011 - Thurstone-Mosteller and Plackett-Luce Update Rules

Summary

The same framework applied to a Gaussian (Thurstone-Mosteller, TM) performance model with a draw margin reproduces TrueSkill’s two-team update exactly, and a Plackett-Luce (PL) variant with tie handling gives a closed-form multi-team rule. TM is numerically touchy; BT-full and PL are recommended.

Overview

With ${\beta }_i^2={\sigma }_i^2+{\beta }^2$ and $c_{iq}^2={\sigma }_i^2+{\sigma }_q^2+2{\beta }^2$ as before.

Main Content

TM with draw margin $\epsilon$ (Eq. 65)

$P(i\text{ beats }q)=P(X_i>X_q+\epsilon )=\Phi \left(\frac{{\theta }_i-{\theta }_q-\epsilon }{c_{iq}}\right)$, $P(i\text{ draws }q)=P(|X_i-X_q|<\epsilon )=\Phi \left(\frac{\epsilon -({\theta }_i-{\theta }_q)}{c_{iq}}\right)-\Phi \left(\frac{-\epsilon -({\theta }_i-{\theta }_q)}{c_{iq}}\right)$.

Algorithm 3 (TM, full-pair)

Using $V(x,t)=\varphi (x-t)/\Phi (x-t)$ and $W(x,t)=V(V+(x-t))$ (Eq. 67), plus draw analogues $\tilde{V},\tilde{W}$ (Eqs. 68-69): ${\delta }_q=\frac{{\sigma }_i^2}{c_{iq}}\times \{\begin{array}{ll}V(\frac{{\mu }_i-{\mu }_q}{c_{iq}},\frac{\epsilon }{c_{iq}})& r(q)>r(i)\\ \tilde{V}(\cdot )& r(q)=r(i)\\ -V(\frac{{\mu }_q-{\mu }_i}{c_{iq}},\frac{\epsilon }{c_{iq}})& r(q)<r(i)\end{array}$, and ${\eta }_q={\gamma }_q\frac{{\sigma }_i^2}{c_{iq}^2}\times W(\cdot )$, $\tilde{W}$, $W$ respectively. For $k=2$ and a win by $i$: ${\mu }_i\leftarrow {\mu }_i+\frac{{\sigma }_i^2}{c}V(\frac{{\mu }_i-{\mu }_q}{c},\frac{\epsilon }{c})$, ${\mu }_q\leftarrow {\mu }_q-\frac{{\sigma }_q^2}{c}V(\cdot )$, identical to the TrueSkill two-player update.

Numerical safeguard. When $x-t$ is very negative, $\varphi$ and $\Phi$ underflow; as in TrueSkill, if $\Phi (x-t)\le 2.22\times 10^{-162}$ set $V=-x+t$ (the limit as $x-t\to -\infty$).

Plackett-Luce with variance and ties (Sec. 4.3)

PL with variance (Eq. 70)

$f(z)={\prod }_{q=1}^k\frac{e^{{\theta }_q/c}}{{\sum }_{s\in C_q}{e}^{{\theta }_s/c}}$, $c=({\sum }_i({\sigma }_i^2+{\beta }^2){)}^{1/2}$, $C_q=\{i:r(i)\ge r(q)\}$ (the teams not ranked better than $q$). A single $c$ is used for simplicity. With ties (Eq. 72): exponent $1/A_q$ with $A_q=|\{s:r(s)=r(q)\}|$ (the geometric mean over the $d$ tied stages).

Algorithm 4 (PL)

${\hat{p}}_{i,C_q}=\frac{e^{{\mu }_i/c}}{{\sum }_{s\in C_q}{e}^{{\mu }_s/c}}$; ${\delta }_q=\frac{{\sigma }_i^2}{c{A}_q}\times \{\begin{array}{ll}1-{\hat{p}}_{i,C_q}& q=i\\ -{\hat{p}}_{i,C_q}& r(q)\le r(i),q\ne i\\ 0& r(q)>r(i)\end{array}$, ${\eta }_q={\gamma }_q\frac{{\sigma }_i^2}{c^2{A}_q}{\hat{p}}_{i,C_q}(1-{\hat{p}}_{i,C_q})$ if $r(q)\le r(i)$, else 0; ${\Omega }_i={\sum }_q{\delta }_q$, ${\Delta }_i={\sum }_q{\eta }_q$; ${\gamma }_q={\sigma }_i/c$ in experiments.

Appendices D-F give the derivations for BT partial-pair, TM, and PL, using $\partial f/\partial z_i$ and ${\partial }^{2}f/\partial z_i^2$ at $z=0$ exactly as in Sec. 3.5.

Examples

TrueSkill-style draw

Setup. Two equal players ($\mu =25$, $\sigma =25/3$, $\beta =25/6$), draw margin $\epsilon =0.1$. Solution. For an actual draw, $\tilde{V}(0,\epsilon /c)=0$ by symmetry, so means do not move but variances shrink (via $\tilde{W}$). Interpretation. A draw between equals carries information on uncertainty, not on the ordering.

Connections

• TM is the probit analogue of BT; the logistic/probit trade-off mirrors logit vs probit in Discrete Choice Models.

See Also

Weng and Lin 2011 - Glicko Derivation and Comparison with Elo