HIAS-E-79

Fair Cake-Cutting among Families
Erel Segal-Halevi(a) and Shmuel Nitzan(b),(c)(a) Department of Computer Science, Ariel University, Ariel 40700, Israel(b) Department of Economics, Bar Ilan University, Ramat Gan 52900, Ierael(c) Hitotsubashi Institute for Advanced Study, Hitotsubashi University

November, 2018

Hitotsubashi Institute for Advanced Study, Hitotsubashi University
2-1, Naka, Kunitachi, Tokyo 186-8601, Japan
tel:+81 42 580 8604
http://hias.ad.hit-u.ac.jp/
HIAS discussion papers can be downloaded without charge from:http://hdl.handle.net/10086/27202
https://ideas.repec.org/s/hit/hiasdp.html

All rights reserved.


Noname manuscript No.
(will be inserted by the editor)

Fair Cake-Cutting among Families
Erel Segal-Halevi · Shmuel Nitzan
Received: date / Accepted: date
Abstract We study the fair division of a continuous resource, such as a landestate or a time-interval, among pre-specified groups of agents, such as families.
Each family is given a piece of the resource and this piece is used simultaneously by all family members, while di⇥erent members may have di⇥erent valuefunctions. Three ways to assess the fairness of such a division are examined.
(a) *Average fairness* means that each family’s share is fair according to the”family value function”, defined as the arithmetic mean of the value functionsof the family members. (b) *Unanimous fairness* means that all members
in all families feel that their family received a fair share according to theirpersonal value function. (c) *Democratic fairness* means that in each family,
at least half the members feel that their family’s share is fair. We compare
these criteria based on the number of connected components in the resulting
division, and based on their compatibility with Pareto-e⇤ciency.
This research was funded in part by the following institutions: The Doctoral Fellowshipsof Excellence Program at Bar-Ilan University, the Mordechai and Monique Katz Graduate
Fellowship Program, and the Israel Science Foundation grant 1083/13.
We are grateful to Galya Segal-Halevi, Yonatan Aumann, Avinatan Hassidim, Noga
Alon, Christian Klamler, Ulle Endriss, Neill Clift and Sophie Bade for helpful discussions.
This paper started with a discussion in the MathOverflow website at
http://mathoverflow.net/questions/203060/fair-cake-cutting-between-groups . We are
grateful to the members who participated in the discussion: Pietro Majer, Tony Huynh andManfred 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, Domotor Palvolgyi (domotorp), Ian Turton (iant) and ivancho.
Erel Segal Halevi: Department of Computer Science, Ariel University, Ariel 40700, Israel,erelsgl@gmail.com.
Shmuel Nitzan: Department of Economics, Bar Ilan University, Ramat Gan 52900, Israeland Hitotsubashi Institute for Advanced Study, Hitotsubashi University. nitzans@biu.ac.il.

2Erel Segal-Halevi, Shmuel Nitzan

Keywords fair division, cake-cutting, public good, club good, fair-share,no-envy

1 Introduction
Fair division of heterogeneous resources among agents with di⇥erent preferences has been an important issue since Biblical times. Today it is an active
area of research in the interface of computer science (Robertson and Webb
1998; Procaccia 2015) and economics (Moulin 2004). Its applications range
from politics (Brams and Taylor 1996) to multi-agent systems (Chevaleyre
et al 2006).
In most fair division problems, the resource is divided among n individual
agents, and the fairness of a division is assessed based on their individual
preferences. A common fairness criterion is the fair share (FS). It requiresthat each agent receives a share that is at least as good as 1/n of the total
endowment, according to the agent’s individual preferences.1
In practice, however, goods are often owned and used by groups. As an
example, consider a land-estate inherited by k families, a river that has tobe divided among k states, or the usage-time of a conference room that has
to be divided among k meeting groups. The resource (whether land or time)should be divided to k pieces, one piece per group. Each group’s share is thenused by all its members simultaneously. The land-plot allotted to a family
is inhabited by the entire family. The share of the river allotted to a state
becomes a national park open to all its citizens. In the time-slot allotted to agroup, the conference room is used by all group members.2
The happiness of each group member depends on his/her valuation of theentire share of the group. But, in each group there are di⇥erent members withdi⇥erent valuations. The group’s share can be valued by some of its members
as at least 1/k of the total and by others as less than 1/k of the total. How,
then, should the fairness of a division be assessed?
The present paper studies this question in the classic setting of cake-cutting,introduced by Steinhaus (1948). In this setting, there is a measurable space(e.g. an interval or a polygon) called the cake. The preferences of each agent
are represented by a value-measure on the cake. We study three ways to assess
the fairness of a division.
First, it is possible to aggregate the valuations in each family to a single family valuation. Following the utilitarian tradition (Bentham 1789), thefamily-valuation can be defined as the sum or (equivalently) the arithmetic
average of the valuations of all family members. We call a division averagefair if it is fair according to these family valuations. In particular, a division
is average-FS if every family receives a share with an average value (averaged
1 The condition of receiving at least 1/n of the total endowment was introduced by Steinhaus (1948). Economists often call it fair-share guarantee (Bogomolnaia et al 2017). Computer scientists often call it proportionality (Robertson and Webb 1998).
2 In economic terms, the allotted piece becomes a ”club good” (Buchanan 1965).

Fair Cake-Cutting among Families

3

over all family members) of at least 1/k of its average value of the entire
endowment.
By this definition, the family-division problem is easy to solve. Since theaverage of measures is itself a measure, each family can be represented by asingle agent, and the problem reduces to fair division among the k representatives. Classic results imply that average-FS allocations exist (Section 3).
Average fairness makes sense only when 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 Moulin (2004) for some real-life examples of suchsituations). However, if the valuations represent individual happiness measuresthat cannot be put on a common scale, then their sum is meaningless, andother fairness criteria should be used.
A second option is to require that all members of every family agree thatthe division is fair. We call a division unanimous fair if it is fair according toevery individual valuation. In particular, a division is unanimous-FS if every
agent values his/her family’s share as at least 1/k of the total value. The advantage of this definition is that it does not need to assume that all valuations
share a common scale. Even though it is a very strong requirement, we provethat unanimous-FS allocations exist (Section 4).
A disadvantage of unanimous fairness, compared to average fairness, isthat unanimously-fair divisions might be highly fractioned. As an illustration,
when an interval is divided, there always exists an average-FS division thatis also connected — the share of each family is a single interval (Section 3).
However, we prove that there might not exist connected unanimous-FS divisions. Moreover, in some cases, the number of intervals in any unanimous-FS
division might be at least n — the number of individual agents (Section 4).
When the number of agents is large, as in the case of dividing land amongstates, such divisions might be impractical.
In democratic societies, decisions are almost never accepted unanimously.
In fact, when the number of citizens is large, it may be impossible to attainunanimity on even the most trivial issue. The simplest decision rule in suchsocieties is the majority rule. Inspired by this rule, we suggest a third fairness
criterion. We call a division democratic fair if at least half the citizens ineach family consider it fair. In particular, a division is democratic-FS if at
least half the agents in each family value their family’s share as at least 1/kof the total.
Democratic fairness can be justified by the following process. After a division is proposed, each group conducts a referendum in which each citizen
approves the division if he/she feels that the division is fair. The division is
implemented only if, in every group, at least half of its members approve it.
Democratic-fairness combines some advantages of average-fairness and unanimous-fairness. It is similar to unanimous-fairness in that it does not need toassume that all valuations share a common scale. When there are k = 2 families, it is similar to average-fairness in that it can be satisfied with connected
pieces — there always exists a democratic-FS division in which each family re-4Erel Segal-Halevi, Shmuel Nitzan

ceives a single connected piece. An additional advantage of democratic fairness
in this case is that it can be computed e⇤ciently (Section 5).3
Although democratic-fairness might leave up to half the citizens unhappy,
this may be unavoidable in real-life situations. This is understandable in lightof Winston Churchil’s dictum: “democracy is the worst form of government,
except all the others that have been tried”.4
While the geometric requirement of having a connected division is practically important, an even more important requirement from an economic perspective is Pareto-e⇤ciency. We prove that all three variants of fair-share arecompatible with Pareto-e⇤ciency (Section 6).
A second fairness criterion that is very common in economics is no envy
(NE). In the context of individual agents, it means that each agent receives ashare that is at least as good as the share of any other agent, according to thefirst agent’s individual valuation.5 In the context of families, three variants of
NE can be defined analogously to the three variants of fair-share: average-NE,
unanimous-NE and democratic-NE (Section 7).
From a geometric perspective, these three variants behave similarly to their
FS counterparts, that is:– Connected average-NE allocations always exist;– Connected unanimous-NE allocations are not guaranteed to exist even for
two families;– Connected democratic-NE allocations are guaranteed to exist for two but
not for three or more families.
However, from an economic perspective, NE behaves di⇥erently:– Pareto-e⇤cient average-NE allocations always exist;– Pareto-e⇤cient unanimous-NE allocations are guaranteed to exist for two
but not for three or more families;– Pareto-e⇤cient democratic-NE allocations are guaranteed to exist for two
but not for five or more families (we do not know whether they always
exist with three or four families).
3 In contrast, average-fair and unanimous-fair allocations cannot be computed by any
finite protocol. See Remark 1.
4 A fourth fairness criterion that could be considered is individual fairness. In particular, an allocation is individually-FS if the allocation X = (X1 , . . . , Xk ) admits a refinement
Y = (Y1 , . . . , Yn ), where for each family Fj , i Fj Yi = Xj , such that for each agent i,
Vi (Yi ) ⇥ 1/n. Individually-fair allocations always exist and can be found by using any classic fair division procedure on the individual agents, disregarding their families. Individualfairness makes sense if, after the division of the land 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 tolive and use their entire share together, rather than dividing it among them. Therefore, thehappiness 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.
5 The condition of receiving at least as much as any other agent was introduced by Gamow
and Stern (1958) and Foley (1967). Economists often call it no envy (Bogomolnaia et al2017). Computer scientists often call it envy-freeness (Robertson and Webb 1998).

Fair Cake-Cutting among Families

5

The paper is organized as follows. Most of the paper focuses on the fairshare criterion. Section 2 formally presents the model. Sections 3, 4 and 5 study
average, unanimous and democratic fair-share divisions respectively. We study
this criterion both for families with equal entitlements and for families thathave di⇥erent entitlements to the resource.
Section 6 studies the three variants of fair-share in combination with Paretoe⇤ciency. Section 7 studies family fairness based on the no-envy criterion,
explaining the di⇥erences between the results for fair-share and for no-envy.
Finally, Section 8 compares our work to previous and ongoing related work.

2 Model and Notation
2.1 Resource and agentsIn the usual cake-cutting setting, there is a resource C (“cake”) that has tobe divided. For simplicity it is assumed that C is an interval in R. A realistic
example of such a resource is time: consider a conference room that can hosta single meeting at a time. It is active between 8:00 and 20:00, and this timeinterval must be divided among all those who want to use the room. Anotherrealistic example is the shoreline of a sea or a river: while usually not a straight
line, it can be easily mapped to an interval.
There is a set of agents N = {1, . . . , n}. Each agent i
N has a value
measure Vi , defined on the Borel subsets of C. The Vi are assumed to be
nonatomic, so that all singular points have a value of 0 to all agents. As theterm measure implies, the Vi are additive — the value of a union of two disjoint
pieces is the sum of the values of the pieces. Such value functions can be viewed
as having a ”constant marginal utility” property (Chambers 2005). The value
measures are normalized such that ⇥i : Vi (⇤) = 0, Vi (C) = 1.
2.2 Families and entitlements
In our setting, there is a set of families F = {F1 , . . . , Fk }. We use the term
“family” to emphasize that the partition of agents to groups is fixed in advanceand cannot be modified during the division process.
The number of agents in Fj is denoted nj . Each agent i N is a memberkof exactly one family Fj F , so n = j=1 nj .
For each family Fj , there is a positive weight wj representing the entitlek
ment of this family. The sum of all weights is one: 1 = j=1 wj .
In the simplest setting, the families have equal entitlements, i.e, for eachj {1, . . . , k}: wj = 1/k. Equal entitlements make sense, for example, whenk siblings inherit their parents’ estate. While an heir will probably like totake his family’s preferences into account when selecting a share, each heir isentitled to 1/k of the estate regardless of the size of his/her family.

6

Erel Segal-Halevi, Shmuel Nitzan

In general, each family may have a di⇥erent entitlement. The entitlementof a family may depend on its size but may also depend on other factors. For
example, consider several families who jointly buy a vacation apartment. Theapartment can host one family at a time, so the families have to divide theyear (a time-interval) among them. The entitlement of each family naturally
depends on the amount of money it contributed to the purchase, rather thanon the family’s size.6

2.3 Allocations and components
An allocation is a vector of k pieces, X = (X1 , . . . , Xk ), one piece per family,such that the Xj are pairwise-disjoint and ⌅j Xj = C.
Each piece is a finite union of intervals. We denote by Comp(Xj ) the
number of connected components (intervals) in the piece Xj , and by Comp(X)the total number of components in the allocation X, i.e:Comp(X) =k⇥

Comp(Xj )j=1

Ideally, we would like that each piece be connected, i.e, ⇥i : Comp(Xi ) =1 and Comp(X) = k. This requirement is especially meaningful when thedivided resource is a time-interval or a land-resource (e.g. a river-bank), sincea contiguous piece of time or land is much easier to use than a collection of
disconnected patches.
However, we will show that a fair division with connected pieces is notalways possible.7 In case a division with connected pieces is not possible, it
is still desirable that the number of connectivity components — Comp(X) —be as small as possible. When dividing an interval, the components are subintervals and their number is one plus the number of cuts. Hence, the numberof components is minimized by minimizing the number of cuts (Robertson
and Webb 1995; Webb 1997; Shishido and Zeng 1999; Barbanel and Brams
2004, 2014). In a realistic, 3-dimensional world, the additional dimensions canbe used to connect the components, e.g, by bridges or tunnels. Still, it is
6 See Cseh and Fleiner (2017) for a recent account of fair division among individual agentswith di⇤erent entitlements.
7 This impossibility appears not only in our one-dimensional theoretic model but alsoin practical, two-dimensional land division situations. A striking example was the IndiaBangladesh border. According to Wikipedia page India–Bangladesh enclaves, up to 2015,“Within the main body of Bangladesh were 102 enclaves of Indian territory, which inturn contained 21 Bangladeshi counter-enclaves, one of which contained an Indian countercounter-enclave... within the Indian mainland were 71 Bangladeshi enclaves, containing 3
Indian counter-enclaves”. Another example is Baarle-Hertog — a Belgian municipality madeof 24 separate parcels of land, most of which are exclaves in the Netherlands. For more details and examples see the Wikipedia page List of enclaves and exclaves. We are grateful to
Ian Turton for the references.

Fair Cake-Cutting among Families

7

desirable to minimize the number of components in the original division inorder to reduce the number of required bridges/tunnels.8
2.4 Fairness criteria
We first define the family-valuation functions:
Wjavg (Xj ) =i Fj Vi (Xj )

nj

for j

{1, ..., k}.

Now, an allocation X is called:
average-FS
unanimous-FS

if ⇥j

if ⇥j

{1, . . . , k} :{1, . . . , k} :democratic-FS
if ⇥j {1, . . . , k},for at least half the members i⇥iWjavg (Xj ) ⇧ wj ;Fj : Vi (Xj ) ⇧ wj ;Fj : Vi (Xj ) ⇧ wj .

A property of an allocation is called feasible if for every k families and n agents
there exists an allocation satisfying this property. Otherwise, the property iscalled infeasible. In the following sections we will study the feasibility of theabove fairness criteria.
Note that unanimous-FS obviously implies both average-FS and democratic-FS. The other two do not imply each other, as shown in the following
example.
Example 1 Consider an interval consisting of four sub-intervals. It has to be divided between two families: (1) {Alice,Bob,Chana} and (2) {David,Esther,Frank}.
The families have equal entitlements, i.e, w1 = w2 = 1/2. Each member’s valuation of each sub-interval is shown in the table below:
Alice
Bob
Chana
David
Esther
Frank

60
50
10
3
3
3

30
40
80
3
3
3

3
3
3
60
60
0

3
3
3
30
30
90

Note that the value of the entire interval is 96 according to all agents. Therefore, FS implies that each family should get a value of at least 48.
If the two leftmost subintervals are given to family 1 and the two rightmost
subintervals are given to family 2, then the division is unanimous-FS, sinceeach member of each family feels that his family’s share is worth 90. Thisdivision is also, of course, average-FS and democratic-FS.
8 The goal of minimizing the number of components is pursued not only in cake-cutting
papers but also in real-life politics. Going back to India and Bangladesh, after many yearsof negotiations they finally started to exchange most of their enclaves during the years
2015-2016. This reduced the number of components from 200 to a more reasonable number.

8Erel Segal-Halevi, Shmuel Nitzan

If only the single leftmost subinterval is given to family 1 and the otherthree are given to family 2, then the division is still democratic-FS, since
Alice and Bob feel that their family received more than 48. However, Chanafeels that her family received only 10, so the division is not unanimous-FS.
Moreover, the division is not average-FS since the average valuation of family
1 is only (60+50+10)/3=40.
If the three leftmost subintervals are given to family 1 and only the rightmost one is given to family 2, then the division is average-FS, since family 2’s
average valuation of its share is (30+30+90)/3=50. However, it is not unanimous-FS nor even democratic-FS, since David and Esther feel that their shareis worth only 30.
⌥⌃
3 Average fairness
With average fairness, the family cake-cutting problem can be reduced to theclassic problem of cake-cutting among individuals. This gives the following
results.
Theorem 1 (a) When families have equal entitlements, average-FS with connected pieces (and k components) is feasible.
(b) When families have different entitlements, average-FS with connected
pieces is infeasible. Moreover, at least 2k 1 components may be required foran average-FS allocation.
(c) When families have different entitlements, average-FS with at most
2k log2 k2 ⌦ + 3 components is feasible.
Proof The positive results — parts (a) and (c) — are based on the following
reduction. For each family Fj , define a representative agent Aj whose valuationis the function Wjavg defined in Subsection 2.4 above. Note that, since the Vi are
all nonatomic measures, the k family-valuations Wjavg are nonatomic measures
too. By classic results (Steinhaus 1948; Even and Paz 1984), when there arek agents with equal entitlements, there always exists a connected FS division.
As shown in a recent technical report (Segal-Halevi 2018), when there are kagents with di⇥erent entitlements, there always exists a FS allocation with at
most 2k log2 ⇤k 2⇤
k + 2 cuts, where ⇤k := 2⇥log2 k⇤ = k rounded up to the nearest
power of two. These cuts create 2k log2 ⇤k 2⇤
k + 3 components. By definition,such a division is an average-FS division among the families.
The negative result (b) follows immediately from an identical negative
result for individual agents (Segal-Halevi 2018), by considering k one-member
families.
⌥⌃
Remark 1 Fairness for individuals and average-fairness for families are equivalent only from an existential perspective; from a computational perspective
they are quite di⇥erent. FS division among k individual agents with equal
entitlements can be found by asking the agents O(k log k) queries (Even andFair Cake-Cutting among Families

9

Paz 1984). However, average-FS division cannot be found using a finite number of queries even when there are k = 2 families. To see this, suppose there
are two identical families, each of which has two di⇥erent members with valuations vA and vB . Then, a division (X1 , X2 ) is average-FS if and only if[vA (X1 ) + vB (X1 )]/2 = 1/2. Therefore, finding an average-FS allocation isequivalent to finding a subset X1 ↵ C for which the sum vA (X1 ) + vB (X1 )equals 1. However, queries can only be sent to individual agents, and it might
be impossible to find such a subset X1 using a finite number of queries to theagents. We omit the details here since our focus is on existence. See the accompanying technical report (Segal-Halevi and Nitzan 2016) for more details.
4 Unanimous fairness
Before presenting our results, we note that unanimous-FS, like average-FS,
can also be defined using family-valuation functions. Define:Wjmin (Xj ) := min Vi (Xj )
i Fj

for j

{1, ..., k}.

Then, a division is unanimous-FS if and only if:⇥j : Wjmin (Xj ) ⇧ wj

However, in contrast to the functions W avg defined in Section 3, the functions
W min are in general not additive. For example, suppose C is an interval withthree subintervals and a family has the following valuations:
Alice
Bob
Chana
W min

C1
1
0
0
0

C2
1
2
1
1

C3
1
1
2
1

C 1 ⌅ C2 ⌅ C3
3=1+1+1
3=0+2+1
3=0+1+2
3>0+1+1

While the individual valuations are additive, W min is not additive (it is noteven subadditive). Therefore, the classic results we used in Theorem 1 areinapplicable here, and di⇥erent techniques are needed.
4.1 Exact division
Initially, we assume that the entitlements are equal, i.e: wj = 1/k for all j. We
relate unanimous-FS to the problem of finding an exact division:9 .
Definition 1 Exact(N, K) is the following problem. Given N agents and an
integer K, divide C to K pieces, such that each of the N agents assigns exactly
the same value to all pieces:⇥j = 1, ..., K : ⇥i = 1, ..., N : Vi (Xj ) = 1/K.

9 The definition uses capital N and K to distinguish the parameters of exact divisionfrom the parameters of unanimous-fair division.

10Erel Segal-Halevi, Shmuel Nitzan

From an economic perspective, there is little intrinsic value in the concept ofexact division. However, in this section we will prove that it is closely linked
to the concept of unanimously-fair division. In fact, we will prove that theexistence a solution to each of these problems implies a solution to the otherproblem.
Denote by UnanimousFS(n, k) the problem of finding a unanimous-FS division when there are n agents grouped in k families with equal entitlements.

4.2 UnanimousFS =Exact

Lemma 1 For every pair of integers N ⇧ 1, K ⇧ 1, a solution to UnanimousFS (N (K 1) + 1, K) implies a solution to Exact (N, K).
Proof Given an instance of Exact(N, K) (N agents and a number K of required pieces), create K families. Each of the first K 1 families contains N
agents with the same valuations as the given agents. The K-th family contains
a single agent whose valuation is the average of the N given valuations:
N

V⌅ =

1 ⇥
Vi .
N i=1

The total number of agents in all K families is N (K 1) + 1. Use UnanimousFS (N (K 1) + 1, K) to find a unanimous-FS division, X. By definitionof unanimous fairness, for each agent i in family j: Vi (Xj ) ⇧ 1/K.
By construction, each of the first K 1 families has an agent with valuation
Vi . Hence, all N agents value each of the first K 1 pieces as at least 1/K
and:⇥i = 1, ..., N :

K⇧1
⇥
j=1

Vi (Xj ) ⇧

K

1
K

.

Hence, by additivity, every agent values the K-th piece as at most 1/K:
⇥i = 1, ..., N :Vi (XK )⇥i = 1, ..., N :Vi (XK ) = 1/K.

1/K.

The piece XK is given to the agent with value measure V ⌅ , so by fair-share:V ⌅ (XK ) ⇧ 1/K. By construction, V ⌅ (XK ) is the average of the Vi (XK ).
Hence:

Again by additivity:⇥i = 1, ..., N :

K⇧1
⇥
j=1

Vi (Xj ) =

K

1
K

.

Fair Cake-Cutting among Families

11

Hence, necessarily:⇥i = 1, ..., N,⇥j = 1, ..., K

1:

Vi (Xj ) = 1/K.

So we have found an exact division and solved Exact(N, K) as required.

⌥⌃

Alon (1987) 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 theabove lemma implies the following negative result:
Theorem 2 For every N, K, let n = N (K 1) + 1. A unanimous-FS division
for n agents grouped into K families might require at least n components.
In particular, unanimous-FS with connected pieces is infeasible.
4.3 Exact =UnanimousFS

Lemma 2 For every pair of integers n ⇧ 2, k ⇧ 1, a solution to Exact (n1, k) implies a solution to UnanimousFS (n, k) for any grouping of the n agents
to k families.
Proof Suppose we are given an instance of UnanimousFS(n, k), i.e, n agents ink families. Select n 1 agents arbitrarily. Use Exact(n 1, k) to find a partitionof C to k pieces, such that each of the n 1 agents values each of these pieces
as exactly 1/k. Ask the n-th agent to choose a favorite piece; by the pigeonhole
principle, this value is worth at least 1/k for that agent. Give that piece tothe family of the n-th agent. Give the other k 1 pieces arbitrarily to theremaining k 1 families. The resulting division is unanimous-FS.
⌥⌃
Alon (1987) proved that for every N and K, Exact(N, K) has a solution withat most N (K 1) + 1 components (at most N (K 1) cuts). Combining thisresult with the above lemma implies the following positive result:
Theorem 3 Given n agents in k families with equal entitlements, a unanimous-FS division with (n 1) · (k 1) + 1 components is feasible.
For k = 2 families, the number of components in Theorem 3 is n, whichmatches the lower bound of Theorem 2. For k > 2 families, the number ofcomponents can be made smaller, as explained below.
4.4 Less components: equal entitlements
The purpose of this subsection is to find a unanimous-FS allocation with lesscomponents than the guarantee of Theorem 3, when all families have equal
entitlements.
We start with an example. Assume there are k = 4 families. By Theorem
3, using 3(n 1) cuts, C can be divided to 4 subsets which are consideredequal by all n members. But for a unanimous-FS division, it is not required

12Erel Segal-Halevi, Shmuel Nitzan

that all members think that all pieces are equal, it is only required that all
members believe that their family’s share is worth at least 1/4. This can beachieved as follows:– Divide C to two subsets which all n agents value as exactly 1/2. This isequivalent to solving Exact(n, 2), which by Alon (1987), can be done withat most n cuts. Call the two resulting subsets West and East.
– Assign arbitrary two families to West and the other two families to East.
Mark by nW the total number of members in the families assigned to Westand by nE the total number of members assigned to East.
– Divide the West to two pieces which all nW agents value as exactly 1/4;
this can be done with nW cuts. Give a piece to each family. Divide theEast similarly using nE cuts.
The first step requires n cuts and the second step requires nW + nE = n cuts
too. Hence the total number of cuts required is only 2n, rather than 3n 1.
In fact, two cuts can be saved in each step by excluding two members(from two di⇥erent families) from the exact division. These members will notthink that the division is equal, but they will be allowed to choose the favorite
piece for their family. Thus only 2(n 2) cuts are required. A simple inductive
argument shows that whenever k is a power of 2, (log2 k) · (n k/2) cuts are
required.
When k is not a power of 2, a result by Stromquist and Woodall (1985)
can be used. They prove that, for every fraction r [0, 1], it is possible to cut
a piece of C such that all n agents agree that its value is exactly r using at
most 2n 2 cuts.10 This can be used as follows:– Select integers l1 , l2 {1, ..., k 1} such that l1 + l2 = k.
– Apply Stromquist and Woodall (1985) with r = l1 /k: using 2n 4 cuts,
cut a piece X1 that n 1 agents value as exactly l1 /k. This means thatthese n 1 agents value the other piece, X2 , as exactly l2 /k.
– Let the n-th agent choose a piece for his family; assign the other families
arbitrarily such that l1 families are assigned to piece X1 and the other l2families to piece X2 .
– Recursively divide piece X1 to its l1 families and piece X2 to its l2 families.
After a finite number of recursion steps, the number of families assigned toeach piece becomes 1 and the procedure ends. The number of cuts in each levelof the recursion is at most (2n 4). The depth of recursion can be boundedby log2 k⌦ by dividing k to halves (if it is even) or to almost-halves (if it isodd; i.e. take l1 = (k 1)/2 and l2 = (k + 1)/2). Hence:
Theorem 4 Given n agents in k families with equal entitlements, a unanimous-FS division with log2 k⌦ · (2n 4) + 1 components is feasible.
10 They prove that, if C is a circle, the number of connected components is n ⇤ 1. Hence,
the number of cuts is 2n ⇤ 2. This is also true when C is an interval, although the numberof connected components in this case is n.

Fair Cake-Cutting among Families

13

Note that Theorem 3 and Theorem 4 both give upper bounds on the number ofcomponents required for unanimous-FS. The bound of Theorem 3 is stronger
when k is small and the bound of Theorem 4 is stronger when k is large.
4.5 Less components: di⇥erent entitlements
The purpose of this subsection is to find a unanimous-FS allocation with lesscomponents than the guarantee of Theorem 3, when families may have di⇥erent
entitlements.
When families have di⇥erent entitlements, the procedure of the previous
subsection cannot be used. We cannot let the n-th agent select a piece forhis family, since the pieces are di⇥erent. For example, suppose there are two
families with entitlements w1 = 1/3, w2 = 2/3. We can divide C to two pieces
X1 , X2 such that n 1 agents value X1 as 1/3 and X2 as 2/3. So all of themagree that X1 should be given to family 1 and X2 should be given to family
2. But, the n-th agent might select the wrong piece for his family. Therefore,
the procedure should be modified as follows.
– Select an integer l {1, ..., k}.
– Divide the families to two subsets: F1 , . . . , Fl and Fl+1 , . . . , Fk .
l
– Apply Stromquist and Woodall (1985) with r = j=1 wj : using 2n2lcuts, cut a piece X1 which all n agents value as exactly j=1 wj . Thiskmeans that all n agents value the other piece, X2 , as exactly j=l+1 wj .

– Recursively divide piece X1 to F1 , . . . , Fl and piece X2 to Fl+1 , . . . , Fk .

Here, the number of cuts in each level of the recursion is at most (2n 2).
The depth of recursion can be bounded by log2 k⌦ by choosing l = k/2 (if kis even) or l = (k 1)/2 (if k is odd). Hence:
Theorem 5 Given n agents in k families with different entitlements, a unanimous-FS division with log2 k⌦ · (2n 2) + 1 components is feasible.
In concluding the analysis of unanimous-FS, recall that, even for k = 2
families, unanimous-FS is as di⇤cult as exact division and might require thesame number of components — n. In the worst case, we might need to givea disjoint component to each member, which negates the concept of division
to families. Therefore we now turn to the analysis of an alternative fairness
criterion that yields more useful results.
5 Democratic fairness
Like unanimous-FS (Section 4), democratic-FS can also be defined using familyvaluation functions. Define:Wjmed (Xj ) :=mediani Fj Vi (Xj )
nj

for j

{1, ..., k}.

14Erel Segal-Halevi, Shmuel Nitzan

A division is democratic-FS if and only if:⇥j : Wjmed (Xj ) ⇧ wj
However, the W med functions are not additive,11 so again the classic results
referred to in Theorem 1 are inapplicable.

5.1 Two families: a division procedure
We start with a positive result for two families with equal entitlements, whichshows that democratic-FS is substantially easier than unanimous-FS.
Theorem 6 When there are k = 2 families with equal entitlements, democratic-FS with connected pieces is feasible. Moreover, it can be found by ane⇥cient algorithm.
Proof The proof is given by Algorithm 1. It finds a democratic-FS division
between two families. For each family, a location Mj is calculated such that, if
C is cut at Mj , half the members value the interval [0, Mj ] as at least 1/2 andthe other half value the interval [Mj , 1] as at least 1/2. Then, C 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 theirfamily’s share as at least 1/2, so the division is democratic-FS. Each family
receives a single connected piece.

Algorithm 1 Finding a democratic-NE division for two families
INPUT:- C, which is assumed to be the unit interval [0, 1].
- n additive agents, all of whom value C as 1.
- A grouping of the agents to 2 families, F1 , F2 .
OUTPUT:A democratic-NE division of C to 2 pieces.
ALGORITHM:- Each agent i = 1, ..., n marks an xi ⌅ [0, 1] such that Vi ([0, xi ]) = Vi ([xi , 1]) = 1/2.
- For each family j = 1, 2, find the median of its members’ marks: Mj = mediani Fj xi .
Find the median of the family medians: M ⇥ = (M1 + M2 )/2.
- If M1 < M2 then give [0, M ⇥ ] to F1 and [M ⇥ , 1] to F2 .
Otherwise give [0, M ⇥ ] to F2 and [M ⇥ , 1] to F1 .

Unfortunately, this positive result is not applicable when there are morethan two families, as shown in the following subsection.
11 See the example in the beginning of Section 4. In that example W med is identical to
W min .

Fair Cake-Cutting among Families

15

5.2 Three or more families: an impossibility result
This subsection presents a lower bound on the number of components required
for a democratic-fair division. The lower bound holds not only for FS but evenfor a much weaker fairness notion called positivity.
Given a specific division of C among families, define a zero agent as anagent who values his family’s share as 0 and a positive agent as an agent
who believes his family received a share with a positive value. Note that FS
implies positivity but not vice-versa. The following lower bound holds even for
positivity, hence it also holds for FS.
Lemma 3 Assume there are n = mk agents, divided into k families with mmembers in each family. To guarantee that at least q members in each family
are positive, the total number of components may need to be at least:
k·

kq
k

m
1

Proof Number the families by j = 0, ..., k 1 and the members in each family
by i = 0, ..., m 1. Assume that C is the interval [0, mk]. In each family j, eachmember i wants only the following interval: (ik +j, ik +j +1). Thus there is nooverlap between desired intervals of di⇥erent members. The table below illustrates the construction for k = 2, m = 3. The families are {Alice,Bob,Chana}and {David,Esther,Frank}:
Alice
Bob
Chana
David
Esther
Frank

1
0
0
0
0
0

0
0
0
1
0
0

0
1
0
0
0
0

0
0
0
0
1
0

0
0
1
0
0
0

0
0
0
0
0
1

Suppose the piece Xj (the piece given to family j) is made of l ⇧ 1 components. We can make l members of Fj positive using l intervals of positive
length inside their desired areas. However, if q > l, we also have to make theremaining q l members positive. For this, we have to extend q l intervals tolength 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 isthus (k 1)(q l). Adding the q members which must be positive in eachfamily, we get the following necessary condition: (k 1)(q l) + q m. Thisis equivalent to:
l⇧

kq
k

m
.
1

The total number of components is k·l, which is at least equal to the expression
stated in the Lemma.
⌥
⌃

16

Erel Segal-Halevi, Shmuel Nitzan

In other words, if we want at least a fraction h of the members in each family
to have a non-zero utility, the number of components might have to be at least:
k·

khm m
hk 1
=n·
k 1
k 1

In a unanimous-FS division h = 1, so the number of components is at leastn, which coincides with the lower bound of Theorem 2. In a democratic-FSh ⇧ 1/2 so we get the following negative result:
Theorem 7 In a democratic-FS division with n agents grouped into k families, the number of components may need to be at least
n·

k/2 1
k 1

Note that for k = 2 the lower bound is 0, and indeed we already saw thatin this case a connected allocation is feasible.
Lemma 3 has another interesting corollary. Suppose we have k ⇧ 3 but
still insist that the division be connected. We already know that we cannot
guarantee that 1/2 the agents in each group be positive. But there is an evenstronger impossibility result.
Theorem 8 When dividing a cake among k families, for every constant fraction h > 1/k, it may be impossible to find a connected division where at leasta fraction h of the agents in each group are positive.
Proof By Lemma 3 the number of components should be at least n · hk⇧1
k⇧1 .
Since h > 1/k, for su⇤ciently large n the number of components is larger thank, so the division cannot be connected.
⌥⌃
The fraction 1/k in Theorem 8 is tight:
Theorem 9 For every integer k ⇧ 2, there exists a connected division amongk families, that is FS for at least 1/k of the members in each family.
Proof The Dubins-Spanier moving-knife protocol (Dubins and Spanier 1961)
can be adapted to families as follows. A knife moves continuously over the cakefrom left to right. Whenever in a certain family at least 1/k of its members
believe that the cake to the left of the knife is worth at least 1/k, they shout“stop”, the cake is cut at the knife location, and the shouting family receives
the cake to its left (the division is now FS for 1/k the members in this family).
In the other k 1 families, at least (k 1)/k of the members believe theremaining cake is worth at least (k 1)/k of its original value; by dividing theremaining cake recursively using the same procedure, they division is FS for
1/k of their members too.
⌥⌃

Fair Cake-Cutting among Families

17

5.3 Three or more families: positive results
Suppose we do want a democratic-FS division for three or more families. How
many components are su⇤cient?
As a first positive result, we can use Theorem 5, substituting n/2 insteadof n: select half of the members in each family arbitrarily, then find a division
which is unanimous-FS for them while ignoring all other members. This leads
to:
Theorem 10 Given n agents in k families with different entitlements, democratic-FS with log2 k⌦ · (n 2) + 1 components is feasible.

However, for families with equal entitlements we can do much better. Algorithm 2 generalizes Algorithm 1 for any number of families:
Algorithm 2 Finding a democratic-FS division for k ⇧ 2 families.
INPUT:- C, which is assumed to be the unit interval [0, 1].
- n additive agents, all of whom value C as 1.
- A grouping of the agents to k families, F1 , ..., Fk .
OUTPUT:A democratic-FS division of C to k pieces.
ALGORITHM:
Step 1: Halving⇤k/2⌅- Each agent i = 1, ..., n selects an xi ⌅ [0, 1] such that Vi ([0, xi ]) = k (this means 12 if⇧k/2⌃

k is even and k+1
if k is odd). Note: Vi ([xi , 1]) = k .
2k- For each family j = 1, ..., k, find the median of its members’ selections: Mj = mediani Fj xi .
- Order the families in increasing order of their medians. Find the median of the familymedians: M ⇥ = M⇤k/2⌅ . Cut C at x = M ⇥ .
Step 2: Sub-division- Define the western families as the Fj with j = 1, ..., ⇧k/2⌃. Let nW be the total numberof members in these families. Divide the interval [0, M ⇥ ] among the western families using
UnanimousFS(nW /2, ⇧k/2⌃).
- Similarly, define the eastern families as the Fj with j = ⇧k/2⌃ + 1, ..., k. There are ⌥k/2
such families. Let nE be their total number of members. Divide the interval (M ⇥ , 1] among
the eastern families using UnanimousFS(nE /2, ⌥k/2 ).

The algorithm works in two steps.
Step 1: Halving. For each family, a location Mj is calculated such that,
if C is cut at Mj , half the family members value the interval [0, Mj ] as at least⇥k/2⇤
and the other half value the interval [Mj , 1] as at least ⌃k/2⌥
k
k . Then, C is
cut in M ⌅ — the median of the family medians. The k/2⌦ “western families”— for which Mj M ⌅ — are assigned to the western interval of C — [0, M ⌅ ].
By construction, at least half the members in each of the western families value[0, M ⌅ ] as at least ⇥k/2⇤
k . We say that these members are “happy”. Similarly,
the k/2✏ eastern families — for which Mj ⇧ M ⌅ — are assigned to theeastern interval (M ⌅ , 1]; at least half the members in each of these families are“happy”, i.e, value the interval (M ⌅ , 1] as at least ⌃k/2⌥
k .

18

Erel Segal-Halevi, Shmuel Nitzan

If there are only two families (k = 2), then we are done: there is exactly
one western family and one eastern family ( k/2⌦ = k/2✏ = 1 ). For eachfamily j {1, 2}, at least half the members of each family value their family’sshare as at least 1/2. Hence, the allocation of Xj to family j is democraticFS.
If there are more than two families (k > 2), an additional step is required.
Step 2: Sub-division. Each of the two sub-intervals should be further
divided to the families assigned to it. In each family Fj , at least nj /2 members
are happy. So for each Fj , select exactly nj /2 members who are happy. Our
goal now is to make sure that these agents remain happy. This can be doneusing a unanimous-FS allocation, where only nj /2 happy members in eachfamily (hence n/2 members overall) are counted.
The unanimous-FS allocation guarantees that every western-happy-member
1believes that his family’s share is worth at least ⇥k/2⇤· ⇥k/2⇤= k1 . Similarly,kevery eastern-happy-member believes that his family’s share is worth at least⌃k/2⌥
1· ⌃k/2⌥= k1 . Hence, the resulting division is democratic-FS.
k
We now calculate the number of components in the resulting division.
One cut is required for the halving step. For the unanimous-FS division of thewestern interval, the number of required cuts is at most ( k/2⌦ 1)·(nW /2 1)
by Theorem 3, and at most log2 k/2⌦⌦ · (nW 4) by Theorem 4. Similarly,
for the eastern interval the number of required cuts is at most the minimumof ( k/2✏ 1) · (nE /2 1) and log2 k/2✏⌦ · (nE 4). The total number of cutsis thus at most 1 + ( k/2⌦ 1) · (n/2 2) and at most 1 + log2 k/2⌦⌦ · (n 8).
The total number of components is larger by one. To conclude:
Theorem 11 Given n agents in k families with equal entitlements, democratic-FS is feasible, and the number of required components is at most:⌅⇧min 2 + ( k/2⌦ 1) · (n/2 2),
2 + log2 k/2⌦⌦ · (n 8) .
5.4 Comparison and Open Questions
Table 1 compares the three variants of FS, focusing on families with equal
entitlements. Recall that n is the total number of agents in all families.
The case of k = 2 families is well-understood. The results for all fairness
criteria are tight: by all fairness definitions, we know that a fair division exists
with the smallest possible number of connectivity components.
The case of k > 2 families opens some questions:– Is unanimous-FS with n components feasible for all k? (particularly, withk = 3 families, is the number of required components n as in the lower
bound, or 2n 1 as in the upper bound?).
– Is democratic-FS with n· k/2⇧1
k⇧1 components feasible for all k? (particularly,
with k = 3 families, is the number of required components n/4 as in thelower bound, or n/2 as in the upper bound?).

Fair Cake-Cutting among Families#Families(k)

Fairness

19#Connectivity Components
Lower
Upper

average-FS (Sec. 3)
unanimous-FS

k
2
3
4

k
n
n
n

(Sec. 4)
democratic-FS

k
2
3
4

n
2
n/4
n/3

(Sec. 5)

k

n·

k/2⌥1
k⌥1

k (connected)n2n ⇤ 12n ⇤ 3min(1 + ⇧log2 k⌃ · (2n ⇤ 4),(k ⇤ 1) · (n ⇤ 1) + 1)
2 (connected)
n/2
n/2
min(2 + ⇧log2 ⇧k/2⌃⌃ · (n ⇤ 8),
2 + (⇧k/2⌃ ⇤ 1) · (n/2 ⇤ 2))

Table 1: Number of components required for a fair-share division in various situations.

The case of di⇥erent entitlements is much less understood even for individual
agents (Segal-Halevi, 2018), let alone for families.
What fairness notion is the most practical? The table shows that it depends
on the total number of agents (n). When n is small (as is common when
dividing an estate among heirs), it is reasonable to try to attain a unanimouslyfair division. However, when n is large (as is common when dividing disputed
lands among states), unanimous fairness quickly becomes impractical, as thenumber of components might grow linearly with n. In this case, we must settle
for a weaker fairness criterion. When k = 2, we can find a democratically-fairallocation that is also connected. When k > 2, democratic fairness too might
be impractical, and we may have to settle for average-fairness.
6 Pareto-e⇥ciency
So far, we studied the compatibility of fairness criteria with a geometric requirement — reducing the number of connectivity components. In this section
we replace the geometric requirement with an economic requirement — Paretoe⇤ciency. An allocation is called Pareto-e⇥cient (PE) if no other allocation is
weakly better for all individual agents and strictly better for some individual
agents. Fortunately, PE is compatible even with the strongest variant of thefair-share criterion:
Theorem 12 There always exists an allocation that is both PE and unanimous-FS (hence also average-FS and democratic-FS).
Proof We use a famous theorem of Dubins and Spanier (1961), which is a
special case of a measure-theoretic theorem by Dvoretzky et al (1951).
For every partition X of C to k pieces, let M (X) be its value-matrix —an n-by-k matrix M where ⇥i {1, . . . , n}, ⇥j {1, . . . , k} : Mi,j = Vi (Xj ).
Let MC be the set of all matrices that correspond to such partitions:
MC := {M (X)|X is a partition of C to k pieces}

20

Erel Segal-Halevi, Shmuel Nitzan

Theorem 1 of Dubins and Spanier (1961) implies that the set MC is compact.
Define a second set of matrices representing the unanimous-FS condition:
MF S := {M is an n ◊ k matrix|⇥j{1, . . . , k} : ⇥i

Fj : Mi,j ⇧ 1/k}

Finally, define MCF S := MC ⇣ MF S . This set represents all value-matrices ofallocations of C that are unanimous-FS. By Theorem 3, MCF S is non-empty.
Since MC is compact and MF S is closed, their intersection MCF S is compact.
Define the following function U : MCF S ⌘ R:
U (M ) :=

k ⌃
⌃

Mi,j

j=1 i FjThis is a continuous function, so it has a maximum point in MCF S ; let’scall it M ⌅ . This matrix corresponds to an allocation X ⌅ that maximizes,among⌥k ⌥all unanimous-FS allocations, the product of valuations of all agents:
j=1
i Fj Vi (Xj ). This product is strictly increasing with the value of eachagent i N , so the allocation X ⌅ is Pareto-e⇤cient in the set MCF S . Since
every Pareto-improvement of an allocation in MCF S is also in MCF S , the allocation X ⌅ is also Pareto-e⇤cient in general.
⌥⌃
7 No Envy
So far, we used fair-share (FS) as our individual fairness criterion. Anothercriterion that is very common in economics is no-envy (NE). We study thiscriterion for families with equal entitlements.
Analogously to the definitions in subsection 2.4, we call an allocation X:
average-NE
unanimous-NE
democratic-NE

if ⇥j, j{1, . . . , k} :if ⇥j, j{1, . . . , k},if ⇥j, j{1, . . . , k} :for at least half the members i⇥iWjavg (Xj ) ⇧ Wjavg (Xj );Fj : Vi (Xj ) ⇧ Vi (Xj );Fj : Vi (Xj ) ⇧ Vi (Xj ).

With individual agents, it is well known that NE implies FS (with equal entitlements). With two individual agents, NE and FS are equivalent. The same
implications are true with families. Each variant of NE implies the corresponding variant of FS.12 When there are k = 2 families, each variant of NE
is equivalent to the corresponding variant of FS. 13
12 Suppose an agent i ⌅ F thinks the division is not FS. This means that V (X ) < 1/k.
jijBut, the sum of all weights equals 1 which equals the sum of the values of all pieces. Therefore
there must be some j = j for which: Vi (Xj ) > 1/k. Hence, Vi (Xj ) < Vi (Xj ), so agent i
thinks the division is not NE.
13 Suppose an agent i ⌅ F thinks the division is FS. This means that V (X ) ⇥ 1/2. Byjijadditivity, for the other family j = j, Vi (Xj ) ⌦ 1/2. Hence Vi (Xj ) ⇥ Vi (Xj ), so agent i
thinks the division is NE.

Fair Cake-Cutting among Families

21

Most of our results for FS with equal entitlements are also valid for NE. For
average-NE, we can use classic results proving the existence of NE allocations
with connected pieces among individual agents (Stromquist 1980; Su 1999).
Applying the same reduction as in Theorem 1 we get:
Theorem 1’ For any k families, average-NE with connected pieces is feasible.
Since NE implies FS, the negative results are still valid:
Theorem 2’ For every N, K, let n = N (K 1)+1. A unanimous-NE division
for n agents grouped into K families might require at least n components.
Some positive results remain valid too. Lemma 2 is based on an exact
division. Therefore it holds, with the same proof, even if we replace unanimousFS with unanimous-NE. Therefore:
Theorem 3’ Given n agents in k families, a unanimous-NE division with(n 1) · (k 1) + 1 components is feasible.
However, the recursive-halving procedure of Theorem 4 cannot be used
here. Suppose we divide C to two subsets, West and East, which all n agents
value as exactly 1/2. Then, we assign arbitrary k/2 families to West and theother families to East. We find an exact division of the West among the westernfamilies and an exact division of the East among the eastern families. While
this division satisfies FS, it does not satisfy NE, since the agents in the west
might envy families in the east and vice versa. Therefore, while the number ofcomponents required for unanimous-FS division is in O(n log k), the best we
can currently say about the number of components required for unanimousNE is that it is in O(nk).
With two families FS implies NE, so the following positive result holds:
Theorem 6’ When there are k = 2 families, democratic-NE with connected
pieces is feasible. Moreover, it can be found by an e⇥cient algorithm.
Similarly, the negative results for democratic-FS in Theorems 7 and 8 areequally valid for democratic-NE. The positive result of Theorem 9 holds for
NE too:Theorem 9’ For every integer k ⇧ 2, there exists a connected division amongk families, that is NE for at least 1/k of the members in each family.
Proof Su (1999) presents a procedure (attributed to Simmons) for finding aconnected NE division among k individual agents. It is based on presenting
various connected partitions to the agents, and asking each agent which of thek pieces is the best. He proves that there exists a partition in which each agent
gives a di⇥erent answer; that partition corresponds to a no-envy allocation.
He also shows a procedure for finding a sequence of partitions that converges(after possibly infinitely many steps) to that no-envy allocation.
The Simmons-Su procedure can be adapted to families in the following
way. Whenever a family is asked “which of the k pieces is better?”, it answers

22Erel Segal-Halevi, Shmuel Nitzan
Fairness#Families (k)#Connectivity Components
Lower boundUpper boundaverage-NEAnykk (connected)

unanimous-NE(Sec. 4)

2
3
4
Any

n
n
n
n

democratic-NE(Sec. 5)

2
3
4
Any

2
n/4
n/3

n
2n ⇤ 13n ⇤ 2(k ⇤ 1) · (n ⇤ 1) + 1

n·

k/2⌥1
k⌥1

2 (connected)
n/2 + 2n+1
n · (k ⇤ 2)/2 + 2

Table 2: Number of components required for a no-envy division in various situations.

by doing a plurality voting among its members. Then, in the final division,
each family receives a piece that is considered the best by a plurality of its
members, which is at least a fraction 1/k of its members. Therefore, at least
1/k of each family’s members feel that the allocation has no envy.
⌥⌃
Theorem 11 about democratic-FS does not hold as-is for democratic-NE,
but it can be adapted by adapting Algorithm 2. Step 1 — the halving step —remains the same. Step 2 — the subdivision step — should be modified to use
an exact division, as follows:- Using Exact(n/2, k/2⌦) , find an exact division of the interval [0, M ⌅ ]into k/2⌦ pieces, such that all n/2 happy agents find the pieces equal.
Assign these pieces to the western families — the Fj with j = 1, ..., k/2⌦.
- Using Exact(n/2, k/2✏) , find an exact division of the interval (M ⌅ , 1]
into k/2✏ pieces, such that all n/2 happy agents find the pieces equal.
Assign the pieces to the eastern families — Fj with j = k/2⌦ + 1, ..., k.
The halving step requires a single cut. The two exact divisions require(n/2)·(k 2) cuts. Therefore the total number of components is n(k 2)/2+2:
Theorem 11’ Given n agents in k families with equal entitlements, democratic-NE with at most n(k 2)/2 + 2 components is feasible.
Table 2 summarizes our results for no-envy division and shows some remaining gaps.
We now consider the combination of no-envy with Pareto-e⇤ciency. Someof our positive results from Section 6 are still valid:
Theorem 12’ (a) With k = 2 families, there always exists an allocation thatis both PE and unanimous-NE (hence also average-NE and democratic-NE).
(b) With any number of families, there always exists an allocation that is
PE and average-NE.
Proof (a) With k = 2 families, NE and FS are equivalent, so this follows
directly from Theorem 12.

Fair Cake-Cutting among Families

23(b) We use the same reduction as in Theorem 1 and the same compactness
argument as in Theorem 12. For each family Fj , define a representative agent
Aj whose valuation is Wjavg . There exists an allocation X ⌅ that maximizes the⌥kproduct of valuations of the representatives: j=1 Wjavg (Xj ).

Segal-Halevi and Sziklai (2018, Section 5) prove, in the setting of cakecutting among individuals, that every allocation maximizing the product ofvalues has no envy. Therefore, in the allocation X ⌅ , there is no envy among therepresentatives. By definition of average-NE, X ⌅ is an average-NE allocation
among the families.
⌥k
The product j=1 Wjavg (Xj ) is strictly increasing with the value of eachindividual agent i N . Therefore, the allocation X ⌅ maximizing this productis Pareto-e⇤cient.
⌥⌃

In contrast to these positive results, Pareto-e⇤ciency is incompatible with
unanimous-NE and democratic-NE.
The incompatibility between PE and unanimous-NE appears even when
we take a minimal step forward from the case of two families: there are threefamilies, only one of which is a couple and the other two are singles.

Theorem 13 With three or more families, there might be no allocation thatis both PE and unanimous-NE.

Proof The proof is based on an example used by Bade and Segal-Halevi (2018)
in the context of fair division of homogeneous goods. C is an interval composedof two sub-intervals Y and Z of length 1. C has to be divided among threefamilies — a couple and two singles — with the following valuations:

Y

Z

Alice
George

1
7

1
1

Bob

2

1

Esther5

1

Suppose that we have a unanimous-NE allocation of C among the three families. Denote by YAG , ZAG the lengths of Y, Z given to Alice+George, and24Erel Segal-Halevi, Shmuel Nitzan

similarly YB , ZB , YE , ZE are the lengths given to Bob and Esther. Then:
7YAG + ZAG ⇧ 7YB + ZB(George does not envy Bob)

2)YAG ⇧ (7(from the above inequalities)

2YB + ZB ⇧ 2YAG + ZAG
(7

2)YB

YAG ⇧ YB(✓)

(Bob does not envy George)

1YAG + ZAG ⇧ 1YB + ZB

(Alice does not envy Bob)

2)YAG ⇧ (1(from the above inequalities)

2YB + ZB ⇧ 2YAG + ZAG(1(✓✓)(✓ ✓ ✓)

YAG

=

2)YB

(Bob does not envy Alice)YB

YAG = YB

(from * and **)ZAG = ZB

(Bob and Alice+George do not envy)

We proved that, in any unanimous-NE allocation, the share given to Alice+George is identical to the share given to Bob (i.e, the same lengths ofboth subintervals). The proof does not depend on the exact valuation functions — it only depends on the fact that 1 < 2 < 7, i.e, Bob’s valuation of Y
is strictly between Alice’s and George’s valuations. Hence, exactly the same
proof works for Esther, i.e: YAG = YE and ZAG = ZE . Therefore, the shares
given to all three families are identical.
We now prove that this allocation cannot be PE. We consider three cases.
– Case 1: YB = 0. Then also YE = YAG = 0 so Y remains unallocated andthe allocation is not PE.
– Case 2: ZE = 0. Then also ZB = ZAG = 0 so Z remains unallocated andthe allocation is not PE.
– Case 3: YB and ZE are positive. Let = min(YB , ZE /3). Suppose that Bob
gives of his Y to Esther, and gets in exchange 3 of her Z. Then, Bob’svalue increases by 3
2 ; Esther’s value increases by 5
3 ; and thevalues of Alice and George are unchanged. This means that the original
allocation was not Pareto-e⇤cient.
⌥⌃
Weakening unanimous-NE to democratic-NE does not help when there are
5 or more families.
Theorem 14 With five or more families, there might be no allocation that isboth PE and democratic-NE.
Proof The proof is based on an extension of the example of Theorem 13, where
there are five families — one triplet and four singles — with the valuations:Fair Cake-Cutting among Families

25

Y

Z

Alice
Dina
George

1/4
1
4

1
1
1

Bob

1/2

1

Chana

1/3

1

Esther

2

1

Frank

3

1

Suppose that we have a democratic-NE allocation of C among the families.
By definition of democratic-NE, all singles must not feel any envy. Moreover,in the first family, at least two members must not feel any envy. There arethree options for the identity of these non-envious members.
Option A: Alice and Dina feel no envy. We consider Bob and Chana. The
value of Y for each of them is strictly between the value of Y for Alice and thevalue of Y for Dina. Therefore, similar arguments as in the proof of Theorem
13 imply that the three allocations of Chana, Bob, and Alice+Dina+George
are identical. Now there are three cases:– Case A1: YC = 0. Then also YB = YADG = 0. Each of Chana, Bob, andAlice+Dina+George receive at most 1/3 of Z, so Dina’s value is at most
1/3. Since Dina does not envy Esther and Frank, each of them must receive
at most 1/3 of Y . This means that at least 1/3 of Y remains unallocated,so the allocation is not PE.
– Case A2: ZB = 0. Then also ZC = ZADG = 0. Again Dina’s value is at
most 1/3, so Esther and Frank must receive at most 1/3 of Z, so at least
1/3 of Z remains unallocated, so the allocation is not PE.
– Case A3: YC and ZB are positive. Then, Bob can give /2.5 of his Z to
Chana in exchange for of her Y (for some small > 0) and attain aPareto improvement, so the original allocation is not PE.
Option B: George and Dina feel no envy. We consider Esther and Frank.
The value of Y for each of them is strictly between the value of Y for George
and the value of Y for Dina. Therefore the three allocations of Esther, Frank,
and Alice+Dina+George are identical. The rest of the proof is analogous to
Option A.
Option C: Alice and George feel no envy. The value of Y for all thesingles is strictly between the value of Y for Alice and the value of Y for
George. Therefore, the allocations of all five families must be identical. The
rest of the proof is analogous to Theorem 13.
⌥⌃
An interesting question that is left open by Theorems 12’ and 14 is what
happens when there are 3 or 4 families — does there always exist an allocationthat is both PE and democratic-NE?

26

Erel Segal-Halevi, Shmuel Nitzan

8 Related Work
There are numerous papers about fair division in general and fair cake-cuttingin particular. We mentioned some of them in the introduction. Here we survey
some work that is more closely related to family-based fairness.
8.1 Dividing indivisible items among groups
In a contemporaneous and independent work, Manurangsi and Suksompong(2017) and Suksompong (2018) have studied the problem of fairly dividing
discrete items among groups of agents. They focused on unanimous fairness.
They proved that, in many cases, unanimously-fair allocations do not exist.
These results complement our impossibility results for unanimous fairness in
dividing a continuous resource. After the publication of their work and ourworking paper, we joined forces to study democratic-fair allocation of indivisible goods (Segal-Halevi and Suksompong 2018).
8.2 Group-envy-freeness and on-the-fly coalitions
Berliant et al (1992); Hüsseinov (2011); Todo et al (2011) study the concept ofgroup-envy-freeness. They assume the standard model of fair division amongindividuals (and not among families). They define a group-envy-free division as
a division in which no coalition of individuals can take the pieces allocated toanother coalition with the same number of individuals and re-divide the pieces
among its members such that all members are weakly better-o⇥. Coalitions in
cake-cutting are also studied by Dall’Aglio et al (2009); Dall’Aglio and Di Luca(2014).
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-fair-division problem
becomes easier. For instance, it is easy to achieve a unanimous-FS division withconnected pieces between two coalitions: ask each agent to mark its medianline, 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 themedian-of-medians.
8.3 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 Diamantaras(1992); Diamantaras and Wilkie (1994, 1996); Guth and Kliemt (2002). 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

Fair Cake-Cutting among Families

27

is consumed by all agents in a single family — a situation not captured byexisting public-good models.

8.4 Non-additive utilities
As explained in Sections 4 and 5, the di⇤culty with unanimous-FS and democratic-FS is that the associated family-valuation functions are not additive. It
is therefore interesting to compare our work to other works on cake-cuttingwith non-additive valuations.
Berliant et al (1992); Maccheroni and Marinacci (2003); Dall’Aglio andMaccheroni (2005) focus on sub-additive, or concave, valuations, in which thesum of the values of the parts is more than the value of the whole. These
works are not applicable to our setting, because the family-valuations are notnecessarily sub-additive — the sum of values of the parts might be less thanthe value of the whole (see the example in the beginning of Section 4).
Sagara and Vlach (2005); Dall’Aglio and Maccheroni (2009); Hüsseinov
and Sagara (2013) 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 isimportant in practical division applications.
Su (1999) 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
FS.
Mirchandani (2013) suggests a division protocol for non-additive valuations
using non-linear programming. However, the protocol is practical only when
the resource to divide is a collection of a small number of homogeneous components, where the only thing that matters is what fraction of each componentis allocated to each agent. In contrast, in our model the resource is a single
heterogeneous good.
Finally, Berliant and Dunz (2004); Caragiannis et al (2011); Segal-Halevi
et al (2015) study specific non-additive value functions which are motivatedby 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 di⇥erent consideration: handling the di⇥erent preferences of family members. A possible future research topic is to find fair divisionrules that handle these considerations simultaneously, as both of them are important for fair division of land.

References
Alon N (1987) Splitting necklaces. Advances in Mathematics 63(3):247–253, DOI
10.1016/0001-8708(87)90055-7, URL http://dx.doi.org/10.1016/0001-8708(87)90055-7
Bade S, Segal-Halevi E (2018) Fair and E⌅cient Division Among Families, mimeo

28

Erel Segal-Halevi, Shmuel Nitzan

Barbanel JB, Brams SJ (2004) Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond. Mathematical Social
Sciences
48(3):251–269,
DOI
10.1016/j.mathsocsci.2004.03.006,
URL
http://dx.doi.org/10.1016/j.mathsocsci.2004.03.006
Barbanel JB, Brams SJ (2014) Two-Person Cake Cutting: The Optimal Number of Cuts.
The Mathematical Intelligencer 36(3):23–35, DOI 10.1007/s00283-013-9442-0, URL
http://mpra.ub.uni-muenchen.de/34263/
Bentham J (1789) An Introduction to the Principles of Morals and Legislation (Dover Philosophical Classics). Dover Publications, URL http://www.worldcat.org/isbn/0486454525
Berliant M, Dunz K (2004) A foundation of location theory: existence of equilibrium, thewelfare theorems, and core. Journal of Mathematical Economics 40(5):593–618, DOI
10.1016/s0304-4068(03)00077-6, URL http://dx.doi.org/10.1016/s0304-4068(03)000776
Berliant M, Thomson W, Dunz K (1992) On the fair division of a heterogeneous commodity.
Journal of Mathematical Economics 21(3):201–216, DOI 10.1016/0304-4068(92)90001-n,
URL http://dx.doi.org/10.1016/0304-4068(92)90001-n
Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2017) Competitive division ofa mixed manna. Econometrica 85(6):1847–1871, URL http://arxiv.org/abs/1702.00616,
arXiv preprint 1702.00616, 1702.00616
Brams SJ, Taylor AD (1996) Fair Division: From Cake Cutting to Dispute
Resolution.
Cambridge
University
Press,
Cambridge
UK,
URL
http://www.worldcat.org/isbn/0521556449
Buchanan JM (1965) An economic theory of clubs. Economica pp 1–14, DOI
10.2307/2552442, URL http://dx.doi.org/10.2307/2552442
Caragiannis I, Lai JK, Procaccia AD (2011) Towards more expressive cake cutting. In:
Proceedings of the Twenty-Second international joint conference on Artificial Intelligence (IJCAI’11), AAAI Press, IJCAI’11, pp 127–132, DOI 10.5591/978-1-57735-5168/ijcai11-033, URL http://www.cs.cmu.edu/˜./arielpro/papers/nonadd.ijcai11.pdf
Chambers CP (2005) Allocation rules for land division. Journal of Economic
Theory121(2):236–258,
DOI
10.1016/j.jet.2004.04.008,
URL
http://dx.doi.org/10.1016/j.jet.2004.04.008
Chevaleyre Y, Dunne PE, Endriss U, Lang J, Lemaı̂tre M, Maudet
N, Padget J, Phelps S, Rodriguez-Aguilar JA, Sousa P (2006) IssuesinMultiagent
Resource
Allocation.
Informatica
30(1):3–31,
URL
http://www.informatica.si/index.php/informatica/article/view/70
Cseh A, Fleiner T (2017) The complexity of cake cutting with unequal shares. URL
http://arxiv.org/abs/1709.03152, 1709.03152
Dall’Aglio M, Di Luca C (2014) Finding maxmin allocations in cooperative and competitive
fair division. Annals of Operations Research 223(1):121–136, DOI 10.1007/s10479-0141611-9, URL http://dx.doi.org/10.1007/s10479-014-1611-9
Dall’Aglio M, Maccheroni F (2005) Fair Division without Additivity. American Mathematical Monthly pp 363–365, DOI 10.2307/30037474, URL
http://dialnet.unirioja.es/servlet/articulo?codigo=1140450
Dall’Aglio
M,
MaccheroniF(2009)
Disputedlands.
Games
andEconomic
Behavior
66(1):57–77,
DOI
10.1016/j.geb.2008.04.006,
URL
http://eprints.luiss.it/727/1/Dall’Aglio no.58 2007.pdf
Dall’Aglio M, Branzei R, Tijs S (2009) Cooperation in dividing the cake. TOP - the o⌅cial
journal of the Spanish Society of Statistics and Operations Research 17(2):417–432,
DOI 10.1007/s11750-009-0075-6, URL http://dx.doi.org/10.1007/s11750-009-0075-6
Diamantaras D (1992) On equity with public goods. Social Choice and Welfare 9(2):141–157,
DOI 10.1007/bf00187239, URL http://dx.doi.org/10.1007/bf00187239
Diamantaras D, Wilkie S (1994) A Generalization of Kaneko’s Ratio Equilibrium for
Economies with Private and Public Goods. Journal of Economic Theory 62(2):499–512,
DOI 10.1006/jeth.1994.1028, URL http://dx.doi.org/10.1006/jeth.1994.1028
Diamantaras D, Wilkie S (1996) On the set of Pareto e⌅cient allocations in economies
with public goods. Economic Theory 7(2):371–379, DOI 10.1007/bf01213913, URL
http://dx.doi.org/10.1007/bf01213913

Fair Cake-Cutting among Families

29

Dubins LE, Spanier EH (1961) How to Cut A Cake Fairly. The American Mathematical
Monthly 68(1):1–17, DOI 10.2307/2311357, URL http://dx.doi.org/10.2307/2311357
Dvoretzky A, Wald A, Wolfowitz J (1951) Relations among certain ranges of vector measures. Pacific Journal of Mathematics 1(1):59–74, DOI 10.2140/pjm.1951.1.59, URL
http://dx.doi.org/10.2140/pjm.1951.1.59
Even S, Paz A (1984) A Note on Cake Cutting. Discrete Applied Mathematics 7(3):285–
296, DOI 10.1016/0166-218x(84)90005-2, URL http://dx.doi.org/10.1016/0166218x(84)90005-2
Foley DK (1967) Resource allocation and the public sector. YALE ECON ESSAYS 7(1):45–
98
Gamow G, Stern M (1958) Puzzle-math, first edition edn. Viking Adult, URL
http://www.worldcat.org/isbn/0670583359
Guth W, Kliemt H (2002) Non-Discriminatory, Envy Free Provision ofaCollective
Good:
A
Note.
PublicChoice111(1-2):179–184,
URL
http://search.proquest.com/openview/6a73b773b43c00706940913d6ecf5324/1?pqorigsite=gscholarHüsseinov F (2011) A theory of a heterogeneous divisible commodity exchange economy.
Journal of Mathematical Economics 47(1):54–59, DOI 10.1016/j.jmateco.2010.12.001,
URL http://dx.doi.org/10.1016/j.jmateco.2010.12.001
Hüsseinov F, Sagara N (2013) Existence of e⌅cient envy-free allocations of a heterogeneous
divisible commodity with nonadditive utilities. Social Choice and Welfare pp 1–18, DOI
10.1007/s00355-012-0714-y, URL http://dx.doi.org/10.1007/s00355-012-0714-y
Maccheroni F, Marinacci M (2003) How to cut a pizza fairly: Fair division withdecreasing marginal evaluations. Social Choice and Welfare 20(3):457–465, DOI
10.1007/s003550200192, URL http://dx.doi.org/10.1007/s003550200192
Manurangsi P, Suksompong W (2017) Asymptotic existence of fair divisions for groups.
Mathematical Social Sciences 89:100–108
Mirchandani RS (2013) Superadditivity and Subadditivity in Fair Division. Journal of Mathematics Research 5(3):78–91, DOI 10.5539/jmr.v5n3p78, URL
http://dx.doi.org/10.5539/jmr.v5n3p78
Moulin H (2004) Fair Division and Collective Welfare. The MIT Press, URL
http://www.worldcat.org/isbn/0262633116
Procaccia AD (2015) Cake Cutting Algorithms. In: Brandt F, Conitzer V, Endriss U, LangJ, Procaccia AD (eds) Handbook of Computational Social Choice, Cambridge University
Press, chap 13, pp 261–283, URL http://procaccia.info/papers/cakechapter.pdf
Robertson JM, Webb WA (1995) Approximating fair division with a limited number ofcuts. Journal of Combinatorial Theory, Series A 72(2):340–344, DOI 10.1016/00973165(95)90073-x, URL http://dx.doi.org/10.1016/0097-3165(95)90073-x
Robertson JM, Webb WA (1998) Cake-Cutting Algorithms: Be Fair if You Can, 1st edn. A
K Peters/CRC Press, URL http://www.worldcat.org/isbn/1568810768
Sagara N, Vlach M (2005) Equity and E⌅ciency in a Measure Space with Nonadditive
Preferences: The Problem of Cake Division. Journal of Economic Literature 90:1, URL
http://web.econ.keio.ac.jp/sta⇤/maruyama/rcme/seminar/abst050523.pdf
Segal-Halevi E (2018) Cake-Cutting with Di⇤erent Entitlements: How Many Cuts are
Needed? ArXiv preprint 1803.05470
Segal-Halevi E, Nitzan S (2016) Envy-Free Cake-Cutting among Families. URL
http://arxiv.org/abs/1607.01517, arXiv preprint 1607.01517
Segal-Halevi E, Suksompong W (2018) Democratic Fair Allocation of Indivisible Goods. In:
Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI’18), URL http://arxiv.org/abs/1709.02564, arXiv preprint 1709.0256
Segal-Halevi E, Sziklai BR (2018) Monotonicity and Competitive Equilibrium in Cakecutting. Economic Theory URL https://doi.org/10.1007/s00199-018-1128-6, arXiv
preprint 1510.05229
Segal-Halevi E, Hassidim A, Aumann Y (2015) Envy-Free Cake-Cuttingin
TwoDimensions.
In:
Proceedings
of
the
29th
AAAI
Conferenceon
Artificial
Intelligence(AAAI-15),
pp1021–1028,
URL
http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9656, arXiv preprint
1609.03938

30

Erel Segal-Halevi, Shmuel Nitzan

Shishido H, Zeng DZ (1999) Mark-Choose-Cut Algorithms For Fair And Strongly Fair Division. Group Decision and Negotiation 8(2):125–137, DOI 10.1023/a:1008620404353,
URL http://dx.doi.org/10.1023/a:1008620404353
Steinhaus H (1948) The problem of fair division. Econometrica 16(1):101–104, URL
http://www.jstor.org/stable/1914289
Stromquist W (1980) How to Cut a Cake Fairly. The American Mathematical Monthly
87(8):640–644, DOI 10.2307/2320951, URL http://dx.doi.org/10.2307/2320951
Stromquist W, Woodall DR (1985) Sets on which several measures agree. Journal of Mathematical Analysis and Applications 108(1):241–248, DOI 10.1016/0022-247x(85)90021-6,
URL http://dx.doi.org/10.1016/0022-247x(85)90021-6
Su FE (1999) Rental Harmony: Sperner’s Lemma in Fair Division. The American Mathematical Monthly 106(10):930–942, DOI 10.2307/2589747, URL
http://www.math.hmc.edu/˜su/papers.dir/rent.pdf
Suksompong W (2018) Approximate maximin shares for groups of agents. Mathematical
Social Sciences Http://doi.org/10.1016/j.mathsocsci.2017.
09.004
Todo T, Li R, Hu X, Mouri T, Iwasaki A, Yokoo M (2011) Generalizing envy-freeness toward group of agents. In: IJCAI ProceedingsInternational Joint Conference on Artificial Intelligence, vol 22, p 386, URL
https://www.aaai.org/ocs/index.php/IJCAI/IJCAI11/paper/viewFile/3255/3382
Webb WA (1997) How to cut a cake fairly using a minimal number of cuts. Discrete Applied Mathematics 74(2):183–190, DOI 10.1016/s0166-218x(96)00032-7, URL
http://dx.doi.org/10.1016/s0166-218x(96)00032-7