Bradley–Terry model

The Bradley–Terry model is a probability model that can predict the outcome of a paired comparison. Given a pair of individuals i and j drawn from some population, it estimates the probability that the pairwise comparison i > j turns out true, as

${\displaystyle P(i>j)={\frac {p_{i}}{p_{i}+p_{j}}}}$

where p_i is a positive real-valued score assigned to individual i. The comparison i > j can be read as "i is preferred to j", "i ranks higher than j", or "i beats j", depending on the application.

For example, p_i may represent the skill of a team in a sports tournament, estimated from the number of times i has won a match. ${\displaystyle P(i>j)}$ then represents the probability that i will win a match against j.^[1][2] Another example used to explain the model's purpose is that of scoring products in a certain category by quality. While it's hard for a person to draft a direct ranking of (many) brands of wine, it may be feasible to compare a sample of pairs of wines and say, for each pair, which one is better. The Bradley–Terry model can then be used to derive a full ranking.^[2]

History and applications[]

The model is named after R. A. Bradley and M. E. Terry,^[3] who presented it in 1952,^[4] although it had already been studied by Zermelo in the 1920s.^[1][5][6]

Real-world applications of the model include estimation of the influence of statistical journals, or ranking documents by relevance in machine-learned search engines.^[7] In the latter application, ${\displaystyle P(i>j)}$ may reflect that document i is more relevant to the user's query than document j, so it should be displayed earlier in the results list. The individual p_i then express the relevance of the document, and can be estimated from the frequency with which users click particular "hits" when presented with a result list.^[8]

Definition[]

The Bradley–Terry model can be parametrized in various ways. One way to do so is to pick a single parameter per observation, leading to a model of n parameters p₁, ..., p_n.^[9] Another variant, in fact the version considered by Bradley and Terry,^[2] uses exponential score functions ${\displaystyle p_{i}=e^{\beta _{i}}}$ so that

${\displaystyle P(i>j)={\frac {e^{\beta _{i}}}{e^{\beta _{i}}+e^{\beta _{j}}}}}$

or, using the logit (and disallowing ties),^[1]

${\displaystyle \operatorname {logit} (P(i>j))=\log \left({\frac {P(i>j)}{1-P(i>j)}}\right)=\log \left({\frac {P(i>j)}{P(j>i)}}\right)=\beta _{i}-\beta _{j}}$

reducing the model to logistic regression on pairs of individuals.

Estimating the parameters[]

The following algorithm computes the parameters p_i of the basic version of the model from a sample of observations. Formally, it computes a maximum likelihood estimate, i.e., it maximizes the likelihood of the observed data. The algorithm dates back to the work of Zermelo.^[1]

The observations required are the outcomes of previous comparisons, for example, pairs (i, j) where i beats j. Summarizing these outcomes as w_ij, the number of times i has beaten j, we obtain the log-likelihood of the parameter vector p = p₁, ..., p_n as^[1]

${\displaystyle L(\mathbf {p} )=\sum _{i}^{n}\sum _{j}^{n}[w_{ij}\ln p_{i}-w_{ij}\ln(p_{i}+p_{j})].}$

Denote the number of comparisons "won" by i as W_i. Starting from an arbitrary vector p, the algorithm iteratively performs the update

${\displaystyle p'_{i}=W_{i}\left(\sum _{j\neq i}{\frac {w_{ij}+w_{ji}}{p_{i}+p_{j}}}\right)^{-1}}$

for all i. After computing all of the new parameters, they should be renormalized,

${\displaystyle p_{i}\leftarrow {\frac {p'_{i}}{\sum _{j=1}^{n}p'_{j}}}.}$

This estimation procedure improves the log-likelihood in every iteration, and eventually converges to a unique maximum.

Worked Example of Iterated Procedure[]

Suppose there are 4 teams who have played a total of 22 games among themselves. Each team's wins are given in the rows of the table below and the opponents are given as the columns. For example, Team A has beat Team B twice and lost to team B three times; not played team C at all; won once and lost four times against team D.

We would like to compute the relative strengths of the teams; that is, we want to compute one parameter per team, with higher parameters indicating greater prowess. We initialize the 4 entries in the parameter vector p arbitrarily, for example, assigning the value 1 to each team: [1, 1, 1, 1].

${\displaystyle p_{1}={\frac {W_{1}}{\sum _{j\neq 1}{\frac {w_{1j}+w_{j1}}{p_{1}+p_{j}}}}}={\frac {2+0+1}{{\frac {2+3}{1+1}}+{\frac {0+0}{1+1}}+{\frac {1+4}{1+1}}}}=0.6}$

${\displaystyle p_{2}={\frac {W_{2}}{\sum _{j\neq 2}{\frac {w_{2j}+w_{j2}}{p_{2}+p_{j}}}}}={\frac {3+5+0}{{\frac {3+2}{1+1}}+{\frac {5+3}{1+1}}+{\frac {0+0}{1+1}}}}=1.231}$

${\displaystyle p_{3}={\frac {W_{3}}{\sum _{j\neq 3}{\frac {w_{3j}+w_{j3}}{p_{3}+p_{j}}}}}={\frac {0+3+1}{{\frac {0+0}{1+1}}+{\frac {3+5}{1+1}}+{\frac {1+3}{1+1}}}}=0.667}$

${\displaystyle p_{4}={\frac {W_{4}}{\sum _{j\neq 4}{\frac {w_{4j}+w_{j4}}{p_{4}+p_{j}}}}}={\frac {4+0+3}{{\frac {4+1}{1+1}}+{\frac {0+0}{1+1}}+{\frac {3+1}{1+1}}}}=1.556}$

Then, we normalize all the parameters by dividing them by ${\displaystyle 0.6+1.231+0.667+1.556=4.053}$ to get the estimated parameters p = [0.148, 0.304, 0.164, 0.384].

To get better estimates, we can repeat the process, using the new p values. For example,

${\displaystyle p_{1}={\frac {W_{1}}{\sum _{j\neq 1}{\frac {w_{1j}+w_{j1}}{p_{1}+p_{j}}}}}={\frac {2+0+1}{{\frac {2+3}{0.148+0.304}}+{\frac {0+0}{0.148+0.164}}+{\frac {1+4}{0.148+0.384}}}}=0.147}$

Repeating this for the remaining parameters and normalizing, we get p = [0.145, 0.280, 0.162, 0.413]. Repeating this process a total of 20 times will show rapid convergence to p = [0.139, 0.226, 0.143, 0.492]. This shows that Team D is the strongest, Team B is the second strongest, and Team A and Team C are nearly equal in strength, but less than Teams B and D. The Bradley-Terry model lets us extrapolate the relationship between all 4 teams, even though all teams haven't played each other.

See also[]

• Ordinal regression
• Rasch model
• Scale (social sciences)
• Elo rating system
• Thurstonian model

References[]