"Playing" a Combinatorial Math Game I Invented Recently, I thought of the following "game" that I would like to frame as a combinatorial optimization problem:


*

*Assume there are 5 Baskets. The first basket has 5 discrete objects (e.g. apples), the second basket has 3 discrete objects (e.g. oranges), the third basket has 1 discrete object (e.g. watermelon), and the fourth and fifth baskets have 11 kilograms of some continuous object (e.g. coffee and rice - not the right analogy, but bear with me)


*Assume that there exists some discrete and non-differentiable (black box) function" which assigns a cost to combinations of objects from different baskets. For example : A1,A2, B2, D = (1 : 2.5), E = (6.1 : 7, 8.1 : 9.2) might have a cost of "7.1" and A1,A3, B1, C = C1 D = (1 - 8), E = (5.1 - 5.5) might have a cost of "8.773".
For this "game", here are the rules:

*

*There are 3 players.


*The first player chooses some items from some of these 5 baskets. If the first player wanted, the first player could pick everything and leave the other 2 players with nothing. The first player also has the choice of ignoring baskets if he want to (e.g. A1, A2, C1, D = (1 : 3.1) )


*From the remaining items, the second player chooses some combination of items. The second player also has the option of selecting all the remaining items and leaving the third player with nothing.


*Finally, the third player chooses items from the remainder (at the end, some items can remain unchosen by all 3 players).


*Once each player has made their selections, the "function" assigns a cost to each of their selections.


*This function has the general form of : f(selection A = a, B = b, C = c, D = d, E = e) = Cost


*Let's say for the purpose of this game, the cost function isn't  "linear". For example f(A = A1, B = 0, C = 0, D = 0, E = 0) = 3.1 , f(A = A2 , B = 0, C = 0, D = 0, E = 0) = 1.6 , f(A = (A1, A2) , B = 0, C = 0, D = 0, E = 0 ) = 0.89.
The goal of the game is for:

*

*Objective: All 3 players have to try and ensure that the total summed cost of the group's selection is as close to 30 as possible (a cost of exactly 30 automatically results in a win), but any cost over 30 automatically results in a loss. Either all 3 players win together or lose together.


*Constraint: Each player should at least have 1 Red Square in their selection - this will ensure none of the players can finish the game with an empty basket.
Thus - what is the optimal selection that each player should make such that the group's objective is maximized and the constraint is met?
My Question: To me, this "game" seems to be some variant of the "Knapsack Optimization Problem" or a "Assignment/Resource Allocation Problem". In particular, this seems to be a Discrete Combinatorial Gradient-Free Optimization Problem (an Mixed Integer Programming Problem).
Suppose these these 3 players can play this game over and over while they study "how their selections influence the overall cost" and "which selections result in the cost function being closer to the desired value".
For instance:

*

*Round 1: Player_1_Cost = 12.1, Player_2_Cost = 8.5, Player_3_Cost = 19.11.  Total Cost = 30 - 39.7 = - 9 .7


*Round 2: Player_1_Cost = 1.5, Player_2_Cost = 0.5, Player_3_Cost = 0. Total Cost = 30 - 2 = + 28


*Round 1000: Player_1_Cost = 9.5, Player_2_Cost = 7, Player_3_Cost = 8 . Total Cost = 30 - 24.5 = + 5.5
In this case, the players would keep playing the game until they start to "learn" which selections will result in the "Total Cost" being closest to 0. At first, the players might simply pick random selections and observe the "Total Cost." Later, they might use a more sophisticated approach such as "Evolutionary Algorithms and Metaheuristics" to "strategically combine" successful selections from the past and gradually progress towards more optimal selections:

Although I know very little about Game Theory, I think that we might be able to view a "progression and evolution" of selection strategies as the number of rounds increases. For instance, Player 1 always chooses first - at first, Player 1 might behave very erratically and leave Player 2 and Player 3 in a position that will make it impossible for the group to win the game; but as all 3 players continue to play the game and try to "reverse engineer" the nature of the Cost Function by studying the impact of including/removing certain items on the Total Cost; they might be able to learn how to strategically cooperate with each other to win the game as a group.
Can someone please tell me if this "game" that I have created can be interpreted as a (Discrete Combinatorial) Optimization Problem? Does this problem that I have created correspond to some a pre-existing type of Optimization Problem? Could certain types of Optimization Algorithms (e.g. Evolutionary Algorithms) make progress in this game and slowly start to "learn" optimal selections?
Thanks!
 A: Sure. There are $6*4*2$ possible combinations of things to choose from the first three categories, or $48$ total combinations. Then, given some choice of the first three, you have a 2D plane remaining of values you can take from D and E.
So you can think of there as being 48 different functions $f(d,e)$ which take only the value of d and e and give the total result, with each function corresponding to one partial selection of A, B, and C with D and E remaining.
If the black box function is continuous, in D and E, meaning that small changes in D and E lead to small changes in the output, you can try things like gradient descent to look for local minima in D and E, beginning at different starting points. I mean, this is the bread and butter of machine learning right now - looking at some n-dimensional function and trying to find the parameters that minimize it, and there are all kinds of algorithms for this with differing degrees of success in different situations. If it isn't continuous, you can at least have some success with this as long as it's continuous almost everywhere. If the function is everywhere discontinuous then it gets really difficult to figure out how you could gain information about any result from any other result.
So a computer could easily solve this problem just by searching for the global minimum for all 48 of these functions using any available strategy.
But there is an unspoken assumption in your question, which is: the players may not want to play a zillion rounds of this game just to map out the landscape of the cost function, because they will get tired. This is analogous to assuming there is some kind of "penalty" or "cost" to playing each round of the game - the cost of spending time doing it - so you really want to iterate toward a winning strategy as quickly as possible, in the minimum number of rounds. This is also a very common problem in machine learning: for instance in quantitative finance, where you will want to develop a winning strategy for some kind of trading situation - which similarly involves choosing some allocation of resources to assets - but every time you want to do a "test" you put some capital at stake, and you don't want to do so many "tests" that you run out of money. So you want to somehow develop a model of which tests are expected, somehow, to yield the most useful information, and only run the tests you think are most useful. Popular YouTube channel 3 Blue 1 Brown just did a video on this involving developing a strategy to win the game Wordle, where you have only 6 guesses, so that may be useful to look at. Either way there is another entire branch of machine learning devoted to this, involving hypothesis testing and so on, so that may be a useful place to look at as well.
