2
$\begingroup$

There are $n$ closed boxes and one and only one box of them contains a prize. The $i$-th box has probability $p_i$ of containing a prize. A player must pay $c_i$ coins to open the $i$-th box. The player must open boxes until the prize is found, then the game ends. Find the optimal box opening strategy that minimizes the expected money spent before obtaining the prize.

For example, let there be two boxes: $p_1 = 0.8$, $p_2 = 0.2$, $c_1 = 3$, $c_2 = 2$. There are two possible variants: 1-2 and 2-1 (a player can open box 1 or box 2 first).

Expected value of spent money for 1-2 order is $0.8\times3+0.2\times(3+2)=3.4$ coins.

Expected value of spent money for 2-1 order is $0.2\times2+0.8\times(3+2)=4.4$ coins.

Therefore 1-2 order is better.

Is there an algorithm that solves this problem faster than brute force $O(n!)$? What is the optimal algorithm for solving this task?

$\endgroup$
0
4
$\begingroup$

The algorithm is simple. Just sort the boxes from highest $p/c$ value to lowest. This takes $O(n \log n)$ time.

The proof is a little more complicated.

Consider a box-picking strategy $S$, and number the boxes in the order that strategy $S$ picks boxes. The expected cost of picking boxes in this order is $c_1+(1-p_1)c_2 + (1-p_1-p_2)c_3 + \cdots$. We definitely incur a cost of $c_1$ to open the first box, then we have a $1-p_1$ probability of having to open the second box and pay $c_2$, and a $(1-p_1-p_2)$ probability that the prize wasn't in either of those boxes, and so on.

A necessary (though not obviously sufficient) condition for a strategy to be optimal is that we can't swap the order of two consecutive box picks and get a better strategy. If we compare the expected cost of strategy $S$ and the expected cost of strategy $S_i$, where box $i+1$ is picked before box $i$, we find that these costs differ in only two terms, corresponding to the costs associated with picking boxes $i$ and $i+1$.

For strategy $S$, these terms are $$(1-p_1-p_2-\cdots-p_{i-1})c_i + (1-p_1-p_2-\cdots-p_{i-1}-p_i)c_{i+1}$$

For strategy $S_i$, these terms are $$(1-p_1-p_2-\cdots-p_{i-1})c_{i+1} + (1-p_1-p_2-\cdots-p_{i-1}-p_{i+1})c_i$$

If we eliminate the $(1-p_1-p_2-\cdots-p_{i-1})(c_i+c_{i+1})$ component from both sides, we find that strategy $S_i$ wins if $$-p_ic_{i+1} >-p_{i+1}c_i$$

or equivalently, if $$p_i/c_i<p_{i+1}/c_{i+1}$$

so strategy $S_i$ wins if box $i+1$ has a higher $p/c$ value than box $i$.

For a strategy to be optimal, each box must have a $p/c$ value greater than or equal to the next box in picking order. This can be achieved with a simple sort. If all $p/c$ values are distinct, then there is only one possible outcome of this sort, and the resulting order is the single optimal strategy. If there are duplicate $p/c$ values, then we can order boxes with the same $p/c$ value arbitrarily, since (by a variation of the above logic) shuffling boxes within a group of equal $p/c$ value will not change the expected cost of a strategy.

$\endgroup$
9
  • 1
    $\begingroup$ The way I understood the problem is that the prize is found in a unique box $I$, and $\Pr[I=i]=p_i$. $\endgroup$ Oct 11 at 6:35
  • $\begingroup$ I don't think your expected value calculation is correct. c3 is paid if the prize is not in the first two boxes. This happens with probability (1 - p1 - p2) not with probability (1 - p1)(1 - p2). (1 - p1)(1 - p2) should be used if each box can contain a prize independently of any other boxes, not if one and only one box has the prize. $\endgroup$ Oct 11 at 11:37
  • $\begingroup$ Sorry if "one and only one box has the prize" was not clear from the original wording, I'll change it. $\endgroup$ Oct 11 at 11:43
  • $\begingroup$ I believe, the correct formula for expected value should be $\sum_{i=1}^N (p_i * \sum_{j=1}^i c_j) = \sum_{i=1}^N (c_i * \sum_{j=i}^N p_j) = \sum_{i=1}^N (c_i * (1 - \sum_{j=1}^{i-1} p_j))$ $\endgroup$ Oct 11 at 11:58
  • 1
    $\begingroup$ @VladimirBogachev: The proof in the answer shows that any strategy that does not pick boxes in descending $p/c$ order can be improved by swapping a pair of consecutive boxes. The descending $p/c$ order strategy must be optimal because all the alternatives aren't. $\endgroup$ Oct 11 at 15:04
2
$\begingroup$

There's a simple dynamic programming algorithm which runs in time $O^*(2^n)$. For a set $S$, let $C(S)$ be the cost of opening just the boxes in $S$ in the optimal order. Then $C(\emptyset) = 0$ and for $S \neq \emptyset$, $$ C(S) = \min_{i \in S} \left[ C(S \setminus \{i\}) + p_i \sum_{j \in S} c_j \right]. $$ You are interested in $C(\{1,\ldots,n\})$.

$\endgroup$
1
  • 1
    $\begingroup$ I think you can do better by sorting the boxes by $p/c$. If we plan to open box $j$ immediately after box $i$, and $p_i/c_i<p_j/c_j$, then swapping the boxes reduces the expected cost. $\endgroup$
    – stewbasic
    Oct 11 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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