Take the 2-minute tour ×

Let $[n]$=$\{1,\dots,n\}$ be a set of players in a round-robin tournament. Each player $i$ has an associated skill parameter, $\lambda_{i}$, and the probability that player $i$ defeats player $j$ is $\frac{\lambda_{i}}{\lambda_{i}+\lambda_{j}}$ (ordinary Bradley-Terry comparison). Once a tournament has concluded the players are ranked by their score, with ties being broken at random, so if a score vector was $(3,2,3,0,2)$ then a valid rank vector would be $(4,2,5,1,3)$.

The expected score for player $i$ is $\mathbb{E}[\lambda_{i}]=\sum\limits_{j\not=i}{\frac{\lambda_{i}}{\lambda_{i}+\lambda_{j}}}$. Is there a closed form expression for the expected rank?

share|improve this question
Note that when estimating the skill parameters (by maximum likelihood) based on a full round robin, the ranks of the estimated parameters will match the ranks of the winning percentages of the players. –  cardinal Dec 31 '13 at 16:06

1 Answer 1

up vote 2 down vote accepted

The rank for player $i$ is $R_i=1 + \sum_{j \ne i} I(i,j)$ where $I(i,j)$ is an indicator random variable for whether player $j$ has a higher score than player $i$, so $E[R_i] = 1 + \sum_{j \ne i} E[I(i,j)]$. The expected value $E[I(i,j)]$ can be computed by considering the $2^{2n-3}$ possible results of players $i$ and $j$ instead of the $2^{n \choose 2}$ tournaments. You can also write a recurrence for the distribution of the difference between the scores of players $i$ and $j$ after facing the first $k$ opponents which takes $O(n^2)$ steps to compute for numerical skill values.

I would not expect to find a closed form. Here is a way to eliminate some possible closed forms: Compute the exact value for particular choices of the skill parameters, possibly with some left as variables, and factor the numerator and denominator. A factorization involving large primes suggests that there isn't be a simple closed form expression, or at least that it would have to be a sum of multiple terms.

For example, suppose there is one player with skill $3$, and $3$ players each with skills $1$ and $2$. The expected rank of the player with skill $3$ is $25439/9600$, and $25439$ is prime. If $0$-based ranks are more natural, $25439-9600$ is a product of two primes, $47\times 337$.

share|improve this answer
@cardinal: Thanks. –  Douglas Zare Dec 31 '13 at 16:33

Your Answer


