Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.