Is this a version of the Knapsack Optimization Problem?

Question

Suppose you have the following problem:

• There are 100 basketball players : Player 1 is a pro, Player 100 has never played basketball before - and the rest follow some sort of Normal Distribution. However, let's assume we don't know this.

• We have a lot of data (only the final game score) about games played between these players. For example, (Player 6 ,Player 51) beat (Player 8, Player 82, Player 75) with a score of 15-2. (Player 5) beat (Player 91, Player 92, Player 93, Player 94) with a score of 15-5. (Player 2, Player 3, Player 4) beat (Player 1) with a score of 15-11. Etc.

• For simplicity sake, we can summarize games as : (Player 5) beat (Player 91, Player 92, Player 93, Player 94) = + 10 (i.e. 15 - 5 = 10)

The general goal of this problem is to find out:

• Rank the players based on individual ability in order from best to worst

I think this could be a difficult problem, because we don't always know if a player is good overall or only good because he is playing alongside good players. For example, suppose (Player 1, Player 100) often play on the same team - we have no way of knowing if Player 100 is equally contributing to the victories or if he just happens to be on the court and passively contributes.

• Find out which "pairs of players" are better: For example, (Player 71 and Player 43) are the best pair

• Find out which "triplets of players" are better: For example, (Player 63 and Player 45, Player 9) are the best triplets

This problem seems very difficult because there is no clear-cut way of isolating the skill of individual basketball players.

My Question: Is there some optimization algorithm that can be used to "reverse engineer" and "untangle" the individual skills of basketball players - perhaps this problem could be framed as some sort of "Knapsack Optimization Problem"?

Could some algorithm try to scan through different combinations of the data and try to identify the "weakest links"? Something like

• Player 1 and Player 100 always do well together
• Player 1 always does well no matter who he is playing with or who is he playing against
• Player 100 does really bad when he plays with lower tier players
• Lower tier players generally perform poorly unless they are playing with upper tier players
• Therefore, Player 100 isn't likely a good player

Is there some algorithm that can solve a problem like this?

Answer 1

I don't see how this is could be a knapsack problem if there are "second order" effects such as "Player 1 and Player 100 always do well together".

Even if you already have all possible playoffs results known a meaningfull way of ranking is not clear. It would also make a difference whether you want to find the best player against a particular team or the best players in general. If all possible $100*99*98*97*96*95=858277728000$ 3-vs-3 playoffs results are known a robust way of ranking single players would be the winrate of teams which have that player.

If you do not have all possible playoffs and making a playoff is expensive this fall under the discipline of optimal experiment design. I am not aware of any model based approaches for that. Genetic algorithms would be worth looking into if you want to find good teams, however they will not yield much insight.

One idea which is just barely at intersection of OR and machine learning would be to encode the features you are looking for in a mixed-integer model, such as players doing well together (f.e. quadratic terms) or how good certain players are and find a sparse models which does fit all the play-offs you did. Since you can solve this at different levels of sparsity you have multiple models which might disagree with eachother. If you have a point of disagreement you can then run that playoff until you are happy with the predictions. The idea to use sparse OR-style models to replace machine learning models is well explained in this talk Scoring Systems: At the Extreme of Interpretable Machine Learning. I have not seen it used in a data generation loop i proposed and i have not tested this loop either. So it is indeed possible that you might invent novel methods to deal with your problem.

Note that this entire reply doesn't address the stochastic nature (or influence of unobservable variables) which would be inherent to such a play off, as well as that players are not static but change with time. Dealing with these assumptions might additionally complicate the problem.

I must agree with Prof. Rubin that this question is better addressed using machine learning tools. If you had a machine learning model with a satisfying performance you might also be able to recover a sparse model from which can derive the insights you are looking for.