On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness
Authors: Arnav Mehra
Alexandros Psomas
Venue: NeurIPS 2025 poster ()
Keywords: fair division
cake cutting
fairness
Primary area: theory

Abstract: We consider the classic cake-cutting problem of producing fair allocations for $n$ agents, in the Robertson–Webb query model. In this model, it is known that: (i) proportional allocations can be computed using $O(n \log n)$ queries, and this is optimal for deterministic protocols; (ii) envy-free allocations (a subset of proportional allocations) can be computed using $O\left( n^{n^{n^{n^{n^{n}}}}} \right)$ queries, and the best known lower bound is $\Omega(n^2)$; (iii) perfect allocations (a subset of envy-free allocations) cannot be computed using a bounded (in $n$) number of queries.

In this work, we introduce two hierarchies of new fairness notions: \newnotioninverse \,(\newnotioninverseabbrev) and \newnotionlinear \,(\newnotionlinearabbrev). An allocation is \newnotioninverseabbrev-$k$ if the allocation is complete and, for any subset of agents $S$ of size at most $k$, every agent $i \in S$ believes the value of all pieces allocated to agents in $S$ to be at least $\frac{1}{n-|S|+1}$, making the union of all pieces allocated to agents not in $S$ at most $\frac{n-|S|}{n-|S|+1}$; for \newnotionlinearabbrev-$k$ allocations, these bounds become $\frac{|S|}{n}$ and $\frac{n-|S|}{n}$, respectively. Intuitively, these notions of fairness ask that, for every agent $i$, the collective value (from the perspective of agent $i$) that a group of agents receives is limited. If the group includes $i$, its value is lower-bounded, and if the group excludes $i$, it is upper-bounded, thus providing the agent some protection against the formation of coalitions.

Our hierarchies bridge the gap between proportionality, envy-freeness, and super envy-freeness.
\newnotioninverseabbrev-$k$ and \newnotionlinearabbrev-$k$ coincide with proportionality for $k=1$. For all $k \leq n$, \newnotioninverseabbrev-$k$ allocations are a superset of envy-free allocations (i.e., easier to find). On the other hand, for $k \in [2, \lceil n/2 \rceil - 1]$, \newnotionlinearabbrev-$k$ allocations are incomparable to envy-free allocations. For $k \geq \lceil n/2 \rceil$, \newnotionlinearabbrev-$k$ allocations are a subset of envy-free allocations (i.e., harder to find), while \newnotionlinearabbrev-$n$ coincides with super envy-freeness: the value of each agent for their piece is at least $1/n$, and their value for the piece allocated to any other agent is at most $1/n$.

 We prove that \newnotioninverseabbrev-$n$ allocations can be computed using $O(n^4)$ queries in the Robertson–Webb model. On the flip side, finding \newnotioninverseabbrev-$2$ (and therefore all \newnotioninverseabbrev-$k$ for $k \geq 2$) allocations requires $\Omega(n^2)$ queries, while \newnotionlinearabbrev-$2$ (and therefore all \newnotionlinearabbrev-$k$ for $k \geq 2$) allocations cannot be computed using a bounded (in $n$) number of queries. 
 Our results reveal that envy-free allocations occupy a curious middle ground, between a computationally impossible notion of fairness, \newnotionlinearabbrev-$\lceil n/2 \rceil$, and a computationally ``easy'' notion, \newnotioninverseabbrev-$n$.

On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness
Arnav Mehra Capital One mehraarn0000gmail. com
Alexandros Psomas Purdue University apsomas@purdue. edu
Abstract
We consider the classic cake-cutting problem of producing fair allocations for n agents, in the Robertson- Webb query model. In this model, is known that: (i) proportional allocations can be computed using (n lo queries, and this is opti- mal for deterministic protocols; (ii) envy-free allocations (a subset of proportional
allocations) can be computed using O nonaa" queries, and the best known
lower bound is ((n²); (iii) perfect allocations (a subset of envy-free allocations) cannot be computed using a bounded (in n) number of queries.
In this work, we introduce two hierarchies of new fairness notions: Harmonically malition-Resistann (HCR) and Linearly Coalition- Coalition-Resistant (LCR). An allocation is HCR-k if the allocation is complete and, for any subset of agents S of size at most every agent
believes the value of all pieces allocated to agents S to be at least [8|+T making the union of all pieces allocated to agents not in S most n-|s| n-|s|+1 for LCR-k allocations, these bounds become |S] and n-|S| respectively. Intuitively, these notions of fairness ask that, for every agent i, the collective value (from the perspective of agent i) that group of agents receives is limited. If the group includes its value is power-bounded, and if the group excludes i, it is upper- boupee,, thus providing the agent some protection against the formation of coalitions.
Our hierarchies bridge the gap between proportionality, envy-freeness, and super envy-freeness. HCR-k and LCR-A: coincide with proportionality for k 1. For all & S n, HCR-k allocations are a superset of envy-free allocations (i.e., casier to find). On the other hand, for A [2, nn/2 1]. LCR-k allocations incomparable to envy-free allocations. For à 2 nn/27. LCR-k allocations are a subset of envy-free allocations (i.e., harder to find), while LCR-n coincides with super envy-freeness: the value of each agent for their piece is at least 1/n, and their value for the piece allocated to any other agent is at most 1/n.
We prove that HCR-n allocations can be computed using O(n²) queries in the Robertson-Webh model. On the flip side, finding HCR-2 (and therefore all HCR-k for l: 2 2) allocations requires ?(n²) queries, while I.C--2 (and therefore all LCR-k for & 2 2) allocations cannot be computed using a bounded (in n) number of queries. Our results reveal that envy-free allocations occupy curious middle ground, between computationally impossible notion of fairness, LCR- [n//2] and a computationally "easy" notion, HCR-n.
Introduction
We consider the classic problem of cake cutting, proposed by Hugo Steinhaus [Ste48], while in hiding during World War II [Wik25]. In this problem, there is heterogeneous resource, the "cake,"
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

typically represented by the interval [0, 1]. There is a set N of n agents with different valuations functions Vi.... Vn, over subsets of the cake; these valuations functions are induced by probability measures over [0. 1] (and hence, for example, the value of every agent for the entire cake is equal to 1). The goal in this problem is to allocate to each agent piece of the cake -a a finite union of disjoint intervals - in a fair manner, under various notions of fairness. This simple model has served as a cornerstone for fair division, shaping many of the field's foundational questions.
A major focus has been the complexity of computing fair allocations. The complexity of discrete cake-cutting protocols is measured by the number of queries they require in the query model suggested by Robertson and Webb [RW98] and later formalized (and named) by Woeginger and Sgall [WS07]. For example. it is well understood that proportional allocations, those where every agent E N values their piece at least 1/n, can be computed using On log n.) queries [EP84]; and, this is tight: every deterministic protocol requires Si(n log n) queries [EP11], I]. Another major notion of fairness is equitability, which requires that every agent has the same value for the piece allocated to them, i.e. for all agents j E N, (A)) = (A,) (where Ag the piece allocated to agent E). Procaccia and Wang [PW17] proved that equitable allocations cannot be computed in bounded (in n) number of queries. This result, in turn, rules out bounded protocols for another major notion of fairness, perfection: an allocation A is perfect if for all agents j E N, V:(A,) = 1/n.'
Arguably the most important notion of fairness - the holy grail of fair division - is envy-freensss; an allocation A is envy- free if every agent prefers their piece to the piece allocated to any other agent, i.c., for all agents i E N. (A(),) 2 V.(A,), ). is easy to see that every perfect allocation is envy-free, and every envy-free and complete (U:A; = [0. 1) allocation is proportional. Unlike proportionality, equitability, and perfection, the complexity of computing (complete) envy-free allocations has been rather elusive. The existence of bounded protocols remained open for two decades until Aziz and
Mackenzie [AM]6a] presented a protocol that requires at most an queries. The best known lower bound is ((x²) [Pro09], leaving an astronomical gap in our understanding.
In this paper. we zoom in on the landscape of fairness between proportionality and perfection, focusing on the query complexity of different notions in this less understood intermediate space.
1.1 Our contributions
We introduce two new hierarchies of fairness: Harmonically Coalition-Resistann (HCR) and Linearly Doalition-Resistaann (LCR). An allocation A satisties HCR-k if, for every subset of agents S such that |S] S ks and for every agent E S. the value of for the union of pieces allocated to agents not in S is n-|s|
at most -1|s| R-1s|+T.144 i.e., Ejes Vi(A,) = V((ANss) S R- +I- Equivalently, Vi(As) Z n- For
LCR-K, the upper bound is S= and the lower bound is [s] The existence of HCR-k allocations implied by the existence of envy-free allocations. Let be an envy-free allocation; for all agents
i,j E N, ((A)) I V.(A,). Adding up for all j & S gives Ejes Vi(A,) S (n (A.) S (n - (S)( E V.(A))); re- re-arranging gives the desired inequality. The existence of LCR-k allocations is similarly implied by the existence of perfect allocations.
Our new faimess notions are interesting precisely because they occupy a natural but largely unexplored middle ground between proportionality and envy-freeness. HCR-k allocations limit how much value groups of agents collectively derive from other agents' shares; thus, they may be particularly suited for contexts where collective perceptions of faimess are important. LCR-k allocations impose stronger conditions, which makes them appealing when perfection is desired (where the computational cost is prohibitive/unboundedd) By providing a spectrum of fairness guarantees, these notions offer more nuanced toolkit, enabling practitioners to better navigate the trade-off between computational complexity and fairness requirements.
In Appendix A we start by showing how our new notions relate to the existing notions of fairness; we focus on complete allocations (as, otherwise, envy-freeness is the casiest notion, since it is satisfied by an empty allocation). We show that the entire HCR-k hierarchy lies between proportionality and envy-freeness, with HCR-1 being proportionality, but HCR-n being a strict superset of envy-freeness. On the other hand, the entire LCR-k k hierarchy lies between proportionality and perfection, with LCR-1 also being proportionality, while LCR-n is equivalent to super env--freeness. An allocation
Whicc,, perhaps surprisingly, always exist [Lia40, Alo87J!

---

O
HCR-2
HCR-n
[+)
[AMI6a]
12 [+]
PROP-
SUPER-EB EF
HCR-1
EF
LCR- [ +
<LCR- - 2) +
LCR(n 1)
LCR-1
Unbounded [+:
LCR-n
LCR-2
LCCR 1)
(n log n [EP84, EPII]
Figure 1: Relation hetween our new notions of fairness, Proportionality (PROP), Envy-Freeness (EF), and Super Envy-Freeness (SUPER-EF), A solid arrow from Y X represents that notion Y implies notion X, i.c. X < Y means X 2 Y. X + Y implies that finding an allocation with property Y is harder task. Our results, highlighted in colored rectangles, are marked with [*].
A is super envy-free if, for all agents i,j E N, V((A) 2 1/n 2 va(A)). Regarding LCR-k and envy-freenent for 2 < k < [ 1, LCR-k is incomparable envy-freeness; for k: > [3] LCR-k implies envy-freeness. See Figure 1.
We proceed to study the complexity of computing our new notions in the Robertson- Webb model. In Section 3 we prove our main upper bound, Theorem I: there exists a protocol that computes complete, HCR-n allocations, using at most (n=²) queries in the Robertson- Weebb model. The first key observation is that, a complete, proportional and "near-perfect" allocation = (A1,... An) satisfies all the constraints required by HCR-n; concretely, completeness, along with Vi,), " and Vi(A,) 2T for all j, implies HCR-n. Therefore, it is natural to start with e-perfect allocation which can be computed using only (n²² /e) queries [BM15]- - and try adjust it to satisfy the additional proportionality property. An obstacle in this approach is that, for any e >> 0, it might be the 1. for all j A making it impossible
1
case that the e-perfect allocation such that V4(4, n proportionality for i, unless we trim other agents' pieces. This obstacle can be bypassed with the following trick: introduce l phantom agents, with arbitrary valuation functions, and find an e-perfect partition for the instance with n + agents. Then, the "real" agents get almost equal allocations, no one gets a piece whose value is larger than n. and the allocations of the phantom agents can be combined into a new piece. the residue, to be allocated among the real agents, using, e.g., a clever recursion. However, intuitively, such a step forces us to find an allocation of the residue that is weighted proportional, where agents have different weights (or, equivalently, find an allocation such that agents' utilities meet specific utility lower bounds). Unfortunately, this leads us to dead-end: there is no bounded protocol for finding a proportional division with unequal shares [CF20]. The final piece of this puzzle is that pieces returned by the e-perfect call do not need to be matched to specific "real" agents, but should be available for anyone to claim.
satisfy
In more detail, our algorithm, Algorithm 1, starts by finding an c-perfect allocation for 4n/3 agents, where the n/3 extra agents, agents n + 1...., 4n/3 /3, have arbitrary valuation functions. Let Bi...., B,, be the first n pieces of this allocations: pieces Ba+1,.... Ban/3 are combined into the residue Rt. Importantly, "real" agents are not allocated any of the B, pieces (yet). Algorithm I then proceeds Dubins-Spanier [DS61] ] (or Last Diminisher [Ste48]). Let S be the subset of the B₁ pieces still available. The algorithm asks every agent to make mark on R, such that their value to the left of the mark is equal to 1/n max (B). The agent i* with the left-most mark (breaking ties arbitrarily) gets the two corresponding pieces, one from cutting the residue and their favorite piece from S, and exits the process. The process is repeated until a single agent j is left, who is allocated the entire remaining residue, and the unique piece left in S. We prove that Algorithm I computes HCR-n n allocation using O(n²) queries. Importantly, our query complexity bound relies on the fact that the algorithm of Brânzei and Miltersen [BM15] for finding e-perfect allocation produces most (n²)) intervals.
In Appendix B we prove our main lower bounds. First, we prove that computing a HCR-2 allocation requires 2(n²) queries (Theorem 6), while computing LCR-2 allocation impossible using a bounded protocol (Theorem 7). To prove our first lower bound, Theorem 6, we first formalize the
3

---

amount of knowledge an algorithm can have about an agent i after t queries. We use the notion of active intervals. Intuitively. if an interval I is active for agent at step t, denoted by IT, then VI(T) is known to the algorithm, but for all I' Ç 7, an adversary can pick (?") to be anything from 0 to VT( That is, all these choices for Vi( are consistent with the query responses up until time t. This definition was also at the core of the 22n2²) lower bound for envy-freeness, by Procaccia [Pro09]. Here, we argue that, if the adversary responds to queries as if the valuation functions are uniform for the entirety of an algorithm's 's execution, the allocation A (AI,..., A.) that the algorithm outputs must be such that A, E 11." and Vi(A.) = 4. for all i E NN where T is the number of queries the algorithm made before terminating. For LCR-2 to be satisfied, Vi(A,) = 1 implies a condition on (A)),, that similarly needs to be "checked" (i.e., I E II,, for some I C A,) for all pairs of agents i.j E N; the (2n²) lower bound follows. Our second lower bound, Theorem 7, reduces the problem of finding an LCC-2 allocation to a known problem with unbounded query complexity: the problem of finding an exact division. In the exact division problem, we are given target values wi..... 22, and are asked to split the cake into 2 picces, so that every agent has value wy for piece E. for f= 1,
2. Exact division is known to be impossible to solve with a bounded protocol, even pieces with equal weights [RW98]. Theorem 7
for the case of two valuation functions and immediately implies that the problem of finding super-envy free allocation has unbounded query complexity the Robertson- Webb model, which, to the best of our knowledge, was an open problem.
Finally, in Section 4, in light of the strong lower bounds for LCR-2, we consider approximations.
The minimally weaker notion that we could hope to achieve is the following: (i) if |||
then Vi(Ag) S n-1, for all i E S (i.e., the allocation is proportional), (2) if | = 2, then vi(Ag) I (1 +1,, 8). for all i E S. We show that this notion is possible to achieve with a bounded protocol. More generally, we define 5-LCR-k to be the set of complete and proportional allocations,
such that if k 2 |S| 2 2, then V.(As) < n=|s| (1 + 5); we prove that the query complexity of
computing 6-LCR-n allocation is O (n_ ( To prove this result, we give an algorithm
for finding complete, proportional. and e-perfect allocations using O
( (n" Im(I/c) queries, which "I[m]]
might be of independent interest. The high-level blueprint of this algorithm, Algorithm 2, is similar to Algorithm I: in phase one split the cake into approximately equal pieces and residue, and in phase two run a "cut-and- match Last Diminisher." " Algorithm 2 requires much stricter conditions from the pieces and residue the end of phase one. As opposed to Algorithm 1, phase one in Algorithm 2 is implemented via a recursion: at each iteration the residue is split into an (n + 1)-piece e' e'ppeffct allocation. Out of these + 1 pieces, one of them serves as the residue in the next iteration. The first n pieces are carefully matched to previously computed pieces. This process is done d times in total, where d and c' need to be carefully chosen that the value of every agent for every "combined" piece (across iterations) is within the required bounds.
Our results provide significant insight into the spectrum of fairness notions between proportionality and super envy-freeness; see Figure 1. We observe that the two ways of strengthening proportionality, HCR-2 and LCR-2, lead to strikingly different lower bounds the corresponding query complexity. Envy-freeness occupies a curious middle ground. The minimally weaker fairness notion, HCR-n, can be solved in Onn²) queries, while the minimally stronger fairness notion, LCR- (CR- 1. has unbounded query complexity. A concrete take-home message of our work regarding the query complexity of finding envy-free allocations is that, if a super polynomial lower bound exists, then there must exist a subproblem strictly harder than finding HCR-n allocations which requires a super number of queries to solve.
super polynomial
1.2 Related work
As already discussed, proportional allocations can be computed using Onn log n) queries [EP84], and this is tight for deterministic protocols [EP11]. Randomized algorithms can bypass this lower bound [EP06]. Surprisingly, finding a (weighted) proportional allocation when agents have unequal shares requires an unbounded number of queries [CF20].
Regarding envy-freeness, the cut-and-choose method gives an envy-free allocation for n = 2 agents, and the Selfridge-Conwee procedure gives an envy-free allocation for = 3 agents. The problem of finding an envy-free allocation for four agents, using a bounded number of queries, was resolved by [AM]6b], and later improved by [ACF+ 18). For n agents, the best known protocol requires
4

---

Onnnaann queries, while the currently best known lower bound is 22(2²) [Pro09]. Equitable alloca- tions, and therefore perfect allocations, cannot be found in a bounded number of queries IPW17].
Approximate solutions typically easier find. Brânzei and Miltersen [BM15] prove that finding an e-perfect allocation requires at most O(n*/e) queries, and Brânzei and Nisan [BN22] prove that finding an e-envy free and connected allocation requires at most (nz/e) queries (and least (llo((//e) queries. Cechlárová and Pillárová [CP12] prove that finding an e-cquitable and propor- tional allocation requires most (nog n + log(1/c)) queries.
Segal- -egeli and Suksompong [SHS20, SHS23] and Segal-Halevi and Nitzan [SHN19] study cake cutting among groups. Specifically, Segal- and Suksompong [SHS20, SHS23] study contiguous and envy-free cake cutting among groups (where agents within a group also get a contiguous piece). Segal-Halevi and Nitzan [SHN19] study a problem where cake must be divided and allocated to (pre-determined) groups of agents, and study the existence and query complexity of various fairness notions in this model. For example, in their unanimous FS allocations the n agents are placed in groups, K, of size n/k, and for any group S K and any agent i S it must hold that Vi(As) 2 & This condition is quite similar to LCR-k; however, it is considerably less restrictive, as it places no constraints subsets of size less than k different groupings of the agents (LCR-k considers all possible groupings of size at most k). Segal-Halevi and Nitzan [SHN19] prove that unanimous-F'S allocations require infinite queries; yet little is known about how close one can get with bounded number of queries. Our algorithms provide allocations as close to LCR-k as possible, with a bounded number of queries.
Berliant et al. [BTD92], and later Husseinov [Hus I IJ. study a notion of group fairness, group envy- freeness, where, similar to our work, the subsets are not predefined. However, their definition only considers groups of equal size: they call an allocation A = (Ai,..., AA) group envy-free, if for every pair of groups of agents C1 and C2, with |C1| = |C2| there is no partition { [B, Bi,e, of Ujec, such that, for all E C1, é prefers B, to A,, with strict preference for at least one i E C₁. This notion is stronger ("harder achieve"") than perfection; the focus of the aforementioned works is existence of such allocations, and compatibility with economic efficiency.
Further afield, numerous papers study fair allocation of indivisible items among groups of agents [CFSV19, FT22, CLS25, MS22, STZ23, KSV20, AR21J.
2 Preliminaries
We have an infinitely divisible resource, the "cake," denoted by the interval [0. 1]. A piece of cake refers to finite set of disjoint intervals of [o. 1]. Our goal is to allocate the cake among set N of n agents. An allocation A = (A1...., An) of the cake to the agents consists of n pieces, where A, is the piece allocated to agent i, such that A, n A = @ for all pairs of agents i. An allocation A is complete if U
[0, 1]. For allocation A and subset of agents S C N, we will use notation As = S to denote the union of all pieces allocated to the agents in S. We also use notation S = N W for the complement of a set S.
Every agent E N has valuation function V; that assigns a non non-negative value to any subinterval of [0, 1j. It is convenient to think of these values as being induced by density function Uy. That is, for an interval
(a, b), VI(T) - (x))dx.. Valuations are (i) normalized: V.( 1) =
f ve(r)dee 1, (ii) additive: for set of disjoint intervals II,...; ; Im. Vi(UnL [1) =ド Vi(Ts).
(iii) non-atomic: Vx, y E [0, 1], X E [0, 1], 3z [xr v] where Vi([,, z]) X Vi(lE, v.).
2.1 Robertson-Webb Model
We study the complexity of cake-cutting algorithms in the model suggested by Robertson and Webb [RW98] and later formalized (and named) by Woeginger and Sgall [WS07]. This model allows for two types of queries:
1. (V)L;(T): Given an agent and an interval I C [0, 1J. this query returns Vi(T).
2. CUT, v): Given an agent i, point x E [0, 1). and a value E [0, 1). this query returns the smallest point x' e [z, such that Vi[[z, x²)) v.
5

---

To the best of our knowledge, every discrete cake-cutting algorithm can be (and has been) analyzed in this model. As a simple example, the cut-and-choone choose algorithm can be implemented by two queries as follows. First, a CUT, (0, 1/2) will return the point y such that (i{(0, vl) (V 1J) = 1/2. The algorithm can determine whether [0, y] or [v. 1] should be allocated to agent 1, by making a 2 y)) and checking whether the value returned is at most 1/2.
2.2 Fairness notions
Our goal is to produce allocations that are fair. An allocation A is proportional if V, 2 1/n for all E N. An allocation <-perfect if for all i,j E N. 1/n + e 2 Vi(A,) 2 1/n - c; an allocation A is perfect if is O-perfect. Finally, an allocation, A, super envy-free if every agent values their own piece at least 1/n, and values any other agent's piece at most 1/nn, i.e., V:(A:) 2 2 V((A)), for all i, E N.
envy-free if for all i.j E N. V.(A.) 2 V.(A,). An allocation is
We write PROP, EF, SUPER-EF, and PERF for the set of all complete proportional, envy-free, super envy-free, and perfect allocations, respectively. For complete allocation, every perfect allocation super envy-free, every super envy-free allocation is envy-free, and every envy-free allocation is proportional, and there exist perfect allocations that are not super envy-free, super envy-free allocations that are not envy-frree as well as envy-free allocations that are not proportional; that is, PROP 2 EF 2 SUPER- EF 2 PERF.
In this paper, we define the following new notions of fairess.
Definition 1 (Harmonically Coalition-Resistaann (HCR-k)). Let i be integer, such that n 2 k 2 1. An allocation is Harmonically
-iaiition--Rsssaant--k- (HCR-k) it is complete and, for every non-empty subset of agents S C N such that [S] k, and every i S, Vi(As) - Ejes Vi(A,) S
n-1S1 [S]
It is easy to see that the definition of Harmonically of proportionality. Slightly overloading notation, write HCR-k for the set of all complete Harmonically Daaiition-Reiistante A: allocations.
coincides with the definition
Definition 2 (Linearly
Resistantn--sstttt--kk (LCR-E)) Let i be an integer, such that n 2 k: 2 1. An allocation A is Linearly Resistttn--Rstttt---k-k (LCR-k) if it is complete, for every non-empty
subset of agents S C N such that |S| S k, and every i E S, Vi(As) = Eees Vi(A,) S n-|s|
Slightly overloading notation, again, we write LCR-k for the set of all complete Linearly Coalition- Resistant-k: allocations. Notice that every Linearly Sealition-Resistanmt allocation is Harmonically
since n-
1-18 --
for all [S| 1.
3 An Algorithm for HCR-n
In this section, we prove our main upper bound: HCR-n allocations can be computed using ((n.) queries in the Robertson- Webb model.
Theorem 1. Algorithm computes HCR-n allocation using O(n') CUT and EVAL queries.
Proof. We first prove that every complete and proportional allocation A such that Vi(A,) 2 2n
1 for
all agents j. satisfies HCR-n. Towards this, consider such an allocation A, and an arbitrary subset of agents S C NN and i S. (A())) 1 (A() <
S1
2n [ -1
as long as |S| < n 1. For |S| = n, V.(Ag) = 0 < n- S|+1 Therefore, A E HCR-n.
It remains to prove that Algorithm 1 finds an allocation with these properties (completeness, propor- tionality, and Vi(A,) 2 +) using O(n²) CUT and EVAL queries.
Algorithm first computes - -erffect allocation B for 4n/3 agents, where the n//3 extra agents, agents n + 1,..., 4n/3,, have arbitrary valuation functions. Let Bı...., B2 be the first n pieces of this allocations; pieces B Ban/3 are combined into the residue R. i.e., R = / By- Importantly, "real" agents not allocated any of the By pieces (yet).

---

ALGORITHM 1: An algorithm for finding HCR-n allocations
Let V+ nttl..., Van/3 be n/3 arbitrary valuation functions.
2 B + L. -PEERFECTVV Va Vit V=t1...., Vin.s) Find an e- E-PERFECT allocation with the
In
extra agents
3 R 1/1/3 Bj-
b The pieces of the additional agents becomes the residue
4 M + (I....,n) n).
P Initialize the set of active agents.
for X E (BI..... 1 } do
Ask every agent i E M to make a mark on R such that the piece to the left of the mark has value 1/n (X).
7
Let E . be the agent with the left-most mark on R (breaking ties arbitrarily).
Let Rτ- be the part of R the left of is mark.
A;- < RG- X.
D Allocate to agent i" Update the residue > Remove i"'s piece from S and i" from M
R R Rg.. M + M (r).
11
12 end
For the remaining agent i E M, A; + Bn U.
14 return
Algorithm then proceeds à la Dubins-Spanier [/S6]]/Last Diminisher [Ste48]. Let S the subset of the B, pieces still available. The algorithm asks every agent i to make mark on Rt, such that their value to the left of the mark is equal to 1/n max (B). The agent 1" with the left-most mark (breaking ties arbitrarily) gets the two corresponding pieces (one from cutting the residue and their favorite piece from S), and exits the process; we denote their final allocation by A.- = A/. U Rg where A is their favorite piece in S, and (slightly overloading notation) R,, is the part of the residue allocated to them. The process is repeated until a single agent j is left, who is allocated the entire remaining residue, and the unique piece left in S.
Query complexity. Using the algorithm of Brânzei and Miltersen [BM15] for finding e-perfect allocation, computing (B, R) costs O((4n/3) /3)//(1/42)) = O(n*) queries. This protocol produces most (n²) intervals, and therefore, at most O(n²) EVAL queries are necessary for every agent to compute the value of every interval. When the value of each interval is known, any query across any set of these intervals, which we refer to as a super-query, will require at most 2 queries (see proof below). Applying this, the "Last Diminisher" steps (the while loop in Algorithm 1) will cost another Onn²) queries. Marking piece of value n Vz(S,) on R for single agent requires super-query. So, (nn²) super-queries, O(n²) actual queries are required for this step. Therefore, the overall complexity is Onn))
Claim 1. Let I be collection of noncontiguous intervals. If Vi(zg) is known for all i E N, I, then any super-query over any subset of intervals of will require at most 2 "real" queries.
Proof. Consider the super-query (VAI)([ where x1 7 and 22 E I' for some intervals I E I. If T = I", xi and x2 belong to the same interval, meaning only actual query is required. I + I', then EVAL;([F1,
- / "hetwenn" 1. VI(I). Now consider the super-query CUT, #1) where 21 E I for some interval I I. This requires at most 2 queries: First, perform the true query EVAL, (ngmu)). Then, using this evaluation along with those of the intervals to the right of / to determine the interval I' the mark 22 will be placed and the value 122 = Vi(21, I that should be to the left of 22 in 7'. Finally, only one actual query required to determine the cut 22, 22- = CUT, ). Thus, given each agent's 's evaluation of each noncontiguous interval, any super-query requires most 2 actual queries.
EVAL, +EVAL
Correctness of Algorithm 1. All allocations are complete, by construction. First, we prove that each allocation is proportional, i.e., Vi(A,) V.(A,) 2 1/n, which simply means that each iteration, all remaining agents in M will be able to mark out piece of value 7. Consider some iteration i. Assuming that previous iterations were completed successfully, each agent in M did not have the left-most mark in R, VA(A < 1 for all i M,j E NYM Let B, be the piece arbitrarily chosen to
7

---

create an allocation in iteration t. V,(R) + V((,)) = =1 -11EjENAA EJENAM Vi(Ag)
EB,ES,B -(B Vi(B))
1 ا_ 2=1 L. Thus, this iteration, all agents will be able to place mark on the residue. Starting with the trivial case of t = and inductively applying this logic shows that enough of R will remain for each agent remaining in M to place such a mark.
Regarding the second condition, Vi(A,) 2 1. for all agents i. we have the following. By the fact that B is IV -perfect for the instance with 4n/3 agents: V.(B,) In/3 In 2n Observing that Vi(A,) = - + V2, 2 Vi(44), and A' is one the Bg pieces, completes the proof.
2n
4 Algorithms for Relaxations of LCR-n
In this section, study approximations of LCR-k, aiming bypass the strong lower bounds of Theorem 7. Since LCR-2 is impossible, but LCR-1 (aka, proportionality) is easy to achieve, the minimally weaker notion that we could hope achieve the following: (i) if |S| = then v.(As) S 1-1 for all i E S (i.e., the allocation is proportional), (ii) if |S| = 2, then V:(As) S 2 (1 + 8), for all E S. More generally, we have
Definition 3 (6-LCR-k).. Let & be an integer, such that n 2 k 2 1. An allocation A is ö-Linearly CaliitionRessisaant-e (LCR-k) if is proportional, and, for every non-empty subset of agents S S N such that 2 < |S| < k; and every i E S. (1()s) = Ejes Vi(A,) < -= (1 + 6).
We prove that 6-LCR n allocations can be computed efficiently, by expanding on our approach for HCR-n, i.e., Algorithm 1. First, is easy A is (en)-L.CR-1 for all S C N such that 2 < [S]. and E S, (A()s) S (n -(S)) ( +c)
that complete, e-perfect, and proportional allocation
R- (1 + en). We give an algorithm, Algorithm 2, for finding a complete, e-perfect, and exactly
proportional allocation that requires O [ -i((//)) queries, which might be on independent interest.
Im(a)) (TT((a)
To the best of our knowledge, the closest results in the literature are: (i) algorithm that finds proportional and e-equitable allocations using On n + log(1/c)) queries, by Cechlárová and Pillárová [CP12], and (ii) the O(n /c) algorithm of Brånzei and Miltersen [BM15] for finding perfect allocations. Algorithm 2 immediately implies that the query complexity of finding a 5-LCR-n Iu(1/5) allocation is O In(m)
[n(1/e) and e' E 0 (,5), such that Algorithm 2, with In(n)
Theorem 2. For all e > 0, there exists d E +
parameters d and e', computes complete, e-perfect, and proportional allocation using O ( nn In(1/e) In[n]]
CUT and EVAL queries.
Algorithm 2 differs from Algorithm in its computation of S and the residue R prior to the final "Last Diminisher" phase (i.e. line 5 in Algorithm 1, line 11 in Algorithm ). In Algorithm 1, the goal was for each piece of S to have value at least L but most x goal is similar, but quite harder. Each piece of must have value at least 1 ē but most for any n
& for any agent. In Algorithm 2, the
2n
agent, for ē = ; as we show, this will suffice for e-perfection.
To achieve this Algorithm 2 computes S and R recursively. Starting with the entire cake, it computes an (n + 1) pieee é' c'-perfect allocation, designating a single piece of the allocation as R and the remaining n pieces S. Then it repeats this process, treating the residue R itself as entire cake, designating a piece of the new allocation as the new residue, and combining each of the remaining n pieces with distinct piece in S. This process is done d times in total, with the goal that the expected value of each piece of S (for any agent) is spaced enough between 1 ē and 1. This allows us to choose a non-zero that keeps the potential values of each piece in S for any agent within a desired range. In short, if the number of subdivisions d and the margin of error for near-perfect divisions e' are chosen correctly, then غ < V,(B,) < _ for all i,j E N.
Proof of Theorem 2. In Appendix C, we show that if the parameters e' and d are picked correctly, Algorithm 2 outputs an allocation where V((A,) 2 1. V,(A,) 2 1 ē, Vi,j E N for any > 0. By picking غ = s, our allocations are e-perfect (in addition to proportional and complete). To see this, notice that (i) vi(A,) 2 - _-__ 2 - and (ii) Vi(A,) < 1- (n - 1) (1 -)
8

---

ALGORITHM 2: An algorithm for finding complete, e-perfect, and exactly proportional alloca-
tions
Input: Parameters e' and d.
Let V+ be an arbitrary valuation function.
Let B be set of n empty pieces. R. {[0, 1}}
Initialize the residue as the entire cake
3 for t E {l....,d dd do
P C'PPERFECT
Vu, V+) with respect to, and normalized on, R.
R Pn+1
for
i E [1,
n.
B: + B.U.P
Assign the other pieces in B to a piece in S
end
end
10
M +- (I...., for
X E ..., Bn- do
Ask every agent E M make mark on R such that the piece to the left of the mark has value 1/n - (X()). Let E M be the agent with the left-most mark on R (breaking ties arbitrarily).
13
14
Let RG- the part of the left of i*'s mark.
A.. RG- U.X
Allocate to agent i" > Update the residue > Remove i"'s piece from S and i* from M
16
R + R Rs.. M + M }
18 end
19 For the remaining agent E M, A; + Bn U.
return A
+ -
1- (n - () satisfies the desired property, and has query complexity O [n(1/8) In(n)
+ In the remainder of the proof, prove that Algorithm
Query Complexity. We claim that the algorithm requires at most O
In(1/2) In(xe)
to compute an
allocation such that Vi(A.) > 1. and Vi(A,) > 1 è. The algorithm involves (i) computing d (n + 1)-peece é' d'-perfect allocations and (ii) performing "cut-and-match Last Diminisher." Brânzei
and Miltersen give protocol for finding e-perfect allocations that uses O (n") queries [BM15], and it is well-known that traditional "Last Diminisher" requires O(n²) queries. However, it is premature to conclude that this would require O
.d queries. Many of these "queries" are performed over collection of noncontiguous intervals, rather than contiguous cake, i.e, they are super-queries. To account for this, similar to our analysis of Algorithm 1, we maintain each agent's valuation of each interval, so that each super-query requires at most 2 actual queries. This is shown as Claim in Algorithm 1; an identical argument works here as well.
n d + O E
n² T
Next, show that if we tracked each agent's evaluation of each noncontiguous interval, then the algorithm would still require just O -- d) (actual) queries. Prior to computing each e'-perfect allocation, we must normalize each agent's valuation function over R. While we do not have access to valuation functions, this can be achieved by scaling the output of an EVAL super-query by V.(R)* or scaling the input value CUT super-query by Vi(R). Fortunately, since R is set of intervals whose values are assumed to be known, this requires no additional queries. Thus, computing all
c'pperfect allocations (with (n + 1)-pieces each) requires O d) (actual) queries. As for performing "cut-and-maach Last Diminisher". at worst, agent will perform EVAL super-queries on every piece in 5 and n CUT super-queries on R. Applying our prior result again, this translates to only O(n?) actual queries in total (which dominated by O d)).
Finally, we show that tracking each agent's evaluation of each noncontiguous interval requires On d) queries (which also dominated by O d). The e-perfect algorithm by Brânzei and

---

Miltersen [BM15] produces allocations with (n²)) cuts (thus introducing On noncontiguous intervals). To incorporate each new cut on an existing interval I (thus creating intervals 1 = [een, æ] and 2 = [x, Light) for an agent i, we perform 1 query EV)) to determine the values of the new intervals created (V1(22) is deduced from Vi(I) - V((+))). Thus, introducing cut (and by extension noncontiguous interval) only requires (nn) true queries to keep our noncontiguous interval evaluations up-to-date, To account for the scaling performed in iterations performed on the residue, no additional queries are necessary as the scaling factor can be computed using the value of the residue (which is comprised of intervals of known valuations). Since our d c' c'pperfect allocations introduce On d) cuts and our "cut-and-match Last Diminisher" introduces (n) cuts (one for each of the first O(n d) + (m)) E O(n² d) queries in total.
1 pieces allocated), tracking the desired information requires
Putting these pieces together, we can conclude that Algorithm computes complete and proportional allocations, where Vi(A,) 2 + ē for all i, E N, using 0 nn (= = =0
In(1/E)
queries in
[n(m]
total (and therefore a complete, proportional and e-perfect allocation using O n In(1/el queries). Tn(m)
Correctness. From our earlier discussion on query complexity and choice of parameters d and e', we have that the first phase of the algorithm (lines I to 10) end with n pieces, Bi,.... Ba, such that 1. ē S (B,) S 1, as well as a residue. Since the final allocation of every agent j a superset of some piece Bj, we have that V:(A,) 2 V:(B,) 2 can apply the same logic as done for Algorithm to conclude that, for all i E N, Vi(A,) 2 after the "cut-and-match Last Diminisher" stage. Thus, by Theorem 2 we conclude the final allocation A to be 6-LCR-n.
Following this stage of the algorithm, we
Acknowledgements
The authors would like to thank Yorgos Amanatidis, Yorgos Christodoulou, John Fearnley and Vangelis Markakis for their input in the initial development of this project. The authors would also like to thank Ariel Procaccia for the valuable discussions and suggestions. Alexandros Psomas is supported in part by an NSF CAREER award CCF-2144208, and a research award from the Herbert Simon Family Foundation.
References
(ACF+18) Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Aleistos-Alexaddross Psomas, and Eftychia Vakaliou. An improved envy-free cake cutting protocol for four agents. In Algorithmic Game Theory: 11th International Sympo- sium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings 11, pages 87-99. Springer, 2018
[Alo87] Noga Alon. Splitting necklaces. Advances in Mathemaics, 63(3):247-253, 1987.
[AM16a] Haris Aziz and Simon Mackenzie, A discrete and bounded envy-free cake cutting protocol for any number of agents. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 416-427. IEEE, 2016.
[AM16b] Haris Aziz and Simon Mackenzie. discrete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 454 464, 2016.
[AR21] Haris Aziz and Simon Rey. Almost group envy-free allocation of indivisible goods and chores. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 39 45, 2021.
[BM15] Simina Brånzei and Peter Bro Miltersen. A dictatorship theorem for cake cutting. In Twenty-fourth international joint conference on artificial intelligence. Citeseer, 2015.
[BN22] Simina Brânzei and Noam Nisan. The query complexity of cake cutting. Advances in Neural Information Processing Systems, 35:37905-37919 2022.
10

---

[BTD92] Marcus Berliant, William Thomson, and Karl Dunz. On the fair division of a heteroge- neous commodity. Journal of Mathematical Economics, 21(3):0012266 1992.
[CF20] Ágnes Cseh and Tamás Fleiner. The complexity of cake cutting with unequal shares. ACM Transactions on Algorithms (TALG), 16(3):1-21, 2020.
[CFSV19] Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan. Group fairness for the allocation of indivisible goods. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1853-1860, 2019.
[CLS25] Ioannis Caragiannis, Kasper Green Larsen, and Sudarshan Shyam. A new lower bound for multi-color discrepancy with applications to fair division. arXiv preprint arXiv:2502.10516, 2025.
[CP12] Katarína Cechlárová and Eva Pillárová. On the computability of equitable divisions. Discrete Optimization, 9(4):249 257, 2012.
[DS61] Lester E Dubins and Edwin H Spanier. How eut cake fairly. The American Mathe- matical Monthly, 68(1P)):1117, 1961.
[EP84] Shimon Even and Azaria Paz. A note on cake cutting. Discrete Applied Mathematics, 7(3):285-299) 1984.
[EP06] Jeff Edmonds and Kirk Pruhs. Balanced allocations of cake. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS (06), pages 623-634, 2006.
[EP1]] Jeff Edmonds and Kirk Pruhs. Cake cutting really is not piece of cake. ACM Transac- tions on Algorithmss (TALG), 7(4):1-12, 2011.
[FT22] Uriel Feige and Yehonatan Tahan. On allocations that give intersecting groups their fair share. arXiv preprint 22XXi:22044068200 2022.
[Husl1] Farhad Husseinov. A theory of heterogeneous divisible commodity exchange economy. Journal of Mathematical Economics, 47(1):54 2011.
[KSV20] Maria Kyropoulou, Warut Suksompong, and Alexandros A Voudouris. Almost envy- freeness in group resource allocation. Theoretical Computer Science, 841:110-123, 2020.
[Lia40] AA Liapounoff. Sur les fonctions-vecteurs completement additives. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 4(6):465-478, 1940.
[MS22] Pasin Manurangsi and Warut Suksompong, Almost envy-freeness for groups: Improved bounds via discrepancy theory. Theoretical Computer Science, 930:179-195, 2022.
[Pro09] Ariel D Procaccia. Thou shalt covet thy neighbor's cake. In Twenty-First International Joint Conference on Artificial Intelligence, 2009.
PPW77] Ariel D Procaccia and Junxing Wang. A lower bound for equitable cake cutting. In Proceedings of the 2017 ACM Conference Economics and Computation, pages 479- 495, 2017.
[RW98] Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can. AK Peters/CRC Press, 1998.
[SHN19] Erel Segal-Halevi and Shmuel Nitzan. Fair cake-cutting among families. Social Choice and Welfare, 53:709-740, 2019.
[SHS20] Erel Segal-Halev and Warut Suksompong. How to cut a cake fairly: A generalization to groups. The American Mathematical Monthly, 128(1):79 83, 2020.
[SHS23] Erel Segal-Halevi and Warut Suksompong. Cutting a cake fairly for groups revisited. The American Mathematical Monthly, 130(3):203-213, 2023.
[Ste48] Hugo Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948.

---

[STZ23] Jonathan Scarlett, Nicholas Teh, and Yair Zick. For one and all: Individual and group fairness in the allocation of indivisible goods. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 2466-2468, 2023.
[Wik25] Wikipedia contributors. Hugo Steinhaus. https: //en. wikkppedia.org/vkki. Steinhaus, 2025. [Online; accessed 2-February-2022
[WS07] Gerhard J Woeginger and Jifí Sgall. On the complexity of cake cutting. Discrete Optimization, 4(2):213-220, 2007.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper and supplementary material contain the proofs of all theorems, lemmas, claims, stated in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See the introduction for discussion of the scope of this paper. The model includes all assumptions needed for the results to hold. The results themselves (theorems, lemmas, etc) state any additional requirements.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: The model is in Section 2. Proofs are included in the main body and supple- mentary material (technical appendix).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.cooo cttpss/cccpbccc///cccccccc guides/ /CodeSubmi ssi ssionPolccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///neerrpp.eeeee wwtp///bcc...ccccccteeeeeeeeeeee
Answer: [Yes]
Justification:
We have checked the guidelines and we follow them.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The introduction discusses relevance to practice, The work is theoretical, so there are no societal impacts of the nature described in the guidelines.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is theoretical; there are no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were used.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https tattps://neet /ttps/////.u...////eee http://rpp..cccoooffaerrae/e//// / for what should or should not be described.
19

---

A Relations Between Fairness Notions
In this section, we show the relation between our new fairness notions, and existing fairness notions: proportionality, envy-freeness, and perfection.
A.1 HCR-k Relations
Theorem 3. PROP HCR-1 2 HCR-2 2 ... ...2 HCR-(n HCR-n 2 EF.
Proof of Theorem 3. The first equality, PROP HICR-1ix is immediate from the definition of HCR-1: for |S| = 1, V((A.) = V.(As) 5 n-1 = -/2 is equally easy to see that HCR-k 2 HCR-(k + 1), for 1 < k S n - 2, since the conditions required to satisfy the latter are a subset of the conditions required to satisfy the former notion; Claim gives an allocation A such that A E K
but A & HCR-(k + 1). proving that HCR-k 2 HCR-(k + 1).
Claim 2. HCR-k does not imply HCR-(k: + 1) for S n
Proof. Let A HCR-k be allocation such that, for all E N, Vi(A,) n-k+I and there exists an agent j. E N \ {i), such that Vi(A,) = n- (all other (A(A,) are 0). is straightforward to construct such an allocation. E HCR-k, since (15) I n-k+1 I n-18| n-1S|+1 for all S such that [S] S A and S. However, by picking S such that i S, $ S, and [S] that V1(Ag) = n n-141
1, we have
81 S-1S|+ i.e., $ HCR-(A: + +)).
R-
The last equality, HCR-(n 1) HCR-n, again immediately follows from the definitions. Fi- nally, Claim proves that HCR-n 2 EF.
Claim 3. EF & HCR-n.
Proof. To see that EF C HCR-n, consider an allocation A E EF; we will show that A E HCR-n. Let C N be arbitrary subset of agents of size |S| I By the definition of envy-freeness, have that, for i E N, Vi(A,) s Vi(A.). Consider i E S; adding up for all j & S we have that
v4(As) I (n (A.) I (n (As)
(V((A)) S Vi(A)))
= (n - [s()(1 - v((As)).
Re-arranging we get the desired inequality: vi(Ag) S n-13 (
To see that HCR-n does not imply EF, consider an allocation
HCR-n such that, for all agents
i E N V,,))) = f furthermore, for every agent i E N, there exist distinct agents j: and & such that VI(A,,)
2 and vA,))
(and ((w).) 0 for all other agents w). It is easy
that
such an allocation can be constructed. A E HCR-n, since: (i) for all C N, |S| S n 2, and
all i E S, V((Ag) < - Vi(A,) 3 (i(As) S (Vi(A.) + (in(V((AA)))) (((,,)))) - 2-181 n-1SI+T and (iii V2(As) for S N. However, A & EF, since every agent i E N envies agent ji-
n- |S|
FI (ii) for all S C N, |S| n 1, and all i E S,
This concludes the proof Theorem 3.
A.2 LCR-k Relations
Theorem 4. PROP = I.CR1 ICR-2 ... LCR-(n - = LCR-n = SUPER-EF.
Proof of Theorem 4. By the definition of LCR-k, we have that Prop LCR-1, LCR-k 2 LCR-(k + 1) for 1 < h < n 1, and LCR-(n - 1) is equivalent to LCR-n. The theorem follows from Claim and Claim 5.
Claim 4. LCR-k does not imply LCR-(K + , for any 1 < k < n-
20

---

Proof. Consider an allocation A E LCR-k such that, for all i E N: (1) Vi(A,) = A
(i) (1(A,) = 0.
n²
for all j E Z,, for some Z: C N \ {i} such that 2,| = k; and (iii) V.(A,) = (1+ n- 1/4 for
all j E N (Z U (i)). S. Z, U [i]: [S|| = k + 1. Then, Vs(As;) V.(A,) =. and therefore
(.(As;) n-k n- [S i.e. A $ LCR-(K + 1).
Claim 5. LCR-n = SUPER-EF.
Proof. Consider an allocation A LCR-n. For all S N such that |S| n - and all i S, Vi(As) S ;: however, S has a single (arbitrary) agent. That is. Vi(As) = +V((A)) S f. for all JE N \ [i). And, since LCR-n C PROP, we also have Vi(A,) 2 n. therefore, A E SUPER-EF.
Consider an allocation A E SUPER-EF. We have that, for all i E N. J + i, 1 > V((A)). Adding up this for all j & S, for some arbitrary set S C N. ||| S n, such that E S, we have (1(Ag) - --18| i.e., A E LCR-n.
This concludes the proof of Theorem 4
Theorem 5. EF 2 LCR-[27, but EF 2 LCR-([ 1) and EF g LCR-2.
Proof of Theorem 5. Consider an allocation A E L.CR- [ Let j E N be two arbitrary agents.
Let S C NN (i), such that (i) i E S, and (ii), |S| = [ We have that Vi(As) = - V((Ag) 2
R-191 = 2 mod 2, Let S' be such that S' = (5)(t))) (i.., S' = (()
We
2n
have that |S"| = n - [ = J therefore, since E LCR- and E S" Vi()s)) S --15" mod Therefore, vi(As) 2 Vi(Ag)). However, Vi(As) = V.(A,) + Σ>Esi (4) Vi(As), and V.(Ag.) = v.(AA)) + Eces V.(2).. Therefore, we have that Vi(A,) 2 Vi(Ag), i.e., i does not envy j.
+ 2n
Next, notice that LCR- [[ 1) (and by extension, LCR-k for k < < 1) does not imply EF. Consider an allocation A E (.CR-((35 - 1) such that, for all i E N, Vi(A,) = ( 2 1) 1 n and there exists an agent ja such that (A(,) = - ( - 1) 1, and V₁(A,) = 0, for all agents
* i, Since Vi(A:) < Vi(A),), envy-freeness is violated.
Finally, EF does not imply LCR-2 (and by extension, LCR-k for k > 2). Consider an allocation A E EF such that, for all i E N there exists an agent ji. such that Vi(Aj,) = 0, and Va(A))
for all 2 + j. For S = { and n > 2, V((A)) =
n=2 n-1 n- 2
B Lower Bounds
In this section, we state our lower bounds for HCR-2 (Theorem 6) and LCR-2 (Theorem 7).
Theorem 6. Computing HCR-2 allocations requires M(n²) queries.
Proof. For this proof, we use many definitions and lemmas from the work of Procaccia [Pro09], who proves the M(n²) lower bound for finding envy-free allocations.
Consider an arbitrary algorithm. First, to analyze the information available to the algorithm each step, we define, for every agent i E N and every step t, a set of disjoint intervals 11Ş that is a partition of [0, 1]. We say that interval E IIŞ active with respect to agent i at step t.
It's are defined recursively. ITC = {10, 1]}. since the only information available to the algorithm after 0 steps/queries is that (i(
1. Assuming that step / we have IJ if step 1+ the algorithm does not make query for agent i (i.e., the query at step / + 1 is EVAL, or CUT, for some j # i), then 11 = II Otherwise, 11.+1 gets updated accordingly. For example, if the query is EVAL; x2), where Φ E 11 and x2 1z. for some intervals 4, 12 E 11 then, informally,
II (II) \ (4, 42) U ([left(I1), m1), [11, right(41), [left([2)) m2). [m2, r2)h) where for an interval = (a, b). le (e) = a and (T) = b. Intuitively, the algorithm at step I. "knew" i's value for I and 12, and after the EVAL x2). it can infer (at most) the value of agent i for
21

---

four additional intervals: [left(A), right(()))) [left(I2), Ø2), and [æz, (I2) (noting, that the first two imply the value for I1 and the second two imply the value for 12). Procaccia [Pro09] proves two crucial lemmas:
Lemma ((Pro09]; Lemma 3.2). For all i N and stage 4, | |IT < 2.
Lemma 2 ([Pro09]: Lemma 3.3). For all i N and stage f, II has the following properties:
1. For every I E II, Vi(I) is known to the algorithm at stage t.
2. For every I E II, I' I, and 0 < A & 1, it might be the case (based on the information available the algorithm at stage t) that Vi(I'= = (T).
Consider an adversary that, for every agent E N, responds as if the valuation of the agent was uniform over the interval [0, 1] (i.e., responds EVAL, æ22) = x2 - 21, and CUT, u) = x + v). Let T be the number of queries our algorithm asks before it terminates and outputs allocation
A = (A1, (A,,...,A,) A,) E HCR-2.
First, we claim that for all i E N, there exists an active interval I; S A., such that (i) I, E II. and (ii) v1(1,) 2 A. If this is not the case, one can define Vi (consistently with I1;") such that proportionality is violated. Concretely, (1) if & II for all I C A; then we can concentrate the value of all / such that I n A, * 0 to the sub-intervals outside of A; (and therefore, Vi(4,) 0), and (2) if (I() < J for all / S A., 1 E 11," then we can pick Vi such that V(().) maxren? Vi(I)= < 1/n.
Since all queries until time T have been answered as if the valuations were uniform, it must be that 1/n S VI( |4] for all i E N. However, if for all i E N we have: (i) L S. A,, (ii) I 2 1/n, (iii) A, O Aj = @ for all j * i, and (iv) 1 = [0, then it must be that 4 = A 1/n, as well as Vi(A,) 1/n, for all E N. The HCR-2 property then implies that
V. ((AN(()))) = 1 Vi,,,) - V((4,) S 7- or Vi(A,) 2 -
1 for all i, E N. m(n-1j
To meet this condition, it must be that for every agent i and piece A,. there exists an active interval I E 11." such that (i) / S Ay, and (ii) Vi(l) & O. Similarly to our earlier argument, if this is not the case, one can define V; (consistently with I13") such that V((A,) = 0 (< m(n-Ty). Concretely, we can pick V. such that (I n A₂) and V,(T) A,) = V,(T) for all I E IT! and Tn # 0.
Since allocations are pair-wise disjoint, we must then have at least n active intervals per agent by time T, i.e. |1 2 n for every agent i. Since [1 = 1, Lemma implies that [II 27 1, and therefore 27 + n, i.e. the algorithm makes at least " queries every agent i N. Overall, the algorithm makes at least n n_1 E ?(n²) queries overall.
Theorem 7. Computing LCR-2 allocations requires an infinite number of queries, for all n 2 3.
Proof. We prove the statement for all odd n, n 2 3; the proof can be easily adjusted to even n.
Consider an instance where [ agents agents through | - have the same valuation function
V1, L agents- - agents [ + 1 through n - have the same valuation function Vz, and the last agent, agent n, has valuation function (xx)) Vi (2)+ for all [0, 1].
Let A be a LCR-2 allocation. For every agent = I...., L... let ji = i = Since agent has valuation Vi, we have that ([0, 11% (A,UA)) < 1 2/n, or simply, (A(A,A,,, 2 2/n, from the definition of LCR-2. It also holds that (A, U A 2 2/n. We have اقاا (A, U A,,) = [0, 1] An. and ([0 1)) = V2(10, 1)) = 1, therefore, V (A,)) = 1 - V1, U A₁,)) S 1 1 = 1 n-12 2 1 Similarly, Vi((A,) < 1. Since LCR-2 implies proportionality, V,,),))) (2n) +22()) 2 3. Therefore, it must be that (A() = V/(An)) = -
(((A))+V
i.. (i())) +
2
Since Vi (A, U A, 2 2. for all = 1, ...... |3), and [3 = = = - 1 (which is exactly the value of [0, 1] A,), it must be that Vi (A, U A 2 .x Similarly, it must be that (A, U A,,) = 2 Therefore, we overall have that, there are 1 + 1 pieces, An and the (A, U A,,)s, such that, 1/2 and V/22 have the same value of 1 for the first piece, and the same value of 2 for all remaining pieces.
"
22

---

Given n valuations functions U1...., Un and weights wi...., asking for a partition of the cake into & pieces I..... 1x such that (I, = w, known as the exact division, or consensus splitting, problem. This problem is known to be impossible to solve with a bounded protocol, even for the case of two valuation functions and = 2 pieces with equal weights [RW98]. Since finding a L.R-2 allocation would give a solution to the exact division problem for two valuation functions and | pieces, we can conclude that there is no bounded protocol for finding a LCR-2 allocation.
Note that for even n, the proof is near-identical: the only difference is that the n-th agent is not necessary (i.e., half the agents have valuation V11 and the other half have valuation V2), and using the same arguments we would conclude that Vi U Az,)) = V2(A, U Aj.) = 2 for all i .//.
C Picking the parameters of Algorithm 2
Consider the partition, B, created in the tt iteration of line 4. Due the normalization of R each iteration, B will have the following property:
( 1 n+1 ( S Vi(B,)
(nt ViijeN
Let S' describe the state of S prior the final "Last Diminisher" phase of the algorithm (i.e. line 11). S will be comprised of piece from each e'pperfect partition, B, created. As discussed, each piece of S' needs to have value at least 1 - but at most i3 for any agent.
vi(S))
+
+
1
++1
(((S)) Σ e'
1 -
n
Notice that by polynomial expansion, we can see that:
( h+t+ (nti+e)²
1 1111)= )
1n+11 (nt--e)
n2 +1+1
Therefore, if we define d such that EL lower bounds of V,)))),, then for increasing e', the computed upper bound of Vi(Sg) will exceed 1 before the computed lower bound dips below č. With this in mind, define d as described: "
2 (the average of the required upper and
n+1
d
n ++1 )
x+1
>
n
2
In En
(n( + In(1/E) + In(1/))
e [n(1/a]
d=
In(n + 1)
In(n)
23

---

Now, we define e' such that Vi(S)) < 1 noting that if the required upper bound holds, then so will the required lower bound. For simplicity, we first loosen the upper bound:
vi(S)) - Σ -=1 n +e)
1
n++1 +t'
n-1
n+1
1
+e)
a+1
n+1
+
n-1
1
én
+c)
n+1
n+1
+
n-1
+e))
Enforcing that this last expression is at most 1/n we have
(
++")
a11
or
m41
?n
in 2
+1
n+1
2(n
+ 1)a2
12
m+T
2
Considering that Zn 2(++1)
> 0, we can tighten this constraint by decreasing the upper bound as so:
čn²²
(
E E
2(n + 1)3
Thus, the aforementioned conditions will hold for some d θ
[m(1/E) In(n)
and é' (
24


Reviews:
[{"review_id": "qEvjFsdxmO", "reviewer": "Reviewer_3btH", "summary": "This paper studies the problem of fair cake-cutting. There are some well-studied notions of fairness in this problem including proportionality and envy-freeness. This paper introduces two hierarchical fairness notions to bridge the gaps in the number of queries  (in the RW model) needed to achieve different notions. These notions are called Complement Harmonically Bounded-k (CHB-$k$) and Complement Linearly Bounded-$k$ (CLB-$k$). An allocation is CHB-$k$ if for any subset of size $s \\le k$ of agents and agent $i$ in this subset, value of $i$ for the union of the pieces received by the agents not in this set is at most $\\frac{n-s}{n-s+1}$. This bound changes to $\\frac{n-s}{n}$for CLB-$k$. Both CLB-1 and CHB-1 are equal to proportionality and CLB-$n$ coincides with super envy-freeness.\n\nThey show upper and lower bounds on the number of queries required for these notions, and also study approximate versions of them. Figure 1 show a great overview of the main results.", "questions": "Do you have some intuition on how relaxed versions of these notions look in the indivisible setting? Let's say we want to talk about CLB-$k$ up to one item/any item.", "limitations": "-", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\nThe paper is well-written and easy to follow.\n\nThe idea of introducing such fairness notions is novel and interesting and the results advance our understanding of fair cake cutting in the Robertson-Webb model.\n\nThe algorithms are mostly intuitive and proofs are solid.\n\nThe paper provides a nice overview of the related literature.\n\n\n## Weaknesses\n\nI pretty much like the contribution of this paper. My only concern is whether this is the right venue for this work. The paper is rather technical and due to lack of space most of the interesting part had to move to the appendix. In general I would suggest WINE/EC/SODA for this paper.\n\nI think after the definition of these notions, lower-bounds are the most interesting part of this work. I was a bit disappointed that they were all in the appendix.\n\nIn the definitions of CLB and CHB, $S$ is defined as the set that includes $I$ but then n-$S$ is used in the bounds. I don't see the reason for this as you can instead define $S$ as a set that does not include $i$  and use $|S|$ instead of $n-|S|$ everywhere.", "was_revised": true, "final_justification": "I like the paper in general. I'm still not sure if this is the right venue for this but I rather let the authors choose their audience. As other reviewers have mentioned some definitions lack enough motivation. I can see the paper going either way but I would vote for acceptance.", "rebuttal": "Thank you for your thorough and thoughtful review.\n\nRegarding your question, the short answer is that we have not explored this direction in depth. We believe it’s an interesting direction for future work. Here are some preliminary thoughts: looking at the proof that CHB is implied by EF, if one were to replace “EF” with “EF-1” or “EF-X,” the approximation would blow up (so, e.g., “CHB up to |S| items”). At the same time, “CHB up to one item” seems easy to achieve, intuitively, so perhaps simply looking at the proof of existence for CHB-k from EF-k is not the right approach. The existence of “CHB up to *any* item” seems like the first interesting question here. We are not sure whether the answer is more similar to the case of PROPX (known not to exist, even in simple settings) or EFX (known to exist for a small number of agents and certain valuation classes, but generally difficult to resolve).\n\nRegarding your comment about the definitions of CLB/CHB, perhaps our responses to Reviewers oPsd and JByF help clarify our motivation and intuition for these notions."}, {"review_id": "rr2oNoXL0h", "reviewer": "Reviewer_oPsd", "summary": "This paper introduces two new fairness notions, including Complement Harmonically Bounded-$k$ (CHB-$k$) and Complement Linearly Bounded-$k$ (CLB-$k$), to the cake-cutting model. There are several contributions in this paper. \n\n(1) They study the relationship between the above two notions and the existing fairness concepts, including EF and PROP. \n\n(2) For CHB-$n$, they design an algorithm to compute such an allocation in $O(n^4)$ queries with RW model and provide a lower bound of $\\Omega(n^2)$ queries for CHB-2 allocations. \n\n(3) For CLB-$k$, they construct an instance where CLB-2 allocations cannot be computed in bounded queries. Then, they focus on the approximate CLB-$n$ allocation and propose an algorithm to compute it in bounded queries.", "questions": "Q1: Could you please give me some practical examples or non-mathematical explanation of the proposed notions?\n\n\nQ2: For the computation of approximate CLB-$n$ allocations, I am a little curious about the lower bound of queries. So, could you please provide some insights for it?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n(1) This paper provides a new perspective of fairness besides EF and PROP, which fills the gap in the cake cutting model.\n\n(2) They smartly adapt the current technique to develop new algorithms to compute CHB-$n$ and the approximate CLB-$n$ allocations.\n\n(3) The whole paper is well written, and it is easy for us to read.\n\nWeakness:\n\n(1) In the relationship graph, we can easily find the position of CHB and CLB, which gives us a mathematical view of them. It may be a little bit hard to understand the practical motivation or meanings of these two notions, compared to the classic notions, including EF and PROP. For example, for PROP, each agent has a value threshold, and then compares the value of her bundle with it, which is easy for us to understand.\n\n(2)  For the CHB-$n$ allocations, the algorithm design is nice, but there is still a gap between the lower and upper bounds of queries. For the approximate CLB-$n$ allocations, it seems that the lower bound of queries is missing.", "was_revised": true, "final_justification": "The research problem is interesting, and the major concern for me is the motivation, since EF or PROP has strong theoretical and real application motivation, but the proposed notions may not be motivated sufficiently. Considering that the authors will strengthen the motivation, I will keep my score.", "rebuttal": "Thank you for your thorough and thoughtful review.\n\nRegarding your first question about practical examples/non-mathematical explanations for CHB/CLB: one can think of proportionality as a guarantee to every agent i that, from $i$'s perspective, \"the remaining $n-1$ agents, combined, don’t have too much of the cake\" (as opposed to the standard phrasing/viewpoint: \"agent $i$ has enough of the cake\"). Envy-freeness sits at the other extreme: the guarantee to every agent $i$ is that, from $i$'s perspective, \"for every other agent $j$, agent $j$ doesn't have too much of the cake.\" CHB interpolates between the two extremes: the guarantee to every agent $i$ is that, from $i$'s perspective, \"for every group of agents, the group, combined, doesn’t have too much of the cake.\" Put differently, proportionality limits the bundle of \"everyone else combined,\" envy-freeness limits the bundle of \"every other individual,\" and CLB/CHB limit the bundle of \"every group.\" Yet another intuition for CLB/CHB is that each agent wants the top $x$% of other agents not to have more than $y$% of the cake. Of course, different definitions of \"too much\" (linear vs harmonic) lead to notions that are not strictly between PROP and EF, but we hope that this perspective/viewpoint gives some more intuition and motivation for our new notions.\n\nRegarding your second question about lower bounds for approximate CLB-allocations: this is a great question! Our work does not provide any lower bounds, and we view this as a very interesting direction for future work. That said, we note that even for (the arguably more fundamental notions of) approximate proportionality and approximate envy-freeness, the literature does not provide any answers. To the best of our knowledge, the only known lower bound for approximate envy-freeness is by [BN22], which prove a $\\Omega(log(1/\\epsilon))$ bound for finding an epsilon EF allocation with *contiguous* pieces. That would imply a lower bound for finding contiguous $\\delta-CLB-(n/2)$ allocations; given the restrictive setting and mild lower bound, we chose not to emphasize this point in the paper.\n\nWe would be happy to incorporate these clarifications in the final version of the paper."}, {"review_id": "ls1IpIWgs6", "reviewer": "Reviewer_CnGJ", "summary": "This paper studies the cake-cutting problem, where a cake, modelled by [0, 1], is to be allocated to $n$ agents, each of whom admits an unknown distinct preference, and considers the popular RW query model. It was previously known that a proportional (PROP) allocation can be found in $O(n \\log n)$ queries, an envy-free (EF) allocation can be found using $O(n^{n^{n^{n^{n^n}}}})$ queries, and a perfect allocation cannot be computed within a bounded number of queries.\n\nThis paper proposes new fairness notions that interpolate between PROP and EF/perfection, which are respectively named Complement Harmonically Bounded (CHB) and Complement Linearly Bounded (CLB). An allocation satisfies CHB-$k$ (resp. CLB-$k$) for some $k \\in [n]$ if for all subsets $S$ with $|S| \\leq k$ and $i \\in S$, the value of $i$ for the union of pieces allocated to agents not in $S$ is at most $\\frac{n - |S|}{n - |S| + 1}$ (resp. $\\frac{n - |S|}{n}$), assuming each agent's total value for the cake is normalized to be $1$. CHB interpolates between PROP and EF with CHB-$1$ coinciding with PROP and CHB-$n$ being strictly weaker than EF. CLB interpolates between PROP and perfection with CLB-$1$ coinciding with PROP and CLB-$n$ being strictly weaker than perfection.\n\nThis paper gives an algorithm that computes a CHB-$n$ allocation in $O(n^4)$ queries and shows that no algorithm can compute a CLB-$2$ allocation with a bounded number of queries. Then, the paper considers an approximation version of CLB and provides an algorithm for finding a $\\delta$-CLB-$n$ allocation using $O(\\frac{n^6 \\ln (1 / \\delta)}{\\delta \\ln(n)})$ queries. Both algorithms exploit the observation that finding a complete, proportional, and nearly perfect allocation suffices, and invokes the algorithm for finding nearly perfect allocations given by prior work.", "questions": "- Line 272: Should $O(n^2)$ be $O(n^4)$? This is because there are $n$ iterations, and in each iteration, each agent takes $O(n^2)$ queries to mark. Or perhaps one can use the same trick as in the proof of Theorem 2 to reduce the last $O(n^2)$ cost to $O(1)$?\n\n- In the statement of Theorem 2, how are $d$ and $\\epsilon'$ defined? Can they be computed efficiently given the instance parameters?\n\n- Line 355: Should $O(n^2)$ be $O(n^3)$? This is because there are $n$ iterations, and in each iteration, each agent needs to query $O(n)$ times.\n\n- For the CHB-$k$ and CLB-$k$, do they imply any approximate version of EF? I'd especially like to know how far (whatever it means) CHB-$n$ is from EF in order to evaluate the significance of the $O(n^4)$ query complexity for CHB-$n$.\n\n- Is there an intuitive description (ideally a description without using any math) of CHB-$k$ or CLB-$k$ for $k>1$?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The study of cake-cutting has been initiated decades ago, and it still remains an important and interesting topic in algorithmic game theory. This paper contributes to this line of literature by proposing new fairness notions that interpolate between PROP and EF/perfection and providing a variety of intersting results. Personally, I find both notions quite natural in hindsight as they come from certain conditions implied by EF and perfection, and they nicely bridge between PROP and EF/perfection. On the other hand, it is less obvious that these notions can be interpreted as fairness even though they imply PROP, one of the most well-studied fairness concepts. This drawback makes it hard to judge whether such notions alone would find applications in either theory or practice.\n\nThe following algorithmic and hardness results in the paper are particularly good to know: (1) CHB-$n$ allocations, which is intuitively quite close to EF, can be computed in polynomially many queries, and (2) CLB-$2$ allocations, a seemingly mild relaxation of PROP toward perfection, inherits the hardness of computing perfect allocations. I believe these results will be of great interest to the fair division community as they seem to serve as an important step toward bridging the dichotomy between PROP and EF/perfection and closing the gap between upper and lower bounds for the query complexity of EF.\n\nMoreover, the paper is in general well-written, and I really enjoy reading it, especially for the technical overview in the introduction. The proofs are correct to the extent that I checked. Overall, I believe that this paper exceeds the bar of NeurIPS and should be accepted.\n\nHere are some detailed comments:\n- Line 99-101: it is unclear why such a step forces us to deal with the weighted case.\n- Line 126: It is unclear what \"uniform\" means here.\n- Line 143: \"$\\delta$-CLB-$n$\" -> \"$\\delta$-CLB-$k$\".\n- Line 144: \"such that $k$\" -> \"such that if $k$\".\n- Line 161-164: The statement here seems obvious and redundant, since finding EF allocations has already been a strict subproblem of finding CHB-$n$ allocations.\n- Line 13 in Algorithm 1: $S$ is a set of pieces instead of a piece, although it only contains one element at that time.\n- In the proof of Theorem 1, it is not argued that Line 6 of Algorithm 1 can always be implemented, i.e., such a mark on $R$ is well-defined. Although this should follow easily from the same argument for the last remaining agent, it should be added for completeness. Same for the proof of Theorem 2.\n- Line 325: \"runtime\" -> \"query complexity\".\n- Line 333-334: This sentence seems to be grammatically problematic.\n- Line 344: Should $I_{2,left}$ be $I'$?\n\nThe following papers are also relevant and are recommended to be cited:\n\nA recent paper which also proposes a hierarchical type of notion for fair division, although it is for the strategic setting:\n- It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents. Eden Hartman, Erel Segal-Halevi, Biaoshuai Tao.\n\nPapers on computing approximate EF allocations:\n- Envy-Free Cake-Cutting for Four Agents. Alexandros Hollender, Aviad Rubinstein.\n- Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi.\n- Algorithmic Solutions for Envy-Free Cake Cutting. Xiaotie Deng, Qi Qi, Amin Saberi.\n\nPapers on cake cutting with strategic agents:\n- ​The Incentive Guarantees Behind Nash Welfare in Divisible Resources Allocation. Xiaohui Bei, Biaoshuai Tao, Jiajun Wu, Mingwei Yang.\n- On Existence of Truthful Fair Cake Cutting Mechanisms. Xiaolin Bu, Jiaxin Song, Biaoshuai Tao.", "was_revised": true, "final_justification": "My concerns are fully addressed, and I'd like to see the comments being incorporated in the future version of the paper.", "rebuttal": "Thank you for your thorough and thoughtful review.\n\nRegarding your first question, great catch! You are correct in both comments: the same trick can be used to reduce the $O(n^2)$ to $O(1)$, but this is not explained properly, so it should be $O(n^4)$. We will update the paper to correct this.\n\nRegarding your second question, about $d$ and $\\epsilon’$, in Appendix C we give a closed form for $d$ right above line 906, and a bound for $\\epsilon’$ in line 909.\n\nRegarding your third question, about line 355, we are counting total queries, so we believe what is written is correct. Perhaps the confusion is that super-queries can be implemented using a constant number of actual queries; if so, see lines 335-345. Or, maybe the confusion is that we are tracking the evaluations of all intervals; if so, see lines 356-365.\n\nRegarding your fourth question, about the connection to approximate EF: a proportional allocation is, in the worst-case, $(n-2)/n - EF$, since, in the worst-case, $v_i(A_i) = 1/n$, but $v_i(A_j) = (n-1)/n$ for some other agent $j$. For a $CHB-n$ allocation, things can be as bad as $v_i(A_i) = 1/n$, $v_i(A_1) = ½$, and $v_i(A_j) = 1/(2n)$ for all remaining agents $j \\neq 1$. This is a $(½ - 1/n)-EF$ allocation. We believe this is the worst case. This is a great observation that we had not made before, and we will include it in the revised version of the paper.\n\nRegarding your fifth question, about intuitive descriptions for these notions, observe that one can think of proportionality as a guarantee to every agent $i$ that, from $i$'s perspective, \"the remaining $n-1$ agents, combined, don’t have too much of the cake\" (as opposed to the standard phrasing/viewpoint: \"agent $i$ has enough of the cake\"). Envy-freeness sits at the other extreme: the guarantee to every agent $i$ is that, from $i$'s perspective, \"for every other agent $j$, agent $j$ doesn't have too much of the cake.\" CHB interpolates between the two extremes: the guarantee to every agent $i$ is that, from $i$'s perspective, \"for every group of agents, the group, combined, doesn’t have too much of the cake.\" Put differently, proportionality limits the bundle of \"everyone else combined,\" envy-freeness limits the bundle of \"every other individual,\" and CLB/CHB limit the bundle of \"every group.\" Yet another intuition for CLB/CHB is that each agent wants the top $x$% of other agents not to have more than $y$% of the cake.\n\nWe will also address the minor comments you point out (citations, typos, etc) in the final version of the paper."}, {"review_id": "hgl8xVnmEr", "reviewer": "Reviewer_JByF", "summary": "The paper studies the cake cutting problem. It introduces two new families of fairness notions, which both conceptually lie in between the known fairness notions of proportionality and envy-freeness. The paper gives upper and lower bounds on the query complexity of finding outcomes satisfying these fairness notions and relate them to previously defined ones. Most importantly, the paper gives an algorithm which finds a CHB-n outcome (which is one of the defined fairness notions) with O(n^4) queries.", "questions": "I am very much willing to increase my score, given a better intuitive motivation of (in particular) CHB and the accompanying algorithm answering (a subset of) the following questions: \n\nWhat is your motivation behind CHB? Why is the CHB family of fairness notions natural and worth achieving over just proportionality? Why does an agent (implicitly) care about what other agents receive?\n\nI might also be misunderstanding something, so I am quite open-minded regarding the rebuttal :)", "limitations": "/", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "In general, cake cutting (or fair division in total) is a suitable topic for NeurIPS. The paper is well-written and for the most part easy to follow, the introduced fairness notions are interesting (in particular, since they manage to slot in somewhere between the almost \"untouchable\" envy-freeness and the easy-to-achieve proportionality) and I can see this paper sparking some follow-up in the fair division community. \n\nYet, there is something I am struggling with in this paper and which makes me question its suitability for NeurIPS. \nIn essence, I do not really find the introduced fairness notions to be entirely convincing and I do not think the authors really motivate them well-enough, besides the fact that they are (let's say) curious fairness notions, that lie somewhere in-between the standard ones of envy-freeness and proportionality. In particular, I am missing some motivation and discussion on why one might be interested in the utility of bundles assigned to other agents. Why do I as an agent do not just care about my own bundle and maybe the bundle of other agents in comparison to mine, but also about the total welfare (according to my own subjective opinion) of every subgroup I could possibly be a part of? Similarly, I am missing some motivation for the actual form the fairness notions take. CLB is easy to understand, but what is the motivation behind CHB (except that it works out with the algorithm and that envy-freeness implies it). I think especially for a conference like NeurIPS (which is not just purely a theory conference) a discussion on things like this is important. To add on to this, I think these prior points also lead to \"weirdly-behaving\" algorithms. Consider for instance the case of two agents, where the first agent uniformly values the interval [0,1/2] and does not value the rest, while the second agent only values [1/2, 1]. Here, Algorithm 1, (due to its requirement of having every agent value every other agents bundle positively) gives agent 1 some part of [1/2, 1] and vice versa for agent 2, now this is not forced by CHB, but still due to the insistence on giving every subset of agents something (in the eyes of every agent) it seems somewhat inevitable that something like this would happen in a simple algorithm satisfying CHB. Still, this makes the algorithm seem more like a theoretical novelty, and not like a \"rule\" or an actual algorithm which you would want to use for an actual cake cutting instance --- which in my mind would greatly improve its suitability for NeurIPS. \n\nMinor comments: \n- I am not a big fan of citing Wikipedia. For this particular use case there are better/more scientific sources on Steinhaus\n- Line 169: Missing a space after \"queries\"\n- Line 263: Might be worth making a brief comment why this is non-negative\n- Line 269: should be \"for finding *an* epsilon-perfect\" (also I prefer the $\\varepsilon$ over $\\epsilon$, but this is personal preference)\n- I am personally missing a discussion section in this paper\n- Line 824: Sometimes you write V_i(\\overline{S'}) instead of V_i(A_\\overline{S'})", "was_revised": true, "final_justification": "I thank the authors for their rebuttal. I think fundamentally, we agree on the issues at hand, but perhaps we disagree at the \"weights\" assigned to these issues. I still feel that the motivation for the provided fairness axiom is very lacking and I am not sure the algorithmic contribution is enough for we to outweigh this (especially for NeurIPS compared to say Wine/EC/Soda, as another reviewer mentioned).  Copying from what I mentioned in the discussion: \"To re-iterate, I especially find the CHB notion to be quite not so well motivated. Yes, it implies proportionality, but proportionality on its own does not (at least to me) imply fairness. Proportionality (again at least to me) seems more like a minimal \"test\" of fairness, so positive and negative results for proportionality are in some sense akin to mapping the boundary of possible fair algorithms. CHB much less seems like a minimal \"test\", but also seems far to weak to be a sufficient condition to be fair. (I hope this makes sense)\".", "rebuttal": "Thank you for your thorough and thoughtful review.\n\nRegarding the motivation (and intuition) for CHB: one can think of proportionality as a guarantee to every agent $i$ that, from $i$'s perspective, \"the remaining $n-1$ agents, combined, don’t have too much of the cake\" (as opposed to the standard phrasing/viewpoint: \"agent $i$ has enough of the cake\"). Envy-freeness sits at the other extreme: the guarantee to every agent $i$ is that, from $i$'s perspective, \"for every other agent $j$, agent $j$ doesn't have too much of the cake.\" CHB interpolates between the two extremes: the guarantee to every agent $i$ is that, from $i$'s perspective, \"for every group of agents, the group, combined, doesn’t have too much of the cake.\" Put differently, proportionality limits the bundle of \"everyone else combined,\" envy-freeness limits the bundle of \"every other individual,\" and CLB/CHB limit the bundle of \"every group.\" Yet another intuition for CLB/CHB is that each agent wants the top $x$% of other agents not to have more than $y$% of the cake. (Also, to answer your last question, note that all three notions impose limits on what others receive.)\n\nViewed through this lens, we believe CHB is a natural and very well-motivated notion --- especially given our limited understanding of the complexity of envy-freeness, despite substantial efforts from the fair division community. Our results imply that CHB also offers an algorithmically tractable alternative to envy-freeness.\n\nRegarding relevance to NeurIPS, the NeurIPS community has been increasingly interested in formal models of fairness. Cake cutting is the canonical model for studying resource allocation with fairness guarantees to individual agents (as opposed to fairness guarantees to groups of agents). Therefore, we believe our work will resonate with the NeurIPS audience. \n\nThe \"weird behavior\" of Algorithm 1 you point out is interesting; however, one can raise similar concerns for perfect allocations ($v_i(X_j) = 1/n$), which are considered extremely fair. We understand your concern as, at least implicitly, suggesting adding some form of efficiency; we agree this is an interesting and important direction. That being said, it is well known that Pareto efficiency cannot be achieved by a finite protocol in the RW model (see \"How to Cut a Cake Before the Party Ends\" by Kurokawa et al.). One can, of course, turn to approximations to fairness/efficiency (like \"Optimal Envy-Free Cake Cutting\" by Cohler et al.) or change the model a bit (like \"Beyond Cake Cutting: Allocating Homogeneous Divisible Goods\" by Caragiannis et al.). We find these directions compelling, but beyond the scope of this work, and leave them as promising future directions.\n\nWe would be happy to incorporate these clarifications in the final version of the paper. We will also address the minor comments you point out (Wikipedia citation, typos, etc) in the final version of the paper."}]

Author rebuttal:

Meta-review: The paper proposed two new hierarchies of notions of fairness in cake cutting that interpolate well-studied notions, and investigated their properties. Reviewers agreed that the problem studied in this paper is significant and acknowledged the novelty and clarity of the paper. The main reservation is the motivation behind the two new notions of the fairness. Unfortunately the issue was not addressed after the rebuttal and discussions. Multiple reviewers felt that the paper might be a better fit for a more theoretical/specialized venue such as EC, WINE, or SODA. Still, the paper can be a good fit for NeurIPS and would stimulate more discussions and future work.

If the paper is accepted, the authors are strongly encouraged to think about justifications in camera ready and for future work. Proposing new notions of fairness and investigating their relationship/properties are great research topics, but motivating the new notions by real-life scenarios will have greater impact and do a better service to research community and our society.
Decision: Accept (poster)