This week’s Riddler is about a hypothetical gameshow, and knowing when to stop.
You’re on a game show, and you’re asked to sit down at a table covered with sealed envelopes. You are told that each envelope contains a check for an amount of money, each amount different from all the others, but you are given no other information about the distribution of amounts. (As far as you know, the biggest check on the table could be $1.06 or it could be $98,765,432,100.00.) You may pick an envelope, open it and read the amount of the check. You can then either keep that check, ending the game, or toss it away permanently and open another envelope. You can then keep that second check or toss it away and open a third envelope. And then you can keep the third check or throw it away and pick a fourth envelope. But that’s it — if you open a fourth envelope, you have to keep that check, no matter how paltry it is.
What strategy should you follow to maximize your chances of getting a nice payday?
There are probably some ‘real-life’ things you could do at the margins (e.g. if you draw $0, then you know there’s nowhere to go but up; if you draw $10^45, then the gameshow can’t give you that much money and would cause hyperinflation if it did; if you draw $10m then you might not care whether there’s more money in the other envelopes), but I think it’s intended as a more ‘pure’ puzzle, so my solution is a long those lines.
Specifically, let’s assume that (i) we have no information about the distribution the numbers are picked from (not even ‘reality’ constraints), (ii) the order of the numbers in the envelopes is randomized, and (iii) we want to maximize our expected payout, not just our odds of getting ‘enough’.
Let’s call the 4 values a, b, c, and d (in increasing order). There are 4! = 24 possible orderings of the numbers in the envelopes, as illustrated below (from red as a / the lowest to green as d / the highest):
When we open the first envelope, we have no information about the distribution, so our decision has to be independent of the number it shows. If we stick with the first envelope, our expected payout is (a+b+c+d)/4, i.e. we’re equally likely to have any of the 4 values. But if we reject the first envelope, the expected payout for the second is the same, so we can do at least as well by rejecting, and maybe better.
Once we’ve draw 2 envelopes, we have one piece of information, namely which of the first 2 is bigger. If the number in the second envelope is bigger, then we’re in one of the 12 situations below:
If we keep the second envelope, the expected payout is (b+2c+3d)/6. But now, consider the best-case if we reject it, i.e. that we get the higher of the remaining 2 envelopes. If you count them up, you’ll see the number of bs, cs, and ds is the same, so the best-case expected payout is still (b+2c+3d)/6. The actual payout would be worse since, for example, we wouldn’t be able to distinguish between the first two lines based on the information available after opening the 3rd envelope, so we couldn’t reliably get the higher of the two. So, if the second envelope has a higher number than the first, we should keep it.
Now, if the number in the second envelope is lower, we’re in one of these 12 situations:
The expected payout to stick is (3a+2b+c)/6. But by the same logic as above, the *worst-case* outcome if we reject the second envelope (i.e. the lower of the two options left) has the same expected payout. So if the second envelope has a lower number than the first, we should reject it.
So now we open the third envelope, and there are 3 cases to consider: where the third number is higher than the first two, lower than the first two, and in between.
If the third number is higher than the first two (and given that the second was lower than the first), we’re in one of these situations:
We need to choose either the third or the fourth column, and it’s clear that in this case choosing the third is the dominant strategy.
Similarly, if the third number is lower than the first two, rejecting it is clearly the dominant strategy:
Finally, we have the situation where the third number is between the first two. In this case, the expected payout of sticking with the 3rd envelope is (b+c)/2, while the expected payout for rejecting it is (a+b+c+d)/4. So the difference is (a-b-c+d)/4, and without having more information about a, b, c, and d than their order, there’s no way to tell the sign of this, and hence no dominant strategy.
If you do make some assumption about the expected values of a, b, c, and d, then it’s a question of your risk tolerance, to choose between a safer bet in the middle, with no chance of the bigger upside or the bigger downside, or a wider range of outcomes with the last envelope.
Overall, the expected payouts for the two optimal strategies are (a+5b+8c+10d)/24 (if you keep the 3rd envelope in the edge case) and (2a+4b+7c+11d)/24 (if you reject it).
If you only want to maximize the odds of getting the single highest payout, this becomes a special case of the famous Secretary Problem (which has n envelopes instead of 4, but otherwise the same setup).
If you take away the assumption that the order of the envelopes is random, then you get into a much more complex 2-player game, in which the optimal strategy for the chooser would look very different (otherwise, your adversary could always put the top prize in the first envelope, since we always choose to reject that). But since it’s a Friday evening, I’m not going to try to solve that one now!