There is a class of problems that I noticed comes up again and again in various scenarios. Abstractly, you can formulate it like this: given a time limit, how much time should you spend increasing your production capacity, and then how much time should you use your production capacity to produce utility? Let's take a look at two version of this problem:

Version 1:

You have N days. You start with a production capacity C=0 and accumulated utility U=0. Each day you can either: 1) increase your production capacity (C=C+1) or 2) use your current production capacity to produce utility (U=U+C).

Question: On what days should you increase your production, and on what days should you produce utility to maximize total accumulated utility at the end of the N days?

It's trivial to prove that the optimal solution looks like increasing capacity for T days, and then switching to producing utility for N-T days. What is T? In this case it's really straight-forward to figure it out. We can compute final utility as U(T)=(N-T)*T. The maximum is at T=N/2. So, you should spend the first half increasing your production and the second half producing utility. Interesting...

Version 2:

You have N days. You start with a production capacity C=1 and accumulated utility U=0. Each day you can either: 1) increase your production capacity by a factor F (C=C*F), where F>1 or 2) use your current production capacity to produce utility (U=U+C).

Same question. Now the final utility is U(T)=F^T*(N-T). Doing basic calculus, we find the optimal T=max(0, N-1/ln(F)). A few interesting points you can take a way from this solution:

1) If your growth factor F is not large enough, you might have to stick with your original production capacity of 1 and never increase it. E.g. F=1.01 and N=100, where optimal T=max(0,-0.499171).

2) The bigger the N, the lower growth factor you can accept as being useful, i.e. T>0.

3) For most scenarios, you should spend 80-90% of the time increasing the production. Example. With larger F, T will approach N. This reminds me of Reducing Astronomical Waste post.

 

Questions for you: where have you seen these types of problems come up in your life? Is this a known class of problems?

New Comment
8 comments, sorted by Click to highlight new comments since: Today at 10:54 PM

In real life, increasing your production capacity often costs you money. So you have to use your production capacity to pay for increasing your production capacity.

Then, there is the uncertainty. (You spend 30 years increasing your production capacity, and then a technological change makes your existing capacity obsolete. Or you die in accident.)

Then, there is the problem of realistic human motivation, and of signalling to others. (How would you convince you have a superior production capacity, when I never saw you produce anything?)

Then, there are conflicts and the first-mover advantage. (Your production capacity is conquered by an enemy who decided to produce sooner.)

Some of these may or may not apply in specific scenarios.

You often get those kind of problems when playing strategy games, especially 4X (civ-like) games, with developing your cities/bases vs producing military units. The main difference with your "toy problem" is that in games the N isn't fixed, but probabilistic, which makes it much harder.

I often tend to spend most of the time developing my production capacity (as you said, it's the most efficient thing to do with a fixed N) but sometimes I do it too much and I get caught unprepared by an attack...

Yup, what immediately came to mind when I started reading the post were CMS & 4X games like Hamurabi & Civilization.

I expect the simplest way to handle a probabilistic N is to apply a discount factor to future utility. (It's what the Freeciv AI does.)

Oh, haha, yup! Now I'm anticipating a flood of negative comments on my post as well.

Don't think so. That is not easy to find via google except if you already know it. The same results are often rediscovered independently. This just shows that were smart enough to rediscover it.

Questions for you: where have you seen these types of problems come up in your life? Is this a known class of problems?

The solutions you derived resemble bang-bang solutions in control theory. If you have a control knob you can turn to any value between some minimum and some maximum, a bang-bang solution is an optimal solution which turns the knob all the way in one direction for a while, then turns it all the way in the other direction and leaves it there indefinitely.

Here is one possible domain expert.