# Consensus division of a cake

There is a pie and two people with different tastes. The goal is to cut a piece, using two radial cuts like this: such that both people agree that the piece has a value of exactly a fraction $p$ of the total, where $p\in[0,1]$ is a given constant.

Formally, the pie is described as the interval $[0,1]$ whose two endpoints are identified (- a topological circle). There are two non-negative value measures over the interval, $V_A$ and $V_B$. They are absolutely continuous with respect to length (this means that they are non-atomic). Both measures assign the same value to the whole interval: $V_A([0,1])=V_B([0,1])=1$. The goal is to find an interval $[x,y]$ such that $V_A([x,y])=V_B([x,y])=p$.

I found a solution for the special case in which the measure $V_A$ is equal to the length measure. Here it is. Hold two knives over the pie, such that the distance between them is exactly $p$. Move the knives a whole round around the pie, always keeping the distance between them at $p$. I claim that there is a point in which $V_B$ of the piece between the knives is exactly $p$.

PROOF: At each time $t\in[0,1]$, the piece between the knives is $[t,t+p]$. Mark by $S$, the sum of the values of $V_B$ when the knives make a whole round:

$$S = \int_{t=0}^1 V_B([t,t+p]) dt$$

Since $V_B$ is continuous, it has a derivative $v_b$, such that $V_B([t,t+p])=\int_{x=t}^{t+p} v_b(x)dx$. So:

$$S = \int_{t=0}^1 \int_{x=t}^{t+p} v_b(x)dx dt = \int_{t=0}^1 \int_{x=0}^{p} v_b(t+x)dx dt$$

Substitute the order of integration and get:

$$S = \int_{x=0}^{p} \int_{t=0}^1 v_b(t+x) dt dx = \int_{x=0}^{p} 1 dx = p$$

The integral of $V_B([t,t+p])$ equals $p$ and the functions are continuous, so by the Mean Value Theorem there must be a $t$ in which $V_B([t,t+p])=p$. $\square$

Is it possible to generalize this argument to arbitrary continuous value measures?

EDIT: I just thought of an informal idea.

Let $N$ be a large integer. Normalize the value measures such that the value of the entire cake for each person is $N^2$.

Divide the cake to $N$ arcs such that, in each arc, $V_A+V_B=2N$. Additionally, round the values of $V_A$ and $V_B$ in each arc to the nearest integers.

Now, we have a discrete problem. We can imagine that in each arc, there are $V_A$ Azure balls and $V_B$ Black balls.

Move two knives around the cake in the following way. In each step $t$, knife #1 is just before Azure ball $t$, and knife #2 is just before Azure ball $t + p N^2$. Hence the number of Azure balls between the knives is always $p N^2$. Move the knives until the knives return to their original location.

At each step, count the number of Black balls between the knives, and sum over the entire round-trip. Each black ball is counted whenever there are between 1 and $p N^2$ azure balls before it. Hence, it is counted exactly $p N^2$ times. Hence, the sum of the counts over the entire trip is $p N^4$. This is a fraction $p$ of the product of the total number of balls.

An interactive illustration is available here: http://tube.geogebra.org/m/1355529

There, $p N^2 = 5$. The green arc is the arc between the knives. You can increase $t$ and see that the green arc always covers exactly 5 azure balls, and each black ball is covered exactly 5 times.

When $N$ is sufficiently large, the sum becomes an integral, and by continuity, the integral of the $V_B$ is $p$.

Hence, by the Mean Value Theorem, there is a point in the trip in which $V_B=p$.

Can this idea be made formal?

• Just one short comment: In your proof you use that $V_B$ is absolutely continuius (with respect to Lebesgue measure), not just continuous. – PhoemueX Jun 20 '15 at 23:57
• Fixed, thanks.. – Erel Segal-Halevi Jun 21 '15 at 17:47
• Are the value measures non-negative, or can it be that a piece of the pie has negative value for one [or both] of the two? – Daniel Fischer Jun 22 '15 at 15:36
• @DanielFischer They are non-negative. If this helps, it can also be assumed that they are positive. – Erel Segal-Halevi Jun 22 '15 at 15:54
• Then I have some typing to do after dinner. – Daniel Fischer Jun 22 '15 at 15:58

The cases $p = 0$ and $p = 1$ are either trivial or, if an empty sector/the whole pie are disallowed, in general not possible to achieve, so let's assume $0 < p < 1$.

Then let's lift the value functions to $\mathbb{R}$, so we have two functions $V_\ast \colon \mathbb{R}\to \mathbb{R}$ with $V_\ast(0) = 0$ and $\bigl(\forall x\in \mathbb{R}\bigr)\bigl(V_\ast(x+1) = V_\ast(x) + 1\bigr)$, where $V_\ast(x)$ is the value that person $\ast$ ascribes to the piece of the pie between angle $0$ [arbitrarily determined] and angle $2\pi x$ for $0 \leqslant x < 1$, and the function is extended by setting $V_\ast(x) = \lfloor x\rfloor + V_\ast(x-\lfloor x\rfloor)$ for arbitrary $x$.

By assumption, the two functions $V_A$ and $V_B$ are continuous and monotonically increasing (but not necessarily strictly). Since $x \mapsto V_\ast(x) - x$ is continuous and has period $1$, $V_\ast$ is uniformly continuous.

First, let us assume that - without loss of generality - $V_A$ is strictly increasing. Then $V_A$ has a continuous inverse $\varphi$, and since $x\mapsto \varphi(x) - x$ also has period $1$, $\varphi$ is also uniformly continuous. Define $s(x) = \varphi(V_A(x) + p)$. Then $s$ is uniformly continuous, $s(x+1) = s(x) + 1$ for all $x\in \mathbb{R}$ and $V_A(s(x)) - V_A(x) = p$ for all $x\in \mathbb{R}$. We then look at

$$\psi \colon x \mapsto V_B(s(x)) - V_B(x).$$

We need to show that there is an $x_0\in\mathbb{R}$ with $\psi(x_0) = p$. Since $\psi$ is continuous and has period $1$, if there were no such $x_0$, there would be an $\varepsilon > 0$ such that either $\psi(x) \leqslant p-\varepsilon$ for all $x\in \mathbb{R}$ or $\psi(x) \geqslant p+\varepsilon$ for all $x\in \mathbb{R}$. Suppose $\psi(x) \neq p$ for all $x$.

There is a $\delta > 0$ such that $\lvert x-y\rvert \leqslant \delta \implies \lvert V_\ast(x) - V_\ast(y)\rvert \leqslant \varepsilon/2$ by the uniform continuity of $V_\ast$ (we can choose the same $\delta$ for $V_A$ and $V_B$). The uniform continuity of $s$ gives us a $0 <\eta < \varepsilon/2$ with $\lvert x-y\rvert \leqslant \eta \implies \lvert s(x) - s(y)\rvert \leqslant \delta$.

Further, there are $k,m \in \mathbb{N}\setminus \{0\}$ such that $m - \eta \leqslant k\cdot p \leqslant m$. For rational $p$ we can achieve equality ($kp = m$), and for irrational $p$ the sequence $k p - \lfloor kp\rfloor$ is dense in $[0,1]$.

Now, letting $s^j$ denote the $j$-fold iterate of $s$, we have $[0,s^k(0)[ = \bigcup\limits_{j=1}^k [s^{j-1}(0), s^j(0)[$ where the union is disjoint, and $V_A(s^j(0)) - V_A(s^{j-1}(0)) = p$ for all $j$, so $V_A(s^k(0)) = kp \in [m-\eta,m]$. Then $s^k(0) = \varphi(V_A(s^k(0)) \in [m-\delta,m]$ since $\varphi(m) = m$, and therefore $V_B(s^k(0)) \in [m-\varepsilon/2,m]$.

But on the other hand we have

$$V_B(s^k(0)) = \sum_{j=1}^k V_B(s^j(0)) - V_B(s^{j-1}(0)) = \sum_{j=1}^k \psi(s^{j-1}(0)) \begin{cases} \leqslant k(p-\varepsilon) \leqslant kp-\varepsilon < m-\varepsilon/2\\ \geqslant k(p+\varepsilon) \geqslant kp+\varepsilon > m.\end{cases}$$

This contradiction shows that $\psi$ attains the value $p$. By periodicity, it attains the value $p$ in $[0,1[$.

If neither of $V_A$ and $V_B$ is strictly increasing, we can approximate the value functions by strictly increasing ones. For $n \geqslant 1$, consider the modified value functions $W_\ast^{(n)}$ given by

$$W_\ast^{(n)}(x) = \frac{n}{n+1}\biggl(V_\ast(x) + \frac{x}{n}\biggr)$$

on $[0,1[$, and extended by the relation $W_\ast^{(n)}(x+1) = W_\ast^{(n)}(x) + 1$ to all of $\mathbb{R}$. These are continuous and strictly increasing, so by the above, we have $x_n \in [0,1[$ and $y_n > x_n$ with

$$W_A^{(n)}(y_n) - W_A^{(n)}(x_n) = p = W_B^{(n)}(y_n) - W_B^{(n)}(x_n).\tag{1}$$

Pick a subsequence such that $x_{n_k}$ and $y_{n_k}$ converge, say to $x_0$ resp. $y_0$. Since $W_\ast^{(n)}$ converges uniformly to $V_\ast$, we have $W_\ast^{(n_k)}(x_{n_k}) \to V_\ast(x)$ and $W_\ast^{(n_k)}(y_{n_k}) \to V_\ast(y)$ and therefore obtain

$$V_A(y) - V_A(x) = \lim_{k\to\infty} W_A^{(n_k)}(y_{n_k}) - W_A^{(n_k)}(x_{n_k}) = p = \lim_{k\to\infty} W_B^{(n_k)}(y_{n_k}) - W_B^{(n_k)}(x_{n_k}) = V_B(y) - V_B(x)$$

from $(1)$.

• Just to give some intuition: person A holds two knives such that the value between them is exactly $p$. The function $s(x)$ is the location of the second knife, when the first knife is at $x$. The function $\psi(x)$ is the value of person B for the piece between the knives, when the first knife is at $x$. – Erel Segal-Halevi Jun 22 '15 at 20:34
• Right. And if person B would always value the part higher, or always lower than A, the two couldn't have the same total value for the pie. Then one somehow needs to prove that obvious fact. – Daniel Fischer Jun 22 '15 at 20:37