On solving the wrong problem
NFL "survivor" pools are an ideal form of gambling. A bunch of people enter, everyone picks a team every week, and if your team loses, you're out. You can't pick the same team twice. The last person standing wins.
A quick Web search suggests that a lot of people begin by asking the first question I asked: Given some interval of the NFL season, which set of picks gives you the best chance of getting through that interval without losing a game?
If you ask yourself this question, how should you answer it?
Recognize that this is a graph problem
(There are different ways to approach this, but I've found it easiest to treat every permissible prefix of games—that is, every way of picking the first N games, for N from 1 to the length of the interval—as a node.)
The goal is to find a path to the node corresponding to the highest cumulative probability, among all nodes representing full pick sets (prefixes as long as the interval).
Convert products to sums
Recall that problems where we need to maximize products can be converted into problems where we need to maximize sums (just take the logarithm of each factor and exploit the fact that the sum of logarithms is the logarithm of the product; see, e.g., section 6.1.7 of the second edition of Skeina's The Algorithm Design Manual, or use a slide rule until this is intuitive).
Realize that brute forcing the problem makes the state space too big
Figure out, either by estimation or by trying it, that brute forcing this problem will make you look at way too many nodes.
Implement A* search with an admissible heuristic
Implement a first, very naive heuristic: put a lower bound on the distance between a node and the goal by calculating the path cost if, from that node, there were a path including only games with the biggest possible favorite (in the NFL these are something like 15-1 to 20-1 favorites).
When the search is still too slow, try a slightly stronger heuristic
For each node, calculate the cost of a path corresponding to the best games for each remaining week in the interval, but excluding games in which you've already chosen the favorite. That is, pretend that, at any node, you are barred in the future from picking any team you've already picked, but you don't have to worry about whether those future picks conflict with each other.
This takes a bit longer to calculate, but it turns out to be far more effective: it runs through the whole season in roughly half a second on my computer, and that's in Python and without taking much care to optimize anything. [Note from the editor: this was written a long time ago! "My computer" was probably some sort of 2013 MacBook.]
Why it makes a fun and straightforward project
The goal is easy to define and the problem can be solved by combining a few fundamental ideas, finding a happy “middle ground” heuristic that is easy to calculate but also sufficiently informative, and taking care of some implementation details.
For example, we can choose any node corresponding to a full pick set, so there's not a single goal node we know in advance if we describe the graph as above. One way to get around this problem is to calculate shortest paths to every node, but this graph is too big for that to be a good idea. There are several alternatives here, but my preferred one is to add a dummy Week 18 in which there is only one game, in which the Browns or a fake team are huge favorites, and to call any node including that game a goal.
But none of this gives you the right solution.
What's most important, though, is not to fool yourself into mistaking the easily defined question for the right one. If this is your whole analysis, you will be making very big mistakes in any survivor pool!
There are many reasons for this:
- You don't know in advance how many games you need to pick correctly to win.
- Your estimates of win probabilities will change between now and future weeks (a whole bunch of the lines will move significantly, even if you don't know which direction they're going to move in).
- Most importantly, there is value in picking games that other people don't pick: when an upset wipes out a lot of the field but you picked a different game, that's a big windfall for you.
The process I described above entirely ignores this effect, which drives correct strategy in survivor pools.
Because of this, I've come to think of this as a nerd sniping scenario. (In the metaphor, you are you, the resistance problem is the probability-maximizing problem, and the truck is the consequences of making gambling decisions without considering the effects of your opponents' choices.)
The A* search technique is still useful: It helps you estimate the value of picking one week correctly (how much does having picked that team handicap your ability to choose high-value paths after that?); it is useful in endgame scenarios (though in those cases, brute-force search will do fine); and it can be useful for estimating how many weeks the pool is likely to take.
As so often happens, when you're answering a hard question ("Which team do I pick in the survivor pool?"), it can be useful to answer a related and simpler one ("Which team allows me the best chance at sweeping the season?"), but only if that doesn't cause you to make mistakes that matter more than the answer you find.