The Query Complexity of Cake Cutting
Authors: Simina Branzei
Noam Nisan
Venue: NeurIPS 2022 Accept (2022)
Keywords: fair division
cake cutting
query complexity
lower bounds
upper bounds

Abstract: We consider the query complexity of cake cutting in the standard query model and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing contiguous  envy-free allocations among $n=3$ players and for computing perfect and equitable allocations with minimum number of cuts between $n=2$ players. For $\epsilon$-envy-free  allocations with contiguous pieces, we also give an upper bound of $O(n/\epsilon)$ and  lower bound of $\Omega(\log(1/\epsilon))$ queries for any number $n \geq 3$ of players.

We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.

The Query Complexity of Cake Cutting
Simina Brânzei Purdue University, USA s simina. branzei ariina.brazzei @gmail. com
Noam Nisan
Hebrew University of Jerusalem, Israel noamccs .uw.ssuuji..... huji.ac.il
Abstract
We consider the query complexity of cake cutting the standard query model and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing contiguous envy-free allocations among and for computing perfect and equitable allocations with minimum number of cuts between
players
2 players. For c-envy-free allocations with contiguous pieces, we also give an upper bound of (n/cc) and lower bound of ((log(1/c)) queries for any number n 2 3 of players.
We also formalize moving knife procedures and show that large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson- -eebbb query model.
Introduction
We consider the classical cake cutting problem due to Steinhaus [62], which captures the fair division of a heterogeneous resource- succh land, time, mineral deposits, fossil fuels, and clean water among several parties with equal rights but different interests over the resource. This model has inspired rich body of literature mathematics, political science, economics [58, 11, 49], and computer science [15, 27]. Implementations of fair division algorithms can be found on Spliddit [45].
Mathematically, the cake represented as the unit interval [o, 1]. There is set of players with valuation functions induced by probability measures over [o, 1]. Given such a resource, the goal is to compute an allocation of the cake in which every player is content with the piece received. A major challenge for mediator trying compute a desirable allocation is that the preferences of the players are private. Discrete cake cutting protocols operate in query model, due to Robertson and Webb [68], in which a center that does not know the players asks them cut and evaluate queries until it manages to extract enough information about their preferences to determine fair allocation.
An example of a cake cutting protocol is ago when appeared in written records in the context of land division. -ut-and-Choose to obtain an envy-free allocation among two players, Alice and Bob, trying to divide heterogeneous resource (e.g. birthday cake with different toppings): First Alice cuts the cake in two pieces of equal value to her, then Bob picks his favorite and Alice takes the remainder.
which dates back to more than 2500 years
be used
Fairness Notions. Two of the prominent fairness notions, envy-freeness and proportionality, have been the subject of in depth study from computational point of view. Proportionality requires that each player gets their fair share of the resources, which is their total value for the whole cake divided by the number of players, while envy- snvy-freeness is based on social comparison and means no player should want to swap their piece with anyone else's. The two notions are not necessarily comparable, since
can be trivially achieved by throwing away the entire resource, which is not true for proportionality. However, when the entire cake must be allocated, envy-freeness implies proportionality and can be surprisingly hard to reach.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The problem of finding an envy-free cake cutting protocol was suggested by Gamow and Stern [41] and solved by Selfridge and Conway for three players (cca. 1960, see, e.g., [58, 1 11]) and by Brams and Taylor [14] for any number of players. From a computational point of view, the Brams and Taylor protocol has the major drawback that its runtime can be made arbitrarily long by setting up the valuations of the players appropriately. In 2016, Aziz and Mackenzie [6] announced a breakthrough by giving the first bounded envy-free cake cutting protocol for any number of players, where bounded means that the number of queries is only function of the number of players, and not of the valuations.
The query complexity of proportionality is well understood. The problem of computing proportional allocation with contiguous pieces can be solved with O(n log n) queries in the Robertson- -eettsonn-WWbbbbbb model by running a protocol due Even and Paz [36], with a matching lower bound due to Woeginger and Sgall [68] for contiguous pieces; this was extended to arbitrary allocations by Edmonds Pruds [34].
In contrast, for the query complexity of envy-free cake cutting lower bound of (2n2)) was given by
Procaccia [55] and upper bound of O nanann
by Aziz and Mackenzie [6]. The algorithm in [6] outputs highly fragmented allocations on some instances. Envy-free allocations with contiguous pieces do in fact exist for very general valuations (see, e.g., [61, 63, 65]), but cannot be com- puted in the Rohertson- Webb model [64] except for specific classes such as polynomial functions [16].
Approximate Fairness. In light of this impossibility, it makes sense to study the computation of e-envy-free allocations with few cuts. For a general utility model where the valuations are arbitrary functions (not necessarily induced by probability measures), bounds on the query complexity of approximate envy-free cake cutting with contiguous pieces were given in [32] together with a proof of PPAD-hardness. While the problem of computing contiguous e-env--free allocations is in PPAD [65], neither the computational hardness nor the query lower and upper bounds in [32] carry over (or are close to tight) in the usual cake cutting model where the valuation functions are induced by probability measures, which leaves wide open the complexity of this problem.
Aside from proportionality and envy-freeness, a third notion of faimess is known as equitability, in which each player must receive a piece worth the same value. Equitable and proportional allocations with contiguous pieces were shown to exist by Cechlarova, Dobos, and Pillarova [24]. The compu- tational complexity of approximate equitability was investigated by Cechlarova and Pillarova [25],
who gave an upper bound of O (n (log n + log e ))) for computing an e-equitable and proportional allocation with contiguous pieces for any number of players, and by Procaccia and Wang [57]
who showed a lower bound of & (log e log log e 1) for finding an e-equitable allocation (not necessarily contiguous) for any number of players.
More stringent fairness requirements are also possible, such as (i) the necklace splitting problem, for which the existence of fair solutions was established by Neyman [50], with bound the number of cuts given by Alon [2], (fi) the more general notion of exact division 2, which generalizes necklace splitting and was shown exist by [33], and (iii) the competitive equilibrium from equal incomes, the existence of which was determined by Weller [67]. The necklace splitting problem is contained in PPA and in fact is PPAD-hard [38]. A well known instantiation of the necklace splitting solution is that of perfect allocations, which are simultaneously proportional, envy-free, and equitable.
The complexity and existence of various fairness concepts in cake cutting and related models, such as cake cutting where the resource is a chore, pie, multiple homogencous goods, multiple discrete goods have also been studied (see, c.g., [29, 52, 4, 22, 42, 30, 17, 13, 23, 53, 9, 1, 18]). The communication complexity of cake cutting was studied in [21].
Related Work.
Since the initial manuscript of our paper was circulated, there have been many follow-up up works. The complexity of cake cutting (e.g. envy-free division, consensus halving, necklace splitting) was studied, e.g., in [31, 43, 28, 44, 40, 39, 3. 54, 8). Indivisible goods were studied, e.g., in [51] for their query complexity and in [48, 26] for algorithms. Cake cutting with separation was studied [35], fair division of a graph in [10]. multi-layere cakes in [46], fair cutting in practice in [47]. and cake cutting where some parts are good and others bad in [59] and when the whole cake is a "bad" in [37].
'Such allocations exist even for valuations not induced by probability measures (see, e.g., [61]. [63] for proof based on a topological lemma on intersection of sets, and [65] for a proof using Sperner's lemma). 'The problem of exact division is the following: given a cake with players and target non- non-negative weights wi wa. find partition A (Ai...., As) such that Vi(A,) = wy for each player and every piece Aj.
2

---

2 Our Contribution
We consider the query complexity of cake cutting in the standard Rohertson- -eerbb (RW) query model [68] for several fairness notions: envy-free, perfect, and equitable allocations with the minimum number of cuts. Such allocations known exist for each instance, but several impossibility results preclude their computation in the standard query model [64, 25].
Nevertheless, the computation of approximately fair solutions is possible by discretizing the cake in very small pieces. For the fairness notions we consider, a number of queries that is polynomial in n and 1/c suffices to find e-fair allocations for several fairness concepts, such ((n/c) for contiguous envy-free allocations and (n 1)/c) for (e, k) memasree splittings.
2.1 Lower Bounds
Our first main contribution is to give lower bounds for the problems of computing approximately fair allocations (with deterministic protocols).
Theorem 2.1. Consider cake cutting problem. In the standard (RW) query model, for each >> 0:
Finding an e-envy-free allocation with contiguous pieces for 2 3 players, where is fixed, requires (log :) queries.
Finding an e-equitable allocation with contiguous pieces for n = players requires Ω (log 2) queries.
Findinn an e-perfect allocation with two cuts for n = 2 players requires (log) :) queries.
In the case of perfect allocations for two players, we are always guaranteed to have solution with at most two cuts, while solution with one cut may not exist. The lower bounds for envy-freeness and perfect allocations are the first query lower bounds for these problems. The main idea underpinning these results is that of maintaining a self-reducible structure throughout the execution of a protocol, which may be useful more generally for obtaining other lower bounds.
2.2 Upper Bounds
We give the following upper bounds for these fairesss notions.
Theorem 2.2. Consider cake cutting problem. In the standard (RW) query model, for each e >> 0:
An e-envy-free allocation with contiguous pieces for n = 3 players can be found with Ologg 2) queries and for n 2 4 players with O(n/e) queries.
An e-perfect allocation with at most two cuts for 2 players can be found with O(log ) queries.
The upper bounds do not assume any restrictions on the valuations and the proofs rely on approxi- mately simulating in the RW model two moving knife procedures, due Barbanei-Brams [7] and Austin [5], respectively. An upper bound of O (log 2) for computing an e-equitable allocation with contiguous pieces between two players was given by Cechlarova and Pillarova [25].
summary of our bounds for the query complexity of computing fair allocations can be found in Table together with the results from previous literature.
2.3 Moving Knife Protocols
Our second main contribution is to formalize the class of moving knife procedures, which was previously viewed as disjoint from the RW query model. Using this definition, we show that any fair moving knife procedure with fixed number of players and devices can simulated in O(lo !) queries in the RW model when the players have value densities that are bounded from above by constant. The next theorem written for an abstract fairness notion, which we later deñne.
Theorem 2.3. Consider cake culting problem where the value densities are bounded from above and below by strictly positive constants. Let M be an RW moving knife protocol with at most r steps, such that M outputs F F-fair allocations demarcated by at most constant number C of cuts.
3

---

Then for each > O, there is an RW protocol Me that uses O (log !) queries and computes e-F F-F-fair
partitions demarcated with at most cuts.
Fairness notion
Players
Upper bound
Lower bound
2
c-envy-free (connected)
n = 3
Ollog c
2loo e
n 2 4
O(n/e) (*)
Q
(loge
= 2
Olloge E
22(log
(*)
e-perfect (min cuts)
n 2 3
0 (n² /c) [19]
log
[57]
log log.
n 2
Olloge ') [25]
(2(loge e
(*)
e-equitable (connected)
n 2 3
O (n (logn + log ()) [25]
Ω
log e-
[57]
lox log -
n
envy-free (exact)
n 2 2 n1 2
[6]
M(n2)) [55]
proportional (exact)
0 log
[36]
S2(n log n) 168, 34]
Query complexity of cake cutting in the standard query model. Our results are marked with (+). The lower bounds for finding é-perfect and e-equitable allocations for 2 3 players hold for any number of cuts [57]. The bounds for exact envy-free and proportional allocations hold for any number of cuts, except the upper bound for proportional works for contiguous pieces.
Figure I:
This simulation immediately implies that all the known moving knife procedures, such as the procedures designed by Austin, Barbanel-Brams, Webb [66], and Brams-Taylor Taylor-Zwicker Zwicker [12], can be simulated efficiently within e-error in the RW model when the measures of the players are bounded. In this context we also found a moving knife procedure for computing contiguous equitable allocations for any number of players, which was discovered independently by Segal-Halevi [60]. Note that our version of the protocol works only for hungry valuations (i.e. when the value densities are strictly positive everywhere), while the protocol in [60] works for value densities that could be zero well.
3 Model
The resource (cake) is represented as the interval [0. 1]. There is a set of players N = (1....... ........) nn}
interested in the cake, such that each player i E N is endowed with private valuation function V; that assigns a value to every subinterval of [o, 1). These values are induced by a non-negative integrable value density function Us that for interval I, Vi(I) Jeer (z(z) dr. The valuations
are additive, so VE (U) EE V.(T,) for any disjoint intervals I,,..., Im S [0, 1]. The
value densities are non non-atomic, and in fact sets of measure zero are worth zero to player. Without loss of generality, the valuations are normalized to Vi((0, 1]) = 1, for all = 1.... n.
A piece of cake is a finite union of disjoint intervals. A piece is contiguous (or connected) if it consists of a single interval. An allocation Á (A1, ...,,.,, A,) is a partition of the cake among the players, such that each player i receives the piece A,, the pieces are disjoint, and UIeN A, = [0, 1).
We say that a value density v is: (i) hungry if v(x) > 0 for all x E [0, 1]. (ii) uniform on an interval (a, b] if v(x)
for all E [a, b). and (Hii) bounded on interval [a, b) if there exists constant D >> such that o(z) 2 D for all x E [a, b] (or simply bounded if a = and = 1). We sometimes to refer to valuation (or player) as hungry to mean that the corresponding density is strictly positive.
3.1 Fairness Notions
An allocation is said to be proportional V(A,) > 1/n for all E N; envy-free Vf > Vi(A,) for all í,j E N; perfect if Vi(A,) = 1/n for all i.j E N; equitable if Vi(A+) = c. for all E N and some value E [0, 1]. In addition to allocations, we will refer to partitions as divisions of the cake into pieces where the number of pieces need not equal the number of players. A partition A = (AI,..., Av) is k-measure splitting if V:(A,) 1/k for each player and piece Aj-
Envy-free allocations with contiguous pieces and equitable allocations with contiguous pieces always exist [65, 24], while k-measure splittings exist with n2(k 1) cuts [2].

---

We will also be interested in e-fair division, where the faimess constraints are satisfied within e-error; for instance, an allocation e-envy-free if (A.) 2 V, (A,,, - c. for each i, 1... n, and an (e, k) measure splitting if Vi(A,) E (1/k - e, 1/k + c) for each i = 1....
....k.
We consider abstract definition for fairness notions that admit approximate versions as follows. Definition 1 (Abstract fairness). A fairness notion F must satisfy the following condition:
A = (A1 ; An) be allocation that is F-fair with respect to valuattions ह =(11.. (V1.... .p)) For each e > O and valuations v' = (v² (o/_...') r.)). if Vv(AA) - V(()) S </22. Vi.j E N, then allocation A is e-F-fair with respect valuations 0².
Proportionality, envy-freeness, and perfection are instantiations of this notion of abstract fairness. E.g. if an allocation A is envy-free with respect to valuations ह. then A is also e-envy-free for valuations that are close to U.
3.2 Query Complexity
All the discrete cake cutting protocols operate in query model known as the Robertson-Wan model (see, e.g., the book [58]). which was explicitly stated in [68]. In this model, the protocol communicates with the players using the following types of queries:
(at; Player cuts the cake at a point y where Vi( y)) a, where a E [o, 1] is chosen
arbitrarily by the mediator 9. The point y becomes cul point.
-Eval,y)) Player i returns (i vl). where y is a previously made cut point.
An RW protocol asks the players sequence of cut and evaluate queries, at the end of which it outputs an allocation demarcated by cut points from its execution (i.e. cuts discovered through queries). Note that the value of a piece [I. y] can be determined with two Eval queries, Eval; (x) and Eval(
second class of protocols is known as "moving-knife (or continuous) procedures, which typically involve sliding multiple knives across the cake, while evaluating the players' valuations until some stopping condition met. This class has been formalized until now. Examples of moving knife procedures include Austin's 's procedure, which computes a perfect allocation for two players, Stromquist's 's procedure. for finding contiguous envy-free allocation for three players, and Dubins- Spanier, for computing a proportional allocation for any number of players. Dubins Dubins-Spanier is the only known moving knife procedure that can be simulated exactly the RW model.
Envy-Free Allocations
Exact envy-free allocations are guaranteed to exist (see, e.g., Stromquist [63] and Su [65]), but cannot be computed by finite RW protocols for n 2 players (see Stromquist [64]). For n = 2 players, an exact envy-free allocation can be computed with ((1) queries via the Cut and Choose protocol.
An e-envy-free allocation with contiguous pieces can be found with (nn/c) queries as follows.
Theorem 4.1. For each cake cutting problem with n 2 3 players and every >> 0, an e-envy-free allocation with contiguous pieces can computed with O (n/c) queries.
Proof sketch. Let K = [2/c]. Discretize the cake, by asking each player to divide the cake in many small cells (K of them) of equal value 1/K. For each player i, let ü, be the value density consistent with player i's report and furthermore constant inside each interval generated by player Find an exact envy-fire allocation A with contiguous pieces with respect to valuations ō (ū,,.... (01,..... k.). which is guaranteed exist. Then round each demarcation point of allocation Á to the closest cut point reported by some player. The resulting allocation, A, is e-envy-free with respect to the true value densities ग. The total number of queries nk = O(n/e).
We further show that for three players, e-envy-free allocation with contiguous pieces can be computed using only O (log ?) queries.
Theorem 4.2. For each cake cutting problem with n = 3 players and every O, c-envy-free allocation with contiguous pieces can be computed with O (log 2) queries.
"Ties are resolved deterministically, using for example the leftmost point with this property.
5

---

The idea is to approximately simulate moving knife procedure due to Barbanel- [7]. A detail that must be handled that a discrete RW protocol does not allow the mediator to cut the cake directly, so the simulation has to search for the position of the "sword" in the moving knife protocol by keeping track of small interval that must be made very small from the perspective of each player. The details can be found in the full version [20], together with the other omitted proofs.
Next we give lower bound for three players; this will be extended to n 2 3 players in Theorem 4.4. Theorem 4.3. For each > requires 2 (log] !) queries.
O, computing a contiguous c-emvy-free allocation for three players
Generally there are many envy-free allocations, so the proof must ensure that for long enough time none of these solutions are near. We will start from a family of valuations known as "rigid measure systems" [64], which was invented by Stromquist to show that no exact contiguous envy-free allocation can be computed in general in the RW model.
The difficulty is that while in [64] it was sufficient to avoid a single point in order for the protocol to not be able to find an exact envy-free solution with one more query, here we must avoid entire interval and fit the valuations accordingly in order for an approximately envy-free solution to remain far away after each additional query. We first slightly generalize rigid measure systems from [64], to allow a different parameter t; for each player i. Then we will make a self reducible structure using this family of valuations, which will then be used to give the required lower bound.
Definition 2. A tuple of value densities (VI,.... Un) is generalized rigid measure system if:
the density of each player i is bounded by: 1/v2 < (4(2) < v2, Ve E [0.
there exist points 0- = Zu < 11 < < In-1 < In = 1 and values st, for each player such that 0 < 8; < 1/n < < < 1/2 and (,(#;-1, = V,(1,, = 1 for all ==1
1 and Vn (xn x.)) (0, m) = In-
See the full version [20] for an example. Generalized rigid measure systems satisfy the property that the valuations of the players for any given piece cannot differ too much.
Lemma 1. Consider any cake cutting problem where for two players and j where there exist a. > 0 such that for all x E [0, 1]. 1/a < vx(x)) < b and 1/a u, v2(x)) < b. Then for any two pieces S1, S2 of the cake, if (SL)) 2 ab Vi())), it follows that ab (y(S,) > Vy(S)).
A useful notion to measure how close protocol is to discovering approximately envy-free solution on a given instance will be that of a partial rigid measure system.
Definition 3. A tuple of value densities (vi, U2, v3) is a partial rigid measure system if
the density of each player i is bounded everywhere by: 1/v2 vx(x)) < f2r all [0, 1].
there exist values k > 0 and 1/2 > 4 > 1/3 m; 0 for each player i, and points x, x,, U.. E [0, 1). so that the matrix of valuations for pieces demarcated by these points is:
0,
[r, x²)
[x', y]
[y, y²
|111]
Vi
L1
k
C1
mi
12
m2
k
l2
l2
V3
k
m3
Ls
Partial rigid measure systems have the next property: if P = {z1...., 2x3 C [0, 1] is a collection of points such that points from P can be found in the intervals (x,x') and v'). then every contiguous partition attainable using only cut points from P has envy at least 0.01k.
Lemma 2. Let (V1, D2 1z) be a partial rigid measure system with parameters m,, 2,, x', y.y/ so that ([xxx11) = V((ly.e)) = k Vi. IfP = { ..) c [0, 1] is a collection of cut points such that (i) 2, y. v E and (ii) no points from P can be found in the intervals (x, x') and (g. y²), then each allocation with contiguous pieces demarcated by points in P has envy at least 0.01k.
Next we show how queries can be answered one at a time so that the valuations remain consistent with (some) partial rigid measure system throughout the execution of a protocol.
Lemma 3. Suppose that at some point during the execution of an RW protocol for three players the valuations and cut points are consistent with partial rigid measure system with parameters

---

[0,x]
[,,
[r
k.
b t k]
[y t k.
1.
V1
4
k
24
k
V22
k
22
k
2g
V4
&
k
k
8x
Figure 2: Construction for envy-freeness.
1/2 for each i, and points 2; v,y (i.e. as Figure 2). If the intervals T= ==<=,> k) and J 1. k] have cut points inside, then a new cut query can be answered so that the valuations remain consistent with a partial rigid measure system where two new intervals I' - and J' S J have no length 0.01% and no cut points inside, and the densities of all the players are uniform on and J'.
0,0 m4 1/3
Proof. (of Theorem 4.3) Set the initial configuration to partial rigid measure system with k 0.01, & = 0.35, my 0.28 for each player i. Let the initial cut points be 0.34, 0.35, 0.67, 0.68 and set the be verified there exist compatible valuations
intervals [0.34, 0.35] and [0.67, 0.68).
for which the densities are (1/v2, /2).
By iteratively applying Lemma with every Cut query, the valuations remain consistent with a partial rigid system, where the intervals / and J always have uniform density, and their length cannot be diminished by a factor larger than 100 in each iteration. By Lemma 1, every configuration attainable with the existing points when given partial rigid system input has envy of at least 0.01 To get c-envy, we need k/100 < e, and so the number of queries is Ω (log 1)).
The construction can extended to give lower bound for any number of players. Theorem 4.4. Let n 2 be fixed. For each > O, computing an c-envy-free allocation with contiguous pieces for 2 3 players requires Q (log t) queries.
The lower bound of Ω (log 2) is in fact tight for the class of generalized rigid measure systems, for any fixed number of players. To show this, we prove an upper bound of O (log !) for this class by designing moving knife procedure and then simulating it in the RW model.
Theorem 4.5. For the class of generalized rigid measure systems, an c-envy-free allocation with contiguous pieces be compuled with O (log !) queries for every fixed number n of players.
Perfect Allocations
We show that for n = 2 players, the problem of computing e-perfect allocations can be solved more efficiently by simulating Austin's moving procedure in the RW model.
Theorem 5.1. For each cake cutting problem with n players and every > 0, an e-perfect allocation can be computed with Oloog {) queries.
We also show this bound is optimal by giving matching lower bound.
Theorem 5.2. For each > 0, computing an e-perfect allocation with the minimum number of cuts for n 2 players requires 2 (log? +) queries.
We prove the lower bound by maintaining throughout the execution of any protocol two intervals in which the cuts of the perfect allocation must be situated, such that the distance perfect partition cannot decrease too much with any cut query. The work in [21] gave (weaker) lower bound for finding e-perfect allocations between two players in the communication model, which implies a lower bound for query complexity (in the RW model any other query model).
Lemma 4. Consider cake cutting instance with = 2 players and let e >> 0. Suppose a protocol made a sequence of queries such that the valuations are consistent with Figure for some parameters y, a, b, c, d, > O, such that player has uniform density everywhere, y = I 0.5. 0 < a, d S 0.1, x. b, C, e > O, x + + 0.5 c + 2d + 0.5, and moreover:
1. 0.001 min0amin(a,d min((ad))

---

[
[A,A +
[x
[y.y +u]
yy +
V2
x
0.5
b
V
d
0.5 2d
3d
Figure 3: Construction for the perfect lower bound.
2. every allocation demarcated by cuts k. l. (0. with < that is e-perfect from the point of view of player 1 is worth player less than 0.5 d/100 when h. < x and more than 0.5 + d/ 100 + when k > + a.
3. there are no cut points inside the intervals I I= (-,x x + a] and J ly. + a].
Then more query can be answered that the valuations remain consistent with the history of the protocol and conditions 2 and still hold with respect to new parameters x', x', a//100, = d/100 and intervals I' [x', xx + a'),
[y/, a²).
Proof of Theorem 5.2. Set the initial configuration consistent with Figure 3 for suitable initial choice of parameters. Then, by iteratively applying Lemma 4 with every cut query received, we will obtain that the number of queries is f2 (log )
Equitable Allocations
Cechlarova, Dobos, and Pillarova [24] showed that for any number of players and any order, there exists a contiguous equitable allocation in that order. Moreover, the equitable allocation is proportional for some order of the players.
Theorem 6.1 Cechlarova and Pillarova [25]). For every fixed number n of players and each > 0, contiguous e-equitable and proportional allocation can be computed with O(log !) queries.
give a matching lower bound for the number of queries required for finding e-equitable allocations with contiguous pieces between two players.
Theorem 6.2. For each e > O, computing an e-equitable allocation with contiguous pieces for two players requires Ω (log Q) queries.
For two hungry players, the contiguous equitable and proportional allocation is unique. Lemma 5. For two players with hungry valuations, the cut point of the equitable allocation is unique.
Next we show that when the valuations of the players as in the next figure and no cuts may be used from the interval (z, y). the distance from contiguous equitable allocation is high.
[0,x]
[x,y]
[y. 1]
1/
0.5
0.5
V/2
0.5
0.5
Figure 4: Construction for equitable lower bound. The distance from contiguous equitable and 0.5 and x <
proportional allocation is a, where
Lemma 6. Consider two player problem where there exist points O < < < 1 and values
a < < 0.5 such that the valuations are consistent with Figure where Vi x) = 0.5 + a Valu. 1), V2(x, 1) 0.5 + (1 y). Then every contiguous allocation that uses cul points outside the interval (x. y) has distance least b a from equitability.
Given such a configuration, queries can be handled in a way that preserves the symmetry and the distance to equitability gets reduced by constant factor.
Lemma 7. Consider a two player problem where there exist points 0 < r < y < 1 and values 0 < b < 0.5 such that (0, x)) 0.5 + V2ly, 1), Vz(x, 1) 0.5 + b (0, y). Then any Cut query (addressed to either player) can be answered so that the new configuration has two new points < such that z, E (z, y), the valuations satisfy V1 (0, 0.5 + V2 1),
1) = 0.5 + b' = V0 t), and t' 2 (b a)/100.
The proof of Theorem 6.2 follows by combining the previous lemmas (see full version [20]).

---

7 Moving Knife Protocols
We will consider family of protocols that seems to, on one hand, capture all types of protocols that have so far been called "moving knife" procedures and, on the other hand, be simple enough for a transparent simulation. An important ingredient of the definition is that knife positions must be continuous. To ensure that "cut queries" fall within the definition, we will only require continuity for hungry valuation functions. The formal definition can be found in the full version of the paper [20].
Theorem 7.1. Consider cake cutting problem where the value densities are bounded from above and below by strictly positive constants. Let M be an RW moving knife protocol with at most r steps, such that M outputs F F-fair allocations demarcated by at most a constant number C of cuts.
Then for each > O, there is an RW protocol M, that uses O (log 2) queries and computes e-F-fair partitions demarcated with at most C cuts.
Theorem 7.2. The Austin, Austin's 's extension, Barbanel- Barbanel-Brans, Stromquist, Webb, Brams- Brams-Taylor- Zwicker, and Saberi-Wann moving knife procedures can be simulated with O (log () RW queries when the value densities are bounded from above and below by positive constants.
An Equitable Protocol:
Next show simple moving knife protocol in the Robertson Webb model for computing equitable allocations for any number of hungry players. A moving knife procedure for computing exact equitable allocations that works even when the valuations not hungry was discovered independently by Segal-Halevi [60].
Equitable Protocol: Player 1 slides a knife continuously across the cake, from 0 to 1. For each position 21 of the knife, player is asked for its value of the piece [0, æ1); then each player = 2... iteratively positions its own knife at a point x; [2 with Vz(zz-1. v3) = V0, x1) if possible, and at z; otherwise.
Player n shouts "Stop!" when its own knife reaches the right endpoint of the cake (i.e., In = 1). The cake is allocated in the order 1... with cuts 31 Tnn-1.
Theorem 7.3. There is an RW moving knife protocol that computes a contiguous equitable allocation for every cake culting instance with n hungry players.
This immediately implies a moving knife protocol for computing an allocation that is not only equitable, but also proportional; this be achieved by running Equitable Protocol for every permutation of the players and choosing the one that is proportional.
8 The Stronger and Weaker Models
We also discuss two other query models. The first one, which we call RW+ is stronger in that the inputs to evaluate queries need not be previous cut points and at the end the protocol can use arbitrary points (i.c. not just cuts discovered through queries) to demarcate the final allocation.
Definition 4 (RW+ query model). An RW+ protocol for cake cutling communicates with the players via two types of queries:
CCut((o): Player i cuts the cake at a point y where Ve((0, v)) = o,, for any a E [0, 1).
. .Eval:yy): Player returns Ve(10, vl). for any y E [0.
At the end of execution an RW+ protocol outputs an allocation that can be demarcated by any points of its choice, regardless of whether they have been discovered through queries or not.
The RW+ model differs from the RW model in subtle ways. For instance, in RW there exists a characterization of truthful protocols (i.e. all truthful protocols are dictatorships for = 2 players, with a similar statement for n 2 3 players [19]). similar characterization is not known in the RW+ model. However the RW+ model allows general simulation of moving knife protocols without requiring that valuations are bounded from below. Our constructions for the lower bounds work against this stronger query model.
The lower bounds from the RW model still hold, since our constructions did not use in any crucial way the fact that the evaluate inputs must come from previous cut queries.

---

Corollary 1. Computing an c-envy-free allocation with contiguous pieces among n 3 players, an e-perfect allocation with two cuts between n players, and an e-equitable allocation with contiguous pieces between = 2 players in the RW+ models requires @llog :) queries. Computing contiguous e-envy-free allocation for any fixed number n of players requires (olog }) queries.
In the RW+ model we can simulate moving knife protocols without the requirement that the valuations are bounded from below since the center can reduce (half) the time directly with each iteration, instead of reducing it through the lens of the players' valuations.
Theorem 8.1. Consider a cake cutting problem where the value densities are bounded from above by constant D O. Let M be an RW moving knife protocol with at most r steps, such that M outputs F-fair allocations demarcated by at most constant number C of cuts.
Then for each > O, there is an RW+ protocol Me that uses O (log )) queries and computes e-F-fair partitions demarcated with at most C' cuts.
We also introduce a weaker model, which we call RW- where the protocol can ask the players only the evaluate type of query.
Definition 5 (RW- query model). An RW- protocol for cake cutting communicates with the players via queries of the form
EEval Player returns Vi( vl), where y E [o, 1] is arbitrarily chosen by the center.
At the end an RW- protocol outputs an allocation that can be demarcated by any points.
If the valuations are arbitrary, then an RW- protocol may be unable to find any fair allocation at all. The reason is that no matter what queries an RW protocol asks, one can hide the entire instance in a small interval that has value for all the players; this interval will shrink as more queries are issued, but can be set to remain of non-zero length until the end of execution.
However, the valuations are bounded from above*, then an RW- protocol is quite powerful. Theorem 8.2. Suppose the valuations of the players are bounded from above by a conslant D > 0. Then any RW+ query can be answered within e-error using Olog 2) RW- queriex.
Proof. Let there be an instance with arbitrary valuations 01 ... Un such that (x) < D for all [0. 1] and E N. Since an RW- protocol can use the same type of evaluate queries as an RW+ protocol, the simulation has to handle the case where the incoming query is cut. Let this be Cut, (a) and denote by æ the correct answer to the query. In order to find an approximate answer using only evaluate queries, initialize & = 0, r = 1, and search for the correct answer: (+) Let m r)/r Ask player the query Eval,, and let w be the answer given. |W -a S e, return m. Otherwise, if m > a, set r m. and if m a, set f = m; return to (+). This procedure halves the interval [e, r] with every iteration. Moreover, from the bound on the valuations, an interval of length e/ cannot be worth more than to any player. Thus the search stops in elogge") rounds.
Discussion
An important open question is to obtain stronger lower bounds for n 2 4 players for computing contiguous envy-free allocations and for n 2 3 players for perfect allocations with minimal number of cuts. We conjecture that unlike equitability, which remains logarithmic in 1/c for any number of players, computing contiguous e-envy- allocation for n = 4 players and an e-perfect allocation with minimal cuts for n = 3 players will require ? queries. Since moving knife protocols can be simulated with Olog 1) queries, this would imply that no moving knife protocol exists for computing an envy-free allocation for n 2 4 players or a perfect allocation for n 2 3 players (the existence of such procedures has been posed
open question, e.g. in [12]).
Acknowledgements We thank the reviewers for helpful feedback. This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 Research and Innovation Programme (grant agreement no. 740282). part of this work was done while Simina Brânzei was visiting the Simons Institute for the Theory of Computing.
'There exist other types of valuations on which the HW model may be useful, such as piecewise constant valuations defined grid, with the demarcations between intervals of different height known to the protocol.
10

---

References
[1] R. Alijani, M. Farhadi, M. Ghodsi, M. Seddighin, and A. S. Tajik, Envy-free mechanisms with minimum number of cuts. In AAAI, pages 312-318, 2017.
[2] N. Alon. Splitting necklaces. Advances in Mathematics, 63(3):247-253, 1987.
[3] Noga Alon and Andrei Graur. Efficient splitting of measures and necklaces, 2020.
[4] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi. Approximation algorithms for computing maximin share allocations. In ICALP, pages 39-51, 2015.
[5] A.K Austin. Sharing a cake. The Mathematical Gazette, 66(437):212-215 1982.
[6] H. Aziz and S. Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number agents. In FOCS, pages 416 466,44272200 2016.
[7] J. Barbanel and S. Brams, Cake division with minimal cuts: Envy-free procedures for 3 persons,
4 persons, and beyond. Math. Soc. Sci., 48:251-269, 2004.
[8] Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost envy-free allocations with connected bundles. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California. USA, volume 124 of LIPles, pages 14:1-14:22 Schloss Dagstuhl Leibniz-Zentrrum für Informatik, 2019.
[9] S. Bouveret, K. Cechlárová, E. Elkind, A. Igarashi, and D. Peters. Fair division of a graph. In IJCAI, pages 135-141,
[10] Sylvain Bouveret, Katarína Cochlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of graph. In Proceedings of the 26th International Joint Conference Artificial Intelligence, IJCAP11, page 135-141. AAAI Press, 2017.
[11] S. Brams and A. Taylor. Fair Division: from cake cutting to dispute resolution. Cambridge University Press, 1996.
[12] S. Brams, A. D. Taylor, and W. S. Zwicker. A moving-kinn knife solution to the four-person enve-free cake-division problem. Proceedings of the American Mathematical Society, 125(2):547-554, 1997.
[13] J. Brams, M. A. Jones, and C. Klamler. Proportional pie-cutting. Internat. J. Game Theory, 36(3):353-367, 2008.
[14] J. Brams and A. D. Taylor. An envy-free cake division protocol. Am. Math. Mon, 102(():9-18, 1995.
[15] Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, I edition, 2016.
[16] Brânzei. A note on envy-free cake cutting with polynomial valuations. Information Processing Letters, 115(2):93-95, 2015.
[17] Brânzei, H. Hosseini, and P. B. Miltersen. Characterization and computation of equilibria for indivisible goods. In SAGT, pages 244-255, 2015.
[18] S. Brânzei, Y. Lvv, and R. Mehta. To give or not to give: Fair division for single minded valuations. In IJCAI, pages 123-129. AAAI Press, 2016.
[19] S. Branzei and B. Miltersen. dictatorship theorem for cake cutting. IJCAI, pages 482-488 2015.
[20] Simina Brânzei and Noam Nisan. The query complexity of cake cutting. CoRR, abs/ 010/1/05552.4. 2017.

---

[21] Simina Brånzei and Noam Nisan. Communication complexity of cake cutting, In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings the 2019 ACM Conference on Economics and Computation, ECC 2019, Phoenix, AZ, USA, June 24-28, 2019, page 525, ACM, 2019.
[22] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy,
2011.
[23] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. The efficiency of fair division. Theory of Computing Systems, 50(4):589-614 2012.
[24] K. Cechlarova, Dobos, and Pillarova. On the existence of equitable cake divisions. Inf. Sci., 228:239-22222 245, 2013.
[25] K. Cechlarova and E. Pillarova. On the computability of equitable divisions. Discrete Optimiza- lion, 9:249-257, 2012.
[26] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. little charity guarantees almost onvy-freeness. SIAM J. Comput., 50(4): 1336-1358. 1358, 2021.
[27] Y. Chevaleyre, P. E. Dunne, M. Lemaitre U. Endriss, J. Lang, N. Maudet, J. Padget, S. Phelps, A. Aadrriuuz-AAuilar and P. Sousa. Issues in multiagent resource allocation. Informatica, (30):3-31, 2006.
[28] Guillaume Chèze. Envy-free cake cutting: A polynomial number of queries with high probability. 2020.
[29] R. Cole, Devanur, V. Gkatzelis, Jain, T. Mai, V. Vazirani, and S. Yazdanbod. Convex program duality, fisher markets, and nash social welfare. In EC, pages 459-460, 2017.
[30] S. Dehghani, A. Farhadi, M. T. Hajiaghayi, and H. Yami. Envy-free chore division for an arbitrary number of agents. In SODA, pages 2564-2583, 2018.
[31] Argyrios Deligkas, Aris Filos RaassRaassikss, and Alexandros Hollender. Two's company, three's a crowd: Consensus-halving for a constant number of agents. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 347-368. ACM, 2021.
[32] X. Deng, Q. Qi, and A. Saberi. Algorithmic solutions for envy-free cake cutting. Oper. Res, 60(6):1461-144 2012.
[33] L. Dubins and H. Spanier. How cut a cake fairly. Am. Math. Mon, 68(1):1-11 1961.
[34] Edmonds and K. Pruhs. Cake cutting really is not piece of cake. In SODA, pages 271-278.
2006.
[35] Edith Elkind, Erel Segal-Hales and Warut Suksompong. Mind the gap: Cake cutting with separation. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances Artificial Intelligence, FAAI 2021, Virtual Event, February 2-9, 2021, pages 5330-5338. AAAI Press, 2021.
[36] S. Even and A. Paz. A note on cake cutting. Discrete Applied Mathematics, 7(3):255- - -296. 1984.
[37] Alireza Farhadi and MohammadTaghii Hajiaghayi. the complexity of chore division. In Proceedings of the Twenty-Seventh International Joint Conference Artificial Intelligence, IJCAI-18, pages 226-232, International Joint Conferences on Artificial Intelligence Organiza- tion, 7 2018.
[38] A. Filos-Ratsike and P. Goldberg. Consensus halving is ppa-complete. In STOC, 2018.
[39] Aris Filos-Ratsikas. Kristoffer Arnsfelt Hansen, Kasper Hogh, and Alexandros Hollender. Fixp- membership via convex optimization: Games, cakes, and markets. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 827-838, 2022.
12

---

[40] Aris Filos- Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. consensus-halvingg Does ever get easier? In Proceedings of the 21st ACM Conference on Economics and Computation, EC '2,, page 381-399, New York, NY, USA, 2020. Associa- tion for Computing Machinery.
[41] G. Gamow and M. Stern. Puzzle math. Viking Adult, 1958.
[42] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In NSDI, pages 323-336, 2011.
[43] Paul Goldberg, Alexandros Hollender, and Warut Suksompong. Contiguous cake cutting: Hardness results and approximation algorithms. J. Artif. Intell. Res., 69:109-141, 2020.
[44] Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong. Consensus halving for sets of items. In Xujin Chen, Nikolai Gravin, Martin Hoefer, and Ruta Mehta, editors, Web and Internet Economics 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings, volume 12495 of Lecture Notes in Computer Science, pages 384-397. Springer, 2020.
[45] J. Goldman and A. D. Procaccia. Spliddit: Unleashing fair division algorithms. ACM SIG. Exch, 13(2):41-46, 2014.
[46] Ayumi Igarashi and Frédéric Meunier. Envy-free division of multi-layered cakes. In Michal Feldman, Hu Fu, and Inbal Talgam-Cohen, editors, Web and Internet Economics 17th Inter- national Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings, volume 13112 of Lecture Notes in Computer Science, pages 504-521. Springer, 2021.
[47] Maria Kyropoulou, Josué Ortega, and Erel Segal-Halevi. Fair cake-cutting in practice. Games Econ. Behav., 133:28 49, 2022.
[48] Pasin Manurangsi and Warut Suksompong. Closing gaps in asymptotic fair division. SIAM Journal on Discrete Mathematics, 35(2)666-776, 2021.
[49] H. Moulin. Fair Division and Collective Welfare. The MIT Press, 2003.
[50] J. Neyman. Un theorem d'existence. C. R. Acad. Sci. Paris, 222:843-222 845, 1946.
[51] Hoon Oh, Ariel D. Procaccia, and Warut Suksompong. Fairly allocating many goods with few queries. SIAM Journal on Discrete Mathematics, 35(2):788 813, 2021.
[52] A. Othman, C. Papadimitriou. and A. Rubinstein. The complexity of fairness through equilib- rium. ACM Trans. Econ. Comput., 4(4):20:1 2016.
[53] B. Plaut and T. Roughgarden. Almost envy-freeness with general valuations. In SODA, pages 2584 2603, 2018.
[54] Benjamin Plaut and Tim Roughgarden. Communication complexity of discrete fair division. In Timothy M. Chan, editor, Proceedings of the Thirtieth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2014-2033. SIAM, 2019.
[55] A. D. Procaccia. Thou shalt covet thy neighbor's cake. In IJCAI, pages 239-244, 2009.
[56] A. D. Procaccia. Cake cutting: Not just child's play. Communications of the ACM, 56(7):78-87, 2013.
[57] A. D. Procaccia and J. Wang. A lower bound for equitable cake cutting. In ACM EC, pages 479-495, 2017.
[58] J. M. Robertson and W. A. Webb. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters, 1998.
[59] Erel Segal-Halevi. Fairly dividing cake after some parts were burnt in the oven. In Proceedings of the 17th International Conference on Autoromous Agents and MultiAgent Systems, AAMAS '18, page 1276-1284, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
13

---

[60] Erel Regal-Halev and Balázs Sziklai, Resource-monotonicity monotonicity and eppulation-moootoniiityy in connected cake-cutting, Math. Soc. Sci., 95:19-30, 2018.
[61] W. Simmons. Private communication to michael starbird. 1980.
[62] H. Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948.
[63] W. Stromquist. How to cut cake fairly. Am. Math. Mon, (8):640-644) 1980. Addendum, vol. 88, no. 8 (1981). 613-614.
[64] W. Stromquist. Envy-free cake divisions cannot be found by finite protocols. Electron, Combin., 15, 2008.
[65] F. E. Su. Rental harmony: Sperner's lemma in fair division. Am. Math. Mon, 106:930-942, 1999.
[66] W. Webb. But he got a bigger piece than i did, 1978. preprint, n.d.
[67] D. Weller. Fair division of a measurable space. Journal of Mathematical Economics, 14(5). 1985.
[68] G. J. Woeginger and Sgall. On the complexity of cake cutting. Discrete Optimization. 4:213-220, 2007.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license the code and datasets? [No] proprictary.
The code and the data are
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
14

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "bx2oR4_7Mn4", "reviewer": "Reviewer_X5uM", "summary": "The paper studies various problems in the fair cake cutting area, and advances theoretical state of the art by providing improved lower and upper bounds.\n\nIn particular, three notions of fairness are considered: envy-freeness, proportionality, and equitability (plus the combinations of the three, called \"perfect\"). Because of strong impossibility results, the authors focus on the approximate variants of these fairness concepts.\n\nThey establish a lower bound of $O(\\log 1/\\epsilon)$ for the query complexity of three problems: connected $\\epsilon$-envy-free (for three players), connected $\\epsilon$-equitable and $\\epsilon$-perfect allocation with two cuts (for two players). They also present almost tight upper bounds for the 1st & 3rd problems (the other ones already had an upper bound matching the new lower bound).\n\nWhile essentially nothing was known for $\\epsilon$-envy-free, the other two notions already had _similar_ upper bounds for 3 (as opposed to 2) players, with upper bounds that still are pretty loose.\n\nThey show how a large class of cake-cutting methods can be simulated using Robertson-Webb query model (where an outsider asks players about their preferences until a solution can be proposed).", "questions": "none", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Advances state of the art and closes the gap for certain settings.\n\nWeaknesses:\n- The results and methods seem incremental.\n- Relevance to the community is unclear.\n- No real application discussed, hence no experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aF5b_vMPM5", "reviewer": "Reviewer_KLGZ", "summary": "This paper considers several approximate fairness allocation problems among n players (envy-free, perfect, and equitable), and considers query complexity in the Robertson-Webb model (RW). The authors show lower bounds and upper bounds for approximate envy-free allocation (no player prefers another player's piece to her own) for any number of players. For approximate perfect and equitable allocations, improvements were made to the case n=2 players. To achieve their upper bounds, the authors formalize \"moving-knife protocols\" (MKPs) within the RW model.", "questions": "\nNo questions.", "limitations": "\nYes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S1. Novel theoretical upper and lower bounds obtained for approximate allocation.\n\nS2. For epsilon-envy-free allocation, algorithms are efficient, i.e. O( log 1/epsilon ) for 3 players, O( n / epsilon ) for n players. Also, the upper bound in 3-player case matches the lower bound proven.\n\nS3. It was unknown if MKPs could be formalized within the RW model. The fact that they can is quite interesting, in my opinion. This unifies two seemingly disjoint techniques.\n\nW1. With the exception of approximate envy-free allocation, the method of authors did not improve existing upper or lower bounds for n >= 3 players, only for n = 2.\n\nW2. Lower bound for approximate envy-free allocation is not tight for n >= 4 players.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UOL1VJl2UHF", "reviewer": "Reviewer_XBqt", "summary": "\nThe paper is in two parts\nI) The authors prove new upper and lower bounds in the RW model of cake cutting, which is a model for\ndiscrete protocols. The main operations are CUT and QUERY. In all problems each player has a valuation\nfunction on pieces of cake that may differ quite a lot from the other players. The authors consider\nthree types of cake cutting. In all of them assume that there are n people A1,...,An and that at the\nend Ai gets Pi. They consider three types of outcomes\n\na) epsilon-envy free. For all i, Ai thinks that Pi is \\ge Aj +\\epsilon AND Pi is connected. They show\n\n--- for n=3 there is an upper bound of O(log (1/epsilon) queries and a matching lower bound of\nOmega(1/epsilon) queries.\n\n--- for n\\ge 4 an upper bound of O(n/epsilon) queries and a lower bound of Omega(1/epsilon) queries\n\nb) epsilon-perfect. For all i,j Ai thinks Pj is size 1/n PM epsilon. Assume 2 players only.\n\n-- if the min number of cuts is used then this can be done with O(1/epsilon) queries\n\n-- if 2 cuts are used then this requires Omega(1/epsilon).\n\nc) epsilon-equitable if there is some c such that, for all i, Ai thinks Pi is c PM epsilon.\nFor 3 players AND the pieces are connected, this requires Omega(\\log 1/epsilon).\n\n2) There is another cake cutting paradigm: Moving Knife. This paper introduces a model\nfor MK protocols that captures all current MK protocols. They show that all moving knife\nprotocols can be simulated by O(log(1/epsilon) queries in the RW model. This allows one to easily get\nlower bounds on moving knife protocols. These lower bounds match the upper bounds.\n\n", "questions": "\n1) What does your model of Moving Knife protocols say about the\nnon-approximate moving knife protocols. The  epsilon=0 case.\n\n2) The proofs look correct but I could not tell what the new ideas were. \n\n\n", "limitations": "\nThis paper has no societal impact.\nIt is about a very interesting math problem. \n", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) The envy-free protocols have always had the problem of the pieces being very disconnected.\nThis paper addresses that by looking at epsilon-envy free for which they have protocol\nand lower bounds. For n=3 the upper and lower bounds match.\n\n2) The moving knife protocols have not had a good model or any lower bounds. This paper\nprovides both.\n\nThese results are original, significant, and clear.\n\nWeaknesses:\n1) There seem to be two parameters: number of queries and number of cuts. The paper does\nnot mention the number-of-cuts for many of their algorithms, making me wonder if they are\ngalactic.\n\nThis is unclear.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lq6Ptb_8qx", "reviewer": "Reviewer_NhHm", "summary": "The paper does a nice job expositing and motivating the question of query complexity of \\eps-EF cake cutting. Unfortunately, it seems quite outdated, missing important references from the past ~5 years. (I usually wouldn't be too worried about missing references, but the technical contributions in the paper are not so impressive so I view the main contribution as motivating the questions, but then the context is more important.)\n\nI’m also not sure that this is a good fit for NeurIPS, even interpreting the scope quiet liberally.\n\nUPDATE: Given the authors' responses I went back and re-read the paper. \nI think it's nicer than I had originally assessed and will increase the score. \nHowever, I'm still skeptical about whether this is a great fit for NeurIPS. \n\nAs a minor note, I also realized that the $\\Omega(\\log(1/\\epsilon))$ lower bound only holds against deterministic protocols. \n", "questions": "UPDATE: These questions have been answered by reviewers.\n\nHow does your submission relate to a paper by Brânzei and Nisan (EC’19) on communication complexity of cake cutting?\n\n\nHow does your protocol for 3 agents compare to the protocol by Deng et al for monotone valuations?\n", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "See summary above. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept