2
$\begingroup$

I've tried attacking this problem in the past without success but it seems it should be tractable.

Define a "league" as a set of $n$ teams with the property that if team $i$ plays team $j$ it will win with probability $W_{ij}$ (thus $W_{ji}=1-W_{ij}$). And define a linearized league as league with a very special form for that matrix: $W_{ij} = \frac12 - \epsilon(i-j)$ for some small $\epsilon$. (It is required that $\epsilon \leq \frac1{2(n-1)}$, but this problem is concerned with behavior as $\epsilon\to 0$.)

Define a "tournament" as a set of games in which each player plays games against other players, the pairings being determined by some algorithm which may depend on results of earlier games and/or random variates, the games are assigned weights (which again might depend on results of earlier games), and the tournament winner is the team with the most accumulated weight points in winning games. (For completeness, a tie is considered half a win for each of the tied teams.)

A tournament is "fair" if the assignment of games is completely symmetric in the indices of the teams. (For example, a tournament in which team $3$ plays team $2$ and then the winner plays team $1$ for the win is not fair. But if it becomes fair if first, the identities of the three teams are shuffled by some random permutation of $(1,2,3)$.)

Under these definitions, you can define the "effectiveness" of a fair tournament $T$ as $$ E(T;n) = \lim_{\epsilon\to 0} \frac{\mbox{ Prob (team 1 wins tournament)}-\frac1n} {\mbox{ Prob (team 1 wins game versus average team)}-\frac12} $$ Intuitively, a more effective tournament more greatly magnifies the single game advantage to the best team. For example, the best-of-seven two-team playoff format used in baseball, basketball, and hockey has an effectiveness of $\frac{35}{8}$ whereas a best three-of-five series has an effectiveness of only $\frac{30}{8}$.

Define a "single round robin tournament" $R_n$ as a special case of a tournament in which each team will play each other team once, and the team winning the most such games is the tournament winner. For such a tournament $$ E(R_n;n) = \lim_{\epsilon\to 0} \frac{\mbox{ Prob (team 1 wins round robin)}-\frac1n} { \frac{n-1}2 \epsilon} $$ and I am looking for an asymptotic formula for $E(R_n;n)$ valid for large $n$.

Intuitively, as the number of teams increases, the number of games increases and this would tend to make the tournament more effective (perhaps rising as $\sqrt{n}$). But there are many more games not involving team $1$ and the random fluctuations in those would tend to produce a winner that team $1$'s results can do little to sway, thus diminishing the effectiveness. So I can't tell even at the level of "increasing" or decreasing.

$\endgroup$
  • $\begingroup$ BTW, $E(R_1;1) = 1$ (of course) and $E(R_2;2) = \frac32$. $\endgroup$ – Mark Fischler Sep 14 '17 at 23:38
  • $\begingroup$ Before, I meant to say BTW, $E(R_2;2) = 1$ and $E(R_3;3) = \frac32$. I also hand calculated $E(R_4;4) = \frac{197}{192}$ but I'm only pretty sure of my accuracy. $\endgroup$ – Mark Fischler Sep 15 '17 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.