# Algorithm for modified knapsack problem

We have $$n$$-players in a game. We have a population of players we can choose from. Each player score is a normally distributed random variable and each player has a cost to add to the team. We are limited to $$n$$-players and the total cost must be less than or equal to $$m$$.

The total score for a team is calculated as the sum of all of the individual player's score on that team. Our goal is to maximize the expected team score while staying under our allowed player weight and number of players.

Now, suppose that in this game we drop the score of the player that has the lowest score on the team and do not consider it in the total team score.

Does a deterministic algorithm exist that will allow us to reach the optimal solution?

Let $$X_1,\dots,X_n$$ denote the scores of the individual members of the team. Then the score $$Y$$ of the team is given by

$$Y = X_1 + \dots + X_n - \min(X_1,\dots,X_n).$$

So, by linearity of expectation, the expected value of the score of the team will be

$$\mathbb{E}[Y] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] - \mathbb{E}[\min(X_1,\dots,X_n)].$$

This suggests a natural approach. Given a candidate list of members of the team, calculate the expected team score $$\mathbb{E}[Y]$$ using this formula. Try all possibilities for the list of team members, compute the expected team score for each, and pick the one that has the highest expected team score.

The biggest challenge is to evaluate the above formula for a particular list of team members. It is easy to evaluate $$\mathbb{E}[X_i]$$, but evaluating $$\mathbb{E}[\min(X_1,\dots,X_n)]$$ where $$X_1,\dots,X_n$$ are independent Gaussian random variables is challenging. This is an order statistic, and there are various techniques for approximating its expected value. One is to numerically estimate a certain integral. Another is to use the approximation $$-\Phi^{-1}({n-0.375 \over n+0.25})$$, where $$\Phi$$ is the cdf of the normal distribution. See J.P. Royston, Expected Normal Order Statistics (Exact and Approximate), Journal of The Royal Statistical Society Series C (Applied Statistics), vol 31 no 2, pp.161-165. There may be better algorithms; hopefully this gives you the technical terms to use for searching.

• Linearity of expectation is a good insight. I think subtracting the minimum can be dealt with in a simpler way though. E.g., we could sort players by increasing expected score, and use a slight variant of the usual Knapsack DP in which instead of a calculating the maximum expected score per (totalCost, numPlayers) pair, we calculate it per (totalCost, numPlayers, numScoresExcluded) triple, where numScoresExcluded can only take the values 0 or 1. (I.e. twice the number of subproblems.) Subproblems with numPlayers $\ge 1$ but numScoresExcluded $= 0$ are invalid. – j_random_hacker Feb 19 '19 at 12:26
• @j_random_hacker, I didn't quite follow your approach -- perhaps you'd like to write it as a full answer? Given that you're sorting by expected score, I worry that your algorithm might be implicitly effectively making the assumption that $\mathbb{E}[\min(X_1,\dots,X_n)] = \min(\mathbb{E}[X_1],\dots,\mathbb{E}[X_n])$ (which isn't valid). – D.W. Feb 19 '19 at 16:59
• Whoops, I was indeed making that assumption! FWIW it should still be a good approximation if there are many standard deviations of distance between the means of the two smallest-mean distributions. – j_random_hacker Feb 19 '19 at 17:47