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?