Fair cake-cutting between groups

Question

The cake-cutting game is usually played between individuals. What if we try to play it between groups?

A certain land has to be divided between two states. ‎There are $n$ citizens in each state. Each citizen in each state has a subjective continuous value measure over the land. How can the land be divided such that each citizen, in each state, believes that his/her state received at least $1/2$ of the land value?

Some simple observations:

• A solution with a single cut (giving each state a single connected piece) is not always possible. For example, if in each state there are citizens who want only the east and citizens who want only the west, then every single-cut division (using a north-south line, at least) will leave some citizens unsatisfied, feeling that their state has got no value at all. So we must allow multiple cuts (this is in contrast to cake-cutting between individuals, where a single-cut solution is always possible).
• If the valuations are piecewise-constant, i.e. the land can be partitioned to $k$ districts such that each citizen has a constant value measure over each district, then an easy solution is to give each state $1/2$ the area of each district. Every practical continuous value measure can be regarded as approximately piecewise-constant for sufficiently small pieces, so this can be regarded as a sufficient solution. The problem with it is that it gives each state $k$ disconnected pieces, and $k$ may be very large (even larger than the number of citizens).

So the interesting question is: how to divide the land fairly, such that each state receives only a small number of disconnected pieces? (e.g. a constant, or a function of the number of citizens).

^{Initially I thought of a variant in which only half of the citizens in each state should feel that the division is fair. This makes sense in democratic states, since the suggested division may be brought to a referendum in each state, and if at least half vote in favor of it, it is implemented. Under this assumption, it is possible to divide the land in a single cut (a single piece per state). But this does not generalize well to 3 or more states.}

EDIT: many thanks to the repliers. I ended up writing some papers about this:

• Fair cake-cutting among families - with Shmuel Nitzan;
• Fair and efficient division among families - with Sophie Bade;
• How to cut a cake fairly - a generalization to groups - with Warut Suksompong.

Answer 1

Since it is possible that there are citizens in different states with the exact same valuation of land, we might as well solve the stronger version where each citizen in each state believes that her state received exactly $\frac{1}{2}$ the land value.

In this case, I think a suitable version of the Ham Sandwich Theorem for measures should imply the existence result under very general conditions.

See this paper of Golasinski for multiple measure-theoretic versions of the Ham Sandwich theorem.

Answer 2

I take the freedom to interprete the question in the following way:

• the value-measures of the citizens are not secret and the two nations are befriended, so they want to partition the land in a way that the citizens of state $A$ receive a piece of land that is worth at least 50% of the total land's value according to their value-measure and, the citizens of state $B$ also wish to receive a piece of land that is worth at least 50% of the total land's value according to their value-measure.

• the value-measure of each state equals the sum of the cost-measures of its citizens and those value-measures of the states are used for checking the worth of the portion of land that the state received.

• the value-measures of the individuals are functions, that are integrable over the land's coordinate set.

under the above conditions the following observation can be used to describe the set of solutions with not more than two straight-line cuts of infinite length:

if each state's value-measure is interpreted as mass-distribution, then all lines that partition the land into two pieces of equal value according to the state's value-measure, contain the center of mass; now, as the state's centers of mass will be different in general, the line containing both of them will partition the land in the desired way.

That also yields a criterion for deciding if it is possible that the land can be partitioned in a way that each state receives a piece of land, who's value is more than 50% of the total land's value according to the respective state's value-measure: namely exactly if their centers of mass don't coincide.

Provided my interpretation of value as mass is correct, a further consequence is also, that the solution is not unique and further restrictions may be taken into consideration as secondary conditions, e.g. minimizing the individual's discomfort with the solution.
At least, the interpretation of value as mass yields a practical heuristic, which may serve as a starting solution for more elaborate algorithms.

Edit

To address the comment, that taking the median of a state's citizens individual value measures would be a better choice than taking their sum I can only say, that the suggested partitioning method doesn't depend on the function that maps the citizens value measures to a single state measure; as has already been stated before, it is always possible to incorporate additional requirements as a secondary optimality criterion.

$$ $$

Addendum:

should by incidence the centers of mass of each individual's value measure be collinear, then partitioning the land along that line is perceived as balanced according to each individual's value measure.

That observation can be utilized to sketch a method, that allows one to find a partitioning of the land into two parts that are equal according to each individual's value measure:

• Try to find an invertible, area-preserving, continuous mapping of the land's coordinate set with the property, that the centers of mass of each individual's value measure are collinear when calculated for the land's image and, if such a mapping exists,

• take inverse mapping of the line through those centers of mass as the curve along which to split the land.

So the essential question would be, under what conditions such a mapping exists and whether it can be calculated exactly or to arbitrary precision.

Answer 3

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.

Answer 4

In "Consensus-halving via theorems of Borsuk-Ulam and Tucker", Su and Simmons describe a way to divide a cake to two parts such that each of $n-1$ people believe the parts have the same value. This can be done with $n-1$ cuts ($n$ pieces), which is optimal.

Once we have such a division, we can let the $n$-th person choose which half is better. Now, regardless of how the groups are divided, all people in each group believe that the value of their group is at least $1/2$. So we have a group division in which the number of pieces is equal to the total number of people, which is optimal.

So for 2 groups, the problem is solved. The case of $k>2$ groups is mentioned as a conjecture in their Open Problems section.