Weng and Lin 2011 - Bradley-Terry Update Algorithms

Summary

Closed-form online rules for the Bradley-Terry model with variance: each player’s mean moves by ${\sum }_q({\sigma }_i^2/c_{iq})(s-{\hat{p}}_{iq})$ and its variance shrinks by ${\sum }_q{\gamma }_q{\sigma }_i^2{\hat{p}}_{iq}{\hat{p}}_{qi}/c_{iq}^2$. Full-pair uses all opponents; partial-pair only adjacent ranks. With two players this is an Elo step with Bayesian step size.

Overview

Variance-augmented BT (Eq. 48): $P(i\text{ beats }q)=f_{iq}=\frac{e^{{\theta }_i/c_{iq}}}{e^{{\theta }_i/c_{iq}}+e^{{\theta }_q/c_{iq}}}$, $c_{iq}^2={\sigma }_i^2+{\sigma }_q^2+2{\beta }^2$ (via ${\beta }_i^2={\sigma }_i^2+{\beta }^2$). Ties follow Glicko: $P(i\text{ draws }q)=\sqrt{f_{iq}{f}_{qi}}$ (Eq. 51).

Main Content

Algorithm 1 (BT, full-pair)

For team $i$ and each opponent $q\ne i$: $c_{iq}=({\sigma }_i^2+{\sigma }_q^2+2{\beta }^2{)}^{1/2}$, ${\hat{p}}_{iq}=\frac{e^{{\mu }_i/c_{iq}}}{e^{{\mu }_i/c_{iq}}+e^{{\mu }_q/c_{iq}}}$, ${\delta }_q=\frac{{\sigma }_i^2}{c_{iq}}(s-{\hat{p}}_{iq})$, ${\eta }_q={\gamma }_q\frac{{\sigma }_i^2}{c_{iq}^2}{\hat{p}}_{iq}{\hat{p}}_{qi}$, with $s=1$ if $r(q)>r(i)$ (i beats q), $\frac{1}{2}$ if tied, $0$ if $r(q)<r(i)$. Then ${\Omega }_i={\sum }_q{\delta }_q$, ${\Delta }_i={\sum }_q{\eta }_q$; team update ${\mu }_i\leftarrow {\mu }_i+{\Omega }_i$, ${\sigma }_i^2\leftarrow {\sigma }_i^2\max (1-{\Delta }_i,\kappa )$; individuals by Eqs. 43-44. The damping weights ${\gamma }_q\le 1$ control how fast variance falls (default ${\gamma }_q={\sigma }_i/c_{iq}$ in the experiments).

Algorithm 2 (BT, partial-pair)

Same as Algorithm 1 except that ${\Omega }_i,{\Delta }_i$ sum only over $Q$ = the teams ranked immediately above and below $i$ (one neighbour for first and last place).

Derivation sketch. $\partial f_{iq}/\partial z_i=\frac{{\sigma }_i}{c_{iq}}{f}_{iq}{f}_{qi}$ and $\partial f_{qi}/\partial z_i=-\frac{{\sigma }_i}{c_{iq}}{f}_{iq}{f}_{qi}$, so ${\Omega }_i={\sigma }_i^2{\sum }_q[\frac{1}{c_{iq}}(1\{r(q)>r(i)\}-{\hat{p}}_{iq})+\dots ]$ and ${\partial }_{z_i}({\partial }_{z_i}{f}_{qi}/f_{qi})=-\frac{{\sigma }_i^2}{c_{iq}^2}{f}_{iq}{f}_{qi}$.

Relation to Elo. Elo: ${\theta }_i\leftarrow {\theta }_i+K(s-p_{iq}^{\ast })$ with $p^{\ast }=10^{{\theta }_i/400}/(10^{{\theta }_i/400}+10^{{\theta }_q/400})$. $p^{\ast }$ is a variance-free, reparameterised $\hat{p}$; here $K\leftrightarrow {\sigma }_i^2/c_{iq}$ varies per player and falls with uncertainty.

Examples

One game, two new players

Setup. Both players $\mu =25$, $\sigma =25/3$, $\beta =25/6$; player 1 wins. Solution. $c=\sqrt{2{\sigma }^2+2{\beta }^2}\approx 13.2$; $\hat{p}=0.5$; ${\Omega }_1={\sigma }^2/c\cdot 0.5\approx 2.64$, so ${\mu }_1\approx 27.64$, ${\mu }_2\approx 22.36$; ${\sigma }^2$ drops from 69.4 to about 65.05 (verified numerically below). Interpretation. A new player moves about 2.6 points on its first result; a veteran with small ${\sigma }_i$ moves far less.

import numpy as np
def bt_full_update(mu, sig2, rank, beta2=(25/6)**2, kappa=1e-4):
    """One player per team. rank: smaller is better; equal ranks tie."""
    k = len(mu); new_mu = mu.copy(); new_s2 = sig2.copy()
    for i in range(k):
        Om = De = 0.0
        for q in range(k):
            if q == i: continue
            c = np.sqrt(sig2[i] + sig2[q] + 2*beta2)
            p = 1/(1+np.exp((mu[q]-mu[i])/c))
            s = 1.0 if rank[q] > rank[i] else (0.5 if rank[q] == rank[i] else 0.0)
            gamma = np.sqrt(sig2[i])/c
            Om += sig2[i]/c*(s-p)
            De += gamma*(sig2[i]/c**2)*p*(1-p)
        new_mu[i] = mu[i] + Om
        new_s2[i] = sig2[i]*max(1-De, kappa)
    return new_mu, new_s2
mu = np.array([25., 25.]); s2 = np.array([(25/3)**2]*2)
print(bt_full_update(mu, s2, [1, 2]))   # mu -> [27.64, 22.36], sig2 -> 65.05

Connections

• Elo, Glicko and TrueSkill compared in Elo, Glicko and TrueSkill - Dynamic Skill Ratings (Concept Note).
• Offline counterpart: Caron 2012 - Bradley-Terry Likelihood and Latent Exponential Augmentation.

See Also

Weng and Lin 2011 - Thurstone-Mosteller and Plackett-Luce Update Rules · Weng and Lin 2011 - Glicko Derivation and Comparison with Elo