Big Balloon Game

The problem

In this game, you are given empty balloons one by one, and for each balloon you are to inflate it with air until you are satisfied. If it does not burst, you gain happiness points proportional to the volume of air in the balloon (say 1 point per ml). If it bursts, you gain nothing. If you attempt to inflate a balloon beyond 1000L, it will certainly burst. The balloons are inexhaustible infinite, and your goal is to maximize your cumulative gain. More precisely, you want to maximize the asymptotic behaviour of $g(n)$ as $n \to \infty$, where $g(n)$ is the cumulative gain after $n$ balloons. All you know about the balloons is that they are all made by the same factory process, and so you can assume that the maximum inflatable size is always drawn from the same fixed distribution with nonzero variance.

$\def\pp{\mathbb{P}}$$\def\ee{\mathbb{E}}$$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$Is there an optimal strategy, defined as a strategy that guarantees $\ee(\lfrac1n g(n)) \to c$ as $n \to \infty$ and also has asymptotically maximum $\lfrac{\ee(\lfrac1n g(n))-c}{\sqrt{Var(X)}}$ where $X$ is the distribution of the balloon’s maximum inflatable size, and $c$ is such that $c \cdot \pp(X \ge c)$ is maximum ($c$ is the optimal inflate size if we knew $X$)?

Partial solution

If we knew $X$, we could easily get an optimal strategy as follows. Simply always inflate to size $c$, which exists by the extreme value theorem because of the balloon size limit (which is one reason I imposed it). I can construct a strategy that guarantees $\lfrac1n g(n) \overset{a.s.}\to c$ as $n \to \infty$: With probability $\lfrac1{n}$ inflate until it bursts, otherwise use previous tries to estimate $c$ and inflate to that estimate. After $n$ tries we have on average roughly $\ln(n)$ samples, and so by CLT our sample distribution’s cdf will eventually converge to that of the correct distribution because it has finite variance (which is the other reason for the balloon size limit), and also we use the estimate with probability approaching $1$. The problem is to find a strategy that gives the fastest convergence (or prove that no optimal strategy exist). I don’t even know the asymptotic behaviour of this strategy that I’ve described.


I made up this generalized game after playing a simple Javascript variant some months ago, but I can no longer find it. Thanks to joriki, this original variant is known as the Balloon Analogue Risk Task (BART), which can be seen as a variant where the distribution is discrete. The strategy I gave above works but can never be asymptotically as good as the strategy that only takes one sample and then always inflates to that size (as pointed out by Keepthesemind).

For each $k > 0$ there is a balloon distribution such that the optimal strategy cannot expect to gain more than $\lfrac1k$ of the actual possible gain (the sum of the maximum inflatable sizes of the balloons). This also means that there is no optimal strategy for the variant of the game where an adversary chooses the maximum inflatable size just before giving you each balloon.

Solutions Collecting From Web of "Big Balloon Game"