Explain a surprisingly simple optimization result

The following optimization problem came to my attention as an idealization of the silly browser game Cookie Clicker, but is representative of a range of strategy games:

You have an initial production capacity $p_0$ and a number of improvements $A, B, C, \ldots$ to build in some sequence you can choose. Each improvement $X$ has a cost $c_X$ and will take time to build proportional to its cost and inversely proportional to your capacity. When finished it will increase your production capacity by a given amount $p_X$. You can only build one improvement at a time. Which sequence should you build in in order to get all improvements as quickly as possible?

To get a handle on this I started looking at the case where there are only two improvements $A$ and $B$. The time it will take us to build $A$ first and then $B$ is $\frac{c_A}{p_0} + \frac{c_B}{p_0+p_A}$, and mutatis mutandis for $B$ first. So you should choose to build $A$ first iff $$ \frac{c_A}{p_0} + \frac{c_B}{p_0+p_A} < \frac{c_B}{p_0} + \frac{c_A}{p_0+p_B} $$ After a bit of algebra (assuming the various parameters are positive, etc.) this turns out to be equivalent to $$ \tag{*} \frac{c_A}{p_0} + \frac{c_A}{p_A} < \frac{c_B}{p_0} + \frac{c_B}{p_B} $$ This condition has the nice property that all $A$s are on one side of the inequality and all $B$s are on the other. This hints of a solution for the case with more than two improvements, at least heuristically: Compute $c_X/p_0 + c_X/p_X$ for each improvement and start by building the $X$ with the lowest value. Afterwards, repeat the computation with a new $p_0$.

This question is about is the expression $$\frac{c_X}{p_0} + \frac{c_X}{p_X} = c_X\Bigl(\frac1{p_0}+\frac1{p_X}\Bigr)$$ It is suspiciously simple in light of the maze of algebra that me to it. My question is: Is there an intuitive way to understand that this expression is the right thing to compare?

The $c_X/p_X$ term is easy enough to understand: it is the cost per unit of added productivity we pay for building $X$. But what about $c_X/p_0$?

The effect of $c_X/p_0$ makes qualitative sense: In the limit of $p_0$ small this term dominates over the $c_X/p_X$ terms, and (*) reduces to comparing $c_A<c_B$. In other words when we have very little initial production capacity the important thing is to get something built as quickly as possible, and then the other will take comparatively little time. On the other hand, in the limit of large $p_0$s, the $c_X/p_0$ terms vanishe and we're left comparing $c_A/p_A$ with $c_B/p_B$. Then we should just buy the improvement that gives us most bang for the buck first. That makes intuitive sense too.

But between those two limits, why is $c_X/p_0$ the right adjustment term? What does it represent intuitively?

Solution 1:

(Sigh. Of course simply writing down the question made me think enough about it to see the solution, but not before I'd already posted the question. Move along, nothing to see here).

Somehow it had escaped me that the $\frac{c_A}{p_0}$ term is there in both inequalities. It is simply the time it will take for improvement $A$ to be finished. In the same language $\frac{c_A}{p_A}$ is the time it will take for improvement $A$ to produce enough to pay for its own production cost after it is finished.

That makes perfect intuitive sense.

Solution 2:

I'm not sure whether looking for physical meaning makes much sense here because swapping of A and C in the ABC sequence is governed by a completely different law, which does also depend on the B parameters. An interesting problem, by the way! I have no idea how to do the general case...

An example:

Put $c_1=4/3, p_1=1, p_0=p_2=p_3=c_2=c_3=2$. This gives $c_1(\frac 1{p_0}+\frac 1{p_1})=c_2(\frac 1{p_0}+\frac 1{p_2})=c_3(\frac 1{p_0}+\frac 1{p_3})=2$, which means that no particular choice of the first step has any advantage according to the "heuristic strategy", and if we decrease $c_1$ just a tiny bit, it becomes the choice to make.

However, every order starting with $c_1$ currently gives $\frac 46+\frac 23+\frac 25=\frac{26}{15}=\frac 53+\frac 1{15}$ and every order ending with $c_1$ gives $\frac 22+\frac 24+\frac 4{18}=\frac{31}{18}=\frac 53+\frac 1{18}$, which is strictly shorter time, so it remains shorter under small perturbations.

Solution 3:

After hearing about fedja's counterexample, I ran a quick and dirty program looking for other counterexamples to see if I could find one where the scores were not identical. My first suspicion was that the heuristic was bumping into a weird edge case.

Turns out there are a ton of them. Here is one example:

$$p_0=1$$ $$c_1=3,p_1=2$$ $$c_2=4,p_2=7$$ $$c_3=6,p_3=10$$ $$s_n = c_n\Bigl(\frac1{p_0}+\frac1{p_n}\Bigr)$$

Then: $s_1=4.5, s_2\approx4.57, s_3=6.6$ suggesting you should always start with the first choice. However, picking 1, 2, 3 is worse than picking 2, 3, 1:

$$ t_{123} = \frac{3}{1} + \frac{4}{1+2} + \frac{6}{1+2+7} = \frac{74}{15 } = 4.93... $$

$$ t_{231} = \frac{4}{1} + \frac{6}{1+7} + \frac{3}{1+7+10} = \frac{59}{12 } = 4.916... $$

Even though $t_{12} < t_{21}$ and $t_{13} < t_{31}$, $t_{123} > t_{231}$.