calculus - Book Proofs

The war game

This Riddler puzzle is about game theory… War or peace?

Two countries are eyeing each other’s gold. At the beginning of the game, the “strength” of each country’s army is drawn from a continuous uniform distribution and lies somewhere between 0 (very weak) and 1 (very strong). Each country knows its own strength but not that of its opponent. The countries observe their own strength and then simultaneously announce “peace” or “war.”

If both announce “peace,” then they each stay quietly in their own territory, with their own gold, which is worth \$1 trillion (so each “wins” \$1 trillion). If at least one announces “war,” then they go to war, and the country with the stronger army wins the other’s gold. (That is, the stronger country wins \$2 trillion, and the other wins \$0.)

What is the optimal strategy of each country (declaring “peace” or “war”) given its strength?

Extra credit: What if the countries don’t announce at the same time and instead one announces first and the other second? What if the value of winning the war were \$5 trillion rather than \$2 trillion?

Here is my solution for the first part, where both countries declare their intentions simultaneously.
[Show Solution]

Pure, mixed, and threshold strategies

This problem describes what is known as a Bayesian game. Each country must make a decision based only on the strength of its army, which is a random variable. One country’s decision rule might look something like this: “If my army has a strength less than $a$, then declare peace. Otherwise, declare war”. This is a “threshold strategy” where the threshold value $a$ determines how likely the country is to go to war. The threshold strategy is an example of a pure strategy because the country behaves the same way every time it sees the same army strength. A more general strategy would be a mixed strategy, where the country decides on a probability of going to war that depends on the observed army strength.

Although neither country gets to know the other country’s strategy, we can still ask the question: suppose country A knows country B’s strategy, what would country A’s best response be? Similarly, we can ask what country B’s best response would be if they knew country A’s strategy. Suppose country A uses strategy $f_A$ and country B uses strategy $f_B$. If the best response to strategy $f_A$ is $f_B$ and the best response to strategy $f_B$ is $f_A$, then we have what is known as a Nash equilibrium. This means that neither country has an incentive to alter its strategy. This is what it means to have an optimal strategy.

Threshold strategies are optimal

Let’s look for a Nash equilibrium for this game. Define the following:

$x$ is the strength of the first country’s army. We’ll assume a mixed strategy defined by the function $p(x)$, which is the probability that the country declares peace given that its army has strength $x$.
$y$ is the strength of the second country’s army. We’ll assume a mixed strategy defined by the function $q(y)$, which is the probability that the country declares peace given that its army has strength $y$.
For the payoffs, we’ll assume mutual peace results in no change, while war results in $+W$ for the winner and $-L$ for the loser.

Given the above, the first country can expect to win:
\[
J_1 = \int_0^1 \int_0^1 (1-p(x)q(y))\, \text{war}(x-y)\, dy\,dx
\]where we defined:
\[
\text{war}(t) = \begin{cases}
+W&\text{if }t \ge 0\\
-L&\text{if }t < 0 \end{cases} \]This follows because the probability of going to war is $(1-p(x)q(y))$, i.e. 1 minus the probability that both countries declare peace. Let's now ask ourselves what happens if we fix $q$ (the second country's strategy) and try to find $p$ in order to maximize $J_1$. Expanding, we obtain: \begin{align} J_1 &= \int_0^1 \int_0^1 (1 - p(x) q(y))\, \text{war}(x-y)\, dy\,dx \\ &= \tfrac{W-L}{2}-\int_0^1 p(x) \int_0^1 q(y)\, \text{war}(x-y)\, dy\,dx \\ &= \tfrac{W-L}{2}-\int_0^1 p(x) \left( W\!\int_0^x q(y)\,dy-L\!\int_x^1 q(y)\,dy\right) dx \end{align}Inspecting the quantity in brackets, we notice that it is a nondecreasing function of $x$. When $x=0$, it's equal to $-L\!\int_0^1 q(y)dy$ and when $x=1$, it's equal to $W\!\int_0^1q(y)dy$. Therefore there is some value $x=a$ where the bracketed quantity is zero. In order to maximize $J_1$, we should set: \[ p(x) = \begin{cases} 1 & \text{if }x < a \\ 0 & \text{otherwise} \end{cases} \]In other words, the first country should use a threshold policy no matter what the second country’s policy is! By symmetry, the same argument holds if we fix the first country’s policy and optimize the second country’s policy; both countries should always use threshold policies.

The solution is war!

We have established that both countries should use threshold strategies. So let’s suppose the second country uses the threshold $b$. What threshold should the first country use? We can compute this by solving the following equation for $a$:
\[
W\!\int_0^a q(y)\,dy = L\!\int_a^1 q(y)\,dy
\]Substituting the threshold policy for $q(y)$, we deduce that $a \le b$, since we must have a positive quantity on both sides of the equality. The result is that $a W = (b-a) L$. In other words:
\[
a = \left( \tfrac{L}{W+L} \right) b
\]So if $L=W=1$, the optimal threshold for the first country is half the optimal threshold for the second country. In fact, no matter what $L$ and $W$ are, the first country’s optimal strategy is to set a threshold that is smaller than the threshold of the other country. The exact same argument holds if we reverse the roles of the countries and we fix the first country’s strategy instead. We therefore conclude that each country’s best response is to continually lower its threshold. The only way to achieve a (Nash) equilibrium is if both countries set their thresholds at zero. Put another way, both countries should always declare war.

Here is my solution for the second part, where the countries declare their intentions sequentially.
[Show Solution]

If the countries declare their intentions sequentially, the second country gets to see the first country’s declaration before making its own, so it may use this information in its decision-making process. We can solve this version of the problem similarly to how we solved the first version, by looking for a Nash equilibrium.

Threshold strategies are still optimal

Again, we assume the first country uses a mixed strategy $p(x)$. In principle, the second country can have two different strategies depending on what the first country declares, but if the first country declares war then nothing can be done to prevent war. So let $q(y)$ be the second country’s strategy when the first country declares peace.

The first country’s expected profit is the same as it was before, namely:
\[
J_1 = \int_0^1 \int_0^1 (1 – p(x) q(y))\, \text{war}(x-y)\, dy\,dx
\]Therefore we can draw the same conclusion as before: the first country should use a threshold strategy. The second country’s expected profit is different, since we must now condition on the first country declaring peace. This time, the probability of war is only $(1-q(y))$, and the density function of $x$ conditioned on the first country declaring peace is given by Bayes’ theorem:
\[
\mathbb{P}(x\,|\,\text{peace}) = \frac{\mathbb{P}(\text{peace}\,|\,x) \mathbb{P}(x) }{\int_0^1 \mathbb{P}(\text{peace}\,|\,x) \mathbb{P}(x) dx}
= \frac{p(x)}{\int_0^1 p(x) dx}
\]The expected profit for the second country is therefore:
\[
J_2 = \frac{\int_0^1 \int_0^1 (1 – q(y))\, \text{war}(y-x) p(x) \, dx\,dy}{\int_0^1 p(x)dx}
\]It’s not difficult to see that $J_2$ has the same optimal $q$ as it did before. Once again, a threshold strategy is optimal, and the threshold is the same as before.

War is always the answer?

Since both countries use the same threshold strategies as in the original problem, the Nash equilibrium is the same; the first country should always declare war. Therefore, it doesn’t matter what the second country does; war is inevitable. This result is somewhat paradoxical because if the first country should always declare war, then what happens if it declares peace? The second country will be thoroughly confused!

Baking the optimal cake

This Riddler puzzle asks about finding the maximum-volume shape subject to constraints.

A mathematician who has a birthday coming up asks his students to make him a cake. He is very particular and asks his students to make him a three-layer cake that fits under a hollow glass cone he has on his desk. He requires that the cake fill up the maximum amount of volume under the cone as possible and that the layers of the cake have straight vertical sides. What are the thicknesses of the three layers of the cake in terms of the height of the glass cone? What percentage of the cone’s volume does the cake fill?

Here is my solution.
[Show Solution]

Although one could write a formula for the total volume of the cake as a function of each layer height, this turns out to be impractical if there are many layers. A better approach is to use dynamic programming. The key lies in realizing that if you have an optimal cake with $k+1$ layers and you remove the bottom layer, you’ll be left with an optimal cake with $k$ layers.

Let’s define $v_k$ to be the fraction of the total cone volume taken up by a cake with $k$ layers. We can write that:
\[
v_{k+1} = \frac{(\text{bottom layer vol.}) + v_{k}\cdot(\text{cone vol. above bottom layer})}{(\text{total cone volume})}
\]Suppose the total cone has a height $h$ and base radius $r$, and the bottom layer occupies a fraction $\lambda$ of the total height $h$. The cone above the bottom layer therefore has a height of $(1-\lambda)h$ and a base radius of $(1-\lambda)r$. This base radius is also the radius of the cylinder that forms the bottom layer.

We must choose $\lambda$ so that the right-hand side is maximized. Substituting the formulas for the volume of a cone and cylinder, we obtain:
\begin{align}
v_{k+1} &= \max_\lambda \,\frac{\pi (1-\lambda)^2 r^2 \lambda h + v_{k}\cdot \tfrac{1}{3} \pi(1-\lambda)^2 r^2 (1-\lambda) h }{\tfrac{1}{3}\pi r^2 h}\\
&= \max_\lambda \,\left( 3\lambda(1-\lambda)^2 + v_{k}(1-\lambda)^3 \right)
\end{align}This expression is maximized when $\lambda=\tfrac{1-v_k}{3-v_k}$ and the maximum value is $\tfrac{4}{(3-v_k)^2}$. So the max volume fraction satisfies
\[
v_{k+1} = \frac{4}{(3-v_k)^2},\qquad\text{with }v_0=0
\]and the fraction of the total height taken up by the bottom layer is:
\[
\lambda_{k+1} = \frac{1-v_k}{3-v_k}
\]

Three layers

For example, if the cake has three layers, we can use the recursion to find:
\begin{align}
v_1 &= \tfrac{4}{9} & v_2 &= \tfrac{324}{529} & v_3 &= \tfrac{1119364}{1595169} & v_4 &= \dots\\
\lambda_1 &= \tfrac{1}{3} & \lambda_2 &= \tfrac{5}{23} & \lambda_3 &= \tfrac{205}{1263} & \lambda_4 &= \dots
\end{align}We can then build the layers from bottom to top. If the cake is $1$ unit tall, the bottom layer takes up a fraction $\lambda_3$ of the total height, or $\tfrac{205}{1263}$. Out of the remaining $\tfrac{1058}{1263}$, the next layer takes up a fraction $\lambda_2$, which is $\tfrac{230}{1263}$. So far, the two bottom layers have taken up $\tfrac{435}{1263}$. Finally, out of the remaining $\tfrac{828}{1263}$, the top layer takes a fraction $\lambda_1$, which is $\tfrac{276}{1263}$. So in all, the layers (from bottom to top) have heights:

$\displaystyle
h_3 = \tfrac{205}{1263} \approx 0.1623,\quad
h_2 = \tfrac{230}{1263} \approx 0.1821,\quad
h_1 = \tfrac{276}{1263} \approx 0.2185
$

and this fills a fraction $v_3 = \tfrac{1119364}{1595169} \approx 0.7017$ of the volume of the cone.

In general, volume ratios $v_k$ and layer heights $h_k$ are given by:
\begin{align}
v_{k+1} &= \frac{4}{(3-v_k)^2}, & & \text{(go forward from }v_0=0\text{)}\\
\lambda_{k+1} &= \frac{1-v_k}{3-v_k} & & \\
h_{k-1} &= \lambda_{k-1}(\lambda_k^{-1} – 1) h_k, & & \text{(go backward from }h_N=\lambda_N h\text{)}
\end{align}The recursion for $v_k$ is nonlinear and likely does not have a nice closed-form expression. However, it’s easy to compute its value for large $k$ by simply iterating. Here is a plot that goes up to $k=30$.

Here is an animation showing how the cake looks as we add more layers.

Note that the top layer is always $\tfrac{1}{3}$ the height of the remaining cone since $\lambda_1 = \tfrac{1}{3}$.

Here, I go into more detail about bounding the optimal cake volume as the number of layers becomes large.
[Show Solution]

Can you outrun the angry ram?

The Riddler puzzle this week appears simple at first glance, but I promise you it’s not!

You, a hard-driving sheep farmer, are tucked into the southeast corner of your square, fenced-in sheep paddock. There are two gates equidistant from you: one at the southwest corner and one at the northeast corner. An angry, recalcitrant ram enters the paddock from the southwest gate and charges directly at you at a constant speed. You run — obviously! — at a constant speed along the eastern fence toward the northeast gate in an attempt to escape. The ram keeps charging, always directly at you.

How much faster than you does the ram have to run so that he catches you just as you reach the gate?

Here is a very simple solution by Hector Pefo. Minimal calculus required!
[Show Solution]

Suppose the southeast corner where the farmer starts is at $(1,0)$, and the farmer moves north with unit speed. So the farmer’s position at time $t$ is $(1,t)$. Meanwhile, suppose the ram moves with speed $v$. We’d like to find $v$ such that the ram and farmer both reach the northeast gate $(1,1)$ at $t=1$. If the ram starts in the southwest corner $(0,0)$, it turns out $v$ is precisely the Golden Ratio, or roughly 1.618. Suppose from now on that the ram starts at $(a,b)$ instead. We’ll derive a formula for $v$ in terms of $a$ and $b$. See below for a diagram.

ram_diagram2
Suppose the path of the ram at time $t$ makes an angle $\alpha(t)$ with the path of the farmer. First, note that the total $y$-distance covered by the ram must be $1-b$. But we can also find this by projecting the path of the ram onto the $y$-axis. In other words:
\[
1-b = \int_0^1 v\,\cos\alpha(t)\,dt
\]Second, change reference frame so we imagine the ram moving in a straight line, always with the farmer in its sights. One component of the farmer’s motion contributes to shrinking his distance to the ram, while the other doesn’t affect the distance. The total distance traveled by the farmer in the direction of the ram can be found by projecting the farmer’s (now curved) path onto the ram’s path. The difference in the ram’s distance $v$ and the projected distance covered by the farmer is equal to the initial distance separating them since they ultimately reach the same spot:
\[
\sqrt{(1-a)^2+b^2} = v-\int_0^1\cos\alpha(t)\,dt
\]Even though we don’t know $\alpha(t)$, we can substitute one equation into the other to eliminate the integral and solve for $v$! The result is the equation:
\[
v^2-\sqrt{(1-a)^2+b^2}\,v-(1-b) = 0
\]Solving this quadratic equation for $v$ (discard the negative solution, since the ram’s speed is positive), we obtain the solution:
\[
v_\text{ram}=\frac{1}{2} \left(\sqrt{(1-a)^2+b^2}+\sqrt{(1-a)^2+(2-b)^2}\right)
\]If we specialize this formula to the ram starting at the southwest gate by setting $a=b=0$, we obtain the Golden Ratio:

$\displaystyle
(\text{Ram speed}) = \frac{1+\sqrt{5}}{2} \approx 1.618
$

And here is my solution, which finds an equation for the path of the ram but requires knowledge of calculus and differential equations.
[Show Solution]

I’ll derive the equations for the pursuit curves first, and then I’ll show some pretty pictures — hang on!

Solution details

We’ll use the same coordinate setup as in the first solution, again assuming the ram starts at $(a,b)$. Suppose the ram’s position at time $t$ is $(x(t),y(t))$. From now on, we’ll simply write $x$ and $y$ to keep the notation clean. We are given two pieces of information: the ram always moves towards the farmer, and the ram’s speed is constant (let’s call it $v$). We can write these as:
\[
\frac{dy}{dx} = \frac{t-y}{1-x}
\qquad\text{and}\qquad
v\, t = \int_a^x \sqrt{1 + \left(\frac{dy}{d\xi}\right)^2}\,d\xi
\]The first equation forms the slope (see diagram above) while the second equation says that the arc length of the curve traced out by the ram should be $v$ times the distance traveled by the farmer. One might be tempted to substitute and eliminate $\frac{dy}{dx}$, but the remaining equation will still have $x,$ $y,$ and $t,$ so that doesn’t help us. Instead, isolate $t$ from the first equation and substitute it into the second equation to obtain
\[
y+(1-x)\frac{dy}{dx} = \frac{1}{v}\int_a^x \sqrt{1 + \left(\frac{dy}{d\xi}\right)^2}\,d\xi
\]We now have a single equation that relates $y$ and $x$ with no $t$-dependence! Differentiate both sides with respect to $x$ and let $w=\frac{dy}{dx}$. The result is the following separable ordinary differential equation
\[
(1-x)\frac{dw}{dx} = \frac{1}{v}\sqrt{1+w^2}
\]The general solution of this ODE has the form
\[
w = \frac{1}{2}\left( C(1-x)^{-1/v}-C^{-1}(1-x)^{1/v}\right)
\]Where $C$ is a constant that depends on the initial condition. We can solve for $C$ using the fact that when $t=0$, we have $x=a$ and $w=b/(a-1)$. The result is that
\[
C=(1-a)^{-1+1/v}\left(-b+\sqrt{(1-a)^2+b^2}\right)
\]Now recall that $w = \frac{dy}{dx}$ so we can integrate once more to obtain $y$ as a function of $x$, i.e. the path of the ram. We also have the initial condition $y(a)=b$. I’ll spare you the algebra… The result is
\begin{align}
y = b &+ \frac{1}{2}\left[
\frac{ b-\sqrt{b^2+(1-a)^2}}{1-1/v} \left(\left( \frac{1-x}{1-a} \right)^{1-1/v} – 1\right)\right.\\
&\qquad\qquad+\left.\frac{ b+\sqrt{b^2+(1-a)^2}}{1+1/v} \left(\left( \frac{1-x}{1-a} \right)^{1+1/v} – 1\right)
\right]
\end{align}So now we know everything! To figure out where the ram intercepts the farmer, set $x=1$ and obtain
\[
y_\text{final}=\frac{-b+v\sqrt{(1-a)^2+b^2}}{v^2-1}
\]If we know that the ram barely makes it to the northeast gate $(1,1)$ on time, set $y_\text{final}=1$ and solve for $v$. The simplified result is
\[
v_\text{ram}=\frac{1}{2} \left(\sqrt{(1-a)^2+b^2}+\sqrt{(1-a)^2+(2-b)^2}\right)
\]This is precisely the same result we found using the first method!

Cool pictures!

Since we have an explicit formula for $y$ in terms of $x$, we can see what the ram’s path might look like for a variety of starting points. In the figure below, the farmer moves from the southeast corner to the northeast corner at a uniform speed, and each curve is a different ram’s path that starts along the western gate. Note: each ram chases the farmer, and each has a different speed that has been tuned to meet the farmer right at the end of his run.

Finally, suppose we know the speed of the ram. What is the “safe zone” outside of which the ram can’t reach the farmer in time? If you look at the formula for $v$, you’ll notice that it’s actually the average of two distances: the initial distance between the ram and the farmer, and the initial distance between the ram and the farmer’s reflection across the north fence. So if we fix the ram’s speed, the set of starting points $(a,b)$ describes an ellipse with the farmer and his reflection as the foci! See below for an illustration of the safe zones for different ram speeds.

I should point out that these trajectories are known as pursuit curves. Another notable example is circular pursuit, which was covered in a previous Riddler problem!

Infinite pursuit

If the ram and the farmer have identical speeds, something interesting happens… As you might imagine, the ram never catches the farmer. But it turns out that if the farmer continues forever in a straight line, the ram will end up directly behind the farmer, always a constant distance away! The equations we derived for $y$ aren’t helpful in this case, so we must return the the beginning. Rearranging the equation for the slope gives us:
\[
t-y = (1-x)\frac{dy}{dx}
\]Now $t-y$ is precisely what we’re after; it’s the vertical distance separating the farmer from the ram. Substituting our expression for $\frac{dy}{dx}$ into this equation and setting $v=1$, we find
\begin{align}
t-y &= (1-x)\left( \frac{1}{2}\left( C(1-x)^{-1/v}-C^{-1}(1-x)^{1/v}\right) \right) \\
&= \frac{1}{2}\left( C-C^{-1}(1-x)^{2}\right)
\end{align}And in the limit $x\to 1$, this is simply
\[
\text{(limiting distance)} = \frac{1}{2}C = \frac{\sqrt{(1-a)^2+b^2}-b}{2}
\]So if the ram starts at $(0,0)$, the limiting distance between the farmer and ram will be $\frac{1}{2}$. Neat! If we ask for the set of all possible starting ram locations that yield a limiting distance of $\frac{1}{2}$, we get a different conic section: a parabola this time. Here is a plot showing the possible starting points for various limiting distances.