Sub-exponential time algorithm to compute playoff chances

Question

There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the top 4 teams (with the highest number of wins) make playoffs (with some tie-breaking procedure that can be done in polynomial time).

After some number of games, we are given the records for each team (including all head-to-head records). Assuming the remaining $g$ games have outcomes which are coin flips, we want to calculate the percentage chance each team makes playoffs.

---

Here's a brute-force solution. There are $g$ remaining games, so we can consider $2^g$ binary sequences where a 0 in each position means the team earlier in the alphabet wins, and a 1 means the team later in the alphabet wins. For each sequence, we can compute which teams make playoffs. Then, the percentage chance of making playoffs can be computed as the number of sequences in which a given team makes playoffs divided by $2^g$.

This obviously has exponential time complexity (in $g$). Is there a better algorithm to solve this problem - perhaps a polynomial time algorithm using dynamic programming? Is there some way to prove we can do no better than exponential time? Is it possible to show this problem is NP-hard?

---

One simplification that can be made (which unfortunately does not reduce the complexity) is that we can compute, in polynomial time, teams which are guaranteed to make or guaranteed to not make playoffs. All games between teams in either set will not affect the probabilities for teams in the middle. As $g \to 0$, this gives a substantial practical boost to the algorithm.

---

Note that 10 teams playing triple round robin are arbitrary and this problem can be generalized to $N$ teams playing a $k$-round robin. Specifically for the brute-force algorithm, it is exponential in $g$ which may not be related to $N$ or $k$. A sub-exponential algorithm should ideally be not exponential in any of $\{N, k, g\}$.

Answer 1

A pragmatic solution is to use Monte Carlo: do one million random simulations, and for each team, count in how many simulations it made it to the top 5. This should give you a good approximation of these probabilities, even though the number is not exact.

If you want the exact probabilities, I think there is a complex solution that has polynomial asymptotic running time. I don't know whether it will be useful in practice. We'll enumerate all possibilities for the set of teams that make the top-4 and the 5th team, and for each such combination, compute the exact probability obtaining such an outcome. Asymptotically, if there are $n$ teams, this will involve enumerating $O(n^5)$ combinations, and I'll show below how to compute each of these probabilities in polynomial time, which yields a polynomial-time algorithm -- albeit one that might still be to slow to implement in practice.

Here's how to compute the probability of a particular combination of outcomes, namely, that a specified 4 teams make the top-4 (in some order) and one more specified team is #5. For each game yet to be played, we can introduce a zero-or-one variable $x_i$ that records who wins. We can write down a set of linear inequalities that characterize the conditions under which the desired outcome occurs. The total number of wins of each team is a sum of some of these variables, and we want each of the top-4 teams to have at least as many wins as the #5 team, and every other team to have fewer wins than the #5 team, so we obtain inequalities comparing sums of these variables. Also for each $x_i$ we have the inequality $0 \le x_i \le 1$. This gives us a linear program, or in other words, a convex polytope. Now the question is to count the number of integer solutions to this linear program, or equivalently, the number of lattice points inside this convex polytope. There are known polynomial-time algorithms for this problem; see Finding all solutions to an integer linear programming (ILP) problem.

However, I suspect this fancy algorithm might be non-trivial to code up and might not be very useful in practice, even though it is polynomial time in theory, because of the large polynomials involved.

---

If you care about the asymptotic running time, I think there might be an improvement to the latter algorithm. For each team, enumerate all candidates for $t$, the number of wins of the #5-ranked team. Introduce zero-or-one variables $y_i$, where $y_i=1$ means that team $i$ was in the top 5. If we are counting solutions where team $j$ is in the top-5, force $y_j=1$. We obtain an expression $e_i$ for number of wins of team $i$, where $e_i$ is linear in the unknowns $x_i$. We can then add the inequalities $$y_i t \le e_i \le t-1 + (3n-2-t) y_i$$ $$y_1 + \dots + y_n = 5$$ and count the number of solutions to this system.