Last week I posted a puzzle that Mohammed Mahdian was spreading around at FOCS. Given n indistinguishable balloons, with capacities 1/k for each integer k between 1 and n, describe a randomized strategy to fill them with as much air as possible, in expectation. Within minutes, someone posted a strategy with expected payoff π²/6. Here is another equivalent strategy:
Set i = 1.
For each balloon in random order:
Try to fill the balloon to 1/i liters.
If the balloon does not pop,
repeat
increment i
until balloon i has not already been popped.
Unlike the straw man I posted last week, this algorithm gets useful information from its failures. When a balloon pops, we learn its capacity, and we know not to look for that balloon in future iterations. It's not hard to see that balloon k (the one with capacity 1/k) survives if and only if it appears last among the k largest balloons, which happens with probability 1/k. So in the limit as n gets big, the expected return is ∑k≥ 1 1/k² = π²/6 ≈ 1.6449 liters.
Despite Danil's posted argument in the comments, this is not the best possible strategy. It might be the best strategy that either completely fills or pops every balloon, but the rules don't require that! Consider the following alternative:
Set i = 1
For each balloon in random order:
Try to fill the balloon to 1/i liters.
If the balloon does not pop,
Increment i
If balloon i has already been popped, break out of the for loop.
Put 1/n liters in each of the remaining empty balloons.
As in my straw-man strategy, balloon k is fully inflated if and only if balloons 1,2,...,k are encountered in that order, which happens with probability 1/k!. Now suppose balloon k is the largest one that does not survive. We have inflated k-1 random balloons, so the expected number of remaining empty balloons is (n-k+1)/k, which means the expected payoff from the last line of the algorithm is (n-k+1)/kn = 1/k - o(1). Let's retroactively put all this air into (the ghost of) balloon k. NOW we get credit for balloon k if and only if balloons 1,2,...,k-1 are encountered in that order, which happens with probability 1/(k-1)!, so our total expected payoff, in the limit, is ∑k≥ 1 1/k! = e - 1 ≈ 1.7183 liters. This is the expected payoff that Mohammed reported at FOCS.
However, even this is not the best possible strategy. UIUC student Dan Cranston had an idea that gives a very small improvement, but since we haven't worked out a full analysis yet, I'll wait a few days before giving away the secret.
You know, this would be a perfect place to apply genetic programming.
Posted by: Bill Tozier | November 08, 2005 at 07:03 PM
Well, there ought to be a marginal improvement, for finite numbers of balloons, by using 1/z instead of 1/n (where z is the smallest unpopped balloon). Somehow I doubt that's the one that you mean.
This algorithm reminds me of the solution for another problem: consider a deck of N cards, each of which has a real number written on it. Reveal the numbers one at a time - the goal is to successfully identify the highest number in the deck when it appears (you have no knowledge of the numbers on the cards until you look at them, and can only choose the most recently turned card). What strategy gives the highest chance of success?
Posted by: Danil | November 08, 2005 at 10:51 PM
Is the card problem like the two-envelopes paradox, where you're not given the distribution the numbers are drawn from?
Posted by: Bob Hearn | November 08, 2005 at 11:24 PM
If I understand the card problem correctly, the following strategy would seem to have a 1/3 chance of success:
Flip over the first N/2 cards, noting the highest in that range. Then keep flipping until you find a higher one. If you do, choose it.
Posted by: Bob Hearn | November 08, 2005 at 11:44 PM
You understand the card problem correctly.
Posted by: Danil | November 09, 2005 at 05:28 AM
OK. And in that family of strategies, it's easy to see that N/2 is the optimal turning point. But is there any other kind of strategy to consider, or is 1/3 provably the best you can do?
Posted by: Bob Hearn | November 09, 2005 at 07:33 AM
Are you allowed to inflate a balloon in stages?
As in to put some air in one, put some air in another one, and then
add some more in the first one?
Posted by: Vladimer | December 01, 2005 at 11:22 PM