Sub-exponential time algorithm to compute playoff chances
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. 143
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}$. 180