# 15-12 Signing free-agent baseball players

Suppose that you are the general manager for a major-league baseball team. During the off-season, you need to sign some free-agent players for your team. The team owner has given you a budget of $\$X$ to spend on free agents. You are allowed to spend less than $\$X$ altogether, but the owner will fire you if you spend any more than $\$X$.

You are considering $N$ different positions, and for each position, $P$ free-agent players who play that position are available. Because you do not want to overload your roster with too many players at any position, for each position you may sign at most one free agent who plays that position. (If you do not sign any players at a particular position, then you plan to stick with the players you already have at that position.)

To determine how valuable a player is going to be, you decide to use a sabermetric statistic known as "$\text{VORP}$", or "value over replacement player". A player with a higher $\text{VORP}$ is more valuable than a player with a lower $\text{VORP}$. A player with a higher $\text{VORP}$ is not necessarily more expensive to sign than a player with a lower $\text{VORP}$, because factors other than a player's value determine how much it costs to sign him.

For each available free-agent player, you have three pieces of information:

- the player's position,
- the amount of money it will cost to sign the player, and
- the player's $\text{VORP}$.
Devise an algorithm that maximizes the total $\text{VORP}$ of the players you sign while spending no more than $\$X$ altogether. You may assume that each player signs for a multiple of $100,000$. Your algorithm should output the total $\text{VORP}$ of the players you sign, the total amount of money you spend, and a list of which players you sign. Analyze the running time and space requirement of your algorithm.

Let $p.cost$ denote the cost and $p.vorp$ denote the $\text{VORP}$ of player $p$. We shall assume that all dollar amounts are expressed in units of $\$100,000$.

Since the order of choosing players for the positions does not matter, we may assume that we make our decisions starting from position $1$, moving toward position $N$. For each position, we decide to either sign one player or sign no players. Suppose we decide to sign player $p$, who plays position $1$. Then, we are left with an amount of $X - p.cost$ dollars to sign players at positions $2, \ldots, N$. This observation guides us in how to frame the subproblems.

We define the cost and $\text{VORP}$ of a *set* of players as the sum of costs and the sum of $\text{VORP}$s of all players in that set. Let ($(i, x)$ denote the following subproblem: "Suppose we consider only positions $i, i + 1, \ldots, N$ and we can spend at most $x$ dollars. What set of players (with at most one player for each position under consideration) has the maximum $\text{VORP}$?" A *valid* set of players for ($(i, x)$ is one in which each player in the set plays one of the positions $i, i + 1, \ldots, n$, each position has at most one player, and the cost of the players in the set is at most $x$ dollars. An *optimal* set of players for ($(i, x)$ is a valid set with the maximum $\text{VORP}$. We now show that the problem exhibits optimal substructure.

*Theorem (Optimal substructure of the VORP maximization problem)*

Let $L = \{p_1, p_2, \ldots, p_k\}$ be a set of players, possibly empty, with maximum $\text{VORP}$ for the subproblem $(i, x)$.

- If $i = N$, then $L$ has at most one player. If all players in position $N$ have cost more than $x$, then $L$ has no players. Otherwise, $L = \{p_1\}$, where $p_1$ has the maximum $\text{VORP}$ among players for position $N$ with cost at most $x$.
- If $i < N$ and $L$ includes player $p$ for position i, then $L' = L - \{p\}$ is an optimal set for the subproblem $(i + 1, x - p.cost)$.
- If $i < N$ and $L$ does not include a player for position $i$, then $L$ is an optimal set for the subproblem $(i + 1, x)$.

*Proof*

Property 1. follows trivially from the problem statement.

- Suppose that $L'$ is not an optimal set for the subproblem $(i + 1, x - p.cost)$. Then, there exists another valid set $L''$ for $(i + 1, x - p.cost)$ that has $\text{VORP}$ more than $L'$. Let $L^{\prime\prime\prime} = L'' \cup \{p\}$. The cost of $L^{\prime\prime\prime}$ is at most $x$, since $L''$ has a cost at most $x - p.cost$. Moreover, $L^{\prime\prime\prime}$ has at most one player for each position $i, i + 1, \ldots, N$. Thus, $L^{\prime\prime\prime}$ is a valid set for $(i, x)$. But $L^{\prime\prime\prime}$ has $\text{VORP}$ more than $L$, thus contradicting the assumption that $L$ had the maximum $\text{VORP}$ for $(i, x)$.
- Clearly, any valid set for $(i + 1, x)$ is also a valid set for $(i, x)$. If $L$ were not an optimal set for $(i + 1, x)$, then there exists another valid set $L'$ for $(i + 1, x)$ with $\text{VORP}$ more than $L$. The set $L'$ would also be a valid set for $(i, x)$, which contradicts the assumption that $L$ had the maximum $\text{VORP}$ for $(i, x)$.

The theorem suggests that when $i < N$, we examine two subproblems and choose the better of the two. Let $v[i, x]$ denote the maximum $\text{VORP}$ for $(i, x)$. Let $S(i, x)$ be the set of players who play position $i$ and cost at most $x$. In the following recurrence for $v[i, x]$ we assume that the max function returns $-\infty$ when invoked over an empty set:

$$ v[i, x] = \begin{cases} \max\limits_{p \in S(N, x)} {p.vorp} & \text{if $i = N$}, \\ \max \Big\{v[i + 1, x], \max\limits_{p \in S(i, x)}{p.vorp + v[i + 1, x - p.cost]} \Big\} & \text{if $i < N$}. \end{cases} $$

This recurrence lends itself to implementation in a straightforward way. Let $p_{ij}$ denote the $j$th player who plays position $i$.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | FREE-AGENT-VORP(p, N, P, X) let v[1..N, 0..X] and who[1..N, 0..X] be new tables for x = 0 to X v[N, x] = -∞ who[N, x] = 0 for k = 1 to P if p[N, k].cost ≤ x and p[N, k].vorp > v[N, x] v[N, x] = p[N, k].vorp who[N, x] = k for i = N - 1 downto 1 for x = 0 to X v[i, x] = v[i + 1, x] who[i, x] = 0 for k = 1 to P if p[i, k].cost ≤ x and v[i + 1, x - p[i, k].cost] + p[i, k].vorp > v[i, x] v[i, x] = v[i + 1, x - p[i, k].cost] + p[i, k].vorp who[i, x] = k print "The maximum value of VORP is" v[1, X] amt = X for i = 1 to N k = who[i, amt] if k != 0 print "sign player" p[i, k] amt = amt - p[i, k].cost print "The total money spent is" X - amt |

The input to $\text{FREE-AGENT-VORP}$ is the list of players $p$ and $N$, $P$, and $X$, as given in the problem. The table $v[i, x]$ holds the maximum $\text{VORP}$ for the subproblem $(i, x)$. The table $who[i, x]$ holds information necessary to reconstruct the actual solution. Specifically, $who[i, x]$ holds the index of player to sign for position $i$, or $0$ if no player should be signed for position $i$. The first set of nested **for** loops initializes the base cases, in which $i = N$. For every amount $x$, the inner loop simply picks the player with the highest $\text{VORP}$ who plays position $N$ and whose cost is at most $x$.

The next set of three nested **for** loops represents the main computation. The outermost **for** loop runs down from position $N - 1$ to $1$. This order ensures that smaller subproblems are solved before larger ones. We initialize $v[i, x]$ as $v[i + 1, x]$. This way, we already take care of the case in which we decide not to sign any player who plays position $i$. The innermost **for** loop tries to sign each player (if we have enough money) in turn, and it keeps track of the maximum $\text{VORP}$ possible.

The maximum $\text{VORP}$ for the entire problem ends up in $v[1, X]$. The final **for** loop uses the information in who table to print out which players to sign. The running time of $\text{FREE-AGENT-VORP}$ is clearly $\Theta(NPX)$, and it uses $\Theta(NX)$ space.