Envyfree cakecutting
An envyfree cakecutting is a kind of fair cakecutting. It is a division of a heterogeneous resource ("cake") that satisfies the envyfree criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.
Unsolved problem in computer science: What is the runtime complexity of envyfree cakecutting?
(more unsolved problems in computer science)

When there are only 2 partners, the problem is easy and has been solved in Biblical times by the divide and choose protocol. When there are 3 or more partners, the problem becomes much more challenging.
Two major variants of the problem have been studied:
 Connected pieces, e.g. if the cake is a 1dimensional interval then each partner must receive a single subinterval. If there are partners, only cuts are needed.
 General pieces, e.g. if the cake is a 1dimensional interval then each partner can receive a union of disjoint subintervals.
Contents
Short history
The modern research of the fair cakecutting problem has started in the 1940s. The first fairness criterion studied was proportional division, and a procedure for n partners has been found soon.
The stronger criterion of envyfreeness was introduced into the cakecutting problem by George Gamow and Marvin Stern in 1950s.^{[1]}
A procedure for 3 partners and general pieces was found in 1960. A procedure for 3 partners and connected pieces was found only in 1980.
Envyfree division for 4 or more partners has been an open problem until the 1990s, when three procedures for general pieces and a procedure for connected pieces have been published. All these procedures are unbounded  they may require a number of steps which is not bounded in advance. The procedure for connected pieces may even require an infinite number of steps.
Two lower bounds on the runtime complexity of envyfreeness have been published in the 2000s.
 For general pieces, the lower bound is Ω(n^{2}).
 For connected pieces the lower bound is infinity  there is provably no finite protocol for 3 or more partners.
In the 2010s, several approximation procedures and procedures for special cases have been published. The question whether boundedtime procedures exist for the case of general pieces had remained open for a long time. The problem was finally solved in 2016. Haris Aziz and Simon Mackenzie presented a discrete envyfree protocol that requires at most queries. There is still a very large gap between the lower bound and the procedure. As of August 2016, the exact runtime complexity of envyfreeness is still unknown.
For the case of connected pieces, it was noted that the hardness result assumes that the entire cake must be divided. If this requirement is replaced by the weaker requirement that every partner receives a proportional value (at least 1/n of the total cake value according to their own valuation), then a bounded procedure for 3 partners is known, but it has remained an open problem whether there exist boundedtime procedures for 4 or more partners.
Connected pieces
Existence proof
An envyfree division for n agents with connected pieces always exists under the following mild assumptions:^{[2]}
 No agent prefers an empty piece over a nonempty piece.
 The preferences of the agents are continuous.
Note that it is not required that the preferences of the agents are represented by an additive function.
The main concept in the proof is the simplex of partitions. Suppose the cake is the interval [0,1]. Each partition with connected pieces can be uniquely represented by n1 numbers in [0,1] which represent the cut locations. The union of all partitions is a simplex.
For each partition, each agent has one or more pieces which they weakly prefer. E.g., for the partition represented by "0.3,0.5", one agent may prefer piece #1 (the piece [0,0.3]) while another agent might prefer piece #2 (the piece [0.3,0.5]) while a third agent might prefer both piece #1 and piece #2 (which means that they are indifferent between them but like any of them more than piece #3).
For every agent, the partition simplex is covered by n parts, possibly overlapping at their boundaries, such that for all partitions in part i, the agent prefers piece i. In the interior of part i, the agent prefers only piece i, while in the boundary of part i, the agent also prefers some other pieces. So for every i, there is a certain region in the partition simplex in which at least one agent prefers only piece i. Call this region U_{i}. Using a certain topological lemma (that is similar to the Knaster–Kuratowski–Mazurkiewicz lemma), it is possible to prove that the intersection of all U_{i}'s is nonempty. Hence, there is a partition in which every piece is the unique preference of an agent. Since the number of pieces equals the number of agents, we can allocate each piece to the agent that prefers it and get an envyfree allocation.
Procedures
For three agents, an envyfree division can be found using several different procedures:
 The Stromquist movingknives procedure uses four simultaneouslymoving knives  one moved by a referee and another one for each agent.
 Barbanel–Brams movingknives procedure uses two simultaneouslymoving knives.
 The Robertson–Webb rotatingknife procedure can be used when the cake is twodimensional, and uses only a single movingknife.
These are continuous procedures  they rely on people moving knives continuously and simultaneously. They cannot be executed in a finite number of discrete steps.
For n agents, an envyfree division can be found by Simmons' cakecutting protocol. The protocol uses a simplex of partitions similar to the one used in Stromquist's existence proof. It generates a sequence of partitions which converges to an envyfree partition. The convergence might take infinitely many steps.
It is not a coincidence that all these algorithms may require infinitely many queries. As we show in the following subsection, it may be impossible to find an envyfree cakecutting with connected pieces with a finite number of queries.
Hardness result
An envyfree division with connected pieces for 3 or more agents cannot be found by a finite protocol. ^{[3]} The reason this result doesn't contradict the previously mentioned algorithms is that they are not finite in the mathematical sense.^{[4]}
The impossibility proof uses a rigid measure system (RMS)  a system of n value measures, for which an envyfree division must cut the cake at very specific locations. Then, finding an envyfree division reduces to finding these specific locations. Assuming the cake is the real interval [0,1], finding an envyfree division using queries to the agents is equivalent to finding a real number in the interval [0,1] using yes/no questions. This might require an infinite number of questions.
A RMS for 3 agents can be constructed as follows. Let x, y, s, and t be parameters satisfying:
 .
Construct a set of three measures with these two properties:
 The density of each measure is always strictly between √2/2 and √2 (so for a given piece, the agents' valuations differ by a factor of less than 2).
 The values of the pieces determined by x and y are as in the table:
Agent [0,x] [x,y] [y,1] A t t s B s t t C t s t
Then, every envyfree division among Alice Bob and Carl must have cuts at x and y (there are exactly two such divisions), since all other options lead to envy:
 If cuts are made to the left of x and to the right of y, then Alice and Bob both insist on getting the middle piece.
 If cuts are made to the right of x and to the left of y, then no agent would accept the middle piece.
 If cuts are made to the right of x and to the right of y (say, at x*>x and y*>y), then both Alice and Carl prefer the leftmost piece to the rightmost piece, so Bob must agree to accept the rightmost piece. This means that Bob must value the piece [x,x*] at least twice as much as [y,y*]. But because of the restriction on the value densities, this means that both Alice and Carl value [x,x*] more than [y,y*], so they insist on the leftmost piece.
 The fourth case (cuts to the left of x and to the left of y) is analogous.
For every RMS, every agent i and every constant ε>0, there is a slightly different RMS with the following properties:
 The new value measure of agent i is completely identical to his old value measure;
 The new value measures of the other two agents are identical to their old value measure everywhere except in an εneighbourhood of x and y.
This implies that, if all queries answered so far were outside the εneighbourhood of x and y, then agent i has no way to know whether we are in the old RMS or in the new RMS.
Equipped with this knowledge, an adversary can trick every envyfree division protocol to go on forever:
 Start with any RMS, e.g. with parameters x=1/3, y=2/3, s=0.3 and t=0.35.
 As long as the protocol makes cuts at points other than x and y, let it continue.
 Whenever the protocol asks agent i to make a cut at x or y, switch to a different RMS with x'≠x and y'≠y, making sure that the values are the same for all previously made cuts.
Thus the protocol can never make cuts at the correct x and y required for an envyfree division.
Approximations
Since envyfree cakecutting with connected pieces cannot be done in finite time, cakecutters have tried to find workarounds.
One workaround is looking for divisions which are only approximatelyenvyfree. There are two ways to define the approximation  in units of length or in units of value.
Lengthbased approximation uses the following definitions:
 A partition of a cake is represented by the n lengths of intervals it creates. So (0.2,0.5,0.3) is a partition of the unit interval to three subintervals with lengths 0.2, 0.5 and 0.3 (it is generated by cutting the unit interval at 0.2 and at 0.7).
 A multipartition is a set of several different partitions.
 A multipartition X is called envyfree if there exists a permutation of the partners such that, for every i, there exists an element of X such that the ith partner prefers the ith segment.
 A δmultipartition is a multipartition in which, for each pair of partitions, the difference between each of their coordinates is at most δ. For example: {(0.2+δ,0.5,0.3), (0.2,0.5+δ,0.3), (0.2,0.5,0.3+δ)}.
The parameter δ represents the tolerance of the partners in units of length. E.g., if land is divided and the partners agree that a difference of 0.01 meter in the location of the border is not relevant to them, then it makes sense to look for a 0.01multipartition which is envyfree. Deng at al^{[5]} present a modification of Simmons' cakecutting protocol which finds an envyfree δmultipartition using queries. Moreover, they prove a lower bound of queries. Even when the utility functions are given explicitly by polynomialtime algorithms, the envyfree cakecutting problem is PPADcomplete.
Valuebased approximation uses the following definitions:
 A partition X is called εenvyfree if there exists a permutation of the partners such that, for every i, the value of the ith piece plus ε is at least as much as the value of any other piece: .
 A value measure is called Lipschitzcontinuous if there exists a constant K such that, for any pair of intervals, the difference of values between them is at most K times the length of their symmetric difference .
If all value measures are Lipschitzcontinuous, then the two approximation definitions are related. Let . Then, every partition in an envyfree δmultipartition is εenvyfree.^{[5]} Hence, Deng et al.'s results prove that, if all partners have Lipschitzcontinuous valuations, an εenvyfree partition can be found with queries.
Offline calculation is a second workaround that finds a totallyenvyfree division but only for a restricted class of valuations. If all value measures are polynomials of degree at most d, there is an algorithm which is polynomial in n and d.^{[6]} Given d, the algorithm asks the agents d+1 evaluation queries, which give d+1 points in the graph of the value measure. It is known that d+1 points are sufficient to interpolate a polynomial of degree d. Hence, the algorithm can interpolate the entire value measures of all agents, and find an envyfree division offline. The number of required queries is .
Free disposal is a third workaround that keeps the requirement that the division be totally envyfree and works for all value measures, but drops the requirement that the entire cake must be divided. I.e, it allows to divide a subset of the cake and discard the remainder. Without further requirements the problem is trivial, since it is always envyfree to give nothing to all agents. Thus, the real goal is to give each agent a strictly positive value. Every cake allocation can be characterized by its level of proportionality, which is the value of the least fortunate agent. An envyfree division of the entire cake is also a proportional division, and its proportionality level is at least , which is the best possible. But when free disposal is allowed, an envyfree division may have a lower proportionality level, and the goal is to find an envyfree division with the highest possible proportionality. The currently known bounds are:
 For 3 agents the proportionality is , i.e, an envyfree and proportional division is attainable in bounded time.^{[7]}
 For 4 agents the proportionality is .^{[7]}
 For n agents, the proportionality is .^{[8]}
It is not known whether there exists a boundedtime envyfree and proportional division procedure for 4 or more partners with connected pieces.
Variants
Most procedures for cakecutting with connected pieces assume that the cake is a 1dimensional interval and the pieces are 1dimensional subintervals. Often, it is desirable that the pieces have a certain geometric shape, such as a square. With such constraints, it may be impossible to divide the entire cake (e.g., a square cannot be divided to two squares), so we must allow free disposal. As explained above, when free disposal is allowed, the procedures are measured by their level of proportionality  the value that they guarantee to all agents. The following results are currently known:^{[9]}
 For two partners sharing a square cake and wanting square pieces the proportionality is , and this is the best that can be guaranteed even without envy.
 For three partners sharing a square cake and wanting square pieces the proportionality is ; the best that can be guaranteed without envy is .
Disconnected pieces
Procedures
For 3 partners, the Selfridge–Conway discrete procedure makes an envyfree division with at most 5 cuts. Other procedures using moving knives require fewer cuts:
 The Levmore–Cook movingknives procedure requires at most 4 cuts;
 The BramsTaylorZwicker rotatingknives procedure for piecutting requires at most 3 cuts (this results in three connected pieces when the cake is a circle, but when the cake is an interval there will be four pieces);
 Using the Austin movingknife procedure for 2 partners, it is possible to get an envyfree division for 3 partners using at most 3 cuts. This idea is attributed to William Webb.^{[10]}^{:124–125}
For 4 partners, The Brams–Taylor–Zwicker procedure makes an envyfree division with at most 11 cuts.^{[11]} For 5 partners, a procedure by Saberi and Wang makes an envyfree division with a bounded number of cuts.^{[12]} Both these procedures use Austin's procedure for two partners and general fractions as an initial step. Hence, these procedures should be considered infinite  they cannot be completed using a finite number of steps.
For 4 or more partners, there are three algorithms which are finite but unbounded  there is no fixed bound on the number of cuts required.^{[13]} There are three such algorithms:
 The Brams–Taylor protocol, first published in a 1995 paper and later in a 1996 book.
 The RobertsonWebb protocol, first published in a 1997 paper and later in a 1998 book.
 The Pikhurko protocol,^{[14]} published in 2000.
Although the protocols are different, the main idea behind them is similar: Divide the cake to a finite but unbounded number of "crumbs", each of which is so small that its value for all partners is negligible. Then combine the crumbs in a sophisticated way to get the desired division. William Gasarch has compared the three unbounded algorithms using ordinal numbers.^{[15]}
The question of whether envyfree cakecutting can be done in bounded time for 4 or more partners had been open for many years. It was finally solved in 2016 by Hariz Aziz and Simon Mackenzie. Initially they developed a boundedtime algorithm for 4 partners.^{[16]} Then they extended their algorithm to handle any number of partners.^{[8]} Their algorithm requires at most queries. While this number is bounded, it is very far from the lower bound of . So the question of how many queries are required for envyfree cakecutting is still open.
Approximations and partial solutions
A reentrant variant of the last diminisher protocol finds an additive approximation to an envyfree division in bounded time. Specifically, for every constant , it returns a division in which the value of each partner is at least the largest value minus , in time .
If all value measures are piecewiselinear, there is an algorithm which is polynomial in the size of the representation of the value functions.^{[17]} The number of queries is , where is the number of discontinuities in the derivatives of the value density functions.
Hardness result
Every envyfree procedure for n people requires at least Ω(n^{2}) queries.^{[18]} The proof relies on a careful analysis of the amount of information the algorithm has on each partner.
A. Assume that the cake is the 1dimensional interval [0,1], and that the value of the entire cake for each of the partners is normalized 1. In each step, the algorithm asks a certain partner either to evaluate a certain interval contained in [0,1], or to mark an interval with a specified value. In both cases, the algorithm gathers information only about intervals whose endpoints were mentioned in the query or in the reply. Let's call these endpoints landmarks. Initially the only landmarks of i are 0 and 1 since the only thing the algorithm knows about partner i is that v_{i}([0,1])=1. If the algorithm asks partner i to evaluate the interval [0.2,1], then after the reply the landmarks of i are {0,0.2,1}. The algorithm can calculate v_{i}([0,0.2]), but not the value of any interval whose endpoint is different than 0.2. The number of landmarks increases by at most 2 in each query. In particular, the value of the interval [0,0.2] might be concentrated entirely near 0, or entirely near 0.2, or anywhere in between.
B. An interval between two consecutive landmarks of partner i is called a landmarkinterval of partner i, When the algorithm decides to allocate a piece of cake to partner i, it must allocate a piece whose total value for i is at least as large as any landmarkinterval of i. The proof is by contradiction: suppose there is a certain landmarkinterval J whose value for i is more than the value actually allocated to i. Some other partner, say j, will necessarily receive some part of the landmarkinterval J. By paragraph A, it is possible that all the value of interval J is concentrated inside the share allocated to partner j. Thus, i envies j and the division is not envyfree.
C. Suppose all partners answer all queries as if their value measure is uniform (i.e. the value of an interval is equal to its length). By paragraph B, the algorithm may assign a piece to partner i, only if it is longer than all landmarkintervals of i. At least n/2 partners must receive an interval with a length of at most 2/n; hence all their landmarkintervals must have a length of at most 2/n; hence they must have at least n/2 landmarkintervals; hence they must have at least n/2 landmarks.
D. Each query answered by partner i involves at most two new endpoints, so it increases the number of landmarks of i by at most 2. Hence, in the case described by paragraph C, the algorithm must ask each of n/2 partners, at least n/4 queries. The total number of queries is thus at least n^{2}/8 = Ω(n^{2}).
It is an open question whether a bounded algorithm exists for arbitrary valuation functions. Thus there is a huge gap between the lower bound of Ω(n^{2}) and the best currently known algorithm which is finite but unbounded.
Existence proofs and variants
In addition to the general existence proofs implied by the algorithms described above, there are proofs for the existence of envyfree partitions with additional properties:
 There exists an exact division, which is in particular envyfree; see DubinsSpanier theorems.
 There exists an envyfree division which is also Pareto efficient; See Weller's theorem.
Both proofs work only for additive and nonatomic value measures, and rely on the ability to give each partner a large number of disconnected pieces.
Weightedenvyfree division
A common generalization of the envyfree criterion is that each of the partners has a different entitlement. I.e., for every partner i there is a weight w_{i} describing the fraction of the cake that they are entitled to receive (the sum of all w_{i} is 1). Then a weightedenvyfree division is defined as:
 For every agent i with value measure V, and for every other agent k:
 V(X_{i}) / V(X_{k}) ≥ w_{i} / w_{k}
I.e., every partner thinks that their allocation relative to their entitlement is at least as large as any other allocation relative to the other partner's entitlement.
When all weights are the same (and equal to 1/n), this definition reduces to the standard definition of envyfreeness.
When the pieces may be disconnected, a weighted envyfree division can be found constructively using the RobertsonWebb protocol, for any set of weights.
But when the pieces must be connected, only nonconstructive existence proofs are reported. A weighted envyfree division is known to exist in the following cases (each case generalizes the previous case):
 Additive value functions, 1dimensional cake (interval), and the pieces must be connected intervals.^{[19]}
 Additive value functions, multidimensional simplex cake, and the pieces must be simplexes.^{[20]} The proof uses Sperner's theorem, the KKM lemma, Gale's covering lemma and Ky Fan's lemma on coincidence points.
 Nonadditive value functions, multidimensional simplex cake, and the pieces must be polytopes.^{[21]}
Dividing a 'bad' cake
In some cases, the 'cake' to be divided has a negative value. For example, it might be piece of lawn that has to be mowed, or a piece of wasteland that has to be cleaned. Then, the cake is a 'heterogeneous bad' rather than a 'heterogeneous good'.
Some procedures for envyfree cakecutting can be adapted to work for a bad cake, but the adaptation is often not trivial. See envyfree chore division for more details.
Summary tables
Name  Type  Cake  Pieces  #queries  #cuts  envy  Comments  

Divide and choose  Discrete proc  Any  Connected  2  2  1 (optimal)  None  1/2  
Stromquist  Movingknife proc  Interval  Connected  3  ∞  2 (optimal)  None  1/3  
Selfridge–Conway  Discrete proc  Any  Disconnected  3  9  5  None  1/3  
Brams–Taylor–Zwicker  Movingknife proc  Any  Disconnected  4  ∞  11  None  1/4  
Saberi–Wang^{[12]}  Discrete proc  Any  Disconnected  4  Bounded  Bounded  None  1/4  Free disposal 
Aziz–Mackenzie^{[16]}  Discrete proc  Any  Disconnected  4  203  584  None  1/4  
Saberi–Wang^{[12]}  Movingknife proc  Any  Disconnected  5  ∞  Bounded  None  1/5  
Stromquist  Existence  Interval  Connected  n  —  n1  None  1/n  
Simmons  Discrete proc  Interval  Connected  n  ∞  n1  None  1/n  
DengQiSaberi  Discrete proc  Interval  Connected  n  n1  Additive  Only when valuations are Lipschitzcontinuous  
Branzei^{[6]}  Discrete proc  Interval  Connected  n  ?  None  1/n  Only when value densities are polynomial with degree at most d.  
WasteMakesHaste  Discrete proc  Interval  Connected  3  9  4  None  1/3  Free disposal 
WasteMakesHaste  Discrete proc  Any  Connected  4  16  6  None  1/7  Free disposal 
WasteMakesHaste  Discrete proc  Any  Connected  n  None  Free disposal  
AzizMackenzie ConnectedPieces ^{[8]}  Discrete proc  Any  Connected  n  None  Free disposal  
BramsTaylor  Discrete proc  Any  Disconnected  n  Unbounded  Unbounded  None  1/n  
RobertsonWebb  Discrete proc  Any  Disconnected  n  Unbounded  Unbounded  None  1/n  Weightedenvyfree. 
Pikhurko^{[14]}  Discrete proc  Any  Disconnected  n  Unbounded  Unbounded  None  1/n  
Aziz–Mackenzie^{[8]}  Discrete proc  Any  Disconnected  n  None  1/n  
Reentrant last diminisher  Discrete proc  Interval  Disonnected  n  ?  Additive  1/n  
KurokawaLaiProcaccia^{[17]}  Discrete proc  Interval  Disonnected  n  ?  None  1/n  Only when value densities are piecewise linear with at most k discontinuities.  
Weller  Existence  Any  Disconnected  n  —  ∞  None  1/n  Pareto efficient. 
2D  Discrete proc  Square  Connected and Square  2  2  2  None  1/4  Free disposal 
2D  Movingknife proc  Square  Connected and Square  3  ∞  6  None  1/10  Free disposal 
Summary by number of agents and type of pieces:
# agents  Connected pieces  General pieces 

2  Divide and choose  
3 
Stromquist movingknives procedure (infinite time); Wastemakeshaste (boundedtime, bounded cuts, free disposal, proportional) 
Selfridge–Conway discrete procedure (boundedtime, at most 5 cuts). 
4  Wastemakeshaste (boundedtime, bounded cuts, free disposal, proportionality 1/7). 
Brams–Taylor–Zwicker moving knives procedure (infinite time, at most 11 cuts). Saberi–Wang discrete procedure^{[12]} (bounded time, bounded cuts, free disposal, proportional). Aziz–Mackenzie discrete procedure^{[16]} (bounded time, bounded cuts, proportional). 
5  Saberi–Wang movingknives procedure^{[12]} (infinite time, bounded cuts).  
n 
Simmons' protocol (infinite time) DengQiSaberi (approximately envyfree, exponential time). Wastemakeshaste (fully envyfree, exponential time, freedisposal, exponential proportionality) AzizMackenzie ConnectedPieces ^{[8]} (fully envyfree, exponential time, freedisposal, linear proportionality) 
Brams and Taylor (1995); Robertson and Webb (1998).  Both algorithms require a finite but unbounded number of cuts. AzizMackenzie discrete procedure^{[8]} (bounded time, bounded cuts, proportional). 
Hardness  All algorithms for n ≥ 3 must be infinite (Stromquist, 2008).  All algorithms must use at least Ω(n^{2}) steps (Procaccia, 2009). 
Variants  A weighted envyfree division exists for arbitrary weights (Idzik, 1995), even when the cake and pieces are simplexes (Idzik and Ichiishi, 1996), and even with nonadditive preferences (Dall'Aglio and Maccheroni, 2009). 
RobertsonWebb can find weightedenvyfree divisions for arbitrary weights. A perfect division exists (Dubins&Spanier, 1961). An envyfree and efficient cakecutting exists (Weller's theorem). 
See also
 Envyfree chore division
 Envyfree item assignment
 Fair piecutting
 Groupenvyfree
 Proportional cakecutting
External links
 Fair Division Calculator  an applet for calculating envyfree division for cakes, chores, rooms and rents.
References
 ^ Gamow, George; Stern, Marvin (1958). Puzzlemath. ISBN 9780670583355.
 ^ Stromquist, Walter (1980). "How to Cut a Cake Fairly". The American Mathematical Monthly. 87 (8): 640–644. doi:10.2307/2320951. JSTOR 2320951.
 ^ Stromquist, Walter (2008). "Envyfree cake divisions cannot be found by finite protocols" (PDF). Electronic Journal of Combinatorics.
 ^ Stromquist movingknives procedure requires the three agents to adjust their knives whenever the sword of the referee moves. Since the sword moves continuously, the number of steps required is an uncountable infinity. Simmons cakecutting protocol converges to an envyfree division, but the convergence might require an infinite number of steps.
 ^ ^{a} ^{b} Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic Solutions for EnvyFree Cake Cutting". Operations Research. 60 (6): 1461–1476. doi:10.1287/opre.1120.1116.
 ^ ^{a} ^{b} Brânzei, S. (2015). "A note on envyfree cake cutting with polynomial valuations". Information Processing Letters. 115 (2): 93–95. doi:10.1016/j.ipl.2014.07.005.
 ^ ^{a} ^{b} SegalHalevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "Waste Makes Haste". ACM Transactions on Algorithms. 13: 1–32. arXiv:1511.02599. doi:10.1145/2988232.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} Aziz, Haris; MacKenzie, Simon (2016). "A discrete and bounded envyfree cake cutting protocol for any number of agents". FOCS 2016. arXiv:1604.03655. Bibcode:2016arXiv160403655A.
 ^ Erel SegalHalevi and Avinatan Hassidim and Yonatan Aumann (Jan 2015). EnvyFree CakeCutting in Two Dimensions. The 29th AAAI Conference on Artificial Intelligence (AAAI15). Austin, Texas. pp. 1021–1028. doi:10.13140/RG.2.1.5047.7923.
 ^ Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cakecutting to dispute resolution. Cambridge University Press. ISBN 0521556449.
 ^ Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). "A MovingKnife Solution to the FourPerson EnvyFree Cake Division" (PDF). Proceedings of the American Mathematical Society. 125 (2): 547–555. doi:10.1090/S0002993997036149. Retrieved 2 September 2014.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} Amin Saberi and Ying Wang (2009). Cutting a Cake for Five People. Algorithmic Aspects in Information and Management. doi:10.1007/9783642021589_25.
 ^ S. J. Brams, M. A. Jones, and C. Klamler, "Better ways to cut a cake," Notices of the AMS, 2005. [Online]. Available: http://www.ams.org/notices/200611/feabrams.pdf
 ^ ^{a} ^{b} Pikhurko, O. (2000). "On EnvyFree Cake Division". The American Mathematical Monthly. 107 (8): 736–738. doi:10.2307/2695471. JSTOR 2695471.
 ^ Gasarch, William (2015). "Which Unbounded Protocol for Envy Free Cake Cutting is Better?". arXiv:1507.08497 [math.LO].
 ^ ^{a} ^{b} ^{c} Aziz, Haris; MacKenzie, Simon (2016). "A discrete and bounded envyfree cake cutting protocol for four agents". Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing  STOC 2016. p. 454. arXiv:1508.05143. doi:10.1145/2897518.2897522. ISBN 9781450341325.
 ^ ^{a} ^{b} Kurokawa, David; Lai, John K.; Procaccia, Ariel D (2013). "How to Cut a Cake Before the Party Ends". AAAI. Retrieved 2 September 2014.
 ^ Procaccia, Ariel (2009). "Thou Shalt Covet Thy Neighbor's Cake". IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence: 239–244.
 ^ Idzik, Adam (1995). Optimal divisions of the unit interval. Jerusalem.
 ^ Ichiishi, T.; Idzik, A. (1999). "Equitable allocation of divisible goods". Journal of Mathematical Economics. 32 (4): 389–400. doi:10.1016/s03044068(98)000536.
 ^ Dall'Aglio, M.; MacCheroni, F. (2009). "Disputed lands" (PDF). Games and Economic Behavior. 66: 57–77. doi:10.1016/j.geb.2008.04.006.
 ^ Proportionality = the value (as fraction of the whole cake) that is guaranteed to each agent with additive valuations. When there is no envy and the entire cake is divided, the proportionality is always 1/n, which is the best possible.