Thing 18: Build/Produce Toy Model (Part 1)

Okay, so today's thing is more like a blog post in format than an image or interactive thing. Much of this was worked out around a decade ago, but I'm re-working it out as I'm finally getting around to writing it up now.

Basically, I was thinking about a player's progression through building up resources in a board game, and I came up with a toy model that oversimplifies a lot of things (that's what being a toy model is, after all). The model goes like this: imagine a 1-player game where your goal is to maximize your total number of widgets; on every turn, you have a single choice to make between two options: (1) build a widget-factory, or (2) have each widget factory you own produce one widget. The toy model doesn't account for when the game ends. If you know that the game is going to end after some specified number of turns, then it's pretty trivial to solve for the right answer: spend the first half of your turns building and the second half producing. The proof is left as an exercise to the reader.

Now, how do we want to handle the more interesting case where you don't know when the game ends? Well, perhaps the most obvious way is to pick some probability $p$, and say each turn with probability $p$ the game ends. You could pick a specific $p$ or just use $p$ as a variable in your calculations. This isn't what I decided to do. I decided to handle it differently. I decided to make the game infinite instead. My question became: what strategy creates the fastest-growing number of widgets as a function of time? In other words, what sequence of moves gets you the best asymptotic behavior? This is the core question I aim to answer.

Okay, let's start by getting an upper bound. At time/turn $t$, the most widgets you could have by then (as determined above) is to build for the first half and produce for the second half. No real strategy could obviously achieve this for every $t$, but if one could, they would see that at time $t$, they have $\frac{t^2}{4}$ widgets. So that's our upper bound.

Now, let's pick some obvious strategies and see what they gets us, just to get a feel for the problem. Obviously the two trivial strategies of build every turn or produce every turn get us zero widgets. But, we could build once and then produce every turn thereafter. At turn $t$ That gets us $t-1$ widgets. We can do better by building twice and then producing every turn. Or better yet, building $k$ times and then producing every turn. That gets us $kt-k$. Still not great. Not even quadratic.

Let's try the next most obvious thing: diagonalizing. That is, let's alternate build and produce every turn. At turn $t$ (let's just assume $t$ is even for simplicity), we have $\sum_{i=1}^{t/2} i = \frac{\frac{t}{2}(\frac{t}{2}+1)}{2} = \frac{t^2-2t}{8}$. Wow! This is only slightly worse than half of the unattainably optimal upper bound!

(End of part 1. To be continued...)