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?
Best Answer
(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.