Return to Answer

Encouraged by the existence result in Tony Huynh's answer, the next interesting question is: what is the smallest number of connected pieces with which a unanimously-fair division can be achieved?

The following simple example shows that the number of pieces must be at least $N$ - the total number of citizens in all states. In the example there are 3 states - blue, green and red. Each of the 4 citizen in each state values exactly one of the intervals of that state. If we want every citizen in every state to feel that his state got any value greater than 0, we must give 4 pieces to each state, and 12 pieces overall:

Note that the cake is a one-dimensional interval and cannot be cut "horizontally".

The question is now: Is it always possible to achieve a unanimously-fair division with $N$ pieces?

I think the answer is yes in the simplest possible scenario of $N=3$ citizens in two states. An illustrative story: Alice and Bob are married, and they inherited a land-estate in partnership with Charles, who is single. The goal is to divide the land such that both Alice and Bob believe that their common share is at least 1/2 the total, while Charles also believs that his share is at least 1/2 the total.

Here is a traditional-style moving-knife procedure that (I think) achieves such a division. Initially, assume that the cake is the interval $[0,1]$ with the points 0 and 1 identified (e.g. a topological circle).

Charles holds two knives over the cake: knife X at $x$ and knife Y at $y$ such that $V_{Charles}[x,y)=1/2$. He moves knife X continuously from $x=0$ to $x=1$ and moves knife Y accordingly such that the cake between them has a value of exactly $1/2$ for him.

Whenever $V_{Alice}[x,y)\leq 1/2$, Alice raises her hand. Whenever $V_{Bob}[x,y)\leq 1/2$, Bob raises his hand. When both Alice and Bob have their hands raised, the procedure stops. The cake is cut at $x$ and $y$. Charles receives $[x,y)$ which he values as $1/2$, and Alice&Bob receive the remainder which each of them values as at least $1/2$.

Note that in the original cake (the interval), if $x<y$ then Charles receives a single interval and Alice&Bob receive two intervals, while if $x>y$ then Charles receives two intervals and Alice&Bob receive a single interval. In both cases the total number of intervals is 3, which is the best possible.

It remains to prove that there is indeed a time in which both Alice and Bob have their hands raised.

Here is my informal proof. Suppose that the knives are at $x_0,y_0$ with $V_{Alice}[x_0,y_0)> 1/2$. Eventually, the knives make a half-cycle and come to $y_0,x_0$, where $V_{Alice}[y_0,x_0)< 1/2$. So for every point in time in which Alice's hand is down, there is a point in time in which her hand is up. Moreover, when the value is exactly 1/2 Alice's hand is up. Hence, Alice's hand is up in a closed subset of the time interval, whose measure is at least $1/2$.

The same is true for Bob. Hence, there exists a time in which both Alice and Bob have their hands up (see formal proof here http://math.stackexchange.com/a/1264304/29780 ).

I believe this proof can be generalized to two groups of arbitrary sizes, probably by induction, but I currently don't know how to proceed.

Encouraged by the existence result in Tony Huynh's answer, the next interesting question is: what is the smallest number of connected pieces with which a unanimously-fair division can be achieved?

The following simple example shows that the number of pieces must be at least $N$ - the total number of citizens in all states. In the example there are 3 states - blue, green and red. Each of the 4 citizen in each state values exactly one of the intervals of that state. If we want every citizen in every state to feel that his state got any value greater than 0, we must give 4 pieces to each state, and 12 pieces overall:

Note that the cake is a one-dimensional interval and cannot be cut "horizontally".

The question is now: Is it always possible to achieve a unanimously-fair division with $N$ pieces?

I think the answer is yes in the simplest possible scenario of $N=3$ citizens in two states. An illustrative story: Alice and Bob are married, and they inherited a land-estate in partnership with Charles, who is single. The goal is to divide the land such that both Alice and Bob believe that their common share is at least 1/2 the total, while Charles also believs that his share is at least 1/2 the total.

Here is a traditional-style moving-knife procedure that (I think) achieves such a division. Initially, assume that the cake is the interval $[0,1]$ with the points 0 and 1 identified (e.g. a topological circle).

Charles holds two knives over the cake: knife X at $x$ and knife Y at $y$ such that $V_{Charles}[x,y)=1/2$. He moves knife X continuously from $x=0$ to $x=1$ and moves knife Y accordingly such that the cake between them has a value of exactly $1/2$ for him.

Whenever $V_{Alice}[x,y)\leq 1/2$, Alice raises her hand. Whenever $V_{Bob}[x,y)\leq 1/2$, Bob raises his hand. When both Alice and Bob have their hands raised, the procedure stops. The cake is cut at $x$ and $y$. Charles receives $[x,y)$ which he values as $1/2$, and Alice&Bob receive the remainder which each of them values as at least $1/2$.

Note that in the original cake (the interval), if $x<y$ then Charles receives a single interval and Alice&Bob receive two intervals, while if $x>y$ then Charles receives two intervals and Alice&Bob receive a single interval. In both cases the total number of intervals is 3, which is the best possible.

It remains to prove that there is indeed a time in which both Alice and Bob have their hands raised.

Here is my informal proof. Suppose that the knives are at $x_0,y_0$ with $V_{Alice}[x_0,y_0)> 1/2$. Eventually, the knives make a half-cycle and come to $y_0,x_0$, where $V_{Alice}[y_0,x_0)< 1/2$. So for every point in time in which Alice's hand is down, there is a point in time in which her hand is up. Moreover, when the value is exactly 1/2 Alice's hand is up. Hence, Alice's hand is up in a closed subset of the time interval, whose measure is at least $1/2$.

The same is true for Bob. Hence, there exists a time in which both Alice and Bob have their hands up (see formal proof here https://math.stackexchange.com/a/1264304/29780 ).

I believe this proof can be generalized to two groups of arbitrary sizes, probably by induction, but I currently don't know how to proceed.

Encouraged by the existence result in Tony Huynh's answer, the next interesting question is: what is the smallest number of connected pieces with which a unanimously-fair division can be achieved?

The following simple example shows that the number of pieces must be at least $N$ - the total number of citizens in all states. In the example there are 3 states - blue, green and red. Each of the 4 citizen in each state values exactly one of the intervals of that state. If we want every citizen in every state to feel that his state got any value greater than 0, we must give 4 pieces to each state, and 12 pieces overall:

Note that the cake is a one-dimensional interval and cannot be cut "horizontally".

The question is now: Is it always possible to achieve a unanimously-fair division with $N$ pieces?

I think the answer is yes in the simplest possible scenario of $N=3$ citizens in two states. An illustrative story: Alice and Bob are married, and they inherited a land-estate in partnership with Charles, who is single. The goal is to divide the land such that both Alice and Bob believe that their common share is at least 1/2 the total, while Charles also believs that his share is at least 1/2 the total.

Here is a traditional-style moving-knife procedure that (I think) achieves such a division. Initially, assume that the cake is the interval $[0,1]$ with the points 0 and 1 identified (e.g. a topological circle).

Charles holds two knives over the cake: knife X at $x$ and knife Y at $y$ such that $V_{Charles}[x,y)=1/2$. He moves knife X continuously from $x=0$ to $x=1$ and moves knife Y accordingly such that the cake between them has a value of exactly $1/2$ for him.

Whenever $V_{Alice}[x,y)\leq 1/2$, Alice raises her hand. Whenever $V_{Bob}[x,y)\leq 1/2$, Bob raises his hand. When both Alice and Bob have their hands raised, the procedure stops. The cake is cut at $x$ and $y$. Charles receives $[x,y)$ which he values as $1/2$, and Alice&Bob receive the remainder which each of them values as at least $1/2$.

Note that in the original cake (the interval), if $x<y$ then Charles receives a single interval and Alice&Bob receive two intervals, while if $x>y$ then Charles receives two intervals and Alice&Bob receive a single interval. In both cases the total number of intervals is 3, which is the best possible.

It remains to prove that there is indeed a time in which both Alice and Bob have their hands raised.

Here is my informal proof. Suppose that the knives are at $x_0,y_0$ with $V_{Alice}[x_0,y_0)> 1/2$. Eventually, the knives make a half-cycle and come to $y_0,x_0$, where $V_{Alice}[y_0,x_0)< 1/2$. So for every point in time in which Alice's hand is down, there is a point in time in which her hand is up. Moreover, when the value is exactly 1/2 Alice's hand is up. Hence, Alice's hand is up more than half the time.

The same is true for Bob. Hence, there exists a time in which both Alice and Bob have their hands up.

I believe this proof can be made formal and generalized to two groups of arbitrary sizes, probably by induction, but I currently don't know how to proceed.

Encouraged by the existence result in Tony Huynh's answer, the next interesting question is: what is the smallest number of connected pieces with which a unanimously-fair division can be achieved?

The following simple example shows that the number of pieces must be at least $N$ - the total number of citizens in all states. In the example there are 3 states - blue, green and red. Each of the 4 citizen in each state values exactly one of the intervals of that state. If we want every citizen in every state to feel that his state got any value greater than 0, we must give 4 pieces to each state, and 12 pieces overall:

Note that the cake is a one-dimensional interval and cannot be cut "horizontally".

The question is now: Is it always possible to achieve a unanimously-fair division with $N$ pieces?

I think the answer is yes in the simplest possible scenario of $N=3$ citizens in two states. An illustrative story: Alice and Bob are married, and they inherited a land-estate in partnership with Charles, who is single. The goal is to divide the land such that both Alice and Bob believe that their common share is at least 1/2 the total, while Charles also believs that his share is at least 1/2 the total.

Here is a traditional-style moving-knife procedure that (I think) achieves such a division. Initially, assume that the cake is the interval $[0,1]$ with the points 0 and 1 identified (e.g. a topological circle).

Charles holds two knives over the cake: knife X at $x$ and knife Y at $y$ such that $V_{Charles}[x,y)=1/2$. He moves knife X continuously from $x=0$ to $x=1$ and moves knife Y accordingly such that the cake between them has a value of exactly $1/2$ for him.

Whenever $V_{Alice}[x,y)\leq 1/2$, Alice raises her hand. Whenever $V_{Bob}[x,y)\leq 1/2$, Bob raises his hand. When both Alice and Bob have their hands raised, the procedure stops. The cake is cut at $x$ and $y$. Charles receives $[x,y)$ which he values as $1/2$, and Alice&Bob receive the remainder which each of them values as at least $1/2$.

Note that in the original cake (the interval), if $x<y$ then Charles receives a single interval and Alice&Bob receive two intervals, while if $x>y$ then Charles receives two intervals and Alice&Bob receive a single interval. In both cases the total number of intervals is 3, which is the best possible.

It remains to prove that there is indeed a time in which both Alice and Bob have their hands raised.

Here is my informal proof. Suppose that the knives are at $x_0,y_0$ with $V_{Alice}[x_0,y_0)> 1/2$. Eventually, the knives make a half-cycle and come to $y_0,x_0$, where $V_{Alice}[y_0,x_0)< 1/2$. So for every point in time in which Alice's hand is down, there is a point in time in which her hand is up. Moreover, when the value is exactly 1/2 Alice's hand is up. Hence, Alice's hand is up in a closed subset of the time interval, whose measure is at least $1/2$.

The same is true for Bob. Hence, there exists a time in which both Alice and Bob have their hands up (see formal proof here http://math.stackexchange.com/a/1264304/29780 ).

I believe this proof can be generalized to two groups of arbitrary sizes, probably by induction, but I currently don't know how to proceed.

Encouraged by the existence result in Tony Huynh's answer, the next interesting question is: what is the smallest number of connected pieces with which a unanimously-fair division can be achieved?

The following simple example shows that the number of pieces must be at least $N$ - the total number of citizens in all states. In the example there are 3 states - blue, green and red. Each of the 4 citizen in each state values exactly one of the intervals of that state. If we want every citizen in every state to feel that his state got any value greater than 0, we must give 4 pieces to each state, and 12 pieces overall:

Note that the cake is a one-dimensional interval and cannot be cut "horizontally".

The question is now: Is it always possible to achieve a unanimously-fair division with $N$ pieces?

I think the answer is yes in the simplest possible scenario of $N=3$ citizens in two states. An illustrative story: Alice and Bob are married, and they inherited a land-estate in partnership with Charles, who is single. The goal is to divide the land such that both Alice and Bob believe that their common share is at least 1/2 the total, while Charles also believs that his share is at least 1/2 the total.

Here is a traditional-style moving-knife procedure that (I think) achieves such a division. Initially, assume that the cake is the interval $[0,1]$ with the points 0 and 1 identified (e.g. a topological circle).

Charles holds two knives over the cake: knife X at $x$ and knife Y at $y$ such that $V_{Charles}[x,y)=1/2$. He moves knife X continuously from $x=0$ to $x=1$ and moves knife Y accordingly such that the cake between them has a value of exactly $1/2$ for him.

Whenever $V_{Alice}[x,y)\leq 1/2$, Alice raises her hand. Whenever $V_{Bob}[x,y)\leq 1/2$, Bob raises his hand. When both Alice and Bob have their hands raised, the procedure stops. The cake is cut at $x$ and $y$. Charles receives $[x,y)$ which he values as $1/2$, and Alice&Bob receive the remainder which each of them values as at least $1/2$.

Note that in the original cake (the interval), if $x<y$ then Charles receives a single interval and Alice&Bob receive two intervals, while if $x>y$ then Charles receives two intervals and Alice&Bob receive a single interval. In both cases the total number of intervals is 3, which is the best possible.

It remains to prove that there is indeed a time in which both Alice and Bob have their hands raised.

Here is my informal proof. Suppose that the knives are at $x_0,y_0$ with $V_{Alice}[x_0,y_0)> 1/2$. Eventually, the knives make a half-cycle and come to $y_0,x_0$, where $V_{Alice}[y_0,x_0)< 1/2$. So for every point in time in which Alice's hand is down, there is a point in time in which her hand is up. Moreover, when the value is exactly 1/2 Alice's hand is up. Hence, Alice's hand is up more than half the time.

The same is true for Bob. Hence, there exists a time in which both Alice and Bob have their hands up.

I believe this proof can be made formal and generalized to two groups of arbitrary sizes, using a lemma such as the following:

Let $A_{1},...,A_{m}$ be $m$ closed subsets of $[0,1]^{m-1}$ such that: $\mu(A_{i})\geq1/2$ for all $i$ (where $\mu$ is the Lebesgue measure on $\mathbb{R}^{m-1}$). Then $\cap_{i=1}^{m}A_{i}\neq\emptyset$.

The only problem is, I don't know how to prove this lemma :) Any ideas are welcome.

Encouraged by the existence result in Tony Huynh's answer, the next interesting question is: what is the smallest number of connected pieces with which a unanimously-fair division can be achieved?

The following simple example shows that the number of pieces must be at least $N$ - the total number of citizens in all states. In the example there are 3 states - blue, green and red. Each of the 4 citizen in each state values exactly one of the intervals of that state. If we want every citizen in every state to feel that his state got any value greater than 0, we must give 4 pieces to each state, and 12 pieces overall:

Note that the cake is a one-dimensional interval and cannot be cut "horizontally".

The question is now: Is it always possible to achieve a unanimously-fair division with $N$ pieces?

I think the answer is yes in the simplest possible scenario of $N=3$ citizens in two states. An illustrative story: Alice and Bob are married, and they inherited a land-estate in partnership with Charles, who is single. The goal is to divide the land such that both Alice and Bob believe that their common share is at least 1/2 the total, while Charles also believs that his share is at least 1/2 the total.

Here is a traditional-style moving-knife procedure that (I think) achieves such a division. Initially, assume that the cake is the interval $[0,1]$ with the points 0 and 1 identified (e.g. a topological circle).

Charles holds two knives over the cake: knife X at $x$ and knife Y at $y$ such that $V_{Charles}[x,y)=1/2$. He moves knife X continuously from $x=0$ to $x=1$ and moves knife Y accordingly such that the cake between them has a value of exactly $1/2$ for him.

Whenever $V_{Alice}[x,y)\leq 1/2$, Alice raises her hand. Whenever $V_{Bob}[x,y)\leq 1/2$, Bob raises his hand. When both Alice and Bob have their hands raised, the procedure stops. The cake is cut at $x$ and $y$. Charles receives $[x,y)$ which he values as $1/2$, and Alice&Bob receive the remainder which each of them values as at least $1/2$.

Note that in the original cake (the interval), if $x<y$ then Charles receives a single interval and Alice&Bob receive two intervals, while if $x>y$ then Charles receives two intervals and Alice&Bob receive a single interval. In both cases the total number of intervals is 3, which is the best possible.

It remains to prove that there is indeed a time in which both Alice and Bob have their hands raised.

Here is my informal proof. Suppose that the knives are at $x_0,y_0$ with $V_{Alice}[x_0,y_0)> 1/2$. Eventually, the knives make a half-cycle and come to $y_0,x_0$, where $V_{Alice}[y_0,x_0)< 1/2$. So for every point in time in which Alice's hand is down, there is a point in time in which her hand is up. Moreover, when the value is exactly 1/2 Alice's hand is up. Hence, Alice's hand is up more than half the time.

The same is true for Bob. Hence, there exists a time in which both Alice and Bob have their hands up.

I believe this proof can be made formal and generalized to two groups of arbitrary sizes, probably by induction, but I currently don't know how to proceed.