Mfcttrf

Front hydraulic disk brake is too powerful on MTB — solutions?

Why is the empennage design of this Lockheed 1049E so complicated?

"A tin of biscuits" vs "A biscuit tin"

A Problem of Succession

XDSL Internet Connection Over Optical Fibre Telephone Line?

How can I learn to write better questions to test for conceptual understanding?

Is Schrodinger's Cat itself an observer?

Why do adjectives come before nouns in English?

Dice? = Is that so?

Which culture used no personal names?

Is it now possible to undetectably cross the Arctic Ocean on ski/kayak?

Who can change WIP limit in DoW when urgent work emerges?

Is there a push, in the United States, to use gender-neutral language and gender pronouns (when they are given)?

Optimal set order to maximize stochastic reward

Should I avoid "big words" when writing to a younger audience?

What‘s wrong with my proof of the Law of Total Variance?

Are Snap and Flatpack apps safe to install? Are they "official", approved or tested for a particular distro version?

Neither Raman nor IR Active vibrational modes

Does my protagonist need to be the most important character?

How to protect my Wi-Fi password from being displayed by Android phones when sharing it with QR code?

Incorrect mmap behavior when assembly files included in the project

Remove last letter 4 times, get a real word each time, starting word is a car model

Usefulness of Nash embedding theorem

Is anyone against the rational teachings of Maimonides?

Optimal set order to maximize stochastic reward

Stochastic programming MIP solversHow to determine the correct level of detail when modelling?Bin Packing with Relational PenalizationFinding an optimal set without forbidden subsetsRunning a linear programming model to maximize binned predictionsHow to modify EMSR when capacity for each fare class is differentStatic stochastic knapsack problem: unbounded versionVariable fixing based on a good feasible solution

5

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

modeling combinatorial-optimization stochastic-programming dynamic-programming

share|improve this question

edited 8 hours ago

TheSimpliFire♦

2,65477 silver badges3939 bronze badges

asked 9 hours ago

sedgesedge

2622 bronze badges

New contributor

sedge is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  9 hours ago
  

  
  
  
  

add a comment
 | 

5

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

modeling combinatorial-optimization stochastic-programming dynamic-programming

share|improve this question

edited 8 hours ago

TheSimpliFire♦

2,65477 silver badges3939 bronze badges

asked 9 hours ago

sedgesedge

2622 bronze badges

New contributor

sedge is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  9 hours ago
  

  
  
  
  

add a comment
 | 

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

modeling combinatorial-optimization stochastic-programming dynamic-programming

share|improve this question

edited 8 hours ago

TheSimpliFire♦

2,65477 silver badges3939 bronze badges

asked 9 hours ago

sedgesedge

2622 bronze badges

New contributor

sedge is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|improve this question

edited 8 hours ago

TheSimpliFire♦

2,65477 silver badges3939 bronze badges

asked 9 hours ago

sedgesedge

2622 bronze badges

New contributor

sedge is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 8 hours ago

TheSimpliFire♦

2,65477 silver badges3939 bronze badges

asked 9 hours ago

sedgesedge

2622 bronze badges

New contributor

sedge is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 8 hours ago

TheSimpliFire♦

2,65477 silver badges3939 bronze badges

edited 8 hours ago

TheSimpliFire♦

2,65477 silver badges3939 bronze badges

asked 9 hours ago

sedgesedge

2622 bronze badges

New contributor

sedge is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 9 hours ago

sedgesedge

2622 bronze badges

2 Answers
2

active

oldest

votes

2

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

share|improve this answer

edited 8 hours ago

answered 8 hours ago

Rob PrattRob Pratt

1,46711 silver badge1212 bronze badges

$endgroup$

add a comment
 | 

2

$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 textand E(g_3)=100$

the sorted list of choices for the player is:

$$list=(3,1)$$

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

share|improve this answer

edited 7 hours ago

answered 8 hours ago

Oguz ToragayOguz Toragay

4,12711 gold badge33 silver badges3030 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @sedge I edited my answer and included a small example. Please check it again.
  $endgroup$
  – Oguz Toragay
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  7 hours ago
  
  

  
  
  
  

add a comment
 | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

sedge is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f2752%2foptimal-set-order-to-maximize-stochastic-reward%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

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

share|improve this answer

edited 8 hours ago

answered 8 hours ago

Rob PrattRob Pratt

1,46711 silver badge1212 bronze badges

$endgroup$

add a comment
 | 

2

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

share|improve this answer

edited 8 hours ago

answered 8 hours ago

Rob PrattRob Pratt

1,46711 silver badge1212 bronze badges

$endgroup$

add a comment
 | 

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

share|improve this answer

edited 8 hours ago

answered 8 hours ago

Rob PrattRob Pratt

1,46711 silver badge1212 bronze badges

$endgroup$

share|improve this answer

edited 8 hours ago

answered 8 hours ago

Rob PrattRob Pratt

1,46711 silver badge1212 bronze badges

answered 8 hours ago

Rob PrattRob Pratt

1,46711 silver badge1212 bronze badges

answered 8 hours ago

Rob PrattRob Pratt

1,46711 silver badge1212 bronze badges

2

$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 textand E(g_3)=100$

the sorted list of choices for the player is:

$$list=(3,1)$$

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

share|improve this answer

edited 7 hours ago

answered 8 hours ago

Oguz ToragayOguz Toragay

4,12711 gold badge33 silver badges3030 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @sedge I edited my answer and included a small example. Please check it again.
  $endgroup$
  – Oguz Toragay
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  7 hours ago
  
  

  
  
  
  

add a comment
 | 

2

$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 textand E(g_3)=100$

the sorted list of choices for the player is:

$$list=(3,1)$$

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

share|improve this answer

edited 7 hours ago

answered 8 hours ago

Oguz ToragayOguz Toragay

4,12711 gold badge33 silver badges3030 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @sedge I edited my answer and included a small example. Please check it again.
  $endgroup$
  – Oguz Toragay
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  7 hours ago
  
  

  
  
  
  

add a comment
 | 

$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 textand E(g_3)=100$

the sorted list of choices for the player is:

$$list=(3,1)$$

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

share|improve this answer

edited 7 hours ago

answered 8 hours ago

Oguz ToragayOguz Toragay

4,12711 gold badge33 silver badges3030 bronze badges

$endgroup$

share|improve this answer

edited 7 hours ago

answered 8 hours ago

Oguz ToragayOguz Toragay

4,12711 gold badge33 silver badges3030 bronze badges

answered 8 hours ago

Oguz ToragayOguz Toragay

4,12711 gold badge33 silver badges3030 bronze badges

answered 8 hours ago

Oguz ToragayOguz Toragay

4,12711 gold badge33 silver badges3030 bronze badges