7
$\begingroup$

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

Enter image description here

  • 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:

Enter image description here

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?**

$\endgroup$
13
  • 2
    $\begingroup$ What does "A1,A2, B2, D = (1 - 2.5), E = (6.1 - 7, 8.1 - 9.2)" mean? Does it mean "take the objects A1, A2, and B2; take the range 1 - 2.5 from basket D; and take the ranges 6.1 - 7 and 8.1 - 9.2 from basket E"? $\endgroup$ Feb 17, 2022 at 21:56
  • 1
    $\begingroup$ @stats_noob, would you say please, is the value of each object in the cost function deterministic or they will change in each game? I mean, for example, the cost for $A1,A2, B2, D = (1 - 2.5), E = (6.1 - 7, 8.1 - 9.2) = 7.1$ and if in the next game the assignment be the same the cost is $7.1$ or it is different? $\endgroup$
    – A.Omidi
    Feb 19, 2022 at 13:42
  • 1
    $\begingroup$ @stats_noob, Assume that there exists some "mysterious unobservable (discrete and non-differentiable) black-box function. I think you are facing with a deterministic function than a back-box function. $\endgroup$
    – A.Omidi
    Feb 20, 2022 at 5:32
  • 1
    $\begingroup$ @stats_noob, in this case, a deterministic model (MIP/CP) would be useful, and minimizing this cost with regard to the mentioned constraints is what you want. $\endgroup$
    – A.Omidi
    Feb 20, 2022 at 5:47
  • 1
    $\begingroup$ @ A.Omidi: thank you so much for your reply! At this point, I am just interested in knowing if this "game" I invented corresponds to an Optimization Problem in general ... or is this all pure nonsense :) $\endgroup$
    – stats_noob
    Feb 20, 2022 at 5:58

2 Answers 2

7
$\begingroup$

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$;

$\endgroup$
10
  • $\begingroup$ @ worldsmithhelper : I can not thank you enough for your answer! Just some points I wanted to make $\endgroup$
    – stats_noob
    Feb 17, 2022 at 17:02
  • $\begingroup$ 1) Maybe I chose the wrong terms to describe the "function". Let's assume that we have the function that assigns costs, but this function contains several "indicator functions" and is clearly non-differentiable. Does this make the game closer to an optimization problem? (e.g. something like Travelling Salesman but where the costs are non-linear)? $\endgroup$
    – stats_noob
    Feb 17, 2022 at 17:04
  • $\begingroup$ 2) "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." This is a very good point - I imagine this game "hierarchical objectives". As a very loose analogy: $\endgroup$
    – stats_noob
    Feb 17, 2022 at 17:08
  • $\begingroup$ "if two people are on an island, when one person finds food : if he eats all the food he finds instead of sharing the food - he is in a better position compared to the start of the day (e.g. objective is to fill your stomach). But if he shares, he is temporarily in a worse position - but there might be hidden benefits for sharing. For example, if he shares today, it might make the other person more inclined to share when the first person is sick and cant find food - or if the other person becomes weak from not eating, he might not be able to protect the first person from an animal attack $\endgroup$
    – stats_noob
    Feb 17, 2022 at 17:09
  • 2
    $\begingroup$ The cooperation you "hope" for makes no sense in an optimization context. If you use evolutionary pressures your solver is using a different problem then you stated. Framing this as multi-objective problem makes sense, however then you loose any notion of an correct answer and due to the fact the choices of the first player constraint the choices of other players player 1 will (by the definition of pareto frontier) never result in player 1 giving up any of it's objective. $\endgroup$ Feb 18, 2022 at 23:48
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @ Prubin: Thank you so much for your answer! I will check out this link - I am very curious to learn more about "simulation optimization"! $\endgroup$
    – stats_noob
    Feb 17, 2022 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.