# Optimal strategy in repeated cake-cutting

Alice and Bob play the famous game of divide and choose $n$ times with $n$ identical cakes. Each time, Alice cuts the cake to two pieces, and Bob chooses the piece he prefers. Alice does not know Bob's preferences, but she assumes that they come from a uniform distribution.

What is the strategy that maximizes Alice's expected total value?

Here is my solution so far.

Let's assume that the cake is the interval $[0,1]$. Alice cuts the cake by choosing some $x\in [0,1]$. Let $h\in[0,1]$ be a point such that Bob is indifferent between the cake to the left of $h$ and the cake to the right of $h$. Let $V(x)$ be Alice's valuation of the interval $[0,x]$; it is a continuous and increasing function of $x$. Then:

• If $h> x$, then Bob picks $[x,1]$ and Alice gets $[0,x]$ and gains $V(x)$.
• If $h< x$, then Bob picks $[0,x]$ and Alice gets $[x,1]$ and gains $V(1)-V(x)$.
• If $h=x$ then, let's say Bob picks a piece at random so Alice gains on average $V(1)/2$.

If Alice knows $h$, then she has a simple optimal strategy:

• If $V(h) > V(1)-V(h)$, then select $x^* = h-\epsilon$, for some $\epsilon>0$, and gain $\approx V(h)$.
• Otherwise, select $x^* = h+\epsilon$, for some $\epsilon>0$, and gain $\approx V(1)-V(h)$.

Initially, Alice does not know $h$, so she assumes it is distributed uniformly in $[0,1]$. If Alice cuts at $x$ and Bob chooses left, this tells Alice that $h\in[0,x]$; if Bob chooses right, this tells Alice that $h\in[x,1]$. So, using binary search, Alice can estimate $h$ to an arbitrary precision. This seems to be an optimal strategy when $n\to\infty$: spend a lot of rounds initially for getting an accurate estimate of $h$, and use this estimate from then on to get the optimal possible value.

I am stuck at the case where $n$ is finite and small. The question bogs me even for $n=2$: what is the optimal first cut?

• I have edited my answer and undeleted it (my previous version had a glaring mistake where I assumed a random second cut - which makes no sense, you will choose the best second cut). The result is quite surprising, I hope I didn't make a mistake somewhere (it's quite some busywork). – orlp Jun 20 '18 at 23:42

Let $v(x) = \frac{V(x) - V(0)}{V(1) - V(0)}$ so $v(x)$ nicely goes from $0$ to $1$. Maximizing $v$ also maximizes $V$. To cover my ass for future mistakes regarding $<$ vs $\leq$, I will assume that you will never exactly guess $x = h$.

Now, if $n = 1$, we can find the expected value from cutting at $x$ by integrating over all possible $h$:

$$e_1(x) = E[v(x)] = \int_0^x (1 - v(x))dh + \int_x^1 v(x)dh = (1 - 2x)v(x) + x$$

Which allows you to maximize $e_1$ with differentiation to find the optimal $x$. Note that in the above example "all possible $h$" meant $[0, 1]$. But what if we know that $h \in [a, b]$ due to previous information?

Then we get the following sum of integrals for when also $x \in [a, b]$:

$$\int_a^x (1 - v(x))dh + \int_x^b v(x)dh = (a + b - 2x)v(x) - a + x$$

Which makes the total expected valuation:

$$e_{1,a,b}(x) = E[v(x) | a \leq h \leq b] = \begin{cases} v(x) & \text{if x < a}\\ (a + b - 2x)v(x) - a + x & \text{if a \leq x \leq b}\\ 1 - v(x) &\text{if x > b} \end{cases}$$

Now let's analyze $n = 2$. Suppose our first cut is at $x$, then there is a $x$ chance $h \leq x$ and $1 - x$ chance $h \geq x$. In both those scenarios we will then choose our best possible $y$. This gives equation:

$$e_2(x) = e_1(x) + x\left( \max_{0 \leq y \leq 1} e_{1,0,x}(y)\right) + (1-x)\left( \max_{0 \leq y \leq 1} e_{1,x,1}(y)\right)$$

$$\max_{0 \leq y \leq 1} e_{1,0,x}(y) = \max\left(\max_{0 \leq y \leq x} ((x - 2y)v(y) + y), \max_{x \leq y \leq 1} (1 - v(y))\right)$$

$$\max_{0 \leq y \leq 1} e_{1,x,1}(y) = \max\left(\max_{0 \leq y \leq x} v(y), \max_{x \leq y \leq 1} ((x + 1 - 2y)v(y) - x + y)\right)$$

Now let's say $v(x) = x$, a simple linear increase in desire for more cake. Now we can actually solve:

$$\max_{0 \leq y \leq 1} e_{1,0,x}(y) = \max\left(\begin{cases}x(1-x)&0\leq x \leq \frac{1}{3}\\\frac{1}{8}(x+1)^2&\frac{1}{3} \leq x \leq 1\end{cases}, 1 - x\right)$$

$$\max_{0 \leq y \leq 1} e_{1,x,1}(y) = \max\left(x, \begin{cases}\frac{1}{8}(x-2)^2&0\leq x \leq \frac{2}{3}\\x(1-x)&\frac{2}{3} \leq x \leq 1\end{cases}\right)$$

Now $e_2$ is complicated, but is essentially a piecewise function which can be solved.

• So the optimal first cut is around 0.8? This is indeed very surprising. I would expect the function to be symmetric. Why is there a difference between cutting at 0.8 and cutting at 0.2? – Erel Segal-Halevi Jun 21 '18 at 6:22
• $\max_{0\le y\le 1}e_{1,0,x}(y)$ should be $\max\left(\max_{0\le x\le y}((x-2y)v(y)+\color{red}{y})\color{red}{/x},\ldots\right)$. – xskxzr Jun 21 '18 at 7:33
• @xskxzr Oops, it definitely should be $((x - 2y)v(y) + y)$, but I don't see why the division by $x$. Also you changed the subscript from $0 \leq y \leq x$ to $0 \leq x \leq y$, which I don't understand either. – orlp Jun 21 '18 at 9:14
• @ErelSegal-Halevi xskxzr spotted a mistake, I will fix this answer later, I have an exam coming up in 3 hours :) – orlp Jun 21 '18 at 9:15
• @orip Division by $x$ is because the probability is, for example, $(x-y)/x$, rather than $x-y$. $0\le x\le y$ is a typo. – xskxzr Jun 21 '18 at 9:41