Scaling in Tournaments

E. Ben-Naim, S. Redner, F. Vazquez

We study a stochastic process that mimics single-game elimination tournaments. In our model, the outcome of each match is stochastic: the weaker player wins with upset probability $q\leq 1/2$, and the stronger player wins with probability $1-q$. The loser is then eliminated. Extremal statistics of the initial distribution of player strengths governs the tournament outcome. For a uniform initial distribution of strengths, the rank of the winner, $x_*$, decays algebraically with the number of players, $N$, as $x_*\sim N^{-\beta}$. Different decay exponents are found analytically for sequential dynamics, \hbox{$\beta_{\rm seq}=1-2q$} and parallel dynamics, \hbox{$\beta_{\rm par}=1+\frac{\ln (1-q)}{\ln 2}$}. The distribution of player strengths becomes self-similar in the long time limit and moreover, it has an algebraic tail.


source, ps, pdf