[ Home ] [ Library ] [ Bookstore ] [ Contact ] [ Search ]

Knapsack Optimization and the Budget Planning Problem

by Keith Woolner

Posted: September 21, 1997

The following was excerpted from a article posted to the Boston Red Sox mailing list in a discussion about how well Mo Vaughn's production could be replaced if he and the Red Sox were unable to come to terms, and whether he was worth the money (in baseball terms) that he was demanding.  The following tangent addresses how ballclubs ought to be framing the problem of optimizing their budget dollar.


Lastly, I'd like to address the idea that if Jefferson (or Stanley, or some combination of other players) produced more runs per dollar, then the Sox would be better off playing Jefferson and saving the money. I'm going to wander a bit astray in setting up the explanation, but if you stay with me I'll try to make it worth your while. :-)


That approach only works if you are willing to say that you'd prefer a 75-win team with a $20 million payroll to a 90-win team with a $45 million payroll. That is, wins and dollars must be interchangeable and you are indifferent between them so long as you convert them at some rate of exchange (i.e. You'll trade 5 wins for $15 million and not mind).

While this may or not be the case for management, it almost certainly is not the case when it comes to fans. Would we be happy about a team that makes money hand over fist, but finishes in the 100 loss territory year after year? Clearly, we need to be aware of financial constraints (so we don't delude ourselves into thinking that trading for Bonds, Belle, Maddux, Smoltz, Thomas, and Griffey is sensisble or likely), but for most of us the budget is a constraint, and a winning team is the goal.

What we really need to consider is: what is the best team we can assemble for a payroll budget of $X million (whatever the value of X may be). It's like assembling a portfolio of players to go into a season with, much like you might assemble a financial portfolio to play the stock market with.

If this were a financial market, we might be able to buy whatever quantity of a stock or bond that we want (include partial shares). However, we can not choose whatever quantities and proportions of players we want -- there are only a finite number of players, with their associated rates of return (production) and prices (salaries). Furthermore, there are not enough of them out there to simulate a continuous range of points of the curve as you might be able to do in the financial market. It's an important point, however obvious it may seem, that players come in discrete units,
(they get annoyed if you try to cut them in half), so you have to take the whole thing. :-)

A problem with this structure (finding a mix of items from a universe of fixed, indivisible items with costs and values that must fit within a given cost constraint that has the highest value) is known in optimization circles as a knapsack problem. The name comes from the classic form of the problem in which a hiker is filling a knapsack with items to take with him on a hike, but the sack will only hold so much volume. Each item has a usefulness (or value) to him, and a size (cost) that it consumes in the sack  The solution to the problem involves finding the combination of items
that fit in the sack but give him the most usefulness for his hike.

The analogy to baseball budgeting should be clear. In every off-season, there are a few dozen players available for hire. Each one has an expected production (VORP), and a salary at which his services can be had. How do you find the best mix of players to fit within your budgetary knapsack?

In baseball's case, there are a few twists to the classic form of the problem. The value of each item is uncertain (player projections aren't 100% accurate), there may be items already in the sack that you have to take (players already on the team, particularly if they have guaranteed salaries), the costs are not certain (salaries can often depend on negotiations with other teams, and performance incentives that may or may not be met), and there is a limit to the total number of items you can take, regardless of their weight (the 25 man roster is a hard limit, regardless of how much space you might have left under the budget constraint).

However, given the state of the team, a list of available players, a set of performance projections, and estimates of how much it would take to sign the players, you can work out the optimal set of signings for a budget of any given size. The value that the optimal solution represents would be the maximum number of expected wins that the team could reasonably anticipate given the amount of money management is willing to spend.


Ownership controls the size of the knapsack by setting the budget for payroll. Whether or not they choose to spend more money depends on their personal tradeoffs between wins and money (to get back to the point I was making earlier). For example, a team might try to estimate how well it could do with differing payrolls, and come up with the following list:

  Payroll W-L (expected)
A)   $20M   62-100
B)   $30M   71- 91
C)   $40M   81- 81
D)   $50M   88- 74
E)   $60M   94- 68

From ownership's perspective, scenario C) might be the most attractive, providing a not-horrible team without enormous outlays of cash. The marginal returns of 7 wins for $10M, and 13 wins for $20M may simply not be attractive. We as fans certainly prefer E), but we have no direct financial stake in the how profitable the team is, so our perspective is very different.

What's this got to do with Vaughn? Well, let's say for a minute that the team does want to compete this year, and has one roster spot left open to sign a first baseman, and has $10M under their budget left. You have an option of signing any of the following:

Name                VORP Salary (VORP/$M)
1. Mike Stanley     +20   $ 3M (6.67)
2. Reggie Jefferson +28   $ 4M (7.00)
3. Mo Vaughn        +40   $10M (4.00)
4. Frank Thomas     +60   $12M (5.00)

Your optimal signing under these circumstances is Vaughn, *despite* the fact that he gives you the lowest bang for the buck of any of the players listed (lowest VORP per $ million of salary). You can't sign Thomas because he's too expensive, and neither Jefferson nor Stanley add as much value as Vaughn does. You'd actually be better off signing both Stanley *and* Jefferson (+48 VORP for $7M), but you'd be over your 25-man roster limit. Within the constraints of your budget, the roster size, and the market conditions, Mo would be the man you wanted
to maximize your team's chances of making the playoffs. Unless you can revisit the rest of your roster (which still might be optimal as is even after you try shifting things around), increase your budget constraint (which might be a hard sell if the team is trying to finance a new park, or is being put up for sale), or change the roster size (fat chance) it's entirely rational to "overpay" Mo in these circumstances.

Using a simple metric like production per dollar (I've seen HR/$, RBI/$ Pitcher Wins/$, and have used VORP/$ myself) is a good rule-of-thumb for whether a player is earning his keep relative to other players in the market. But basing decisions solely on who the good bargains are isn't likely to lead to a winning team, as it tips the scales towards the financial side of the ledger. Unless you are standing to profit from that money personally, I think you're better off treating your payroll budget as a constraint to be worked with rather than an alternate
goal to be achieved.

[ Home ] [ Library ] [ Bookstore ] [ Contact ] [ Search ]

Last Updated: Contact webmaster@stathead.com for corrections or problems

Copyright 1997-2001 by Keith Woolner. All included authors retain the copyrights to their original works.