Re: Is there a known algorithm to solve this "playoff ranking" problem?


Chris F Clark wrote:
"Proginoskes" <CCHeckman@xxxxxxxxx> writes:

Chris F Clark wrote:
I would like to compute the probabilities of "playoff rankings" given
a set of n teams playing a fixed set of pairwise games (with
probabilities of each team winning at a certain percentage), some
pairs occur more than once and some pairs not at all.
...
The program I am comparing to, does the analysis by Monte Carlo
simulation (see www.nfl-forecast.com), but it seems to me that there
must be a more closed-form way of calculating the results.
...

I'm not 100% clear about what problem you're solving. Are you starting
off with a list of the probabilities that team A beats team B, and
asking what the probability that team A is at position k after n weeks?
I'm not sure how the "cut-off" would work here ...

Yes, that's roughly what I'm calculating, and I roughly need down to
spot 6 in the list. For the cut-off some teams have no chance of
winning enough games to get to the 6th spot. Thus, we don't have to
calculate their wins. Moreover, as the weeks progress and certain
high ranking teams have accumulated more wins, more lower ranked teams
are eliminated from contention.

To make this a bit more concrete, in one conference we have 1 team
with 10 wins, 1 with 9, 2 with 8, 3 with 7, ... and 1 with 2 wins and
we have 5 games left. Thus, the team with 2 wins can at best win 7
games, which means it could be at best in slot 3. If only the top 3
slots were interesting, One wouldn't need to calculate the probability
of the 2 win team winning all its remaining games, because even if it
did so, the result would be irrelevant, the team could at best make
slot 4.

Well, one thing that you need is a rule stating how you rank the teams
at any given time, especially how you break ties.

Making your source code available would help in this regard.

The site mentioned and the software on it isn't mine, so I can't do
that.

Fair enough.

Moreover, I'm just looking for a general solution to this problem, for
example one might say its a branch-and-bound problem (and here's how
branch-and-bound works) or a shortest-path problem or there is a graph
coloring solution or dynamic programming solves it.

You can probably use dynamic programming.

--- Christopher Heckman

.

Relevant Pages

  • Re: Distribution and probability
    ... larger games but this one is small enough to work out by hand. ... First note the tenth flip is pointless: you can't win then if you haven't ... have a 25% chance of getting each of the possible pairs, ... So in the next column we compute the probabilities of winning as ...
    (sci.math)
  • Re: Is there a known algorithm to solve this "playoff ranking" problem?
    ... a set of n teams playing a fixed set of pairwise games (with ... probabilities of each team winning at a certain percentage), ... winning enough games to get to the 6th spot. ... of the 2 win team winning all its remaining games, ...
    (comp.theory)
  • Is there a known algorithm to solve this "playoff ranking" problem?
    ... I would like to compute the probabilities of "playoff rankings" given ... a set of n teams playing a fixed set of pairwise games (with ... teams as vertexes and games as edges, ...
    (comp.theory)
  • Re: Is there a known algorithm to solve this "playoff ranking" problem?
    ... a set of n teams playing a fixed set of pairwise games (with ... teams as vertexes and games as edges, ... transititive closure to get the final probabilities of each possible ... and cut-off evaluating some games once I know they won't ...
    (comp.theory)
  • Re: FA Cup - My Bets
    ... outside Sweden, in many other countries? ... Each weekend there is a fixed set of 13 games, predominantly English during ... The games are decided several weeks in advance. ...
    (rec.sport.soccer)