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&gt; x$, then Bob picks $[x,1]$ and Alice gets $[0,x]$ and gains $V(x)$.
If $h&lt; 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) &gt; V(1)-V(h)$, then select $x^* = h-\epsilon$, for some $\epsilon&gt;0$, and gain $\approx V(h)$.
Otherwise, select $x^* = h+\epsilon$, for some $\epsilon&gt;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?
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 $&lt;$ 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) &amp; \text{if $x &lt; a$}\\
(a + b - 2x)v(x) - a + x &amp; \text{if $a \leq x \leq b$}\\
1 - v(x) &amp;\text{if $x &gt; 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)&amp;0\leq x \leq \frac{1}{3}\\\frac{1}{8}(x+1)^2&amp;\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&amp;0\leq x \leq \frac{2}{3}\\x(1-x)&amp;\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.