# Games

You are currently browsing the archive for the Games category.

## Noxious Fumes+ : Certain Death in sqrt(h) turns

This post can also be found in a nicer format at GitHub (LaTex), Github blog format, and Reddit.

There are three great deck builder card games: Dominion, Slay the Spire, and Magic the Gathering. There are four different characters in Slay the Spire. My favorite is the Silent character who often uses poison to defeat the monsters.

One method of attacking with poison in Slay the Spire is to play the “Noxious Fumes+” card. The card self destructs after it is played (it cannot be played again until the you enter the next room in your quest.) Nothing happens on the turn in which it is played. The next turn, the monster experiences 3 damage from the poison. The next turn after that, the monster experiences 5 additional poison damage for a total of 8 poison damage. The next turn after that 7 additional poison damage for a total of 15 poison damage. And so on.

A few weeks ago, I wrote that if you play an ordinary Noxious Fumes card, every opponent monster with h health points or less will be dead in $\sqrt{2 h}$ turns. (See Footnote [1] for details.)

What about the upgraded Noxious Fumes+? Well amazingly, if you play a Noxious Fumes+, then the monster dies in $\sqrt{h}$  turns or less.

In fact, if

• the monster has h health points when the Noxious Fumes+ card is played,

• the monster can’t heal,

• the monster experiences no poison damage on the turn that the Noxious Fumes+ is played,

• it experiences 3 poison damage on the turn after Noxious Fumes+ is played, 5 poison damage on the next turn, 7 on the next, and so on for t=floor($\sqrt{h}$) turns, and

• the monster experiences only poison damage,

then the monster will die exactly

t = floor($\sqrt{h}$)

turns after the Noxious Fumes+ is played.

Notation: floor(x) is the largest whole number less than or equal to x. It is rounded down. For example, floor(3) = 3, floor(4.8) = 4, and floor(π) = 3.

Example 1

Suppose there is a minion that has 8 hit points when the Noxious Fumes+ is played. Suppose that the minion is not healed, it has no poison on the turn that the Noxious Fumes+ is played, and you do not take any other offensive actions against that minion (nor do you play any area of effect cards). Then, that minion will die in exactly

t = floor($\sqrt{8}$) = floor(2.8284) = 2 turns.

One turn after the Noxious Fumes+ is played, it experiences 3 points poison damage, and the following turn it dies with 5 additional points poison damage.

Example 2

Suppose there is a monster that has 25 hit points when the Noxious Fumes+ is played. Suppose that the monster is not healed, it has no poison on the turn that the Noxious Fumes+ is played, and you do not take any other offensive actions against that monster (nor do you play any area of effect cards). Then, that monster will die in exactly

t = floor(√25) = floor(5) = 5 turns.

The total poison damage over the next 4 turns is 3+5+7+9 = 24. On the fifth turn after the Noxious Fumes+ is played, it experiences 11 additional poison damage and dies.

Footnote [1] If the monster can’t heal or avoid poison damage, and it experiences 2 poison damage on the next turn after an ordinary Noxious Fumes is played, 3 poison damage on the next turn, 4 on the next, and so on, then it will be dead within $\sqrt{2 h}$ turns after the Noxious Fumes is played. With a few more calculations, you can get a better, 100% accurate, but more complicated formula for the number of turns to death if all the damage comes from the Noxious Fumes card.

## Noxious Fumes: Certain Death in ceil((-3 + sqrt(8h + 9)) / 2) turns

### Intro

There are three great deck builder card games:  Dominion, Slay the Spire, and Magic the Gathering.  There are four different characters in Slay the Spire.  My favorite is the Silent character who often uses poison to defeat the monsters.

One method of attacking with poison in Slay the Spire is to play the “Noxious Fumes” card.  The card self destructs after it is played (it cannot be played again until the you enter the next room in your quest.)   Nothing happens on the turn in which it is played.  The next turn, the monster experiences 2 damage from the poison.  The next turn after that, the monster experiences 3 additional poison damage for a total of 5 poison damage.  The next turn after that 4 additional poison damage for a total of 9 poison damage.  And so on.

### Time to Death

I love Noxious Fumes. I love that once I play Noxious Fumes, the enemy will die in square root time no matter what he does and no matter what I do. In fact, every monster with $h$ or less health points will be dead in no more than
$$\mathrm{deathTime}=\mathrm{ceil}\left( \left( -3+ \sqrt{ 8h +9}\right)/2\right)$$ turns. [1][2]

Notation: $\mathrm{ceil}(x)$ is defined to be the smallest integer which is greater than or equal to $x$. For example, $\mathrm{ceil}(13) = 13$, $\mathrm{ceil}(3.2) = 4$, and $\mathrm{ceil}(\pi) = 4$.
“ceil” is an abbreviation for “ceiling” and $\mathrm{ceil}(x)$ is $x$ rounded upward.

### Example

Let’s try out the formula. If the monster has 100 health points, then it will be dead in
\begin{aligned} \mathrm{deathTime}&=\mathrm{ceil}\left( \left( -3+ \sqrt{ 8\cdot 100 +9}\right)/2\right) \\ &=\mathrm{ceil}\left( \left( -3+ \sqrt{ 809}\right)/2\right) \\ &=\mathrm{ceil}\left( \left( -3+ 28.44\right)/2\right) \\ &=\mathrm{ceil}\left( 25.44/2\right) \\ &=\mathrm{ceil}\left( 12.72\right) \\ &=13\end{aligned} turns.

• If you play the Noxious Fumes on turn 4, then on turn 4+1=5, the monster will have 2 poison, and 2 total poison damage.
• On turn 4+2=6, the monster will have 3 poison, and 2+3 total poison damage.
• On turn 4+3=7, the monster will have 4 poison, and 2+3+4 total poison damage.
• On turn 4+12=16, the monster will have 13 poison and $2+3+4+\cdots+13= 90$ total poison damage.
• On turn 4+13=17, the monster will have 14 poison and $2+3+4+\cdots+14= 104$ total poison damage and hence will be dead.

### Theorem

Theorem: If a monster has $h$ health points when a Noxious Fumes card is played and that monster has no way to heal or remove the Noxious Fumes, then it will be dead $$\mathrm{deathTime}=\mathrm{ceil}\left( \left( -3+ \sqrt{ 8h +9}\right)/2\right)$$ turns later. [3]

For the few of you who like proofs, here it is.

Proof:
The sum $2+3+4+\ldots+n$ is the sum of $n-1$ numbers whose average value is $\frac{n+2}{2}$, so that sum is
$$2+3+4+\ldots+n = (n-1)\frac{n+2}{2}.$$
For example,
$$2+3+4+5 = (5-1)\cdot (5+2) /2 = (4\cdot 7)/2 = 28/2 = 14.$$

$t$ turns after the Noxious Fumes card is played, the monster will have $t+1$ poison and a total poison damage of
$$\mathrm{totalPoisonDamage} = 2+3+4+\cdots+(t+1)= t (t+3)/2.$$

If the monster had $h$ health points when the Noxious Fumes card was played, then $t$ turns later the monster will be dead if
$$h\leq \mathrm{totalPoisonDamage} = t (t+3)/2.$$
Now let’s try to find the value of $t$ where the left hand side equals the right hand side. The following are equivalent
\begin{aligned} h&= t (t+3)/2 \\ 0&= \frac{t^2}{2} + \frac{3 t}{2} -h. \\ \end{aligned} According to the quadratic formula, the equation above will be satisfied by
\begin{aligned} t &= \frac{ -3/2 \pm \sqrt{(3/2)^2 – 4 (1/2) (-h) } }{2\cdot (1/2)}\\ &= -3/2 \pm \sqrt{9/4 + 2h } \\ &= \frac{-3 \pm \sqrt{9 + 8h }}{2}.\\ \end{aligned}
The solution $t = \frac{-3 – \sqrt{9 + 8h }}{2}$ can be disregarded because it is negative. So,
$$h = t (t+3)/2$$
if $t = \frac{-3 + \sqrt{9 + 8h }}{2}$. The fact that poison damage is always increasing implies that
$$h \leq t (t+3)/2\quad\mathrm{if\ }t\geq \frac{-3 + \sqrt{9 + 8h }}{2}.$$
If $t$ is an integer, then
$$h \leq t (t+3)/2\quad\mathrm{if\ }t\geq \mathrm{ceil}\left( \frac{-3 + \sqrt{9 + 8h }}{2}\right)$$
which implies the monster is dead if
$$t\geq \mathrm{ceil}\left( \frac{-3 + \sqrt{9 + 8h }}{2}\right).$$

### Endnote

That’s it. Watch out for the sequel,

“Noxious Fumes+ : Guaranteed Death in <Spoiler Removed> turns or less”.

### Footnotes

[1] Alright, technically this formula does not work if the monster can heal or if the monster can remove the noxious fumes. The list of monsters that can heal or remove debuffs includes: Centurion/Mystic, Spheric Guardian, Reptomancer, The Collector, the Awakened One, and the Time Eater.}

[2] It’s not too hard to show that $$\left( -3+ \sqrt{ 8h +9}\right)/2 < \sqrt{2 h}.$$  In fact, $$\frac{\left( -3+ \sqrt{ 8h +9}\right)/2}{\sqrt{2 h}} = \frac{1}{\sqrt{\frac{9}{8 h}+1}+\frac{3}{2 \sqrt{2} \sqrt{h}}} < 1.$$

[3] Possibly earlier if there is any other source of damage.

## 1/log(1+1/237) = 237.49964912… ??

I was rather surprised one day when I typed $$1/\log(1+1/237)$$ into a calculator and got 237.4996491…. I just thought it was strange that it was so very close to 237.5 but very slightly less.

I had been trying to find the maximum number of tanks that you can produce in the tank-factory game. You start the game with any number of factories. On each turn, you can either invest in more factories thereby increasing the number of factories by 10% or you can use the turn to produce one tank per turn per factory. The game lasts for $T$ turns with $T>10$. If you build factories for $k$ turns and build tanks for $T-k$ turns, then the total number of tanks produced is $$f(k) = f_0 \; 1.1^k (T-k)$$ where $f_0$ is the starting number of factories.

Perhaps surprisingly, the maximum value of $f(k)$ is attained both at $k=T-10$ and $k=T-11$. Mathematically[1],
$$\max\{ f(k) | k = 1,2, …, T\} = f(T-10) = f(T-11) \approx 3.9\cdot 1.1^T f_0.$$

But, $f(x)$ can also be thought of as a real valued function, so the maximum value of $f(x)$ over positive real numbers $x$ should be about half way between $x=T-10$ and $x=T-11$.
$$\max_{x>0} f(x) \approx f(T-10.5).$$
To find the precise maximum of $f$ over positive real numbers, we find the point on the curve $y=f(x)$ where the tangent line is horizontal (i.e. where the derivative is zero) as follows: (TFAE)
\begin{aligned} f'(x) &= 0 \\f_0 1.1^x \log(1.1) (T-x) – f_0 1.1^x &= 0 \\ \log(1.1) (T-x) -1 &= 0 \\ \log(1.1) (T-x) &= 1 \\ T-x &= 1/\log(1.1) \\ T- 1/\log(1.1) &=x.\end{aligned}
The max of $f(x)$ occurs at $x = T- 1/\log(1.1)$, but before we estimated that the max would occur at $x\approx T – 10.5$, so we can conlude that
$$1/ \log(1+1/10) = 1/\log(1.1) \approx 10.5.$$
Indeed,
$$1/\log(1.1) = 10.492058687….$$

You can use simillar reasoning to conclude that
$$1/\log( 1 + 1/k) \approx k + 1/2$$
for all positive integers $k$.

A more precise bound can be found with Taylor series. If you go through the math you can prove that for all positive real numbers $x$,
$$f(x) = 1/\log(1+1/x) = x + 1/2 – 1/(12 x) + e(x)$$
where $0< e(x) < 1/(24 x^2).$

Footnote:
[1] More generally, if $k$ and $T$ are postive integers, $k<T$, and $$g(k, n, T) = (1+1/k)^n (T-n),$$ then
\begin{aligned} \max\,\{ g(k,n, T)\; |\; n &= 0, 1,2, \ldots, T \} \\ &= g(k, T-k, T) \\&= g(k, T-k-1, T).\end{aligned}

## Getting 4 under par

I really enjoy disc golf.  This year I have done the 9 hole Circleville course in State College Pennsylvania (USA) about 50 times (usually two or three times per outing) and I’ve gotten 3 under par at least three times, but I have never gotten four under par.  I would love to have a decent estimate of the likelihood of getting four under par.  There is a way to estimate this probability with polynomials.

### Two Holes

Suppose that on hole one you have a 30% chance of birdie (one under par and a score of -1) and a 70% chance of getting par (a score of 0).  Suppose that on hole 2, you have a 20% chance of birdie and an 80% chance of par.  What is the probability of each possible outcome after completing the first two holes?

• You might get two birdies which is a total of -2.  The probability of that is 0.3 times 0.2 = 0.06 = 6%.
• You might get a par followed by a birdie for a total of -1.  The probability of that is 0.7 times 0.2 = 0.14 = 14%.
• You might get a birdie followed by a par for a total of -1.  The probability of that is 0.3 times 0.8 = 0.24 = 24%.
• The last possibility is that you get two pars.  The probability of that result is 0.7 times 0.8 = 0.56 = 56%.

(Technical note: we are assuming that the performance on each hole is statistically independent of the performance on the other holes.)

Notice that the probabilities of getting a score -2, -1, or 0, are 6%, 38%, and 56% respectively.  (The 38% comes from adding 14% to 24%).

Perhaps surprisingly, these three probabilities can be calculated with polynomials.  If we expand

$$( 0.3\, x + 0.7) (0.2\, x + 0.8), \quad\mathrm{then\ we\ get\ }$$

\begin{aligned} ( 0.3\, x + 0.7) (0.2\, x + 0.8)&= 0.3 x\, (0.2 \,x + 0.8) + 0.7(0.2\, x + 0.8) \\&= 0.06 \,x^2 + 0.24 \,x + 0. 14\, x + 0.56 \\&= 0.06\, x^2 + 0.38\, x + 0.56. \end{aligned}

### Nine Holes

I can use the same method to estimate the probability of getting four strokes below par on the 9 hole Circlesville course.  Let’s suppose that the probability of getting a birdie on any given hole is given by the table below.  (We will also optimistically assume that you always get par or a birdie on every hole.)

$$\begin{array}{cc} \text{Hole} & \text{Birdie Probability} \\ \hline 1 & 0.04 \\ \hline 2 & 0.1 \\ 3 & 0.03 \\ 4 & 0.4 \\ 5 & 0.25 \\ 6 & 0.12 \\ 7 & 0 \\ 8 & 0 \\ 9 & 0.3 \\ \end{array}$$

Now the corresponding polynomial is

\begin{aligned}p(x) = &(0.96 + 0.04 x) (0.9 + 0.1 x) (0.97 + 0.03 x) (0.6 + 0.4 x)\\ &\quad\times (0.75 + 0.25 x) (0.88 + 0.12 x)(0.7 + 0.3 x) .\end{aligned}

We can use Wolfram Alpha to expand $p(x)$ thusly

\begin{aligned} p(x) = 0.2323& + 0.4062 x + 0.2654 x^2 + 0.0823 x^3 + 0.0128 x^4 \\ +&0.00098 x^5 +0.000034344 x^6 + 4.32\cdot\, 10^{-7} x^7 \end{aligned}

We can conclude that my most likely result is 1 under par (40.6%) and the probability that I will get exactly 4 under par over 9 holes is about 1.28%.

• the cost of increasing the interest rate is \$1,100, •$r_1=0.05=5\%$, and •$r_2=0.08=8\%, then \begin{aligned}\mathrm{interest\ income\ during\ purchase} &= \frac{c \;r_1 r_2 }{r_2-r_1}\\&= \frac{ \1100\cdot 0.05 \cdot 0.08}{0.08-0.05}\\&= \frac{ \55 \cdot 0.08}{0.03} \approx \146.67\mathrm{\ per\ year.}\end{aligned} ### REMARK Note that the interest income can also be expressed by \label{eqone} \mathrm{interest\ income\ during\ purchase} = c/t_{\mathrm{pay}} where \label{eqtwo} t_\mathrm{pay} = \frac1{r_1} – \frac1{r_2}= \frac{c}{B_0 r_1 \exp(r_1 t_\mathrm{buy})} is the amount of time it takes to payc$dollars from interest starting at the optimal time$t_\mathrm{buy}$. For the previous example, we get $$t_\mathrm{pay} = \frac1{r_1} – \frac1{r_2} = \frac1{0.05} – \frac1{0.08} = 20 – 12.5 = 7.5\mathrm{\ years,\ and}$$ $$\mathrm{interest\ income\ during\ purchase} = c/t_{\mathrm{pay}}= 1100/7.5 \approx \146.67/\mathrm{year}.$$ ### Recovery Time If you do purchase the interest rate hike at the optimal time, how many years will you need to wait until the optimal strategy surpasses the never buy strategy. The recovery time for the second banker’s problem is almost, but not quite the same as the first banker’s problem. For the second banker’s problem, $$t_{\mathrm{surpass}} = t_{buy} + 1/r_1.$$ For the example, $$t_{\mathrm{surpass}} \approx 21.5228+ \frac{1}{0.05} = 41.5228.$$ The black line shows the results of buying the interest rate increase at the optimal time. The blue line shows what happens if you never buy the interest rate hike and just continue to get 5% interest. If you buy the interest rate hike at the optimal time, then you will maximize the account balance at all times$t>1/r_1$years later. (Mathematically, for every$t> t_{\mathrm{buy}} + 1/r_1$, the strategy of purchasing the interest rate upgrade at time$t_{\mathrm{buy}}$results in an account balance at time$t$that exceeds the account balance at time$t$using any other strategy.) ## The Second Banker’s Problem – Part 1 Consider the following game. You have a bank account that is compounded continuously with an interest rate of$r_1$. Your banker offers you the following deal. At any time in the future, you can pay$c$dollars using only the interest from the account to increase your interest rate to$r_2$. If your balance is$b$at the time of the upgrade, then your balance will remain at$b$for$c/(r_1 b)$years which is the time required to pay$c$dollars from interest alone. Other than paying for the interest upgrade, you can never add or subtract any money until retirement which is very far in the future. When should you accept the banker’s offer? Let’s call this game “the second banker’s problem”. (We assume that$c, r_1,$and$r_2$are positive real numbers and$1>r_2> r_1>0$.) (This game is similar to purchasing a growth technology in the game Master of Orion (Original 1993 version). For example, if you buy the “Improved Industrial Tech 9″ technology early in the game, the cost of factories is reduced for the remainder of the game. Reducing the cost of factories increases your economy’s growth rate.) (All proofs for the second banker’s problem can be found in this PDF.) For the first banker’s problem, the balance in the account is immediately reduced by$c$dollars and the interest rate is immediately increased to$r_2$. See this blog post or this PDF for an analysis of the first banker’s problem. The third banker’s problem allows the saver to buy two separate interest rate increases. For the second banker’s problem, you might be tempted to say that you should buy the interest rate increase as early as possible, but that might be bad if$c/(r_1 b)$is a large number of years. On the other hand, there is no reason to buy the interest rate upgrade if the time to retirement is less than$c/(r_1 b)$years. ### Optimal Purchase Time Perhaps surprisingly, the optimal time to purchase the interest rate hike is the same for the first and the second banker’s problems. For either problem, you should take the deal at time $$t_{\mathrm{buy}}=\frac{1}{r_1}\ln\left(\frac{c \; r_2 }{B_0(r_2-r_1)}\right)$$ where$B_0$is the amount of money in the account at time zero, and$\ln(x)$is the natural log. $$\ln(x) = \frac{\log_{10}(x)}{\log_{10}(e)}.$$ I was a bit surprised to find that the optimal purchase time$t_{\mathrm{buy}}$for the second banker’s problem is the same as the optimal purchase time for the first banker’s problem. The amount of money in the account at the optimal purchase time is $$b_{\mathrm{opt}} = \frac{c \; r_2 }{r_2-r_1}.$$ ### Example For example, if • you initially have \$1000 in the account,
• the cost of increasing the interest rate is \$1,100, •$r_1=0.05=5\%$, and •$r_2=0.08=8\%, then the the correct time to buy the interest rate increase is \begin{aligned} t_{\mathrm{buy}}&=\frac{1}{r_1}\ln\left(\frac{c \; r_2 }{B_0(r_2-r_1)}\right)\\ &=\frac{1}{0.05}\ln\left(\frac{1100\cdot 0.08 }{1000(0.08-0.05)}\right)\\ &=\frac{1}{0.05}\ln\left(\frac{88 }{1000(0.03)}\right)\\ &=20\ln\left(\frac{88 }{30}\right)\\ &\approx21.5228\ \mathrm{years.} \end{aligned} In the diagram above, the black line shows the results of paying \1,100 from interest starting at year 21.5228, the optimal time to start paying for the interest rate upgrade. The orange line shows what happens if the player does not invest before year 50. The yellow line shows the result if she or he starts paying for the investment on year 5.

## First Banker’s Problem Part 2 – Income at Purchase and Recovery Time

In part 1, we described the “first banker’s problem” where you can pay a banker to increase your interest rate from $r_1$ to $r_2$ by removing $c$ dollars from your account.  The optimal time to purchase the rate increase is when you have

\mathrm{balanceBefore} =\frac{c \; r_2 }{r_2-r_1}

dollars in your account.  (All of the formulas and theorems about the first banker’s problem as well as Python simulation code for the first banker’s problem and proofs can be found in this PDF.)

### Interest Income immediately before the optimal purchase time

When compounding continuously, the amount of interest that you are earning at any time is the balance at that time times $r_1$.  The amount of interest income just before the optimal purchase time is

$$\mathrm{interst\ income\ immediately\ before\ purchase} = r_1\cdot \mathrm{balanceBefore} = \;\frac{r_1 r_2 c}{r_2-r_1}.$$

### example

If

• you initially have \$1000 in the account, • the cost of increasing the interest rate is \$1,100,
• $r_1=0.05=5\%$, and
• $r_2=0.08=8\%$,

then
\begin{aligned} \mathrm{income\ immediately\ before\ purchase} &= \frac{c \;r_1 r_2 }{r_2-r_1}\\ &= \frac{ \1100\cdot 0.05 \cdot 0.08}{0.08-0.05}\\ &= \frac{ \55 \cdot 0.08}{0.03} \approx \146.67\mathrm{\ per\ year.} \end{aligned}

### Recovery Time

If you do purchase the interest rate hike at the optimal time, how many years will you need to wait until the optimal strategy surpasses the never buy strategy? The answer is you will have to wait approximately $1/m$ years after the purchase where $m$ is the average of $r_1$ and $r_2$.  The exact time when the optimal strategy surpasses the never buy strategy is

$$t_{\mathrm{surpass}} = t_{buy} + \frac{ \ln(r_2) – \ln(r_1)}{r_2-r_1}.$$where $$t_{\mathrm{buy}}=\frac{1}{r_1}\ln\left(\frac{c \; r_2 }{B_0(r_2-r_1)}\right)$$

and $B_0$ is the amount in the account at time 0.  (Bounds for the expression $(\ln(r_2) – \ln(r_1) )/ (r_2 – r_1)$ can be found here.)

For the previous example,

$$t_{\mathrm{surpass}} \approx 21.5228+ \frac{ \ln(0.08) – \ln(0.05)}{0.08-0.05} \approx 37.1868.$$

The black line shows the results of buying the interest rate at the optimal time. The blue line shows what happens if you never buy the interest rate hike and just continue to get 5% interest.

The number of years needed to catch up is between $1/r_2$ years and $1/r_1$ years. GPT wrote a nice proof of this fact.

If you buy the interest rate hike at the optimal time, then you will maximize the account balance at all times $t>1/r_1$ years later. (Mathematically, for every $t> t_{\mathrm{buy}} + 1/r_1$, the strategy of purchasing the interest rate upgrade at time $t_{\mathrm{buy}}$ results in an account balance at time $t$ that exceeds the account balance at time $t$ using any other strategy.

## The First Banker’s Problem Part 1 – The optimal time to buy

In the game Master of Orion and some related games, it is possible to purchase technologies that increase the rate of growth of your empire.  I wanted to simplify this idea enough to get clean mathematical solutions.  I call the resulting three simplified games the first, second, and third banker’s problems.

1. In the first banker’s problem, the saver is offered a deal where they can buy an interest rate upgrade for a fixed amount of money paid from the account balance at any time specified by the saver.
2. The second banker’s problem is the same as the first, except that the payment for the interest upgrade comes solely from account interest.
3. For the third banker’s problem the saver can, at any time, upgrade from interest rate $r_1$ to interest rate $r_2$ for $c_1$ dollars and upgrade from $r_2$ to $r_3$ for $c_2$ dollars, or upgrade directly from interest rate $r_1$ to interest rate $r_3$ for $c_2$ dollars where $r_1<r_2<r_3$ and $c_1<c_2$.

This post will state the formula for computing the optimal time to buy the interest rate upgrade for the first banker’s problem, compute the optimal time to buy for one example, and show the results of buying at non-optimal times.

All of the formulas and theorems about the first banker’s problem as well as Python simulation code for the first banker’s problem and proofs can be found in this PDF.

### the first banker’s problem

Consider the following game. You have a bank account that is compounded continuously with an interest rate of $r_1$. Your banker offers you the following deal. At any time in the future, if your account balance is greater than $c$ dollars, you can pay $c$ dollars from the account to increase your interest rate to $r_2$. You can only use the funds in the account to pay for this interest rate increase and you can never add or subtract any money until retirement which is very far in the future. When should you accept the banker’s offer?  (We assume that $c, r_1,$ and $r_2$ are positive real numbers and $1>r_2> r_1>0$.)

At first you might be tempted to say that you should buy the interest rate increase as early as possible, but it turns out that that is a bad idea. If you have exactly $c$ dollars in the account and you buy the rate increase, then you will have zero dollars in the account and you are stuck with zero dollars in the account until you retire. Similarly, if you have $c+\$0.01$in the account and you buy the interest rate increase, then you will only have one cent in the account after the purchase, and it will take a long time to grow that one cent into a large amount of money. On the other hand, it is probably wrong to wait until the last microsecond before you retire to buy an interest rate increase because the increased amount of interest that you receive is unlikely to be larger than the cost$c$. The answer to the first banker’s problem is that you should take the deal at time t_{\mathrm{buy}}=\frac{1}{r_1}\ln\left(\frac{c \; r_2 }{B_0(r_2-r_1)}\right) where$B_0$is the amount of money in the account at time zero, and$\ln(x)$is the natural log. $$\ln(x) = \frac{\log_{10}(x)}{\log_{10}(e)}.$$ At that time the balance before the purchase will be \mathrm{balanceBefore} =\frac{c \; r_2 }{r_2-r_1}, and the balance immediately after purchasing the interest upgrade will be \mathrm{balanceAfter} =\frac{c \; r_1 }{r_2-r_1}. ### Example For example, if • you initially have \$1000 in the account,
• the cost of increasing the interest rate is \$1,100, •$r_1=0.05=5\%$, and •$r_2=0.08=8\%, then the the correct time to buy the interest rate increase is \begin{aligned} t_{\mathrm{buy}}&=\frac{1}{r_1}\ln\left(\frac{c \; r_2 }{B_0(r_2-r_1)}\right)\\ &=\frac{1}{0.05}\ln\left(\frac{1100\cdot 0.08 }{1000(0.08-0.05)}\right)\\ &=\frac{1}{0.05}\ln\left(\frac{88 }{1000(0.03)}\right)\\ &=20\ln\left(\frac{88 }{30}\right)\\ &\approx21.5228\ \mathrm{years} \end{aligned}and the account balance before making the payment at the optimal time would be \begin{aligned}\mathrm{balanceBefore} &=\frac{c \; r_2 }{r_2-r_1}\\&=\frac{1100 \cdot 0.08 }{0.08-0.05}\\&=\frac{88 }{0.03}\\&\approx \2933.33.\end{aligned} The diagram below shows what happens if you buy the interest upgrade at various times. The purchases are represented as a black vertical dashed lines. The solid black line shows the results of paying \1,100 at year 21.5228, the optimal time to invest. The red line shows what happens if the player does not invest before year 50. The yellow line shows the result if she or he invests on year 5.

## Master of Orion and the Lambert W function

The game Master of Orion, first released in 1995 by Microprose, entails settling the galaxy planet by planet.  To settle a planet, the player must construct a colony ship on one of her/his planets, send that ship to a new, unoccupied habitable planet, land the ship, and then send colonists from some of their planets to the new planet.  Early in the game,

• it costs about 550 MC to build the colony ship,
• it takes around 5 turns for the colony ship to reach a new planet,
• it takes and additional 5 turns for additional colonists to arrive on the planet on separate (free) transport ships,
• it takes around 20 turns for the planet to build new factories before it can build new colony ships, and
• the new planet might generate 110 MC per turn of income to build more ships,

so 30 turns after investing 550 MC, the player’s income increases by about 110 MC per turn.

If we try to create a differential equation to model the early stage of the game, we get something like

$$y'(t) = \frac{110}{550} y(t-30) = \frac{1}{5}y(t-30)$$

where $y(t)$ is the income available for building ships on turn $t$. This differential equation has a solution of the form $$y(t) = c \exp(\alpha t).$$ We can compute the derivative and substitute into the differential equation to find $\alpha$.

$$y'(t) = c\alpha \exp(\alpha t).$$

So,
\begin{aligned} c\alpha \exp(\alpha t) &= y'(t) =\frac{1}{5} y(t-30)\\c\alpha \exp(\alpha t) &=\frac{1}{5}c \exp(\alpha(t-30)) \\\alpha &=\frac{1}{5} \exp(-30 \alpha) \\\alpha \exp(30 \alpha) &=\frac{1}{5}\\30 \alpha \exp(30 \alpha) &= 6 \end{aligned}
According to the definition of the Lambert W function $W_0(x)$ for $x>0$,
$$W_0(z) = x$$
if and only if
$$x\exp(x) = z.$$
Setting $x=30\alpha$ above gives
\begin{aligned}W_0(6) &= 30\alpha\\ W_0(6)/30 &=\alpha\\ \alpha &= W_0(6)/30\approx 0.0477468.\end{aligned}
So the the economy at the start of the Master of Orion gain should grow by about 5% per year.

More generally, if

– the time between the investment in the colony ship and the maturing of the colonized planet is $T$,
– the cost of the ship is $C$,
– and the mature planets produces $i$ income per turn,
then the income on turn $t$ can be approximated by $$y(t) = y(0) \exp(\alpha t)$$ where
$$\alpha = \frac{W_0\left(\frac{i T}{C}\right)}{T}.$$

(Thanks to stackedit.io for helping me format the TeX.)

« Older entries