Does this game that I invented correspond to a valid optimization problem?

Question

Recently, I thought of the following "game" that I would like to frame as an optimization problem:

• Assume there are five baskets. The first basket has five discrete objects (e.g., apples), the second basket has three discrete objects (e.g., oranges), the third basket has one discrete object (e.g., a 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 "mysterious unobservable (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". We have no idea how this cost is calculated, and we just have this mysterious function that assigns costs to different combinations of items from these baskets.

For this "game", here are the rules:

• There are three players.

• The first player chooses some items from some of these five baskets; they have the choice of ignoring baskets if they want (e.g. A1, A2, C1, D = (1 - 3.1) ). From the remaining items, the second player chooses some combination of items. Finally, the third player chooses items from the remainder (at the end, some items can remain unchosen by all three players).

• Once each player has made their selections, the "mysterious 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 always "monotonic". 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: The cost of each player's selection to be less than 10 but as close to 10 as possible
• Constraint: Each player should at least have one red Square in their selection
• Thus - what is the optimal selection that each player should make such that the objective is maximized and the constraint is met?

To me, this "game" seems to be some variant of the knapsack optimization problem or an assignment/resource allocation problem. In particular, this seems to be a discrete combinatorial gradient-free optimization problem.

Suppose these three 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:

Can this "game" that I have created be interpreted as a (discrete combinatorial) optimization problem? Does this problem that I have created correspond to some a preexisting type of optimization problem?**

Answer 1

Your game does not fall into classical discrete optimization as the objective is unknown. As soon as the blackbox function is fully know (or one supposes a model with fixed parameters for it) it would though. However even then due to the probably nonlinear nature of your black box i doubt there is a specific name for MINLP problem that agents solve each round.

Further thoughts:

Given that Agents 1 objective i don't see why it would cooperate with other agents to help explore the assignment space if it found an assignment that is good enough for it. And similarly Agent 2 does not care whether Agent 3 is left with a solvable problem. So i am not sure rational agents playing this game would necessarily converge towards a solution with Total Cost $= 30$.

Objective: The cost of each player's selection to be less than 10 ...

This part of the objective is not computable, it sounds more like a constraint, if you want to express this as an objective one could say for example: the objective is $3||x-10||$ if $x<10$ and $||x-10||$ if $x \geq 10$;

Answer 2

If we strip away the game aspects, this might be related to simulation optimization. Your black box is not stochastic, but simulation optimization methods do apply to deterministic simulations as well.