I have a problem where we have $n$ boxes, each box $i$ have probability $p_i$ of containing a prize with value $h_i > 0$, and remaining probability of containing nothing. Now we are asked to order the boxes ahead of time, and then open them in that order. Once we reach a box with a prize, we have to take the prize and leave the game. The question is what is the optimal way to order the boxes.

Obviously if there is no restriction on the order, we should order the boxes in decreasing $h_i$. However, we consider the case where some of the boxes are fixed in certain place (for instance box 3 must be ordered in position 4, box 5 must be ordered in position 7), is it still the case that the problem is easy?

What I have so far:

  1. For each "fixed box free" segment of the order, the boxes should be in decreasing $h_i$ by an exchange argument.
  2. When there is only one box $j^*$ that is fixed in position $k^*$, let $f: [n] \rightarrow R$ be a function taking index of boxes to a value such that $f(i) = \frac{(h_i - h_{j^*}) \cdot p_i}{(1 - p_{j^*})p_i + p_{j^*}}$.Let $i_1, i_2$ be index of the boxes in the optimal solution that are immediately before and after the fixed box. Then it must be the case that $f(i_1) \geq f(i_2)$. However it's still not clear that this is easy because conditions 1) and 2) are necessary but not sufficient conditions for the solution to be optimal.

Any suggestions will be greatly appreciated!



Your Answer

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

Browse other questions tagged or ask your own question.