A
Waste Makes Haste: Bounded Time algorithms for Envy-Free Cake
Cutting with Free Disposal
EREL SEGAL-HALEVI and AVINATAN HASSIDIM and YONATAN AUMANN,

arXiv:1511.02599v3 [cs.DS] 9 Feb 2018

Bar-Ilan University, Ramat-Gan 5290002, Israel

We consider the classic problem of envy-free division of a heterogeneous good (“cake”) among several agents.
It is known that, when the allotted pieces must be connected, the problem cannot be solved by a finite
algorithm for 3 or more agents. The impossibility result, however, assumes that the entire cake must be
allocated. In this paper we replace the entire-allocation requirement with a weaker partial-proportionality
requirement: the piece given to each agent must be worth for it at least a certain positive fraction of the
entire cake value. We prove that this version of the problem is solvable in bounded time even when the
pieces must be connected. We present simple, bounded-time envy-free cake-cutting algorithms for: (1) giving
each of n agents a connected piece with a positive value; (2) giving each of 3 agents a connected piece worth
at least 1/3; (3) giving each of 4 agents a connected piece worth at least 1/7; (4) giving each of 4 agents a
disconnected piece worth at least 1/4; (5) giving each of n agents a disconnected piece worth at least (1−ǫ)/n
for any positive ǫ.
CCS Concepts: rTheory of computation → Design and analysis of algorithms;
General Terms: Algorithms, Economics
Additional Key Words and Phrases: Cake-cutting, envy-free, fair division, finite algorithm, perfect matching
ACM Reference Format:
Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann, 2016. Waste Makes Haste: Bounded Time
algorithms for Envy-Free Cake Cutting with Free Disposal. ACM Trans. Algor. V, N, Article A (December
2016), 33 pages.
DOI: DOI

A preliminary version of this paper appeared in the proceedings of AAMAS 2015 [Segal-Halevi et al. 2015b].
In the present paper, the algorithms have been greatly shortened and simplified. Algorithms 3, 4 and 5 are
new.
This paper is supported in part by the Doctoral Fellowships of Excellence Program, Mordecai and Monique
Katz Graduate Fellowship Program, ISF grant 1083/13, ISF grant 1241/12 and BSF grant 2012344.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. Copyrights for components of this work owned
by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
c 2016 ACM. 1549-6325/2016/12-ARTA $15.00
DOI: DOI
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:2

Erel Segal-Halevi et al.

1. INTRODUCTION

Fair cake-cutting is an active field of research with applications in mathematics, economics, and recently also in AI [Procaccia 2015]. The basic setting considers a heterogeneous good, usually described as a one-dimensional interval, that should be divided
among several agents. The different agents may have different preferences over the
possible pieces of the good. The goal is to divide the good among the agents in a way
that is deemed “fair”. Fairness can be defined in several ways, of which proportionality
and envy-freeness are the most commonly used.
Proportionality means that each agent gets at least its “fair-share” of the good, i.e.
with n agents, the piece allotted to each agent is worth for him at least 1/n of the
value of the entire good. Envy-freeness means that every agent believes that its piece
is weakly better than any other piece — no agent would prefer to get a piece allotted to another agent. An additional requirement in cake-cutting, particularly relevant
when the divided resource is land, is connectivity — each agent must be given a single
contiguous piece.
Proportional division is a relatively easy task, and the initial work of Steinhaus
[1948] already provided an algorithm for n agents with connected pieces. The algorithm works in a query model. It asks the agents queries of two types: “what is the
value of piece X for you?” and “what piece is worth a fraction r of the cake for you?”,
and proceeds according to their replies (the query model has been formalized later by
Robertson and Webb [1998]). The number of queries required by Steinhaus’ algorithm
is polynomial in the number of agents.
Envy-free division, on the other hand, turns out to be much more challenging. With
connected pieces, the only algorithm for envy-free division is an infinite one; that is,
it may require an infinite number of queries to reach an envy-free division [Su 1999].
Indeed, Stromquist [2008] proved that this is necessarily so; any algorithm for computing an envy-free division with connected pieces must require an infinite number of
queries on some inputs. This is so even when there are only 3 agents!
A closer examination of these discouraging result reveals that it critically relies on
the assumption that the entire cake must be divided. In many practical situations, it
may be possible to leave some parts of the cake undivided, a possibility termed free
disposal. If, for example, your children spend too much time quarreling over the single
cherry on top of the cake, one practical solution is to eat that cherry yourself and divide
only the rest of the cake. As another example, when dividing land it is usually possible
(and sometimes even desirable) to leave some parts of the land unallocated, so that
they can be used freely by the public. The question of interest in this paper is thus:
If free disposal is allowed, can an envy-free allocation be computed using a
bounded number of queries?
This question, however, turns out to have a trivial, but uninteresting, answer; It is
always possible to give nothing to all agents, which is an envy-free allocation. Thus,
the interesting question is whether it is possible to devise a bounded-time algorithm
for envy-free division in which each agent gets a strictly positive value.
1.1. Results

Our first algorithm provides an affirmative answer to this question:
T HEOREM 1 (S ECTION 4). Assuming free disposal, it is possible to divide a cake
envy-freely among n agents, giving each agent a connected piece with a value of at least
1/2n−1 , using 2n−1 − 1 cuts and O(n · 2n ) queries.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:3

Having established that bounded-time algorithms indeed exist, we next consider the
quality of the solution they offer. We measure the quality of an algorithm by the value
guarantee it gives to each agent. We say that an allocation is EnvyFree[n, M ] if it is
both envy-free and gives each of n agents at least 1/M of the total cake value (a formal
definition is given in Section 2). The algorithm of Theorem 1 finds EnvyFree[n, 2n−1 ]
allocations. Ideally, we would like an EnvyFree[n, n] allocation, which is both envy-free
and proportional and thus satisfies the two most common fairness criteria. Such an allocation guarantees each agent at least 1/n of the total cake value, which is the largest
fraction that can be guaranteed (for example, if all agents have identical valuations, it
is impossible to give all of them more than 1/n).
Our next result shows that the ideal goal of an envy-free and proportional division
with connected pieces can be attained in bounded time for three agents (Section 5):
T HEOREM 2. Assuming free disposal, it is possible to find an EnvyFree[3, 3] allocation with connected pieces using at most 3 cuts and 54 queries.
For 4 agents, we do not have an envy-free-proportional algorithm with connected
pieces. Our best result so far guarantees each agent 1/7 of the total cake value (Section
6):
T HEOREM 3. Assuming free disposal, it is possible to find an EnvyFree[4, 7] allocation with connected pieces using at most 6 cuts and 65 queries.
While this algorithm does not solve the envy-free-proportional problem with connected
pieces, it is useful as a building block for cake-cutting with disconnected pieces, as we
describe next.
Given a pre-specified agent i (which we call the “VIP”), we say that an allocation is
EnvyFreeVIP[n, M ] if it is both envy-free and gives the VIP a piece worth at least
1/M of the total cake value. We prove the following reductions (Sections 7-8):
L EMMA 1. (a) If we can find EnvyFreeVIP[n, M ] allocations using T queries then
we can find an EnvyFree[n, M ] allocation using n · T queries.
(b) If we can find EnvyFreeVIP[n, M ] allocations using T queries, then for every ǫ > 0


n
we can find an EnvyFreeVIP[n, 1−ǫ
] allocation using M lnn(1/ǫ) · T queries.
The allocations found by the algorithm of Theorem 3 are not only EnvyFree[4, 7] but
also EnvyFreeVIP[4, 4]. This allows us to provide an alternative proof to a result of
Saberi and Wang [2009]:1
T HEOREM 4. Assuming free disposal, it is possible to find an EnvyFree[4, 4] allocation using at most 24 cuts and 260 queries.
While the algorithm of Theorem 4 does not guarantee connected pieces, it uses only 24
cuts. This means that the cake is cut to at most 25 pieces, so each agent receives less
than 7 pieces in average.
More importantly, the algorithm used in Theorem 1 finds EnvyFreeVIP[n, 2n−2 + 1]
allocations using O(n · 2n ) queries. This gives:
T HEOREM 5. Assuming free disposal, for every ǫ > 0, it is possible to find an
n
EnvyFree[n, 1−ǫ
] allocation using O(4n ln(1/ǫ)) cuts and O(n · 4n ln(1/ǫ)) queries.
This means that we can find, in bounded time, an envy-free division which is as close
as we want to a proportional division (each agent receives at least (1 − ǫ)/n of the
1 Saberi

and Wang [2009] prove that their protocol is finite but do not calculate the number of queries.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:4

Erel Segal-Halevi et al.

total cake value). The number of queries is linear in the binary representation of the
approximation factor (ǫ).
All our algorithms are very simple and use only a single type of query: the Equalize
query (defined in Section 3). The hard work is done in the correctness proofs. We view
this simplicity as an additional advantage of the free disposal assumption.
Table I summarizes our results and compares them to some related work surveyed
in the next subsection.
1.2. Related work
1.2.1. Earlier cake-cutting algorithms. Cake-divisions are commonly modeled in one of two
ways: in the connected model, the algorithm must give each agent a single contiguous
piece; in the unrestricted model, the algorithm may give each agent several disconnected pieces.
Proportional division is well understood from a computational perspective. The algorithm of Steinhaus [1948] generates a proportional division with connected pieces
in O(n2 ) queries, and an improved algorithm by Even and Paz [1984] requires only
O(n log n) queries. Later results proved that this runtime is asymptotically optimal
even if disconnected pieces are allowed [Woeginger and Sgall 2007; Edmonds and
Pruhs 2011].
Envy-free division is a much harder task, even when only 3 agents are involved. The
first envy-free division algorithm for 3 agents with connected pieces was published by
Stromquist [1980]. This algorithm is not discrete — it requires the agents to simultaneously hold knives over the cake and move them in a continuous manner. This means
that this algorithm cannot be accurately executed by a computer in finite time. There
are simpler algorithms for the same task, e.g. Robertson and Webb [1998][pages 77-78]
and Barbanel and Brams [2004], but they also use moving-knives. A discrete and finite
algorithm for envy-free division for 3 agents was constructed by Selfridge and Conway
[Brams and Taylor 1996]. It requires only 13 queries2 but generates partitions with
disconnected pieces.
Finding an envy-free division among four or more agents was a long-standing open
problem. It was solved only in the 1990’s, both for connected and disconnected pieces.
Su [1999] presented an algorithm, attributed to Forest Simmons, for envy-free division
with connected pieces, but it is not finite — it converges to an envy-free division after
a possibly infinite number of queries. Brams and Taylor [1995], Robertson and Webb
[1998] and Pikhurko [2000] presented three different algorithms for envy-free division
with disconnected pieces; while these algorithms are guaranteed to terminate in finite
time, their run-time is not a bounded function of n.
Two important hardness results were proved in the 2000’s. Stromquist [2008] proved
that an envy-free division with connected pieces cannot be found by any finite algorithm, whether bounded or unbounded. This shows that the connectivity requirement
makes the envy-free division problem strictly more difficult. Shortly afterward, Procaccia [2009] proved an Ω(n2 ) lower bound on the query complexity of any envy-free
division algorithm, even with disconnected pieces. This proved that the problem of
envy-free division is strictly more difficult than the problem of proportional division.
1.2.2. Later cake-cutting algorithms. After the publication of the conference version of
this paper [Segal-Halevi et al. 2015b], several groundbreaking results have been published by Haris Aziz and Simon Mackenzie. Initially [Aziz and Mackenzie 2016a] they
2 The

first cutter makes 2 marks to create three equal pieces. The second makes 2 evals and 1 mark to create
two equal pieces. The third makes 2 evals to select the best piece. In the second phase, again the first cutter
makes 2 marks, then the other two agents make 2 evals to select their best pieces.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

Name
Stromquist [1980]
Robertson and Webb [1998]
Barbanel and Brams [2004]
Su [1999]
Deng et al. [2012]
Brânzei [2015]
Selfridge-Conway
Saberi and Wang [2009]
Reentrant-diminisher
[Brams and Taylor 1996]
Brams and Taylor [1995]
Robertson and Webb [1998]
Pikhurko [2000]
Kurokawa et al. [2013]
Aziz and Mackenzie [2016a]
(see also our Appendix B)
Aziz and Mackenzie [2016b]
Aziz and Mackenzie [2016b]
Aziz and Mackenzie [2016b]
Section 4
Section 5
Section 6
Section 7
Section 8

A:5

Pieces

Agents

Valuations

#Cuts

#Queries

Envy

Prop.

Con.
Con.
Con.
Con.
Dis.
Dis.

3
n
n
n
3
4

General
General
Lipschitz
Polynomials
General
General

2
n−1
n−1
n−1
4
Const.

Infinite
Infinite
O((1/ǫ)n−2 )
O(n2 · d)
13
Const.

0
0
ǫ
0
0
0

1/3 *
1/n *
1/n − ǫ
1/n *
1/3 *
1/4 *

Dis.

n

General

?

O(n2 /ǫ)

ǫ

1/n *

Dis.
Dis.

n
n

General
Piecewise-lin.

Unbounded
?

Unbounded
O(n6 k ln k)

0
0

1/n *
1/n *

Dis.

4

General

203

584

0

1/4 *

0
0
0
0
0
0
0
0

1/n *
1/n *
1/(3n)
1/2n−1
1/3 *
1/7
1/4 *
1/n − ǫ/n

Dis.
Dis.
Con.
Con.
Con.
Con.
Dis.
Dis.

n
n
n
n
3
4
4
n

General
General
General
General
General
General
General
General

?
?
n−1
2n−1 − 1
3
6
24
O(4n ln(1/ǫ))

nn

nn

n

n
nn+1
nn+1
O(n · 2n )
54
65
260
O(n · 4n ln (1/ǫ))

Table I: Envy-free cake-cutting algorithms. Top section shows algorithms developed
prior to this paper. Middle section shows algorithms developed after the conference
version of this paper. Bottom section shows the algorithms presented in this paper.
Legend:
— Pieces column: whether the pieces are Connected or Disconnected.
— Queries column: d and k are parameters of the valuation functions (maximum degree
of polynomials and number of pieces, respectively).
— Envy column: ǫ is an additive approximation constant (every agent values other
pieces at most ǫ more than its own piece).
— Prop column: the expression is the proportion of the total cake value that is guaranteed to all agents. 1/n * implies that the division is proportional.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:6

Erel Segal-Halevi et al.

published the first bounded-time algorithm for envy-free division of an entire cake
among 4 agents. Their algorithm uses at most 584 queries and 203 cuts, which means
that the cake is cut to 204 pieces (so each agent receives 51 pieces in average). In
Appendix B we provide a somewhat simpler presentation of this result, based on our
Algorithm 3.
Later, Aziz and Mackenzie [2016b] published the first bounded-time algorithm for
nn

nn

envy-free division of an entire cake among n agents. Their algorithm uses nn
queries, which is also an upper bound on the number of cuts. The core subroutine in
that paper finds an EnvyFreeVIP[n, n] allocation of a part of the cake using nn queries.
By Lemma 1, this implies that an EnvyFree[n, n] allocation with disconnected pieces
can be found using nn+1 queries assuming free disposal. This result provides an affirmative answer to an open question we posed at the end of Segal-Halevi et al. [2015b].
In their latest working paper3 they present an algorithm that finds an EnvyFree[n, 3n]
allocation with connected pieces using O(nn+1 ) queries, assuming free disposal. This is
a great improvement over our Algorithm 1. Finding an EnvyFree[n, n] allocation with
connected pieces in finite time is still an open problem.
Recently, Amantidis et al. [2018] presented an algorithm for envy-free cake-cutting
for four agents, which improves over the one by Aziz and Mackenzie by being simpler
and requiring less cuts and queries.
1.2.3. Approximations. Cake-cutters have tried to cope with the difficulty of envy-free
division in several ways.
One way is to relax the envy-freeness criterion and allow a small amount of envy.
Brams and Taylor [1996](pages 130-131) describe a re-entrant variant of Steinhaus’
algorithm which produces a division with disconnected pieces in which the envy of
every agent is at most an additive constant ǫ (for every agent, the value of its piece
plus ǫ is at least the value of any other piece). The number of queries is polynomial in n
and linear in (1/ǫ). Deng et al. [2012] present a similar approximation with connected
pieces; here the number of queries is exponential in n and polynomial in (1/ǫ). In
contrast to these results, our algorithms guarantee full envy-freeness. Our algorithm
for disconnected piece also guarantees an additive approximation to proportionality.
The number of queries in our approximation is exponential in n but logarithmic in
(1/ǫ) (in other words, it is linear in the binary representation of the approximation
constant).
A second way is to restrict the value functions of the agents. Kurokawa et al. [2013]
require the value functions to be piecewise-linear and find an envy-free division with
disconnected pieces in time polynomial in the size of the representation of the value
functions. Deng et al. [2012] require the value functions to be Lipschitz-continuous
and find an approximately-envy-free division with connected pieces. Brânzei [2015]
requires the value functions to be polynomials of bounded degree and finds an envyfree division with connected pieces in time polynomial in the maximum degree. In
contrast to these results, our algorithms apply to arbitrary non-atomic value functions,
and their runtime guarantee is a function of only the number of agents but not the
peculiarities of their valuation functions.
1.2.4. Free disposal. The free disposal assumption was introduced into envy-free cakecutting by Saberi and Wang [2009]. They used it only for 4 agents and disconnected
pieces.
Later, free disposal has also been studied by Arzi et al. [2011]. They proved that
discarding some parts of the cake may allow us to achieve an envy-free division with
3 http://arxiv.org/abs/1604.03655v7

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:7

an improved social welfare (i.e. the sum of the utilities of the agents is larger than
in the no-free-disposal case). They call this phenomenon the dumping paradox. Our
paper demonstrate a different kind of a dumping paradox — we show that dumping
some parts of the cake can be beneficial not only from an economic perspective but also
from a computational perspective.
A third scenario in which free disposal is required is when the pieces must have a
pre-specified geometric shape, such as a square [Segal-Halevi et al. 2015a].
There is some related work concerning allocation of indivisible goods where the same
idea of not allocating all the objects is used to get better fairness results [Brams et al.
2013; Aziz 2015].4
Partial-proportionality was introduced by Edmonds and Pruhs [2006] and Edmonds
et al. [2008]. They used it, like us, to reduce the query complexity. Their algorithm gives
each agent at least 1/(a · n) of the total value, where a ≥ 10 is some sufficiently large
constant, with a query complexity of O(n). This is better than the optimum of O(n log n)
required for finding a fully-proportional division. Their algorithm is not envy-free.
1.2.5. Computational models. The most prominent computational model for discrete
cake-cutting is the mark-eval model of Robertson and Webb [1998]: an eval query asks
an agent to reveal its value for a specified piece of cake; a mark query asks an agent
to mark a piece of cake with a specified value. Our algorithms use a single primitive
query — Equalize (defined in Section 3). We prove in Lemma 4.1 that Equalize can
be implemented by a bounded number of mark-eval queries, so all our algorithms are
bounded in the standard model.
A different model, the cut-choose model, was recently suggested by Brânzei et al.
[2016]. In this model, a cut query asks an agent to cut one of a subset of the cakepieces currently on the table; a choose query asks an agent to select one of a subset of
pieces. Our Equalize query is just a bounded sequence of cuts, so our algorithms our
bounded in their model, too.
1.3. Paper structure

The model is formally defined in Section 2. The main tools used in our division algorithms, the preference graph and the Equalize query, are introduced in Section 3.
Sections 4-8 are devoted to proving the theorems. For every k ∈ {1, . . . , 5}, Theorem
k is proved in Algorithm k and Section k + 3.
A detailed, computer-generated correctness proof of the four-agents algorithm of Section 6 is given in Appendix A. An application of that algorithm to an envy-free division
of an entire cake (as in Aziz and Mackenzie [2016a]) is presented in Appendix B.
2. MODEL AND NOTATION

The cake is assumed to be the unit interval [0, 1].
There are n agents, denoted by A1 ,A2 ,...,An . When the number of agents is small,
they are denoted instead by A,B,C,... or by Alice,Bob,Carl...
An allocation of a cake is an n-tuple of pairwise-disjoint subsets of the cake: X1 ∪
· · ·∪Xn ⊆ [0, 1]. When connected pieces are required, each piece Xi must be an interval;
when disconnected pieces are allowed, each piece Xi may be a finite union of intervals.
Each agent Ai has a preference relation i that is represented by a non-negative
value measure Vi on the pieces. The term “measure” implies that it is additive — the
value of a piece is equal to the sum of the values of its parts. All value measures are
absolutely continuous with respect to length. This implies that all singular points have
a value of 0 to all agents, i.e. there are no valuable ”atoms” which cannot be divided.
4 We

thank an anonymous referee for referring us to these papers.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:8

Erel Segal-Halevi et al.

The value measures are normalized such that ∀i : Vi ([0, 1]) = 1. All these assumptions
are standard in the cake-cutting literature.
An allocation X is called envy-free if each agent values his allocated piece at least as
much as every other allocated piece:
∀i, j ∈ {1, ..., n} : Vi (Xi ) ≥ Vi (Xj ) (Equivalently: Xi i Xj )
We say that an allocation X has a proportionality of 1/M if it allocates each agent a
fraction of at least 1/M of the total cake value:
∀i ∈ {1, ..., n} : Vi (Xi ) ≥ 1/M
An allocation with a proportionality of 1/n is usually called a proportional allocation.
An allocation X is called EnvyFree[n, M ] if it is both envy-free and has a proportionality of 1/M . Note that every envy-free allocation of the entire cake is EnvyFree[n, n],5
but this is not necessarily true when some cake remains unallocated.
Given a pre-specified agent Aj , an allocation X is called EnvyFreeVIP[n, M ] with
VIP Aj if it is envy-free, and additionally the VIP receives a value of at least 1/M :
Vj (Xj ) ≥ 1/M
3. TOOLS

Our algorithms are described in a bottom-up approach. We first present basic tools
that perform well-defined tasks, then combine these tools to get a full algorithm. We
believe that the bottom-up approach may be beneficial to future cake-cutters, that may
use our tools to develop improved algorithms.
3.1. The preference graph

At any time during the execution of an algorithm, there is a certain number of pieces
on the table, which together comprise the entire cake. The preference graph is a
bipartite graph, in which the nodes in one side represent the n agents and the nodes
in the other side represent the pieces. The pieces are denoted as numbers with a hat,
e.g. b
1, b
2, etc. There is an edge from an agent Ak to a piece bi if Ak prefers bi, i.e., for every
piece b
j: bi k b
j. Note that an agent can “prefer” two or more pieces. This means that
the agent is indifferent between these pieces but values any of them more than any
other piece. Here are two possible preference graphs for three agents:
A

B

C

A

B

C

b
1

b
2

b
3

b
1

b
2

b
3

Both graphs may be the result of Alice cutting the cake to 3 pieces which are equal
in her eyes. In the left graph, Bob and Carl each prefer a different piece; in the right
graph, they prefer the same piece (b
3).
5 An envy-free allocation gives each agent a piece which is best (for that agent) of n pieces. By the pigeonhole principle, the best of n is worth at least 1/n. Hence, an envy-free allocation of an entire cake has a
proportionality of 1/n.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:9

A saturated matching in a bipartite graph is a subset of the edges, in which each
agent-node has a single neighbor and each piece-node has at most a single neighbor. A
saturating matching in the preference graph corresponds to an envy-free allocation of
a part of the cake, since every agent is allocated a preferred piece.
A well-known tool for proving the existence of saturated matchings in bipartite
graphs is Hall’s marriage theorem. This theorem, applied to our setting, implies the
following lemma:
L EMMA 3.1. If for every k ∈ {1, . . . , n}, every group of k agents jointly prefers at
least k pieces, then an envy-free allocation exists.
In a preference graph, Hall’s condition is always satisfied for groups of k = 1 agents
since every agent has at least one preferred piece.
In the left graph above, Hall’s condition is also satisfied for every group of 2 or 3
agents; this means that an envy-free allocation exists. Indeed, the allocation A-b
1, B-b
2
b
and C-3 is envy-free.
In the right graph above, Hall’s condition is violated by the group {B,C}. In this case,
to get an envy-free allocation, the graph should be transformed in order to create a
graph that meets Hall’s condition. The main query we use to transform the preference
graph is the Equalize query, which is described in the next subsection.
3.2. The Equalize query

Given an integer k ≥ 2, the query Equalize(k) asks an agent to mark zero or more
pieces such that, if the pieces are cut according to these marks, that agent will have at
least k best pieces. For example, in the right graph above, an Equalize(2) query to Bob
implies the following question: “where would you cut piece b
3, your currently favorite
piece, such that you will have two equally-best pieces?”.
Suppose Bob’s second-best piece is b
2. Bob can answer the Equalize(2) question in one
of two ways:
(1) If VB (b
3) ≥ 2VB (b
2), then b
3 should be cut to two pieces of equal value, which is
b
VB (3)/2.
(2) Otherwise, b
3 should be cut to two unequal pieces — one having a value of VB (b
2)
and the other having a smaller value VB (b
3) − VB (b
2).
Note that an Equalize(2) query can be implemented by a constant number of mark
and eval queries of the standard model [Robertson and Webb 1998]. In Section 4 below
we prove that the same is true for k > 2; see Lemma 4.1.
A third option is that VB (b
3) = VB (b
2). In this case, no cutting is needed since Bob
already has two pieces of equal value and better than the third piece. Here and in the
rest of the paper, we ignore such fortunate coincidences. This does not lose generality,
since it only makes it harder to find an envy-free division — it decreases the number
of edges in the preference graph and makes it harder to find a saturated matching.
Formally, we make the following assumption about the preference graph:
Assumption 3.2. After an agent A cuts a piece bi, if an agent B 6= A prefers a piece
b
j 6= bi, then B does not prefer bi.
Assumption 3.2 makes the descriptions of division algorithms simpler since it reduces
the number of cases that need to be handled. We now prove that this simplicity does
not lose generality.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:10

Erel Segal-Halevi et al.

L EMMA 3.3. If there is an algorithm P that finds EnvyFree[n, M ] allocations when
Assumption 3.2 is satisfied, then there is an algorithm P ′ that finds EnvyFree[n, M ]
allocations even when Assumption 3.2 is violated.
P ROOF. We assume that the existing algorithm P is given as a service, that accepts
the current preference graph and replies with the next Equalize query to issue.
The new algorithm P ′ uses this service to simulate P . It issues the Equalize query
sent by P to the agents, collects the agents’ replies, makes the required cuts and updates the preference graph. If the new preference graph violates assumption 3.2, so
that e.g. after agent A cut bi agent B prefers both b
j 6= bi and bi, then P ′ removes the
b
edge B → i and sends to P the reduced graph. The modified graph is also a possible outcome of Equalize(k) and it satisfies assumption 3.2, so P must know how to
handle it. Hence, eventually the simulation is terminated and the reduced preference
graph has a saturated matching which corresponds to an EnvyFree[n, M ] allocation.
The same matching is also a saturated matching on the real preference graph, since
the real preference graph contains (at least) all the edges of the reduced graph. Hence,
P ′ returns an EnvyFree[n, M ] allocation.
Assumption 3.2 has several simple corollaries which are implicitly used below. For
every set X of pieces, define the last cutter of X to be the last agent who made a cut on
any piece from the set X.
— If an agent A prefers a set X of pieces with |X| ≥ 2, then A is the last cutter of X.
— Each two agent-nodes in the preference graph have at most one neighbor at common
(there is at most one piece that both agents prefer).
— If an agent cuts the cake to several equal pieces, then every other agent prefers
exactly one piece (as in the graphs above).
We now return to the three-agent example. If the algorithm implements Bob’s suggested cuts, the preference graph is transformed. If Bob gave an answer of type (1),
it is transformed as in the left graph below; if Bob gave an answer of type (2), it is
transformed as in the right graph:
A

B

b
1

b
2

C

b
3

b
4

A

B

b
1

b
2

C

b
3

b
4

Note that in both cases, the edge A-b
3 is gone, because piece b
3 has been trimmed
by Bob so its value for Alice is probably smaller. By Assumption 3.2, we ignore the
fortunate coincidence in which Bob trimmed a part which happens to be worthless for
Alice. The edges A-b
1 and A-b
2 remain, because these two pieces were not touched by
Bob (Alice is still the last cutter of these pieces).
The dotted edges emanating from C imply that we do not know which piece is preferred by Carl after the cuts, since his previously-best piece — b
3 — has been trimmed.
On the other hand, we know that Bob now prefers two pieces — one of them is the
trimmed b
3 and the other is another piece, which is either his previously-second-best
piece b
2 or the new piece b
4.
Even though we don’t know which piece is now preferred by Carl, we can be sure
that a saturated matching exists. This follows from the following lemma:
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:11

L EMMA 3.4. Suppose the n agents are divided to n − 1 agents whose preferences are
known and one agent whose preferences are unknown. If for every k ∈ {1, . . . , n − 1},
every group of k known agents jointly prefers at least k + 1 pieces, then an envy-free
allocation exists.
P ROOF. Suppose every group of k known agents jointly prefers at least k + 1 pieces.
Then, for any possible preference of the unknown agent, every group of k + 1 agents
jointly prefers at least k + 1 pieces. Additionally, every group of 1 agent always prefers
at least 1 piece. Hence, by Lemma 3.1 an envy-free allocation exists.
In the graphs above, there are two known agents — A and B, and one unknown
agent — C. Each of the known agents prefers two pieces, and the two of them together
prefer 3 or 4 pieces. Hence, whatever C’s preferences are, a saturated matching exists
and an envy-free allocation can be found.
3.3. Example: an algorithm for 3 agents

By now, we have described an envy-free division algorithm for three agents. The algorithm can be succinctly summarized by the following two statements:
Alice: Equalize(3)
Bob: Equalize(2)
In words: the algorithm asks Alice to cut the cake to 3 equal pieces in her eyes, then
asks Bob to cut one of these pieces in order to make 2 equally-best pieces in his eyes.
The outcome always looks like one of the preference graphs above, which means that
a saturated matching exists and each agent can be allocated a best piece.
The last step of the algorithm is to actually find the matching and implement the
corresponding envy-free allocation. To do this in our case, it is sufficient to ask Carl to
pick his best piece, then ask Bob to pick one of his best pieces (which must be the piece
that he trimmed, if it is still available), then ask Alice to pick a remaining piece. In the
rest of this paper, we suppress this last step from the description of our algorithms.
Since a maximum matching in a bipartite graph can always be found in polynomial
time, it is sufficient to prove that the algorithm guarantees that a saturated matching
exists.
3.4. The Envy-Free-Proportionality Lemma

We now calculate the proportionality of the resulting allocation — the value guarantee per agent. This is based on a general lemma which we call the EFP (Envy-FreeProportionality) lemma:
L EMMA 3.5. (EFP Lemma) If a cake is partitioned to a set of M ≥ n pieces
and each agent receives a single preferred piece from that set, then the allocation is
EnvyFree[n, M ].
P ROOF. Envy-freeness is obvious since each agent receives one of his best pieces.
Proportionality is a result of the fact that the value functions of the agents are measures, so they are additive. The sum of the values of all pieces is the value of the entire
cake. Hence, by the pigeonhole principle, the value of any best piece is at least 1/M of
the total cake value.
Going back to our three-agents algorithm, we see that the algorithm partitions the
cake to M = 4 pieces. Hence, by the EFP lemma, it generates an EnvyFree[3, 4] alACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:12

Erel Segal-Halevi et al.

location. This is only a warm-up algorithm; the algorithm of Section 5 generates an
EnvyFree[3, 3] allocation, which are optimal (in terms of proportionality) for 3 agents.
Before continuing with more advanced division algorithms, we need two more tools:
an assumption and a lemma.
3.5. The new-pieces assumption

In all algorithms presented in this paper, the first query is an Equalize query, asking one of the agents to cut N equal pieces, where N ≥ n is some constant (like the
“Alice:Equalize(3)” in Subsection 3.3). The following queries are Equalize(k) queries
where k ≤ N . In the rest of this paper, we make the following additional assumption
on the preference graph starting with the second query:
Assumption 3.6. In any query after the first query, when a new piece is created by
a cut, it is not the preferred piece of any agent.
So in the example of Subsection 3.2, we assume that after “Bob:Equalize(2)” the preference graph looks like the rightmost graph. This assumption does not lose generality
because, from Hall’s perspective, it only makes it harder to find a saturated matching
— it concentrates the same number of edges over a smaller number of piece nodes.
Formally:
L EMMA 3.7. If there is an algorithm P that finds EnvyFree[n, M ] allocations when
Assumption 3.6 is satisfied, then there is an algorithm P ′ that finds EnvyFree[n, M ]
allocations even when Assumption 3.6 is violated.
P ROOF. Similarly to Lemma 3.3, P ′ simulates P by reading the next Equalize query,
issuing it to the agents and updating the preference graph.
Suppose the m-th query in P (m ≥ 2) is Equalize(k). This query creates k − 1 new
pieces. The algorithm P ′ defines an injection fm , which maps every new piece b
j to a
unique original piece fm (b
j). By “original piece” we mean one of the pieces generated by
the first Equalize query. There are at least N original pieces and k ≤ N , so an injection
fm always exists.
P ′ then constructs a reduced preference graph, by converting any edge Ai → b
j (for
every agent Ai and new piece b
j) to an edge Ai → fm (b
j). P ′ then sends the reduced
graph to P . The reduced graph corresponds to a possible outcome of Equalize(k) and
it satisfies Assumption 3.6, so P must know how to handle it. Hence, eventually the
simulation is terminated and the reduced preference graph has a saturated matching.
This matching corresponds to an EnvyFree[n, M ] allocation in which each Ai receives
a piece Xi , which is one of the original pieces.
For every original piece Xi where i ∈ {1, . . . , N }, define the set Yi = {Xi } ∪{b
j|fm (b
j) =
Xi , m ≥ 2}. This is the set of all pieces that were mapped to Xi at some point during
the simulation of P . The sets Yi are pairwise-disjoint, since each new piece is mapped
to a single original piece.
In the reduced graph, there is a preference edge Ai → Xi . By construction, this
preference edge comes from some edge in the real graph, Ai → b
j where b
j ∈ Yi . Hence,
for every Ai , the set Yi contains some piece which is a best piece for Ai .
As a final step, P ′ asks each Ai to select a best piece from the set Yi . The total number
of pieces (M ) is unchanged. Hence, the resulting allocation is EnvyFree[n, M ].
Hence, the new pieces are omitted from the preference graphs; only their total number is kept in mind for the sake of calculating the proportionality.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:13

3.6. The unknown-agent lemma

L EMMA 3.8. Suppose the n agents are divided to n − 1 agents whose preferences are
known and one agent whose preferences are unknown. If every known agent prefers at
least 2 pieces, then an envy-free allocation exists.
P ROOF. By Lemma 3.4, it is sufficient to prove that every k known agents jointly
prefer at least k + 1 pieces. The proof is by induction on k. The base k = 1 is given.
Suppose the lemma is true for all groups of less than k known agents. Consider a
group of k known agents A1 , . . . , Ak . Each of these agents prefers at least two pieces.
By Assumption 3.2, each of these agents was the last one to cut at least one of his two
preferred pieces. Suppose that the last agent to cut one of his preferred pieces was A1 .
Suppose that A1 prefers pieces b
1,b
2 and that he was the last agent to cut b
1.
By Assumption 3.2 again, any other agent that prefers b
1 does not prefer any other
piece. This means that any other known agent does not prefer b
1. By the induction
assumption, agents A2 , . . . , Ak jointly prefer k pieces, which must be different than b
1.
With b
1, agents A1 , . . . , Ak jointly prefer k + 1 pieces.
4. CONNECTED PIECES AND

n AGENTS

Generalizing the 3-agent algorithm from the Section 3 to n agents requires the following building blocks: an Equalize(k) query for arbitrary k, and a generalized version of
Lemma 3.8. We now describe each of these generalizations in turn.
Answering an Equalize(k) query for k ≥ 3 is a non-trivial task. There are many
different options. For example, a reply to Equalize(3) can have one of the following
forms:
(1) Cutting the best piece to three equal pieces, which are all better than the previously second-best piece; or (2) Trimming the best piece such that it is twice as valuable as the second-best piece,
then cutting the result to two halves; or (3) Trimming both the best and the second-best pieces, such that the trimmed pieces
are equal to the third-best piece.
Naturally, the number of options grows as k becomes larger.
Fortunately, Equalize(k) can be answered using a bounded number of mark and eval
queries. We prove this by reducing Equalize(k) to the following problem:
EnvyFreeStickDivision[m,k]: Given m sticks of different lengths, make
a minimal number of cuts such that there are at least k pieces with equal
lengths and no other piece is longer.
Reitzig and Wild [2017] have recently presented an algorithm that solves the envy-free
stick-division problem in time O(m). The algorithm works as follows. First, based on
the lengths of the m sticks, it calculates an “optimal length”, l∗ . This is defined as the
largest l such that it is possible to cut at least k pieces of length l. Then, it cuts l∗ -sized
pieces off of any stick longer than l∗ until all sticks have length at most l∗ . We use their
algorithm to prove the following lemma.
L EMMA 4.1. When there are m pieces on the table, an agent’s answer to an
Equalize(k) query can be calculated using m − 1 eval queries and k − 1 mark queries.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:14

Erel Segal-Halevi et al.

Algorithm 1 Finding EnvyFree[n, 2n−1 ] allocations with connected pieces.
For u = n − 1 to 1:
An−u : Equalize(2u−1 + 1).
P ROOF. Denote the pieces currently on the table by X1 , . . . , Xm . Use m − 1 eval
queries to find the agent’s valuations to these pieces, Vi (X1 ), . . . , Vi (Xm ).6 Create m
sticks, such that the length of stick j is Vi (Xj ). Use the algorithm of Reitzig and Wild
[2017] for EnvyFreeStickDivision[m,k] to find the optimal length l∗ . Using k − 1 mark
queries, mark k pieces that the agent values as exactly l∗ .7 By definition of EnvyFreeStickDivision, the values of all other pieces are at most l∗ , so this is a correct answer
to Equalize(k).
The next tool we need is a generalization of Lemma 3.8.
L EMMA 4.2. Suppose the n agents are divided to n − u agents whose preferences
are known and u agents whose preferences are unknown. If every known agent prefers
at least 1 + 2u−1 pieces, then an envy-free allocation can be attained with a bounded
number of queries.
P ROOF. The proof is by induction on u. The base u = 1 is Lemma 3.8. Assume the
claim is true for u; we have to prove it for u + 1 unknown agents.
Suppose the known agents are A1 , . . . , An−u−1 and the unknown agents are
An−u , . . . , An . Suppose that every known agent prefers at least 1+2u pieces. We have to
prove that an envy-free allocation can be attained with a bounded number of queries.
Ask agent An−u to Equalize(1 + 2u−1 ). This requires it to trim at most 2u−1 pieces
and guarantees that it prefers 1 + 2u−1 pieces. Every known agent still prefers at least
(1 + 2u ) − 2u−1 = 1 + 2u−1 pieces. Hence, by adding An−u to the set of known agents,
the situation becomes exactly as in the induction assumption: there are u unknown
agents each of whom prefers 1 + 2u−1 pieces. Hence, by the induction assumption an
envy-free allocation can be attained with a bounded number of queries.
The proof of Lemma 4.2 above immediately translates to a division algorithm (Algorithm 1). Initially, all agents are unknown. A1 is asked to Equalize(2n−2 + 1) and
becomes a known agent. Each step, another agent is asked to Equalize and becomes a
known agent. Finally, An−1 is asked to Equalize(2); then, each of the first n − 1 agents
prefers at least 2 pieces, and by Lemma 3.8 a saturated matching exists.8
Each Equalize action requires 2u−1 cuts. Hence the total number of cuts required is:
n−1
X

2u−1 = 2n−1 − 1

u=1

and the total number of pieces after the last cut is 2n−1 . By the EFP Lemma, the
division is envy-free and each agent receives a connected pieces with value at least:
1
2n−1
The algorithm uses n Equalize queries, each of which can be calculated using O(2n )
mark-eval queries. This proves our Theorem 1.
6 only

m − 1 evals are needed, since the m-th value can be calculated based on the other values and the
additivity of Vi .
7 Only k − 1 marks are needed, since for the maximum length l∗ , at least one stick is cut evenly with no
remainder.
8 The matching can be implemented by letting the agents pick pieces in reverse order, from n to 1.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:15

Algorithm 2 Finding EnvyFree[3, 3] allocations — envy-free and proportional for 3
agents with connected pieces.
One of:
Alice:Equalize(3)
Alice:Equalize(3); Bob:Equalize(2)
Alice:Equalize(3); Carl:Equalize(2)
Bob:Equalize(3)
Bob:Equalize(3); Alice:Equalize(2)
Bob:Equalize(3); Carl:Equalize(2)
Carl:Equalize(3)
Carl:Equalize(3); Alice:Equalize(2)
Carl:Equalize(3); Bob:Equalize(2)

Remark 4.3. The algorithm presented above is similar to an algorithm mentioned
by Brams and Taylor [1996] (chapter 7, page 135) as a sub-routine of their unbounded
algorithm for envy-free cake-cutting with disconnected pieces. However, their subroutine does not use the generalized Equalize query and hence does not guarantee
any positive proportionality with connected pieces.
5. CONNECTED PIECES AND 3 AGENTS

Our goal in this and the next section is to improve the proportionality from the exponential figure guaranteed by the algorithm of Section 4. In this section we focus on
the case of 3 agents. We first note that any algorithm starting with a pre-specified
agent cutting 3 equal pieces cannot guarantee a proportionality of more than 1/4 with
connected pieces (since the values of these pieces in the eyes of the other two agents
might be 1/2, 1/4 and 1/4). However, when the cutting agent can be selected according
to preferences, the optimal proportionality — 1/3 — is attainable. This can be done by
Algorithm 2.
The “One of ” statement means that the algorithm should try each of the 9 execution
branches on paper, and check whether it “succeeds” (i.e, leads to an envy-free and
proportional division). Whenever an execution branch succeeds, the algorithm stops
and implements the resulting allocation on the real cake. We now prove that at least
one branches indeed succeeds.
L EMMA 5.1. For every preferences of the agents, there is at least one branch of Algorithm 2 in which the resulting allocation is EnvyFree[3, 3].
P ROOF. It is convenient to normalize the valuations such that each agent values
the entire cake as 3. Hence, proportionality requires that each agent receives a value
of at least 1.
Note that in each branch, the agent that does the initial Equalize(3) always has at
least one whole piece to choose, so he always feels no envy and has a value of at least
1. It remains to prove that the same is true for the other two agents. I.e, in at least one
branch, there is an envy-free allocation and for every agent there is a piece worth at
least 1.
Assume, for the sake of the proof, that each agent marks two points in the interval
[0, 1] that partition it to three intervals equal in his eyes. Denote the equal pieces of
agent X by: b
1X , b
2X and b
3X , such that the value of biX to agent X is exactly 1.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:16

Erel Segal-Halevi et al.

Assume w.l.o.g. that the order of the first lines is A-B-C. Hence: b
1A ⊆ b
1B ⊆ b
1C . There
are 3! = 6 options for the order of the second lines.9 We treat each of these cases in
turn. Each case is illustrated by a picture; the vertical gray lines in the pictures are
the cuts made by the agent who does the “Equalize(3)” in the successful branch.
5.1. C-B-A

A

b
1C

B

C

b
2C

C

B

b
3C

A

Ask Carl to Equalize(3) by cutting the cake at the points marked by “C” in the above
picture (the vertical gray lines). Both Alice and Bob value two pieces — b
1C and b
3C —
as at least 1. This can be easily seen in the picture. E.g, the fact that Alice’s leftmost
mark is inside b
1C means that Alice values a subset of b
1C as exactly 1, so she values b
1C
as at least 1. The same is true for piece b
3C and for Bob.
Ask either Alice or Bob to Equalize(2). At most one piece is trimmed, so for each
agent, at least one remaining piece has value at least 1. Moreover, both the cutter and
Carl have two preferred pieces, so by Lemma 3.8 an envy-free allocation exists. So the
branch “Carl:Equalize(3); Alice:Equalize(2)” succeeds (the branch “Carl:Equalize(3);
Bob:Equalize(2)” also succeeds, but we only need one successful branch).
5.2. C-A-B

A

b
1C

B

C

b
2C

C

A

b
3C

B

The analysis of the case C-B-A applies as-is to this case.
5.3. A-B-C

b
1B
A

B

C

b
2B

A

B

b
3B
C

Ask Bob to Equalize(3). If Alice and Carl prefer different pieces, then we are done
— an envy-free allocation exists with the current 3 pieces, so by the EFP lemma the
proportionality is 1/3. The branch “Bob:Equalize(3)” succeeds.
Otherwise, Alice and Carl prefer the same piece. This piece must be b
2B , since b
1B is
b
worth less than 1 for Carl and 3B is worth less than 1 for Alice. This means that b
2B is
worth more than 1 for both Alice and Carl. Hence, each of them has two pieces worth
at least 1: b
1B and b
2B for Alice, b
2B and b
3B for Carl. This is the same situation as in
the case C-B-A. An Equalize(2) by either Alice or Carl guarantees an envy-free and
proportional division. So the branch “Bob:Equalize(3); Alice:Equalize(2)” succeeds.

9 We

ignore the fortunate case in which two or more agents make a mark in the exact same spot. This case
can be handled by assuming an arbitrary order between these agents.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:17

5.4. B-A-C

b
1B
A

B

C

b
2B

B

A

b
3B

C

Ask Bob to Equalize(3). Alice values two pieces — b
1B and b
3B — as at least 1. Ask Alice
to Equalize(2). Alice still has two pieces with a value of at least 1. As for Carl, there
are two cases: If Alice trimmed b
1B , then b
3B remains untouched; its value for Carl is
b
more than 1. If Alice trimmed 3B , then she must have trimmed at or to the left of the
second A (since its value for her must be at least the value of b
1B , which is at least 1):
Alice
A

Bob
B

B

C

A

Carl
C

Hence, the value of the trimmed piece for Carl is still at least 1. So the branch
“Bob:Equalize(3); Alice:Equalize(2)” succeeds.
5.5. A-C-B

A

b
1C

B

b
2C

C

A

C

b
3C
B

The previous case, A-B-C-B-A-C, is symmetric to A-B-C-A-C-B. This can be seen by
renaming the agents from A-B-C to B-C-A and reversing the order of lines. The branch
“Carl:Equalize(3); Bob:Equalize(2)” succeeds.
5.6. B-C-A

The last sub-case is handled according to Alice’s preferences — whether she prefers b
1B
(which contains b
1A ) or b
3C (which contains b
3A ). Note that Alice values both these pieces
as at least 1.
If Alice prefers b
1B , then ask Bob to Equalize(3). Alice values two pieces as at least
1. Ask her to Equalize(2). For Carl there are two cases: If Alice trimmed b
1B , then b
3B
remains untouched; its value for Carl is more than 1. If Alice trimmed b
3B , then she
must have trimmed it at or to the left of the C mark, since she values b
1B more than
b
3C :
Alice
A

Bob
B

C

B

C

Carl
A

Hence, the value of the trimmed piece for Carl is still at least 1. The branch
“Bob:Equalize(3); Alice:Equalize(2)” succeeds.
If Alice prefers b
3C , then ask Carl to Equalize(3). Alice still values two pieces as
at least 1. Ask her to Equalize(2). For Bob there are two cases: If Alice trimmed b
3C ,
b
b
then 1C remains untouched; its value for Bob is more than 1. If Alice trimmed 1C , then
she must have trimmed it at or to the right of the B mark, since she values b
3C more
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:18

Erel Segal-Halevi et al.

Algorithm 3 Finding allocations which are both EnvyFreeVIP[4, 4] and EnvyFree[4, 7]
with connected pieces.
Alice:Equalize(4)
One of:
Bob:Equalize(2); Carl:Equalize(2)
Bob:Equalize(3); Carl:Equalize(2)
Carl:Equalize(2); Bob:Equalize(2)
Carl:Equalize(3); Bob:Equalize(2)
than b
1B . Hence, the value of the trimmed piece for Bob is still at least 1. The branch
“Carl:Equalize(3); Alice:Equalize(2)” succeeds.

Bob
A

Carl
B

C

B

C

Alice
A

This completes the correctness proof of the 3-agents division algorithm.10
We now count the number of mark-eval queries required by Algorithm 2 in the worst
case. In order to try all 9 execution branches, the algorithm has to do three different
Equalize(3) statements, each of which requires 2 marks, and six Equalize(2) statements, each of which requires 2 evals (since there are three pieces on the table) and 1
mark. To check whether a branch succeeds (and implement the envy-free allocation if
it exists), the algorithm should ask the agent/s who have not touched the cake so far
to evaluate the pieces. This requires 4 evals in the three short branches and 3 evals in
the six long ones. All in all, at most 3 ∗ 2 + 6 ∗ 3 + 3 ∗ 4 + 6 ∗ 3 = 54 queries are required.
This completes the proof of our Theorem 2.
6. CONNECTED PIECES AND 4 AGENTS

Encouraged by the performance of the algorithm of Section 5, we would like to extend
it to produce a connected envy-free and proportional allocation for n agents. Unfortunately, the number of different cases becomes prohibitively large even for n = 4
agents. The equal partition of each agent is made by 3 parallel marks, so if we name
the agents according to their 1st mark, the number of options for the following two
marks is (4!)2 = 576, and in general (n!)n−2 . The algorithm for each specific case may
be short, but writing down all the different cases takes too long to be practical.
Therefore we walk in a different direction and present Algorithm 3 for 4 agents,
which we call Alice, Bob, Carl and Dana. The main guarantee of this algorithm is:
L EMMA 6.1. For every preferences of the agents, there is at least one branch of Algorithm 3 in which, in the resulting preference graph, each of Alice Bob and Carl prefers
at least 2 pieces.
By Lemma 3.8, this implies that Algorithm 3 finds an envy-free allocation regardless
of Dana’s preferences. Since at least one of Alice’s original pieces remains untouched,
the resulting allocation is also EnvyFreeVIP[4, 4] (Alice is the VIP). The total number
of cuts in each branch is at most 6 so the total number of pieces is at most 7. Hence the
resulting allocation is EnvyFree[4, 7].
10 Note

that the proof did not use all 9 branches in the algorithm. This is because the proof arbitrarily named
the agents A, B and C according to the order of their leftmost division line. If the agents’ names are given,
each of the 9 branches may be required.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:19

We now count the number of mark-eval queries required. The first Equalize(4) requires 3 marks. The second Equalize requires 3 evals (since there are 4 pieces on the
table) and 1 or 2 marks; the last Equalize requires 4 or 5 evals (depending on the number of pieces on the table) and 1 mark. Checking whether a branch succeeds requires
asking Dana 5 or 6 evals. All in all, the number of queries required in all paths is
3 + (3 + 1 + 4 + 1 + 5) + (3 + 2 + 5 + 1 + 6) + (3 + 1 + 4 + 1 + 5) + (3 + 2 + 5 + 1 + 6) = 65,
as claimed in our Theorem 3.

P ROOF OF L EMMA 6.1. After Alice:Equalize(4), there are four pieces on the table.
We rename the pieces, if needed, such that Bob’s preference ordering on these pieces
is: b
1b
2b
3b
4. Now there are 4! = 24 possible preference orderings for Carl. Since
checking 24 cases is a tedious task, we wrote a program in SageMath [Developers
2015] to do it. Our program generates a textual proof that can be read and verified
independently of the program itself (i.e, it is not required to believe that the program
is bug-free in order to verify the proof). The entire proof is given in Appendix A. Below,
we explain the typical cases in detail.
Mark piece bi after agent X cuts it during Equalize(2) by biX and during Equalize(3)
by biXX . The following graphs show the preferences of Alice and Bob after Bob does
Equalize(2) (left) or Equalize(3) (right):

A

B

C

D

A

B

C

D

b
1

b
2

b
3

b
4B

b
1

b
2

b
3BB

b
4BB

Of the 24 possible preference orders of Carl, there are 6 cases in which the best piece
of Carl is b
1. This obviously remains Carl’s best piece after Bob trims some other pieces.
This means that when Carl does Equalize(2), piece b
1 is trimmed. Looking at the left
graph, we see that afterwards, each of Alice Bob and Carl prefers at least two pieces.
This means that the branch starting with “Bob:Equalize(2)” succeeds. The same is
true for the 6 cases in which Carl’s best piece is b
2; we have already covered 12 out of
24 cases.
Next, consider the four cases in which Carl’s best piece is b
3 and Carl’s second-best
piece is b
1 or b
2. Then, after Bob:Equalize(2), Carl’s best piece is b
3 and trimming it leaves
only one best piece for Bob, so the branch starting with “Bob:Equalize(2)” fails. On the
other hand, after Carl:Equalize(2), Bob’s best piece is still b
4 and trimming it leaves two
best pieces for Alice and Carl, so the branch starting with “Carl:Equalize(2)” succeeds.
So far, 16 of 24 cases are covered.
Next, consider the two cases in which Carl’s best piece is b
4 and second-best piece is
b
b
1. After Bob:Equalize(2), 4B may or may not be Carl’s best piece:
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:20

Erel Segal-Halevi et al.

A

B

C

D

A

B

C

D

b
1

b
2

b
3

b
4B

b
1

b
2

b
3

b
4B

The easy case is that for Carl, b
4B  b
1  b
4 (left); then, Carl:Equalize(2) trims
b
1 and leaves two best pieces for Alice and Bob, and the branch starting with
“Bob:Equalize(2)” succeeds. The hard case is b
1b
4B  b
4 (right); then, Carl:Equalize(2)
trims b
4B and leaves only one best piece for Bob, and the branch starting with
“Bob:Equalize(2)” fails. But now, consider the branch starting with “Carl:Equalize(2)”.
Carl trims piece b
4 to make it equal to b
1. But because b
1b
4B  b
4, Carl must trim b
4 to a
shorter length than b
4B (we assume that all agents trim the pieces from the same direction), so b
4C ⊆ b
4B . This means that, if the branch “Bob:Equalize(2)” fails, the following
preference relation must be true globally (for all agents):
b
4C  b
4B

In particular, it must be true for Bob. But by definition, for Bob, b
4B and b
3 are equal.
Hence, for Bob: b
4C  b
3. This means that, after the initial Carl:Equalize(2), Bob’s best
piece is b
3:
A

B

C

D

b
1

b
2

b
3

b
4C

Now, Bob:Equalize(2) leaves two best pieces for both Alice and Carl, so the branch
starting with “Carl:Equalize(2)” succeeds.
An almost identical argument applies in the two cases in which Carl’s best piece is
b
4 and second-best piece is b
2, so we already covered 20 of 24 cases; in each of these
cases, either the branch starting with “B:Equalize(2)” or the branch starting with
“C:Equalize(2)” succeeds.
The other two branches are used in the remaining four cases: in each of these
cases, either the branch starting with “B:Equalize(3)” or the branch starting with
“C:Equalize(3)” must succeed. The proof uses similar arguments to the one explained
above: if the branch starting with “B:Equalize(3)” fails, then some global containment
relations are implied between b
4BB and b
4CC and between b
3BB and b
3CC . These relations
imply that the branch starting with “C:Equalize(3)” must succeed. Although the proof
is longer, the principle is the same so we leave the details to the printout in Appendix
A.
Lemma 6.1 lets us improve the algorithm of Section 4. We note that the core of
that algorithm is Lemma 4.2, which is exponential in nature — it requires that every
known agent prefers 1 + 2u−1 pieces whenever there are u known agents. We would
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:21

like to reduce this figure to 1 + u. Since for u ∈ {1, 2} these two expressions are equal,
we focus on the case u = 3:
L EMMA 6.2. Suppose the n agents are divided to n − 3 agents whose preferences
are known and 3 agent whose preferences are unknown. If every known agent prefers at
least 4 pieces, then an envy-free allocation exists.
P ROOF. Call the three unknown agents Bob, Carl and Dana. Apply Algorithm 3
without the first step “Alice:Equalize(4)”. The assumption of the lemma implies that
every known agent is in the same situation as Alice after the first step. This means
that after the algorithm completes, all agents except the last unknown agent prefer
two pieces. By Lemma 3.8, an envy-free allocation exists.
Lemma 6.2 can be plugged as a base case into Lemma 4.2 to get the following improved lemma:
L EMMA 6.3. Suppose the n agents are divided to n − u agents whose preferences are
known and u agents whose preferences are unknown, where u ≥ 3. If every known agent
prefers at least 1 + 3 · 2u−3 pieces, then an envy-free allocation can be attained with a
bounded number of queries.
The proportionality of the division algorithm of Section 4 improves to 1/[ 43 · 2n−1 + 1].
Remark 6.4. The symmetry of Algorithm 3 hints that it may be generalizable to
5 or more agents. In particular, we thought that an algorithm such as the following
might work:
Alice:Equalize(5)
One of:
Bob:Equalize(2); Carl:Equalize(2); Dana:Equalize(2)
Bob:Equalize(2); Carl:Equalize(3); Dana:Equalize(2)
Bob:Equalize(3); Carl:Equalize(2); Dana:Equalize(2)
Bob:Equalize(3); Carl:Equalize(3); Dana:Equalize(2)
Bob:Equalize(4); Carl:Equalize(2); Dana:Equalize(2)
Bob:Equalize(4); Carl:Equalize(3); Dana:Equalize(2)
[and similarly for the other 5 permutations of Bob, Carl, Dana]
We checked this possibility using our SageMath program, but found a specific combination of preferences in which all these branches fail to produce a saturated matching.11
7. DISCONNECTED PIECES AND 4 AGENTS

In this and the following section, we use our results from the connected case to prove
better proportionality bounds in the disconnected case. We show that, if the pieces may
be disconnected, we can have an envy-free division in which the value of each agent
is arbitrarily close to 1/n, in bounded time. This is done using two general reduction
lemmas which rely on envy-free-VIP algorithms.
L EMMA 7.1. (Weak Reduction Lemma) For every n and M ≥ n,
If there is an algorithm for finding EnvyFreeVIP[n, M ] allocations using T (n) queries,
11 One

such case is when Bob’s preference order is 1  2  3  4  5, Carl’s order is also 1  2  3  4  5
while Dana’s order is 1  3  2  4  5. See http://github.com/erelsgl/envy-free for the source code and
proof.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:22

Erel Segal-Halevi et al.

Algorithm 4 Finding EnvyFree[4, 4] allocations with disconnected pieces.
Let C ′ = C.
For i = 1 to 4:
Rename Ai to “Alice”;
Divide C ′ using Algorithm 3;
Let C ′ = the subset that remained unallocated.
then there is an algorithm for finding EnvyFree[n, M ] allocations using n · T (n)
queries.
P ROOF. (generalizing an idea of Saberi and Wang [2009]). The idea is to use the
existing algorithm n times, each time on the remainder of the previous time and with
a different agent as the VIP. This ensures that all agents enjoy the VIP proportion of
1/M .
Let C be the original cake. Run EnvyFreeVIP[n, M ] on C with agent A1 as the VIP.
The result is an allocation of a certain subset of C (say, C ′ ⊆ C) with the following
properties:
— The allocation of C ′ is envy-free.
— Hence, by the pigeonhole principle, every agent Ai has a value of at least Vi (C ′ )/n ≥
Vi (C ′ )/M .
— Moreover, A1 holds a value of at least V1 (C)/M .
If C ′ = C, then we are done since every agent Ai holds a value of at least
Vi (C)/M . Otherwise, there is a remainder, C ′ = C \ C ′ , that should be divided. Run
EnvyFreeVIP[n, M ] on that remainder with A2 as the VIP. The result is an allocation
of a certain subset C ′′ ⊆ C ′ with the following properties:
— The allocation of C ′′ is envy-free.
— Hence, by the pigeonhole principle, every agent Ai holds a value of at least
Vi (C ′′ )/n ≥ Vi (C ′′ )/M .
— Moreover, A2 has a value of at least V2 (C ′ )/M .
Combining the two previous allocations, we now have an allocation of C ′ ∪ C ′′ , with
the following properties:
— The allocation of C ′ ∪ C ′′ is envy-free (since it is a combination of two envy-free
allocations).
— Hence, by the pigeonhole principle, every Ai has a value of at least Vi (C ′ ∪ C ′′ )/n ≥
Vi (C ′ ∪ C ′′ )/M .
— A1 (still) has a value of at least V1 (C)/M , since nothing was taken from him.
— A2 has a value of at least V2 (C ′ )/M + V2 (C ′ )/M , which is at least V2 (C)/M .
So after the second division, we have an envy-free division in which both A1 and A2
hold at least 1/M of their total cake value.
If C ′ ∪C ′′ = C then we are done. Otherwise, there is a remainder C ′ ∪ C ′′ that should
be divided. Continue in the same way: run EnvyFreeVIP[n, M ] on that remainder with
agent A3 as the VIP, then with A4 as the VIP, and so on. It is easy to prove by induction
that, after at most n runs, all agents have at least 1/M of their total cake value.
The Weak Reduction Lemma is most useful in the case M = n. Note that an
EnvyFree[n, n] allocation is both envy-free and proportional. The Weak Reduction
Lemma implies that such an allocation can be found using an algorithm which guarantees a value of at least 1/n to a single VIP agent.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:23

n
] allocations with disconnected pieces.
Algorithm 5 Finding EnvyFreeVIP[n, 1−ǫ

Rename the agents such that the VIP is A1 .
Let C ′ = C.
For t = 1 to ⌈(2n−2 + 1) ln (1/ǫ)/n⌉:
Divide C ′ using Algorithm 1;
Let C ′ = the subset that remained unallocated.
The 4-agent algorithm of Section 6 finds an EnvyFreeVIP[4, 4] allocation using at
most 6 cuts and 65 queries, so an EnvyFree[4, 4] allocation can be found using at most
6 ∗ 4 = 24 cuts and 65 ∗ 4 = 260 queries. This proves our Theorem 4.
8. DISCONNECTED PIECES AND

n AGENTS

The following lemma allows us to approach an EnvyFreeVIP[n, n] allocation to any
desired precision.
L EMMA 8.1. (Strong Reduction Lemma) For every n, M > n and ǫ > 0:
If there is an algorithm for finding EnvyFreeVIP[n, M ] allocations using T (n) queries,
n
then there is an algorithm for finding EnvyFreeVIP[n, 1−ǫ
] allocations using
 M ln (1/ǫ) 
· T (n) queries.
n
P ROOF. The main idea is to use the existing algorithm many times, each time on
the remainder of the previous time, with the same agent as the VIP. The value of the
VIP agent grows like a geometric series and converges to 1/n. Hence, after a sufficient
number of runs, the VIP agent’s value is at least (1 − ǫ)/n.
The proof uses the following notation:
— t — the number of times the EnvyFreeVIP[n, M ] algorithm has been run on successive remainders.
— Ct′ (t ≥ 1) — the part of C allocated at time t.
— Ct (t ≥ 0) — the total cake allocated up to and including time t (Ct := ∪tj=1 Cj′ ).
— Vt′ (t ≥ 1) — the value given to the VIP agent at time t.
Pt
— Vt (t ≥ 0) — the total value held by the VIP agent after time t (Vt := j=1 Vj′ ).
We first prove that, in every time t ≥ 1:
Vt′ ≥ [1 − nVt−1 ]/M

(1)

P ROOF. Since all allocations are envy-free, the cumulative allocation of Ct−1 is also
envy-free. This means that the VIP agent, like all other agents, holds at least a proportional share of it:
Vt−1 ≥ V (Ct−1 )/n
At time t, the cake that remains to be divided is C \ Ct−1 . The VIP agent receives at
least a fraction 1/M of it:
Vt′ ≥ [1 − V (Ct−1 )]/M
Combining the previous two inequalities gives the desired inequality.
Next we prove that in every time t ≥ 0:
Vt ≥

1 − (1 − n/M )t
n

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

(2)

A:24

Erel Segal-Halevi et al.

P ROOF. By induction on t. For t = 0, by definition V0 = 0. Suppose the claim is true
for t, so there is a constant d ≥ 0 such that:
Vt =

1 − (1 − n/M )t
+d
n

By inequality (1):
′
Vt+1
≥ [1 − nVt ]/M

By the induction assumption, 1 − nVt = (1 − n/M )t − nd. Hence:
′
Vt+1
≥ [(1 − n/M )t ]/M − nd/M

So:
1 − (1 − n/M )t + (n/M )(1 − n/M )t
+ d(1 − n/M )
n
Because M ≥ n, the rightmost term is positive and we get the desired inequality:
′
Vt+1 = Vt + Vt+1
≥

Vt+1 ≥

1 − (1 − n/M )t+1
n

By inequality (2), to get a value of at least Vt ≥ (1 − ǫ)/n, it is sufficient to choose t
such that:
(1 − n/M )t ≤ ǫ
The latter inequality is true whenever:
t≥

ln(1/ǫ)
ln ǫ
=
ln(1 − n/M )
− ln(1 − n/M )

By the log inequality: ln(1 − n/M ) < −n/M , so it is sufficient that:
t≥

M ln (1/ǫ)
ln (1/ǫ)
=
n/M
n

So it is sufficient to run our EnvyFreeVIP[n, M ] algorithm

 M ln (1/ǫ) 
n

times.

By combining the two reduction lemmas we get:
C OROLLARY 8.2. For every n, M > n and ǫ > 0:
If there is an algorithm for finding EnvyFreeVIP[n, M ] allocations using T (n) queries,


n
then there is an algorithm for finding EnvyFree[n, 1−ǫ
] allocations using n· M lnn(1/ǫ) ·
T (n) ≈ M ln(1/ǫ) · T (n) queries.
In the algorithm of Section 4, the first cutter cuts 2n−2 + 1 equal pieces. Hence,
the resulting allocations are EnvyFreeVIP[n, 2n−2 + 1]. The total number of queries is
O(2n ). Hence:
C OROLLARY 8.3. For every n and ǫ > 0, there exists an algorithm for finding
n
EnvyFree[n, 1−ǫ
] allocations using O(4n ln(1/ǫ)) queries.
This completes the proof of our Theorem 5.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:25

9. FUTURE WORK

The main question left open by the present paper is:
Is there a bounded-time algorithm for finding an envy-free and proportional
allocation with connected pieces for 4 or more agents?
The most recent advancement we are aware of was made by Aziz and Mackenzie at
29/7/2016.12 They developed an algorithm that finds an envy-free allocation with connected pieces in which each agent receives a value of at least 1/(3n).
APPENDIX
A. AUTOMATICALLY-GENERATED PROOF FOR 4-AGENT ENVY-FREE-VIP ALGORITHM

For convenience, we repeat here the algorithm of Section 6:
Alice:Equalize(4)
One of:
Bob:Equalize(2); Carl:Equalize(2)
Bob:Equalize(3); Carl:Equalize(2)
Carl:Equalize(2); Bob:Equalize(2)
Carl:Equalize(3); Bob:Equalize(2)
Below, when the proof says e.g. that “B:Equalize(2)... always succeeds”, it means that
the execution branch starting with “Bob:Equalize(2)” necessarily results in a preference graph in which Alice, Bob and Carl each prefer two pieces. Then, by Lemma 3.8
an envy-free allocation exists. Conversely, when the proof says that “this must fail”,
it means that the execution branch necessarily does not result in such a preference
graph. The proof systematically checks all possible preference relations and proves
that in all cases, at least one of the four execution branches must succeed. The notation is explained in Section 6. E.g, “4B” is what remains of piece 4 after it is cut by
Bob doing Equalize(2), “3CC” is what remains of piece 3 after it is cut by Carl doing
Equalize(3), etc.
The source code of the program used to generate the proof is available in
https://github.com/erelsgl/envy-free . We emphasize that the proof can be read and
verified without the source code, so the correctness of the proof does not depend on the
correctness of the code.
Initially, agent A cuts four equal pieces: 1,2,3,4 .
Assume w.l.o.g. that B’s preferences are 1<2<3<4 .
Consider the following 24 cases regarding the preferences of C:
CASE 1 OF 24 : C’s order is 4<3<2<1 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 2 OF 24 : C’s order is 4<3<1<2 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 3 OF 24 : C’s order is 4<2<3<1 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 4 OF 24 : C’s order is 4<2<1<3 :
B:Equalize(2) makes B’s best pieces: 3=4B. This must fail because of C.
C:Equalize(2) makes C’s best pieces: 1=3C. This always succeeds.
CASE 5 OF 24 : C’s order is 4<1<3<2 :
12 http://arxiv.org/abs/1604.03655v7

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:26

Erel Segal-Halevi et al.

B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 6 OF 24 : C’s order is 4<1<2<3 :
B:Equalize(2) makes B’s best pieces: 3=4B. This must fail because of C.
C:Equalize(2) makes C’s best pieces: 2=3C. This always succeeds.
CASE 7 OF 24 : C’s order is 3<4<2<1 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 8 OF 24 : C’s order is 3<4<1<2 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 9 OF 24 : C’s order is 3<2<4<1 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 10 OF 24 : C’s order is 3<2<1<4 :
B:Equalize(2) makes B’s best pieces: 3=4B. This may fail in 1 case : C prefers 4B to 1 2 3 .
Assume the case
C prefers 4B to 1 2 3. Then:
C:Equalize(2) makes C’s best pieces: 1=4C, so globally: 4C<4B . This always succeeds.
CASE 11 OF 24 : C’s order is 3<1<4<2 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 12 OF 24 : C’s order is 3<1<2<4 :
B:Equalize(2) makes B’s best pieces: 3=4B. This may fail in 1 case : C prefers 4B to 1 2 3 .
Assume the case
C prefers 4B to 1 2 3. Then:
C:Equalize(2) makes C’s best pieces: 2=4C, so globally: 4C<4B . This always succeeds.
CASE 13 OF 24 : C’s order is 2<4<3<1 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 14 OF 24 : C’s order is 2<4<1<3 :
B:Equalize(2) makes B’s best pieces: 3=4B. This must fail because of C.
C:Equalize(2) makes C’s best pieces: 1=3C. This always succeeds.
CASE 15 OF 24 : C’s order is 2<3<4<1 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 16 OF 24 : C’s order is 2<3<1<4 :
B:Equalize(2) makes B’s best pieces: 3=4B. This may fail in 1 case : C prefers 4B to 1 2 3 .
Assume the case
C prefers 4B to 1 2 3. Then:
C:Equalize(2) makes C’s best pieces: 1=4C, so globally: 4C<4B . This always succeeds.
CASE 17 OF 24 : C’s order is 2<1<4<3 :
B:Equalize(2) makes B’s best pieces: 3=4B. This must fail because of C.
C:Equalize(2) makes C’s best pieces: 4=3C. This must fail because of B.
B:Equalize(3) makes B’s best pieces: 2=3BB=4BB. This may fail in 1 case : C prefers 1 to 2 3BB 4BB .
Assume the case
C prefers 1 to 2 3BB 4BB. Then:
C:Equalize(3) makes C’s best pieces: 1=4CC=3CC, so globally: 4BB<4CC 3BB<3CC . This always succeeds.
CASE 18 OF 24 : C’s order is 2<1<3<4 :
B:Equalize(2) makes B’s best pieces: 3=4B. This may fail in 2 cases : C prefers 4B to 1 2
Assume the case
C prefers 4B to 1 2 3. Then:
C:Equalize(2) makes C’s best pieces: 3=4C, so globally: 4C<4B . This may fail in 1 case
Assume the case
B prefers 3 to 2 1 4C. Then:
B:Equalize(3) makes B’s best pieces: 2=3BB=4BB. This may fail in 1 case : C prefers 1
Assume the case
C prefers 1 to 2 3BB 4BB. Then:
C:Equalize(3) makes C’s best pieces: 1=3CC=4CC, so globally: 3BB<3CC 4BB<4CC . This
Assume the case
C prefers 3 to 1 2 4B. Then:
C:Equalize(2) makes C’s best pieces: 3=4C, so globally: 4B<4C . This may fail in 1 case
Assume the case
B prefers 4C to 2 1 3. Then:
B:Equalize(3) makes B’s best pieces: 2=3BB=4BB. This may fail in 1 case : C prefers 1
Assume the case
C prefers 1 to 2 3BB 4BB. Then:
C:Equalize(3) makes C’s best pieces: 1=3CC=4CC, so globally: 3BB<3CC 4BB<4CC . This

3;

C prefers 3 to 1 2 4B .

: B prefers 3 to 2 1 4C .
to 2 3BB 4BB .
always succeeds.
: B prefers 4C to 2 1 3 .
to 2 3BB 4BB .
always succeeds.

CASE 19 OF 24 : C’s order is 1<4<3<2 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 20 OF 24 : C’s order is 1<4<2<3 :
B:Equalize(2) makes B’s best pieces: 3=4B. This must fail because of C.
C:Equalize(2) makes C’s best pieces: 2=3C. This always succeeds.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:27

CASE 21 OF 24 : C’s order is 1<3<4<2 :
B:Equalize(2) makes B’s best pieces: 3=4B. This always succeeds.
CASE 22 OF 24 : C’s order is 1<3<2<4 :
B:Equalize(2) makes B’s best pieces: 3=4B. This may fail in 1 case : C prefers 4B to 1 2 3 .
Assume the case
C prefers 4B to 1 2 3. Then:
C:Equalize(2) makes C’s best pieces: 2=4C, so globally: 4C<4B . This always succeeds.
CASE 23 OF 24 : C’s order is 1<2<4<3 :
B:Equalize(2) makes B’s best pieces: 3=4B. This must fail because of C.
C:Equalize(2) makes C’s best pieces: 4=3C. This must fail because of B.
B:Equalize(3) makes B’s best pieces: 2=3BB=4BB. This may fail in 1 case : C prefers 2 to 1 3BB 4BB .
Assume the case
C prefers 2 to 1 3BB 4BB. Then:
C:Equalize(3) makes C’s best pieces: 2=4CC=3CC, so globally: 4BB<4CC 3BB<3CC . This always succeeds.
CASE 24 OF 24 : C’s order is 1<2<3<4 :
B:Equalize(2) makes B’s best pieces: 3=4B. This may fail in 2 cases : C prefers 4B to 1 2
Assume the case
C prefers 4B to 1 2 3. Then:
C:Equalize(2) makes C’s best pieces: 3=4C, so globally: 4C<4B . This may fail in 1 case
Assume the case
B prefers 3 to 1 2 4C. Then:
B:Equalize(3) makes B’s best pieces: 2=3BB=4BB. This may fail in 1 case : C prefers 2
Assume the case
C prefers 2 to 1 3BB 4BB. Then:
C:Equalize(3) makes C’s best pieces: 2=3CC=4CC, so globally: 3BB<3CC 4BB<4CC . This
Assume the case
C prefers 3 to 1 2 4B. Then:
C:Equalize(2) makes C’s best pieces: 3=4C, so globally: 4B<4C . This may fail in 1 case
Assume the case
B prefers 4C to 1 2 3. Then:
B:Equalize(3) makes B’s best pieces: 2=3BB=4BB. This may fail in 1 case : C prefers 2
Assume the case
C prefers 2 to 1 3BB 4BB. Then:
C:Equalize(3) makes C’s best pieces: 2=3CC=4CC, so globally: 3BB<3CC 4BB<4CC . This

3;

C prefers 3 to 1 2 4B .

: B prefers 3 to 1 2 4C .
to 1 3BB 4BB .
always succeeds.
: B prefers 4C to 1 2 3 .
to 1 3BB 4BB .
always succeeds.

Q.E.D!

B. ENVY-FREE DIVISION OF AN ENTIRE CAKE

Recently, Aziz and Mackenzie [2016a] have made an important breakthrough in the
search for bounded-time envy-free cake-cutting algorithms. They presented the first
bounded-time algorithm for envy-free cake-cutting of an entire cake to 4 agents. In this
appendix, we use our envy-free-VIP algorithm of Section 6 to present their results in
a simpler and more general way.
B.1. The domination graph

The main new concept required for envy-free division of an entire cake is domination.13 We say that Alice dominates Bob if Alice won’t envy Bob even if the entire
remaining cake is given to Bob.
To see how a domination relation is created, consider again the envy-free-VIP algorithm for three agents, presented in Subsection 3.2. Alice does Equalize(3) and Bob
does Equalize(2), cutting his favorite piece, say b
3, to make it equal to his second-best,
say b
2. Mark the trimmed piece b
3B and the trimmings b
4, so that b
3=b
3B ∪ b
4. Suppose
b
b
b
b
Carl’s best piece is 2. So Carl takes 2, Bob takes 3B , Alice takes 1, and b
4 remains for
the next round. Now, the following equalities hold for Alice:
VA (b
1) = VA (b
2) = VA (b
3) = VA (b
3B ) + VA (b
4)

Hence, even if the entire remainder (b
4) is given to Bob, Alice will not envy. This means
that Alice dominates Bob.
13 This

concept originated with Brams and Taylor [1996], who used the term “irrevocable advantage”. Aziz
and Mackenzie introduced the shorter term “domination”.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:28

Erel Segal-Halevi et al.

(b)

(a)
A
B

(c)
A

C

B

A
C

B

C

Fig. 1: Domination graphs with 3 agents.
A
B

A
C

D

B

A
C

D

B

C
D

Fig. 2: Domination graphs with 4 agents. All are solvable by Lemma B.2.
The domination relation can be described by a domination graph. In a domination
graph, the nodes are the agents and an edge between two agents means that the source
node dominates the target node.
Three domination graphs are shown in Figure 1. The graph (a) is generated after a
single run of the algorithm, in which Alice dominates Bob (as explained above). Graph
(b) can possibly occur after a second run of the same algorithm, if in the second run
Carl takes the trimmed piece so Alice dominates Carl too. Graph (c) can occur after a
second run of the algorithm in which Carl is the cutter, if Bob takes the trimmed piece.
In general, when an envy-free algorithm is repeatedly executed, each time on the
remainder of the previous time, edges are added to the domination graph but never
removed.
B.2. Solvable domination graphs

A convenient approach to the envy-free division problem is to reduce a given instance
to a simpler instance that we already know how to solve. Formally:
Definition B.1. A domination graph of an envy-free cake-cutting problem for n
agents is called solvable if, once the state of the division arrives at that domination
graph, the problem can be reduced to one or more envy-free cake-cutting problems for
less than n agents.
The domination graphs in Figure 1 (b) and (c) are solvable: in (b), the problem can
be reduced to a 2-agent division between Bob and Carl, since Alice dominates both of
them; in (c), the entire remainder can be given to Bob, since he is dominated by both
Alice and Carl. In general:
L EMMA B.2. If, in a domination graph for n agents, there is a partition of the agents
to two nonempty groups such that every agent in group #2 dominates all agents in group
#1, then the domination graph is solvable.
P ROOF. An envy-free division of the entire cake can be found by letting the agents
in group #1 (whose number is less than n) divide the remainder among them in an
envy-free way.
Figure 2 shows three graphs for 4 agents that are solvable by Lemma B.2.
Another kind of solvable domination graphs is described in the following lemma.
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

(a)

(b)

A:29

(c)
B

A
B

A
B

C

C
D

D

E
C

A

Fig. 3: Domination graphs solvable by Lemma B.3.
L EMMA B.3. If there is a sequence of n − 1 agents, A2 , . . . , An , such that every agent
dominates the following agents (every agent Ai dominates every agent Aj for all 2 ≤ i <
j), then the domination graph is solvable.
P ROOF. The remaining cake can be divided in the following way: A1 (the agent not
in the sequence) cuts the cake to n equal parts. Then, the agents take pieces in the
order An , . . . , A2 , A1 . The agents in the sequence are not envious, because every agent
dominates the agents that took pieces before him, and prefers his piece to the pieces
taken by agents after him. A1 is also not envious because all pieces are equal in his
eyes.
Figure 3 shows graphs for 3, 4 and 5 agents, that are solvable by Lemma B.3. In (a),
the sequence is {B,C}, and the solution of Lemma B.3 yields the well-known SelfridgeConway algorithm. In (b) the sequence is {B,C,D} and in (c) it is {B,C,D,E}.
Combining the two previous lemmas gives a stronger lemma:
L EMMA B.4. If there is a set of n − 1 agents, each of whom dominates n − 2 agents,
then the domination graph is solvable.
P ROOF. Suppose that each of the agents A2 , . . . , An dominates n−2 agents. Consider
the following two cases:
Case #1: all agents A2 , . . . , An dominate A1 . Then by Lemma B.2 the domination
graph is solvable.
Case #2: there is an agent in A2 , . . . , An , say A2 , that does not dominate A1 . Hence,
this agent must dominate all the other agents A3 , . . . , An .
Regarding this smaller set of agents, there are again two cases:
Case #2.1: all agents A3 , . . . , An dominate both A1 and A2 . Then by Lemma B.2 the
domination graph is solvable.
Case #2.2: there is an agent in A3 , . . . , An , say A3 , that does not dominate A1 or does
not dominate A2 . Hence, this agent must dominate all the other agents A4 , . . . , An .
Regarding this smaller set of agents, we can continue the same line of reasoning. Finally we conclude that, either the domination graph is solvable by Lemma B.2, or there
exists a sequence of agents (A2 , . . . , An ) such that each agent dominates the following
agents in that sequence; then by Lemma B.3 the domination graph is solvable.
Lemma B.4 implies that the problem of envy-free division of an entire cake among n
agents can be reduced to the following problem:
Find an envy-free allocation of a part of a cake, such that a pre-specified VIP
agent dominates n − 2 agents.
We now show that this reduced problem can be solved for n = 4 agents.
B.3. The Equalize∗ query

First, we want to guarantee that after every run of an envy-free-VIP algorithm, the VIP
agent (the cutter) will dominate one of the agents. In order to guarantee this, we must
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:30

Erel Segal-Halevi et al.

change the semantics of the Equalize query. We call the changed query Equalize∗. An
Equalize∗(k) query asks an agent to cut his best k − 1 pieces, such that the trimmed
pieces will be equivalent to the agent’s k-th best piece. For example, an Equalize∗(2)
query to Bob in the above example implies the following question: “where would you
cut piece b
3, your currently favorite piece, such that the trimmed piece will be equivalent to b
2?”. Note that in this case (in contrast to the Equalize query), the trimmings
may be more valuable than the trimmed piece. When Equalize∗ queries are used, the
agents are not allowed to choose the trimmings; the trimmings are kept for later iterations. The agents are only allowed to take the trimmed pieces (hence, in contrast
to the algorithms using Equalize, there is no guarantee on the proportionality of the
allocation after a single run of the algorithm). Since the number of original pieces is n,
all trimmed pieces must be taken.
Based on the above observation, we now generalize a lemma proved by Aziz and
Mackenzie [2016a] from 4 to n agents.
B.4. Creating a single domination-edge from the VIP

L EMMA B.5. Let C be a cake and X an envy-free division of a subset C ′ ⊂ C among
n agents. Denote the remaining cake by C ′ = C \ C ′ . Suppose that for two agents (e.g.
Alice and Bob) the following holds:
VA (XA ) − VA (XB ) ≥ VA (C ′ )/k
where k < n. Then, after running an envy-free-VIP algorithm a bounded number f (n)
times with Alice as the VIP, Alice will dominate Bob.
P ROOF. Each run of an envy-free-VIP algorithm gives the VIP (Alice) a value of
at least 1/n. Hence, the value of the remaining cake decreases by a factor of at least
log n
log k
(n − 1)/n. Let f (n) = log(n)−log(n−1)
. Note that f (n) > log(n/(n−1))
. Hence, after f (n)
iterations, the value of the remaining cake for Alice is at most VA (C ′ )/k. When this
happens, the difference between Alice’s value to Bob’s value (in Alice’s eyes) is more
than the value of the remainder; hence Alice dominates Bob.
Motivated by this lemma, we say that Alice k-dominates Bob, if VA (XA ) − VA (XB ) ≥
VA (C ′ )/k. If Alice k-dominates Bob (where k < n), then after a number of steps which
is a bounded function of n, Alice will dominate Bob. Hence, from now on, we add an
edge in the domination graph whenever the source node k-dominates the target node
for some k < n.
L EMMA B.6. After a run of an envy-free-VIP algorithm for n agents, the VIP kdominates at least one other agent, where k < n.
P ROOF. An envy-free-VIP algorithm starts by the VIP agent (say, Alice) cutting the
cake to n equal pieces. Then, a certain number k < n of pieces are trimmed. Consider
the following two cases.
(a) k = 0: all n pieces are taken with no trimmings. Then, the division is fully envyfree and no cake is left, so domination is trivial.
(b) 1 ≤ k < n: the divided cake is C ′ ⊆ C, and the remainder is C ′ = C \ C ′ . This
remainder is the union of the k trimmings. Mark by biX the trimming taken from piece
bi. Then:
C ′ = ∪ki=1biX

By the additivity of Alice’s value measure:

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

VA (C ′ ) =

k
X
i=1

A:31

VA (biX )

Assume, without loss of generality, that the trimming of piece b
1 has the largest value
for Alice (Aziz and Mackenzie call such piece the significant piece). Then, by the
pigeonhole principle, its value for Alice is at least 1/k the value of the remaining cake,
so:
VA (b
1X ) ≥ VA (C ′ )/k

This means that Alice k-dominates the agent that took piece b
1.

Lemma B.6 guarantees that, after each run of an envy-free-VIP algorithm, the domination graph contains an edge going from the VIP agent to another agent. Hence,
n domination edges can be created by running the algorithm n times with different
VIP agents. But this may be insufficient to attain a solvable domination graph. The
worst case is that, whenever a certain agent is the VIP, the same other agent takes the
significant piece and hence the same domination edge is added again and again. Fortunately, Aziz and Mackenzie [2016a] found a way to shift domination edges to other
agents.
B.5. Creating two domination-edge from the VIP

Suppose there are n agents and Alice is the VIP. Suppose that after the first run,
Alice dominates Bob. Our goal now is to make Alice dominate another agent. We run
the algorithm again, this time keeping Bob as the last agent (the agent that does not
trim). The other n − 2 agents trim some of the pieces, until each of the first n − 1 agents
prefers at least two pieces (see Section 3.2 for a description on how it is done when
n = 3 and Section 6 for the case n = 4). Now, Bob has to choose a piece. Suppose w.l.o.g.
that Bob’s best piece is b
1 and his second-best piece is b
2. There are two cases:
Easy case: b
1 is not the significant piece. Then, another agent takes the significant
piece and is k-dominated by Alice. Now two different domination edges emanate from
Alice, as we wanted.
Hard case: b
1 is the significant piece. Consider now what happens if Bob takes b
2
b
instead of 1. The other agents will not care, since each of the other agents prefers at
least two pieces. But then Bob might envy the agent (say, Carl) who takes b
1. In this
case, we say that Bob competes with Carl on the significant piece. Let ∆V = VB (b
1) −
VB (b
2). If Bob takes b
1 then Bob has an advantage of at least ∆V over Carl; if Bob takes
b
2 then Bob has an envy of ∆V at Carl (Carl does not envy Bob in either case since Carl
prefers two pieces).
Now, suppose the algorithm is run again and again with the same VIP, and each
time we fall into the same hard case in which the same Bob prefers the significant
piece. Eventually (after at most n runs), Bob competes with an agent with whom he
already competed in the past (e.g, Bob competes Carl again). Now, we ask Bob in which
of these two runs the ∆V is larger. If the ∆V was larger in the first run, then in the
second run we give Bob his second-best piece; if the ∆V was larger in the second run,
then in the first run we change the allocation and give Bob his second-best piece. In
either case, Bob will not be envious since the larger ∆V cancels the envy caused by the
smaller ∆V .
The above discussion can be summarized in the following lemma:
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

A:32

Erel Segal-Halevi et al.

L EMMA B.7. After at most n runs of an envy-free-VIP algorithm for n agents, the
VIP k-dominates at least two other agents.
Plugging Lemma B.7 into Lemma B.4 yields Aziz & Mackenzie’s envy-free cakecutting algorithm for 4 agents.
ACKNOWLEDGMENTS
We are grateful for useful discussions and suggestions from several members of the Stack Exchange network
(http://stackexchange.com), particularly, Raphael Reitzig, Sebastian Wild, Abhishek Bansai, InstructedA,
FrankW, Pal Gronas Drange (Pal GD), Anand S Kumar, babou, Bernard, BVMR, D.W., David Richerby,
dmbarbour, Herbert, Jair Taylor, kcrisman, Luke Mathieson, Maroun Maroun, Rick Decker, Tsuyoshi Ito,
Xoff and Yuval Filmus.
We are grateful to three anonymous PC members of the AAMAS 2015 conference and to two anonymous
referees of the TALG journal for their helpful comments and suggestions.

REFERENCES
Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, and Eftychia Vakaliou. 2018. An Improved Envy-Free Cake Cutting Protocol for Four Agents.
Orit Arzi, Yonatan Aumann, and Yair Dombb. 2016. Toss one’s cake, and eat it too: partial divisions can improve social welfare in cake cutting. Social Choice and Welfare 46, 4, 933–954.
DOI:http://dx.doi.org/10.1007/s00355-015-0943-y
Haris Aziz. 2015. A generalization of the AL method for fair allocation of indivisible objects. Economic Theory
Bulletin (2015), 1–18. DOI:http://dx.doi.org/10.1007/s40505-015-0089-1
Haris Aziz and Simon Mackenzie. 2016a. A Discrete and Bounded Envy-free Cake Cutting Protocol for 4
Agents. In Proceedings of STOC 2016. DOI:http://dx.doi.org/10.1145/2897518.2897522
Haris Aziz and Simon Mackenzie. 2016b. A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any
Number of Agents. To appear in Proceedings of FOCS 2016. http://arxiv.org/abs/1604.03655
Julius Barbanel and Steven J. Brams. 2004. Cake division with minimal cuts: envy-free procedures for three
persons, four persons, and beyond. Mathematical Social Sciences 48, 3, 251–269.
Steven J. Brams, D. Marc Kilgour, and Christian Klamler. 2013. Two-Person Fair Division of Indivisible
Items: An Efficient, Envy-Free Algorithm. Social Science Research Network Working Paper Series (5
June 2013), 130–141. DOI:http://dx.doi.org/10.1090/noti1075
Steven J. Brams and Alan D. Taylor. 1995. An Envy-Free Cake Division Protocol. The American Mathematical Monthly 102, 1 (Jan. 1995), 9–18. DOI:http://dx.doi.org/10.2307/2974850
Steven J. Brams and Alan D. Taylor. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. http://www.worldcat.org/isbn/0521556449
Simina Brânzei. 2015. A note on envy-free cake cutting with polynomial valuations. Information Processing
Letters 115, 2 (Feb. 2015), 93–95. DOI:http://dx.doi.org/10.1016/j.ipl.2014.07.005
Simina Brânzei, Ioannis Caragiannis, David Kurokawa, and Ariel D. Procaccia. 2016. An Algorithmic
Framework for Strategic Fair Division. In Proceedings of the 30th AAAI Conference on Artificial Intelligence. http://arxiv.org/abs/1307.2225
Xiaotie Deng, Qi Qi, and Amin Saberi. 2012. Algorithmic Solutions for Envy-Free Cake Cutting. Operations
Research 60, 6 (Dec. 2012), 1461–1476. DOI:http://dx.doi.org/10.1287/opre.1120.1116
The Sage Developers. 2015. Sage Mathematics Software, Version 6.7. http://www.sagemath.org.
Jeff Edmonds and Kirk Pruhs. 2006. Balanced Allocations of Cake. In Proceedings of FOCS, Vol. 47. IEEE
Computer Society, 623–634. DOI:http://dx.doi.org/10.1109/focs.2006.17
Jeff Edmonds and Kirk Pruhs. 2011. Cake cutting really is not a piece of cake. ACM Transactions on Algorithms 7, 4 (1 Sept. 2011), 1–12. DOI:http://dx.doi.org/10.1145/2000807.2000819
Jeff Edmonds, Kirk Pruhs, and Jaisingh Solanki. 2008. Confidently Cutting a Cake into Approximately Fair Pieces. Algorithmic Aspects in Information and Management (2008), 155–164.
DOI:http://dx.doi.org/10.1007/978-3-540-68880-8\ 16
Shimon Even and Azaria Paz. 1984. A note on cake cutting. Discrete Applied Mathematics 7, 3 (March 1984),
285–296. DOI:http://dx.doi.org/10.1016/0166-218x(84)90005-2
David Kurokawa, John K. Lai, and Ariel D. Procaccia. 2013. How to Cut a Cake Before the Party Ends. In
Proceedings of the 27th AAAI Conference on Artificial Intelligence. 555–561.

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

Bounded-Time Envy-Free Cake-Cutting with Free Disposal

A:33

Oleg Pikhurko. 2000. On Envy-Free Cake Division. American Mathematical Monthly 107 (2000), 736–738.
DOI:http://dx.doi.org/10.2307/2695471
Ariel D. Procaccia. 2009. Thou Shalt Covet Thy Neighbor’s Cake. In Proceedings of the 21st International
Joint Conference on Artificial Intelligence. 239–244.
Ariel D. Procaccia. 2015. Cake Cutting Algorithms. In Handbook of Computational Social Choice, Felix
Brandt, Vincent Conitzer, Ulle Endriss, Jerome Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, Chapter 13.
Raphael Reitzig and Sebastian Wild. 2017. Building Fences Straight and High: An Optimal Algorithm for
Finding the Maximum Length You Can Cut k Times from Given Sticks. In Algorithmica (2017). arXiv
preprint 1502.04048.
Jack M. Robertson and William A. Webb. 1998. Cake-Cutting Algorithms: Be Fair if You Can (first ed.). A K
Peters/CRC Press. 1–177 pages. http://www.worldcat.org/isbn/1568810768
Amin Saberi and Ying Wang. 2009. Cutting a Cake for Five People. In Algorithmic Aspects in Information
and Management, Andrew V. Goldberg and Yunhong Zhou (Eds.). Lecture Notes in Computer Science,
Vol. 5564. Springer Berlin Heidelberg, 292–300. DOI:http://dx.doi.org/10.1007/978-3-642-02158-9\ 25
Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann. 2015a. Envy-Free Cake-Cutting in Two Dimensions. In Proceedings of the 29th AAAI Conference on Artificial Intelligence. 1021–1028.
Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann. 2015b. Waste Makes Haste: Bounded
Time Protocols for Envy-Free Cake Cutting with Free Disposal. In Proceedings of the
14th International Conference on Autonomous Agents and Multi-Agent Systems. 901–908.
DOI:http://dx.doi.org/10.13140/RG.2.1.1902.0645
Hugo Steinhaus. 1948. The problem of fair division. Econometrica 16, 1 (Jan. 1948), 101–104. http://www.
jstor.org/stable/1914289
Walter Stromquist. 1980. How to Cut a Cake Fairly. The American Mathematical Monthly 87, 8 (Oct. 1980),
640–644. DOI:http://dx.doi.org/10.2307/2320951
Walter Stromquist. 2008. Envy-free cake divisions cannot be found by finite protocols. Electronic Journal of
Combinatorics (Jan. 2008). http://www.emis.ams.org/journals/EJC/Volume\ 15/PDF/v15i1r11.pdf
Francis E. Su. 1999. Rental Harmony: Sperner’s Lemma in Fair Division. The American Mathematical
Monthly 106, 10 (Dec. 1999), 930–942. DOI:http://dx.doi.org/10.2307/2589747
Gerhard J. Woeginger and Jiřı́ Sgall. 2007. On the complexity of cake cutting. Discrete Optimization 4, 2
(June 2007), 213–220. DOI:http://dx.doi.org/10.1016/j.disopt.2006.07.003

ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: December 2016.

