Bradley-Terry Strength MLE

Background

Bradley-Terry estimates per-player strength parameters from head-to-head win records. The probability that player $i$ beats player $j$ is $r_i / (r_i + r_j)$. LMArena uses this to convert tens of millions of side-by-side LLM votes into the Elo-style numbers on the leaderboard.

Problem statement

Implement bradley_terry(wins, max_iter=200, tol=1e-6) via the standard MM (minorisation-maximisation) iteration:

$$r_i \leftarrow \frac{\sum_j w_{ij}}{\sum_{j \neq i} \frac{n_{ij}}{r_i + r_j}}$$

where $w_{ij}$ = times $i$ beat $j$ and $n_{ij} = w_{ij} + w_{ji}$. After each step, normalise so the geometric mean of r equals $1$.

Input

• wins — np.ndarray shape $(N, N)$ of integers. wins[i, j] = times $i$ beat $j$.
• max_iter — int, iteration cap (default 200).
• tol — float, convergence tolerance on max relative change (default 1e-6).

Output

Returns np.ndarray of length $N$ — the strength parameters, normalised so $\prod r_i^{1/N} = 1$.

Examples

Example 1 — strict dominance hierarchy

Input:  wins = [[0, 10, 10], [0, 0, 10], [0, 0, 0]]
Output: r[0] > r[1] > r[2]

Example 2 — symmetric records → equal strengths

Input:  every pair has 5-5 wins
Output: all r equal (and equal to 1 after normalisation)

Example 3 — geometric-mean normalisation

Input:  any non-degenerate matrix
Output: prod(r)**(1/N) ≈ 1.0

Constraints

• Diagonal of wins is ignored (players don't play themselves).
• Players with zero total wins get a tiny strength (floor at 1e-12) to keep the geometric mean non-zero.
• Returns np.ndarray of float.

Notes

• Convergence. MM iterations are monotone in the log-likelihood; convergence is guaranteed but can be slow. Production use Newton-Raphson for $5 \to 10\times$ fewer iterations.
• Mapping to Elo. $\text{Elo}_i = K \log_{10}(r_i)$ for some scale $K$ (LMSYS uses $K = 400$). The shapes are the same; only the units differ.