---
abstract: 'We extend the classic cake-cutting problem to a situation in which the “cake” is divided among families. Each piece of cake is owned and used simultaneously by all members of the family. A typical example of such a cake is land. We examine three ways to assess the fairness of such a division, based on the classic no-envy criterion: (a) Average envy-freeness means that for each family, the average value of its share (averaged over all family members) is weakly larger than the average value of any other share; (b) Unanimous envy-freeness means that in each family, each member values the family’s share weakly more than any other share; (c) Democratic envy-freeness means that in each family, at least half the members value the family’s share weakly more than any other share. We study each of these definitions from both an existential and a computational perspective.'
author:
- 'Erel Segal-Halevi'
- Shmuel Nitzan
bibliography:
- '../erelsegal-halevi.bib'
title: 'Envy-Free Cake-Cutting among Families'
---

Introduction
============

Fair division of land and other resources among agents with different preferences has been an important issue since Biblical times. Today it is an active area of research in the interface of computer science [@Robertson1998CakeCutting; @Procaccia2015Cake] and economics [@Moulin2004Fair]. Its applications range from politics [@Brams1996Fair; @Brams2007Mathematics] to multi-agent systems [@Chevaleyre2006Issues].

In most fair division problems, the goods are divided to individual agents, and the fairness of a division is assessed based on the *valuation* of each agent. A common fairness criterion is envy-freeness: a division is called **envy-free** if each agent values his own share at least as much as any other share.

However, in real life, goods are often owned and used by groups. As an example, consider a land-estate inherited by $k$ families, or a nature reserve that should be divided among $k$ states. The land should be divided to $k$ pieces, one piece per group. Each group’s share is then used by *all* members of the group together. The land-plot allotted to a family is inhabited by the entire family. The share of the nature-reserve alloted to a state becomes a national park open to all citizens of that state. In economic terms, the alloted piece becomes a “club good” [@Buchanan1965Economic]. The happiness of each group member depends on his/her valuation of the entire share of the group. But, in each group there are different people with different valuations. The same division can be considered envy-free by some family members and not envy-free by other members of the same family. How, then, should the fairness of the division be assessed?

One option that comes to mind is to aggregate the valuations in each family to a single *family valuation* (also known as: *collective welfare function*). Following the utilitarian tradition [@Bentham1789Introduction], the family-valuation can be defined as the sum or (equivalently) the arithmetic average of the valuations of all family members. We call a division **[average-envy-free]{}** if, for each family, the average valuation of the family’s share (averaged over all family members) is weakly larger than the average valuation of any share allocated to another family. This definition makes sense in situations in which the numeric values of the agents’ valuations are meaningful and they are all measured in the same units, e.g. in dollars (see chapter 3 of [@Moulin2004Fair] for some real-life examples of such situations). In such cases, it may be possible to transfer value between members of a group after the division is done. Members who are more satisfied with the division can somehow compensate the less satisfied members, such that finally each member enjoys the average value.

A second option is to require that no member of any family feels any envy. We call a division **[unanimous-envy-free]{}** if every agent values his family’s share at least as much as the share of any other family. The advantage of this definition is that it does not depend on the units in which the valuation functions are measured. It is applicable even when the valuations are only abstract representations of ordinal preferences.

A disadvantage of [unanimous-envy-freeness]{} is that it may be difficult to attain in practice, especially when the “families” are large. As citizens in democratic states, we know that it is next to impossible to attain unanimity on even the most trivial issue. Therefore, it is not realistic to expect that all citizens agree that a certain division is envy-free. We call a division **[democratic-envy-free]{}** if at least half the citizens in each family value their family’s share at least as much as the share of any other family. This definition makes sense when land is divided between states with a democratic regime. After a division is proposed, each state conducts a referendum in which each citizen approves the division if he/she feels that the division is envy-free. The division is implemented only if, in every state, at least half of its members approve it.

Of the three definitions presented above, [unanimous-envy-free]{} is clearly the strongest: it implies both [average-envy-free]{} and [democratic-envy-free]{}. The other two definitions do not imply each other, as shown below.

[r]{}[3cm]{}

    Alice    6   3   0   0     
  --------- --- --- --- --- -- --
     Bob     5   4   0   0     
   Charlie   1   8   0   0     
    David    0   0   6   3     
     Eva     0   0   6   3     
   Frankie   0   0   0   9     

Example
-------

Consider a land-estate consisting of four districts. It has to be divided between two families: (1) Alice+Bob+Charlie and (2) David+Eva+Frankie. The valuation of each member to each district is shown in the table to the right.

If the two leftmost districts are given to family 1 and the two rightmost districts are given to family 2, then the division is *[unanimous-envy-free]{}*, since each member of each family feels that his family’s share is better than the other family’s share. It is also, of course, [average-envy-free]{} and [democratic-envy-free]{}.

If only the single leftmost district is given to family 1 and the other three districts are given to family 2, then the division is still *[democratic-envy-free]{}*, since Alice and Bob feel that their family received a better share than the other family. However, Charlie does not feel that way, so the division is not [unanimous-envy-free]{}. Moreover, the division is not [average-envy-free]{} since the average valuation of family 1 in its own share is (6+5+1)/3=4, while the average valuation of family 1 in the other share is (3+4+8)/3=5.

If the three leftmost districts are given to family 1 and only the rightmost district is given to family 2, then the division is *[average-envy-free]{}*, since the average valuation of family 2 in its share is (3+3+9)/3=5 while its average valuation in the other share is (6+6+0)/3=4. However, it is not [unanimous-envy-free]{} and not even [democratic-envy-free]{}, since David and Eva feel that the share given to the other family is more valuable.

Two challenges arise once the fairness criterion is selected. First, determine whether there always exists a division satisfying this criterion. In case the answer is yes, determine whether there exists a protocol for achieving such a division. Cake-cutting protocols are traditionally characterized by two factors: the number of *connectivity components* in the final division, and the number of *queries* required to achieve the division. We now briefly explain each of these factors, as they are relevant to our results.

Number of connectivity components
---------------------------------

Ideally, we would like to allocate to each family a single, connected piece. This requirement is especially meaningful when the divided resource is land, since a contiguous piece of land is much easier to use than a collection of disconnected patches. However, a division with connected pieces is not always possible.

In fact, many countries have a disconnected territory. A striking example is the India-Bangladesh border. According to Wikipedia,[^1] “Within the main body of Bangladesh were 102 enclaves of Indian territory, which in turn contained 21 Bangladeshi counter-enclaves, one of which contained an Indian counter-counter-enclave... within the Indian mainland were 71 Bangladeshi enclaves, containing 3 Indian counter-enclaves”. Another example is Baarle-Hertog - a Belgian municipality made of 24 separate parcels of land, most of which are exclaves in the Netherlands.[^2]

In case a division with connected pieces is not possible, it is desirable to minimize the number of *connectivity components* (hence: *components*) in the division. Minimizing the number of components is a common requirement in the cake-cutting literature. It is common to assume that the cake is a 1-dimensional interval. In this case, the components are sub-intervals and their number is one plus the number of *cuts*. Hence, the number of components is minimized by minimizing the number of cuts [@Robertson1995Approximating; @Webb1997How; @Shishido1999MarkChooseCut; @Barbanel2004Cake; @Barbanel2014TwoPerson].

In a realistic, 3-dimensional world, the additional dimensions can be used to connect the components, e.g, by bridges or tunnels. Still, it is desirable to minimize the number of components in the original division in order to reduce the number of required bridges/tunnels.

The goal of minimizing the number of components is also pursued in real-life politics. Going back to India and Bangladesh, after many years of negotiations they finally started to exchange most of their enclaves during the years 2015-2016. This is expected to reduce the number of components from 200 to a more reasonable number.

Number of queries \[sub:Number-of-queries\]
-------------------------------------------

The most common model for cake-cutting protocols is the *query model*, formally defined by Robertson and Webb [@Robertson1998CakeCutting]. Intuitively, a cake-cutting protocol uses two types of queries: a *mark query* (also called *cut query*) asks an agent “where would you cut the cake such that the value of the resulting piece is X?” and an *eval query* asks an agent “how much is piece Y worth for you?”.

This model has been used to prove results about the *query complexity* of cake-cutting protocols, e.g. [@Even1984Note; @Edmonds2011Cake]. Interestingly, some cake-cutting problems cannot be solved with a finite number of queries. For example, with 3 or more agents, an envy-free division cannot be attained by a finite protocol when the pieces must be connected [@Stromquist2008Envyfree].

Results
-------

Our results regarding the three fairness definitions are summarized in the following theorems. In all theorems, $k\geq 2$ is the number of families and $n$ is the total number of agents in all families. In the impossibility results, it is implicitly assumed that at least one family contains at least 2 members (which implies $n>k$).[^3]

A property of cake partitions is called *feasible* if for every $k$ families and $n$ agents there exists an allocation satisfying this property. Otherwise, the property is called *infeasible*.

(**[average-envy-freeness]{}**)

\(a) [average-envy-freeness]{} with connected pieces is feasible.

\(b) [average-envy-freeness]{}, with either connected or disconnected pieces, cannot be found by a finite protocol.

(**[unanimous-envy-freeness]{}**)

\(a) [unanimous-envy-freeness]{} with connected pieces is infeasible. Moreover, at least $n$ components might be required for a [unanimous-envy-free]{} division.

\(b) [unanimous-envy-freeness]{} with disconnected pieces is feasible. Moreover, the number of required components is at most $1+(k-1)(n-1) = O(n k)$.

\(c) A [unanimous-envy-free]{} division cannot be found by a finite protocol.

(**[democratic-envy-freeness]{}**)

\(a) When $k\geq3$, [democratic-envy-freeness]{} with connected pieces is infeasible. Moreover, at least $n\cdot\frac{k/2-1}{k-1}=\Omega(n)$ components might be required for a [democratic-envy-free]{} division.

\(b) [democratic-envy-freeness]{} with disconnected pieces is always feasible. Moreover, the number of required components is at most $1+(k-1)(n/2-1)$.

\(c) When there are $k=2$ families, [democratic-envy-freeness]{} with connected pieces is feasible. Moreover, there is a finite protocol for finding a [democratic-envy-free]{} division using at most $n$ queries.

The results are summarized in the table below. For $k=2$, the results are tight: by all fairness definitions, we know that a fair division exists with the smallest possible number of connectivity components. For $k>2$, the results are not tight. As an illustration of the currently unsolved gaps, the table includes numeric values for $k=3$ and $k=4$.

[|&gt;p[2.5cm]{}|c||c|c|c|]{}

& & & **Finite**\
& & **Lower bound** & **Existence** & **Procedure**\
Average (Sec.\[sec:AM-fairness\]) & Any & $k$ & $k$ (connected; optimal) & No\
& 2 & $n$ & $n$ (optimal) & No\
Unanimous & 3 & $n$ & $2n-1$ & No\
(Sec. \[sec:unan-fairness\]) & 4 & $n$ & $3n-2$ & No\
& Any & $n$ & $(k-1)\cdot(n-1)+1$ & No\
& 2 & 2 & 2 (connected; optimal) & Yes\
Democratic & 3 & $n/4$ & $n-1$ & ?\
(Sec. \[sec:dem-fairness\]) & 4 & $n/3$ & $3n/2-2$ & ?\
& Any & $n\cdot\frac{k/2-1}{k-1}$ & $(k-1)\cdot(n/2-1)+1$ & ?\

Model and Notation {#sec:Model-and-Notation}
==================

The cake to be divided is $C$. As in many cake-cutting papers, $C$ is assumed to be the unit interval $[0,1]$.

The total number of agents in *all* families is $n$.

Every agent $i\in\{1,...,n\}$ has a personal value function $V_i$, defined on the Borel subsets of $C$. The $V_i$ are assumed to be *absolutely continuous with respect to the length measure* (or simply *continuous*). This implies that all singular points have a value of 0 to all agents (a property often termed *non-atomicity*).

Additionally, the value functions are assumed to be *additive* - the value of a union of two disjoint pieces is the sum of the values of the pieces.

The continuity and additivity assumptions are common to most cake-cutting papers. [^4]

The number of families is $k$. The families are called $F_j$, $j\in\{1,...,k\}$. The number of members in family $F_j$ is $n_j$. Each agent is a member of exactly one family, so $n=\sum_{j=1}^{k}n_j$.

An *allocation* is a vector of $k$ pieces, $X=(X_1,\dots,X_k)$, one piece per family, such that the $X_i$ are pairwise-disjoint and $\cup_{i}{X_{i}} = C$.

Ideally, we would like that each piece be connected (i.e, an interval). If this is not possible, then each piece should be a finite union of intervals, where the total number of components (intervals) should be as small as possible.

In the division procedures presented here, it is assumed that all agents act according to their true value functions and not strategically. Designing cake-cutting mechanisms that take agents’ strategies into account is a challenging task even for individual agents [@Branzei2015Dictatorship] and we leave it to future work.

Average fairness {#sec:AM-fairness}
================

In this section we prove Theorem 1. We assume that the value functions of the agents are additive, and define the following family-valuations: $$W_j(X_j)=\frac{\sum_{i\in F_j}V_i(X_j)}{n_j}\,\,\,\,\,\,\,\,\,\,\,\,\,\textrm{{for}\,}\,j\in\{1,...,k\}.$$ A division is called **[average-envy-free]{}** if $\forall j,j': W_j(X_j)\geq W_j(X_{j'})$.

Existence
---------

Given any $n$ additive value functions $V_i$, $i=1,...,n$ and any grouping of the agents to $k$ families, there exists an [average-envy-free]{} division in which each family receives a connected piece (the total number of components is $k$).

Given any $n$ additive value functions $V_i$, the $k$ family-valuations $W_j$ defined above are also additive. Hence, the classic cake-cutting results are applicable: each of the $k$ families in our problem can be treated as an individual agent in the classic solution. For example, Simmons’ protocol [@Su1999Rental] implies the existence of an [average-envy-free]{} division in which each family receives a connected piece.

Non-existence of finite protocols
---------------------------------

While the existence results from classic cake-cutting are applicable in our setting, their *query complexity* is not preserved. The simplest cake-cutting protocol - cut-and-choose - finds a connected envy-free division between two individuals using only two queries (one cuts, the other chooses). However, with two *families* instead of two individuals, any finite number of queries might be insufficient, regardless of the number of components.

\[lemma:infinity-of-average\]For $k\geq2$ families, if at least one family contains at least 2 members, then an [average-envy-free]{} division (with connected or disconnected pieces) cannot be found by a finite protocol.

We prove that the lemma is true even in the simplest case in which there are two families. Suppose one family, e.g. $F_1$, has two members: $F_1=\{1,2\}$, so their family valuation is: $W_1 = (V_1+V_2)/2$. Also suppose that the valuation of each member of $F_2$ is $W_1$, so that their family valuation is $W_2\equiv W_1$. For convenience, assume here that the agents’ valuations are normalized such that the value of the entire cake is 1. Finding an [average-envy-free]{} division now amounts to finding a piece $X\subseteq C$ such that $W_1(X)=W_2(X)=1/2$. This is equivalent to finding a piece $X\subseteq C$ such that $V_1(X)+V_2(X)=1$. Hence, our lemma reduces to the following lemma:

\[lemma:neg-average\]There is no finite protocol that, given two agents with value measures $V_1$ and $V_2$ satisfying $V_1(C)=V_2(C)=1$, always finds a piece $X\subseteq C$ such that $V_1(X)+V_2(X)=1$.

Define an *average piece* as a piece $X\subseteq C$ such that: $V_1(X)+V_2(X)=1$. We now prove that finding an average piece might require an infinite number of queries.

Each *eval* or *mark* query involves two points in $[0,1]$: in an eval query, both points are determined by the protocol; in a mark query, one point is replied by the agent. Call these points the “known points” and include the endpoints 0 and 1 in the set of known points. Let $P_{m}$ be the set of known points before step $m$. Initially $P_{1}=\{0,1\}$. Each query potentially increases $P_{m}$ by at most two points. For example, after a $mark(0.1,v)$ query with a reply of $0.2$, $P_{m}=\{0,0.1,0.2,1\}$. The protocol can be conceptually divided into steps, such that in each step, one point is added to $P_{m}$. Hence, for every $m\geq1$, $|P_{m}|=m+1$.

If the protocol returns a result at step $m$, this result must be a collection of intervals whose endpoints are in $P_{m}$, since the values of subsets with different endpoints are not known to the protocol. Let $I_{m}$ be the set of $m$ intervals whose endpoints are nearby points in $P_{m}$. If the protocol returns at step $m$, the result must be a subset of $I_{m}$. Let $V_{m}=\{V_{1}(X)+V_{2}(X)|X\subseteq I_{m}\}$. I.e, $V_{m}$ is the set of all values of pieces that can be returned by the protocol at step $m$. Note that $V_{m}$ is finite and $|V_{m}|\leq2^{m}$. The protocol can return an average piece at step $m$, if and only if $1\in V_{m}$. We now prove that this cannot be guaranteed in a finite protocol.

The proof is by induction on $m$. For $m=1$, $V_{m}=\{0,2\}$ so $1\notin V_{m}$. $V_{1}$ is illustrated by the dots:

(210,20) (0,10)(200,10) (0,15) (0,5)[0]{} (100,5)[1]{} (200,15)(200,5)[2]{}

Suppose the claim is true for $m$. Then $V_{m}$ is a set of values that does not contain 1, e.g:

(210,20) (0,10)(200,10) (0,15) (0,5)[0]{} (30,15) (50,15) (110,15) (160,15) (190,15) (195,15) (100,5)[1]{} (200,15)(200,5)[2]{}

At step $m$, the protocol adds to $P_{m}$ a new point $q$, such that $P_{m+1}=P_{m}\cup\{q\}$. This replaces an interval in $I_{m}$ with two smaller intervals, e.g. if $q\in[p,r]$ and $[p,r]\in I_{m}$, then $I_{m+1}=I_{m}\setminus\{[p,r]\}\cup\{[p,q],[q,r]\}$. Let $v_{p}:=V_{1}([p,q])+V_{2}([p,q])$ and $v_{r}:=V_{1}([q,r])+V_{2}([q,r])$. Then:

$$\begin{aligned}
V_{m+1}\subset V_{m}\cup\{v-v_{p}|v\in V_{m}\}\cup\{v+v_{p}|v\in V_{m}\}\cup\{v-v_{r}|v\in V_{m}\}\cup\{v+v_{r}|v\in V_{m}\}\end{aligned}$$

I.e, the new possible values are the previous possible values, plus or minus the values of the new intervals (since the new intervals can be added or subtracted from any piece).

Suppose step $m$ is a mark query sent to agent 1. This means that the protocol can control the values $V_{1}([p,q]),\,V_{1}([q,r])$. It cannot, however, control the values $V_{2}([p,q]),\,V_{2}([q,r])$ since the query can be sent to only one agent at a time. Similarly, if the query is sent to agent 2 then the protocol can control $V_{2}([p,q]),\,V_{2}([q,r])$ but not $V_{1}([p,q]),\,V_{1}([q,r])$. In both cases, the protocol cannot control $v_{p},v_{r}$. This means that for every protocol, there can be value measures such that the new values added to $V_{m}$ do not include 1, so $1\notin V_{m+1}$:

(210,20) (0,10)(200,10) (0,15) (0,5)[0]{} (26,15) (30,15) (34,15) (46,15) (50,15) (54,15) (106,15) (110,15) (114,15) (156,15) (160,15) (164,15) (190,15) (195,15) (100,5)[1]{} (200,15)(200,5)[2]{}

To conclude: after any finite number $m$ of steps, the set of possible piece values $V_{m}$ is finite, and an adversary can select the value measures such that it does not contain 1. Hence finding an average piece cannot be guaranteed.

#### Note:

A similar idea was used by [@Robertson1998CakeCutting] to prove that it is impossible to find an exact division with a finite number of queries.

Unanimous fairness {#sec:unan-fairness}
==================

This section proves Theorem 2. A division is called **[unanimous-envy-free]{}** if: $$\begin{aligned}
\forall j,j'=1,...,k: \forall i\in F_j: V_i(X_j)\geq V_i(X_{j'})\end{aligned}$$

We denote by [UnanimousEnvyFree]{}$(n,k)$ the problem of finding a [unanimous-envy-free]{} division when there are $n$ agents grouped in $k$ families. We relate this problem to the classic cake-cutting problem of finding an *exact division*:

[Exact]{}$(N,K)$ is the following problem. Given $N$ agents and an integer $K$, find a division of the cake to $K$ pieces, such that each of the $N$ agents assigns exactly the same value to all pieces: $$\begin{aligned}
\forall j,j'=1,...,K:\,\,\forall i=1,...,N:\,\,V_{i}(X_{j})=V_{i}(X_{j'}).\end{aligned}$$

Alon [@Alon1987Splitting] proved that for every $N$ and $K$, [Exact]{}$(N,K)$ has a solution with at most $N(K-1)+1$ components. He also showed that this number is the smallest that can be guaranteed. We now use these results in our setting. To this end, we show a two-way reduction between the problem of [unanimous-envy-free]{} division and the problem of exact division.

\[lemma:exact-implies-unprop\] For each $n,k$, a solution to [Exact]{} $(n-1,k)$ implies a solution to [UnanimousEnvyFree]{} $(n,k)$ for any grouping of the $n$ agents to $k$ families.

Suppose we are given an instance of [UnanimousEnvyFree]{}$(n,k)$, i.e, $n$ agents in $k$ families. Select $n-1$ agents arbitrarily. Use [Exact]{}$(n-1,k)$ to find a partition of the cake to $k$ pieces, such that each of the $n-1$ agents is indifferent between these $k$ pieces. Ask the $n$-th agent to choose his favorite piece. Give that piece to the family of the $n$-th agent. Give the other $k-1$ pieces arbitrarily to the remaining $k-1$ families. The division is [unanimous-envy-free]{}.

Combining this lemma with the result of [@Alon1987Splitting] immediately implies the following upper bound on the number of required components:

\[cor:minprop-general\] Given $n$ agents in $k$ families, there exists a [unanimous-envy-free]{} division with at most $(k-1)\cdot(n-1)+1$ components.

\[lemma:unprop-implies-exact\] For each $N,K$, a solution to [UnanimousEnvyFree]{} $(N(K-1)+1,\,K)$ implies a solution to [Exact]{} $(N,K)$.

Given an instance of [Exact]{}$(N,K)$ ($N$ agents and a number $K$ of required pieces), create $K$ families. In each of the first $K-1$ families, put a copy of each of the $N$ agents. In the $K$-th family, put a single agent whose value measure is the average of the given $N$ value measures:

$$V^{*}=\frac{1}{N}\sum_{i=1}^{N}V_{i}.$$ The total number of agents in all $K$ families is $N(K-1)+1$. Use [UnanimousEnvyFree]{} $(N(K-1)+1,\,K)$ to find a [unanimous-envy-free]{} division, X. By the pigeonhole principle, for each agent $i$ in family $j$: $V_i(X_j) \geq 1/K$.

By construction, each of the first $K-1$ families has a copy of agent $i$. Hence, all $N$ agents values each of the first $K-1$ pieces as at least $1/K$ and:

$$\forall i=1,...,N:\,\,\,\,\,\,\sum_{j=1}^{K-1}V_{i}(X_{j})\geq\frac{K-1}{K}.$$ Hence, by additivity, every agent values the $K$-th piece as at most $1/K$:

$$\forall i=1,...,N:\,\,\,\,\,\,V_{i}(X_{K})\leq1/K.$$ The piece $X_{K}$ is given to the agent with value measure $V^{*}$, so again by the pigeonhole principle: $V^{*}(X_{K})\geq1/K$. By construction, $V^{*}(X_{K})$ is the average of the $V_{i}(X_{K})$. Hence, necessarily:

$$\forall i=1,...,N:\,\,\,\,\,\,V_{i}(X_{K})=1/K.$$ Again by additivity:

$$\forall i=1,...,N:\,\,\,\,\,\,\sum_{j=1}^{K-1}V_{i}(X_{j})=\frac{K-1}{K}.$$ Hence, necessarily:

$$\forall i=1,...,N,\,\,\,\,\,\forall j=1,...,K-1:\,\,\,\,\,\,V_{i}(X_{j})=1/K.$$ So we have found an exact division and solved [Exact]{}$(N,K)$ as required.

@Alon1987Splitting proved that for every $N$ and $K$, an [Exact]{}$(N,K)$ division might require at least $N(K-1)+1$ components. Combining this result with the above lemma implies the following negative result:

\[cor:neg-unprop\] For every $N,K$, let $n=N(K-1)+1$. A [unanimous-envy-free]{} division for $n$ agents in $K$ families might require at least $n$ components.

This corollary implies that, in particular, [unanimous-envy-freeness]{} with connected pieces is infeasible. This impossibility result is generalized in Lemma \[thm:neg-majority\].

Infinite procedures and approximations
--------------------------------------

It is impossible to solve [Exact]{}$(N,K)$ by a finite protocol whenever $N\geq2$ and $K\geq2$ [@Robertson1998CakeCutting pp. 103-104]. By Lemma \[lemma:unprop-implies-exact\], this implies:

[UnanimousEnvyFree]{} cannot be solved by a finite protocol whenever $n>k$.[^5]

However, there is an approximation procedure that converges to an exact division of a cake to $k=2$ pieces [@Simmons2003Consensushalving]. By Lemma \[lemma:exact-implies-unprop\], this procedure can be used to find an approximate [unanimous-envy-free]{} division for two families.

Democratic fairness {#sec:dem-fairness}
===================

In this section we prove Theorem 3. A division X is called **[democratic-envy-free]{}** if for all $j,j'=1,...,k$, for at least half the members $i\in F_j$: $$\begin{aligned}
V_i(X_j)\geq V_i(X_{j'})\end{aligned}$$

Existence and number of components
----------------------------------

Given a specific allocation of cake to families, define a *positive* agent as an agent that values his family’s share as more than 0. Note that this is a much weaker requirement than proportionality. Define a *zero* agent as a non-positive agent.

\[thm:neg-majority\] Assume there are $n=mk$ agents, divided into $k$ families with $m$ members in each family. To guarantee that at least $q$ members in each family are positive, the total number of components might have to be at least: $$\begin{aligned}
    k\cdot\frac{kq-m}{k-1}
    \end{aligned}$$

Number the families by $j=0,...,k-1$ and the members in each family by $i=0,...,m-1$. Assume that the cake is the 1-dimensional interval $[0,mk]$. In each family $j$, each member $i$ wants only the following interval: $(ik+j,\,ik+j+1)$. Thus there is no overlap between desired pieces of different members. The table below illustrates the construction for $k=2,\,m=3$. The families are {Alice,Bob,Charlie} and {David,Eva,Frankie}:

    Alice    1   0   0   0   0   0
  --------- --- --- --- --- --- ---
     Bob     0   0   1   0   0   0
   Charlie   0   0   0   0   1   0
    David    0   1   0   0   0   0
     Eva     0   0   0   1   0   0
   Frankie   0   0   0   0   0   1

Suppose the piece $X_j$ (the piece given to family $j$) is made of $l\geq1$ components. We can make $l$ members of $F_j$ positive using $l$ intervals of positive length inside their desired areas. However, if $q>l$, we also have to make the remaining $q-l$ members positive. For this, we have to extend $q-l$ intervals to length $k$. Each such extension totally covers the desired area of one member in each of the other families. Overall, each family creates $q-l$ zero members in each of the other families. The number of zero members in each family is thus $(k-1)(q-l)$. Adding the $q$ members which must be positive in each family, we get the following necessary condition: $(k-1)(q-l)+q\leq m$. This is equivalent to: $$\begin{aligned}
    l\geq\frac{kq-m}{k-1}.
    \end{aligned}$$ The total number of components is $k\cdot l$, which is at least the expression stated in the Lemma.

In a [unanimous-envy-free]{} division, all members in each family must be positive. Taking $q=m$ gives $l\geq m$ and the number of components is at least $km=n$, which is the bound of Corollary \[cor:neg-unprop\]. In a [democratic-envy-free]{} division, at least half the members in each family must be positive. Taking $q=m/2$ gives:

\[cor:neg-majority\] In a [democratic-envy-free]{} division with $n$ agents grouped into $k$ families, the number of components might have to be at least $$\begin{aligned}
n\cdot\frac{k/2-1}{k-1}.\end{aligned}$$

Note that when $k=2$, the lower bound of Corollary \[cor:neg-majority\] is 0. Indeed, for two families there always exist [democratic-envy-free]{} divisions with connected pieces. This is proved in the next subsection.

Division procedure
------------------

Algorithm \[alg:majprop\] describes a procedure that achieves a [democratic-envy-free]{} division for two families. For each family, a location $M_j$ is calculated such that, if the cake is cut at $M_j$, half the members value the interval $[0,M_j]$ as at least $1/2$ and the other half value the interval $[M_j,1]$ as at least $1/2$. Then, the cake is cut between the two family medians, and each family receives the piece containing its own median. By construction, at least half the members in each family value their family’s share as at least 1/2, so the division is [democratic-envy-free]{}.

The division has only 2 components (each family receives a connected piece). In contrast to the impossibility results of the previous sections, this protocol is *finite*. In fact, it requires only $n$ mark queries (one query per agent).

INPUT:

- A cake, which is assumed to be the unit interval $[0,1]$.

- $n$ agents, all of whom value the cake as 1.

- A grouping of the agents to $2$ families, $F_1,F_2$.\
OUTPUT:

A [democratic-envy-free]{} division of the cake to $2$ pieces.\
ALGORITHM:

- Each agent $i=1,...,n$ marks an $x_{i}\in[0,1]$ such that $V_i([0,x_{i}])=V_i([x_{i},1])=1/2$.

- For each family $j=1,2$, find the median of its members’ marks: $M_{j}=\textrm{{median}}_{i\in F_j}x_{i}$. Find the median of the family medians: $M^{*}=(M_1+M_2)/2$.

- If $M_1<M_2$ then give $[0,M^*]$ to $F_1$ and $[M^*,1]$ to $F_2$.\
Otherwise give $[0,M^*]$ to $F_2$ and $[M^*,1]$ to $F_1$.

The above procedure does not work for more than 2 families. Currently, all we have is the following existence result, which is a trivial outcome of the existence results of Section \[sec:unan-fairness\]. Apply these results with $n/2$ instead of $n$: select half of the members in each family arbitrarily, then find a division which is [unanimous-envy-free]{} for them while ignoring all other members. Hence:

\[cor:mjef-general\] Given $n$ agents in $k$ families, there exists a [democratic-envy-free]{} division with at most $(k-1)\cdot(n/2-1)+1$ components.

It is an interesting open question whether a [democratic-envy-free]{} division for 3 or more families (with disconnected pieces) can be found by a finite protocol.

Alternatives
============

Instead of envy-freeness, it is possible to use *proportionality* as the basic fairness criterion. Proportionality means that, when there are $k$ families, each family receives at least $1/k$ of its total cake value. Then, **[average-proportionality]{}** means that the average value of each family in its allocated share (averaged over all family members) is at least $1/k$ of the average value of the entire cake; **[unanimous-proportionality]{}** means that every agent values its family’s share as at least $1/k$ of the total; **[democratic-proportionality]{}** is defined analogously. When the valuations are additive, envy-freeness implies proportionality; when there are only two families, proportionality implies envy-freeness. Theorem 1 (Section \[sec:AM-fairness\]) holds as-is for [average-proportionality]{}. In Theorems 2 and 3, the number of components in the positive results can be improved from $O(n k)$ to $O(n \log k)$, using a recursive halving technique. See [@SegalHalevi2016FamilyProportional] for details.

The above criteria assume that all families have equal entitlements. This makes sense, for example, when $k$ siblings inherit their parents’ estate. While an heir will probably like to take his family’s preferences into account when selecting a share, each heir is entitled to exactly $1/k$ of the estate regardless of the size of his/her family. In general, each family may have a different entitlement. The entitlement of a family may depend on its size but may also depend on other factors. For example, when two states jointly discover a new island, they will probably want to divide the island between them in proportion to their investments and not in proportion their population. This generalized problem can be solved by applying results in cake-cutting with unequal entitlements. In particular, Stromquist and Woodall [@Stromquist1985Sets] prove that, for every fraction $r\in[0,1]$, it is possible to cut a piece of cake made of at most $n$ intervals, which each agent values as exactly $r$ of the total cake value. This result can be used to generalize our theorems to families with different entitlements. See [@SegalHalevi2016FamilyProportional] for details.

One could consider the following alternative fairness criterion: an allocation is *individually-proportional* if the allocation $X=(X_{1},\ldots,X_{k})$ admits a refinement $Y=(Y_{1},\ldots,Y_{n})$, where for each family $F_{j}$, $\cup_{i\in F_{j}}Y_{i}=X_{j}$, such that for each agent $i$, $V_{i}(Y_{i})\geq1/n$. Individually-proportional allocations always exist and can be found by using any classic proportional cake-cutting procedure on the individual agents, disregarding their families. The number of components is at most $n$. Individual-proportionality makes sense if, after the land is divided among the families, each family intends to further divide its share among its members. However, often this is not the case. When an inherited land-estate is divided between two families, the members of each family intend to live and use their entire share together, rather than dividing it among them. Therefore, the happiness of each family member depends on the entire value of his family’s share, rather than on the value of a potential private share he would get in a hypothetic sub-division.

Related Work {#sec:related}
============

There are numerous papers about fair division in general and fair cake-cutting in particular. We mentioned some of them in the introduction. Here we survey some work that is more closely related to family-based fairness.

Group-envy-freeness and on-the-fly coalitions
---------------------------------------------

[@Berliant1992Fair; @Husseinov2011Theory] study the concept of *group-envy-free* cake-cutting. Their model is the standard cake-cutting model in which the cake is divided among *individuals* (and not among families as in our model). They define a group-envy-free division as a division in which no coalition of individuals can take the pieces allocated to another coalition with the same number of individuals and re-divide the pieces among its members such that all members are weakly better-off. Coalitions are also studied by [@DallAglio2009Cooperation; @DallAglio2012Finding].

In our setting, the families are pre-determined and the agents do not form coalitions on-the-fly. In an alternative model, in which agents *are* allowed to form coalitions based on their preferences, the family-cake-cutting problem becomes easier. For instance, it is easy to achieve a [unanimous-proportional]{} division with connected pieces between two coalitions: ask each agent to mark its median line, find the median of all medians, then divide the agents to two coalitions according to whether their median line is to the left or to the right of the median-of-medians.

Fair division with public goods
-------------------------------

In our setting, the piece given to each family is considered a “public good” in this specific family. The existence of fair allocations of homogeneous goods when some of the goods are public has been studied e.g. by @Diamantaras1992Equity [@Diamantaras1994Generalization; @Diamantaras1996Set; @Guth2002NonDiscriminatory]. In these studies, each good is either private (consumed by a single agent) or public (consumed by all agents). In the present paper, each piece of land is consumed by all agents in a single family - a situation not captured by existing public-good models.

Family preferences in matching markets
--------------------------------------

Besides land division, family preferences are important in matching markets, too. For example, when matching doctors to hospitals, usually a husband and a wife want to be matched to the same hospital. This issue poses a substantial challenge to stable-matching mechanisms [@Klaus2005Stable; @Klaus2007Paths; @Kojima2013Matching].

Fairness in group decisions
---------------------------

The notion of fairness between groups has been studied empirically in the context of the well-known *ultimatum game*. In the standard version of this game, an individual agent (the *proposer*) suggests a division of a sum of money to another individual (the *responder*), which can either approve or reject it. In the group version, either the proposer or the responder or both are groups of agents. The groups have to decide together what division to propose and whether to accept a proposed division.

Experiments by [@Robert1997Group; @Bornstein1998Individual] show that, in general, groups tend to act more rationally by proposing and accepting divisions which are less fair. [@Messick1997Ultimatum] studies the effect of different group decision rules while [@Santos2015Evolutionary] uses a threshold decision rule which is a generalized version of our majority rule (an allocation is accepted if at least $M$ agents in the responder group vote to accept it).

These studies are only tangentially relevant to the present paper, since they deal with a much simpler division problem in which the divided good is *homogeneous* (money) rather than heterogeneous (cake/land).

Non-additive utilities
----------------------

As explained in Sections \[sec:unan-fairness\] and \[sec:dem-fairness\], the difficulty with [unanimous-envy-freeness]{} and [democratic-envy-freeness]{} is that the associated family-valuation functions are not additive. It is interesting to compare our work to other works on cake-cutting with non-additive valuations.

[@Berliant1992Fair; @Maccheroni2003How; @DallAglio2005Fair] focus on sub-additive, or concave, valuations, in which the sum of the values of the parts is *more* than the value of the whole. These works are not applicable to the family-cake-cutting problem, because the family-valuations are not necessarily sub-additive - the sum of values of the parts might be less than the value of the whole.

[@Sagara2005Equity; @DallAglio2009Disputed; @Husseinov2013Existence] consider general non-additive value functions. They provide pure existence proofs and do not say much about the nature of the resulting divisions (e.g, the number of connectivity components), which we believe is important in practical division applications.

[@Su1999Rental] presents a protocol for envy-free division with connected pieces which does not assume additivity of valuations. However, when the valuations are non-additive, there are no guarantees about the value per agent. In particular, with non-additive valuations, the resulting division is not necessarily proportional.

[@Mirchandani2013Superadditivity] suggests a division protocol for non-additive valuations using non-linear programming. However, the protocol is practical only when the cake is a collection of a small number of *homogeneous* components, where the only thing that matters is what fraction of each component is allocated to each agent. Our model is the standard, general model where the cake is a single *heterogeneous* good.

Finally, [@Berliant2004Foundation; @Caragiannis2011Towards; @SegalHalevi2015EnvyFree] study specific non-additive value functions which are motivated by geometric considerations (location, size and shape). The present paper contributes to this line of work by studying specific non-additive value functions which are motivated by a different consideration: handling the different preferences of family members. A possible future research topic is to find fair division rules that handle these considerations simultaneously, as both of them are important for fair division of land.

Conclusions
===========

One practical conclusion that can be drawn from our results concerns the selection of fairness criterion. When $n$ (the total number of agents) is sufficiently small, it is reasonable to use unanimous-fairness, which guarantees that all agents are satisfied with their family’s share. However, when $n$ is large, as is the case when dividing land between states, insisting on unanimous-fairness might result in each country having an absurdly fractioned territory. In this case, democratic-fairness is a more reasonable choice. This is particularly true when there are only two states, since in this case democratic-fairness can be achieved with connected pieces and in finite time, which is impossible with the other fairness criteria.

Acknowledgements
================

This research was funded in part by the following institutions: The Doctoral Fellowships of Excellence Program at Bar-Ilan University, the Mordechai and Monique Katz Graduate Fellowship Program, and the Israel Science Fund grant 1083/13. We are grateful to Yonatan Aumann, Avinatan Hassidim, Noga Alon, Christian Klamler, Ulle Endriss and Neill Clift for helpful discussions.

This paper started with a discussion in the MathOverflow website.[^6] We are grateful to the members that participated in the discussion: Pietro Majer, Tony Huynh and Manfred Weis. Other members of the StackExchange network contributed useful answers and ideas: Alex Ravsky, Andrew D. Hwang, BKay, Christian Elsholtz, Daniel Fischer, David K, D.W, Hurkyl, Ittay Weiss, Kittsil, Michael Albanese, Raphael Reitzig, Real, babou, Dömötör Pálvölgyi (domotorp), Ian Turton (iant) and ivancho.

[^1]: Wikipedia page “IndiaBangladesh enclaves”.

[^2]: Wikipedia page “Baarle-Hertog”. Many other examples are listed in Wikipedia page “List of enclaves and exclaves”. We are grateful to Ian Turton for the references.

[^3]: Without this assumption, the problem is equivalent to cake-cutting among individuals.

[^4]: A third common assumption is that the valuations are normalized such that for every agent $i$: $V_i(C)=1$. The results of the present paper do not rely on this assumption.

[^5]: Because $N(K-1)+1>K$ iff $(N-1)(K-1)>0$ iff $N\geq2$ and $K\geq2$.

[^6]: http://mathoverflow.net/questions/203060/fair-cake-cutting-between-groups
