Excel help for auction?

August 24, 2008 5:16 PM

Excel filter: Help me optimize my auction!

Also, fantasy football filter.

Ok, so I have a set of projections/predicted stats for NFL players, and their predicted points scored according to my league's settings. I also have the average auction price that each player has been going for in mock auctions and other leagues.

What is the best way to use excel -- using functions, visual basic, whatever -- to figure out what the best combination of players at certain prices is? In other words, can excel help me figure out what starting lineup will best use all of the money I can use to auction and get me the most points?

posted by shotgunbooty to sports, hobbies, & recreation (2 comments total)

I think what we have here is an instance of the 0-1 knapsack problem, which is NP-complete.

There's an algorithm in the Wikipedia article that solves the problem. You'll probably need to write that in VBA. NP-complete problems in general can't be solved by computers in a reasonable amount of time for large inputs, but the knapsack problem is considered one of the "easier" NP-complete problems, so you might have some success.
posted by zixyer at 6:03 PM on August 24, 2008

Indeed, though this task is (likely) in a class of NP-complete problems, you can usually get by with a good heuristic.

In this case, one of the most commonly used strategies is to order by "bang-for-the-buck" and choose greedily (this is called the "Greedy Approximation Algorithm" in the Wikipedia article). Namely, for each player, divide their predicted points by the average auction price to get a score. Sort the list of players by their score in decreasing order (i.e.: highest score on top). Go down the list in order until you exhaust your budget. You should have no problem doing this in Excel.

This approach often gives pretty good results on real-world problems. And, you can always manually tweak the results so you don't end up with, say, an all-kicker team.
posted by mhum at 3:46 PM on August 25, 2008