Statistical Extensions of the Bradley-Terry and Elo Models

Contributors:
Anastasios N. Angelopoulos*
Wei-Lin Chiang*
Shishir G. Patil

Based on our previous posts, Chatbot Arena uses the Bradley-Terry model for the purposes of statistical inference on the model strength. Recently, we have developed some extensions of the Bradley-Terry model, and the closely related Elo model, for the purpose of binary-comparison inference problems. Our extensions target the case where each of the two players in the comparison may contain more than one subsystem that contributes to their strength. We will develop these extensions in the batch form (Extended Bradley-Terry) and in the online form (Extended Elo).

Let ℓ:[0,1]×{0,1}→R denote the binary cross-entropy loss, where the first argument is the predicted probability, and the second argument is the ground-truth binary outcome. As a reminder, for a prediction y^∈[0,1] and a binary label y∈{0,1}, the binary cross-entropy loss is defined as

ℓ(y^,y)=−ylog⁡(y^)−(1−y)log⁡(1−y^).

Furthermore, let MA,MB∈N, dmA,−1,dmB,1∈N for all mA∈[MA] and mB∈[MB], and dtotal=∑mA∈[MA]dmA,A+∑mB∈[MB]dmB,B. Next, define the set

X={x∈{−1,0,1}dtotal:|{j:xj=−1}|=MA and |{j:xj=1}|=MB}.

That is, X is the set of vectors of length dtotal with MA entries equal to −1, MB entries equal to 1, and the rest equal to 0. The interpretation is that we have MA subsystems for player A and MB subsystems for player B, and the feature vector x∈X encodes which subsystems are active in the current battle. The active subsystems for player A are those with −1, and the active subsystems for player B are those with 1. Then, with σ as the sigmoid function, the extended Bradley-Terry model postulates that the probability that player B beats player A is given by

P(B beats A)=σ(x⊤θ∗),

for some (unknown) parameter vector θ∗∈Rdtotal.

As in the standard Bradley-Terry model, this parameter vector can be expressed as the solution to a logistic regression:

θ∗=arg⁡minθ∈RdtotalE(X,Y)∼P[ℓ(σ(X⊤θ),Y)],

where P is some joint distribution over X×{0,1}. The standard Bradley-Terry model is recovered when MA=MB=1. As a side note, we normally report these coefficients after multiplying them by 400 and adding 1000, so that the coefficients are in the same range as the Elo ratings in chess. This is a purely cosmetic transformation and does not affect the model’s predictions.