10
$\begingroup$

You have a ticket allowing you to visit up to $n$ of $M$ carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth can be visited once at most. You can visit the booths in any order but you can only win once, and you have to accept the first reward that you win. The objective is to select the subset of booths to visit, and the order in which to visit them, to maximize the expected reward.

It's easy enough to solve the problem using brute force. The expected value of the reward can be calculated for each permutation of $n$ of $M$ booths.

What would be a more computationally feasible way to formulate the problem?

Improve this question
$\endgroup$
2
  • $\begingroup$ Hi sedge and welcome to OR.SE, I couldn't understand this part: "You can visit the booths in any order but once you win a reward you are finished playing." Can you explain a little more? $\endgroup$
    – Oguz Toragay
    Commented Oct 7, 2019 at 18:08
  • 1
    $\begingroup$ @OguzToragay You can only win once, and you have to accept the first reward that you win. Edited the description to clarify. $\endgroup$
    – sedge
    Commented Oct 7, 2019 at 18:14

2 Answers 2

Reset to default
6
$\begingroup$

As it is explained here, this problem is a portfolio selection problem. The player should select the first $n$ booths with the maximum $E(g_i)=p_i \times r_i$ in which $E(g_i)$ represents the expected value of gain, then among the selected $n$ booths, the player should start playing the games from the one with maximum $r_i$. In other words, the selected booths should be sorted based on their $r_i$ value (from max to min value).

Edit(example):

Consider $M=3, n=2, r_1=100, p_1=0.6, r_2=50, p_2=0.95, r_3=1000, p_3=0.1$ with these data, we have:

$$E(g_1)=60 , E(g_2)=47.5 \ \ \text{and} \ \ \ E(g_3)=100.$$

The sorted list of choices for the player is $\text{list}=(3,1)$.

Also consider that in this type of problem, the solution is related to the amount of risk that the player is willing to take. This relation can be explained as the tradeoff between the risk value and expected total gain.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you describe which algorithm or technique you would suggest for selecting the first $n$ booths with the maximum $E(g_{i})$? There are many listed in the linked presentation. It would be appreciated if you could narrow it down to a good starting point. $\endgroup$
    – sedge
    Commented Oct 7, 2019 at 19:48
  • $\begingroup$ @sedge I edited my answer and included a small example. Please check it again. $\endgroup$
    – Oguz Toragay
    Commented Oct 7, 2019 at 20:06
  • 1
    $\begingroup$ Based on the example I see what you mean now. (Although the variables are switched compared to the OP: $p$ is now the reward and $r$ is the probability). So, would the number of computations needed be only $M$, or $p_{i}$ x $r_{i}$ for each $i\in M$? If so that is very simple indeed. $\endgroup$
    – sedge
    Commented Oct 7, 2019 at 20:21
3
$\begingroup$

To get $O(2^M M^2)$ instead of $O(M!)$, you could modify the dynamic programming formulation of the traveling salesman problem, with a state for each subset of booths visited so far.

Improve this answer
$\endgroup$

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.