{"id":"b3bb426a-d3b9-43c4-856f-f94b97536bec","arxiv_id":"2506.12950","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Introduces CHB-k and CLB-k cake-cutting fairness hierarchies, with an O(n^4)-query protocol for CHB-n, an Ω(n^2) lower bound for CHB-2, and proof that CLB-2 and super envy-freeness require unbounded queries.","lead":"This paper introduces two new hierarchies of fairness notions for cake cutting, CHB-k and CLB-k, and maps their query complexity between proportionality, envy-freeness, and super envy-freeness. The authors show that a fairness guarantee weaker than envy-freeness can be computed in polynomial time, while a stronger guarantee cannot be achieved with any bounded number of queries.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 assumes without proof that the Brânzei–Miltersen 1/(4n)-perfect allocation has O(n^2) intervals; if this fails, the Eval charge exceeds O(n^4) and the central upper bound collapses.","rationale":"The central upper bound (Theorem 4) rests on two quantitative assumptions: the BM15 subroutine costs O(n^4) queries, and it produces an allocation with O(n^2) intervals. The first is standard. The second is asserted but not derived or cited. It is the true load-bearing step because every subsequent computation—evaluating V_i(B_j) for all pieces, implementing residue marks, and maintaining partial-interval values after removals—scales with the number of intervals. The reader's weakest assumption (residue-mark simulation) is a downstream symptom: if intervals are O(n^2), the simulation is implementable with one Cut query per agent per iteration plus arithmetic on known interval values, and additional partial-interval Evals after removals add only O(n^2), preserving O(n^4). Thus the reader's specific worry is answerable. The unaddressed interval-count assumption is the more fundamental risk. It is likely true (necklace-splitting constructions give O(n^2) cuts), but the paper should state and prove it. The remaining issues the reader flags (Claim 1's range, Section 6 typo) are minor and do not affect the main results, so the conditional verdict stands.","tokens_in":19404,"tokens_out":28463,"duration_ms":296065,"concrete_test":"Verify, by reading the Brânzei–Miltersen protocol or running an implementation for m=4n/3 agents with ϵ=1/(4n), that the returned allocation has O(n^2) total intervals; if the interval count is ω(n^3), recompute the O(n^3) Eval cost in Section 4 and the O(n^4) bound for Algorithm 1 fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4 (Section 4) charges the Brânzei–Miltersen 1/(4n)-perfect call O(n^4) queries and then adds \"at most O(n^3) Eval queries are necessary for every agent to compute V_i(B_j)\" because the protocol \"produces at most O(n^2) intervals.\" This interval bound is load-bearing: the subsequent Last-Diminisher loop needs V_i of each constituent interval of the residue R to locate each agent's mark with a single Cut query, and to update partial-interval values after each removal. If the BM15 allocation actually has ω(n^3) intervals, the Eval charge becomes ω(n^4) and the advertised O(n^4) bound collapses. The paper cites no lemma from [BM15] establishing the O(n^2)-interval property; it is asserted without proof. The reader's concern about simulating marks on the non-contiguous residue is a symptom of this same gap: with O(n^2) intervals the simulation is constant-overhead, but with more intervals it is not.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces two hierarchies of fairness notions for cake cutting, Complement Harmonically Bounded (CHB-k) and Complement Linearly Bounded (CLB-k), which interpolate between proportionality and envy-freeness on one side and proportionality and perfect/super envy-freeness on the other. It proves the inclusion relations between these notions and existing ones (Theorems 1–3), gives a Robertson–Webb protocol computing CHB-n allocations in O(n^4) queries (Theorem 4), an Ω(n^2) lower bound for CHB-2 (Theorem 5), an unbounded-query lower bound for CLB-2 (Theorem 6), and an approximate CLB algorithm with O(n^5/ε · ln(1/ε)/ln n) query complexity (Theorem 7). The conceptual contribution is a clean parametrized family of fairness notions with a polynomial-time CHB-n algorithm, contrasting with the astronomical complexity of envy-freeness and the unbounded complexity of CLB-2.","tokens_in":19564,"tokens_out":33864,"duration_ms":408388,"significance":"If the results are correct, the paper provides a useful map of the terrain between proportionality and envy-freeness, and it identifies a new pair of computationally meaningful thresholds: CHB-n is polynomially computable, while CLB-2 is not computable with a bounded number of queries. The CHB-n protocol is a genuine algorithmic contribution, and the lower-bound framework adapts Procaccia's active-interval method in a way that could be reused. The CLB-2 unboundedness result also resolves, as a corollary, the unbounded query complexity of super envy-freeness. The paper is clearly written and the elementary inclusion proofs are largely sound. However, the main upper bound rests on an unproved interval-count assertion about an external protocol, and one step of the Theorem 5 proof is written incorrectly, so the central claims need a nontrivial revision before the paper can be accepted.","major_comments":[{"comment":"The advertised O(n^4) bound rests on the unproved assertion that the Brânzei–Miltersen 1/(4n)-perfect protocol \"produces at most O(n^2) intervals.\" This property is load-bearing: the subsequent per-agent evaluations of the n pieces B_j cost O(n · I), where I is the number of intervals, and the Last-Diminisher phase must compute marks inside the non-contiguous residue R whose interval decomposition comes from the same protocol. The paper cites no lemma in [BM15] establishing I=O(n^2); the generic bound from a protocol with O(n^4) queries is only I=O(n^4), which would make the Eval charge O(n^5) and invalidate Theorem 4. Please supply a proof of the interval bound or revise the algorithm and complexity claim.","section":"§4, Theorem 4 (query complexity)"},{"comment":"The proof's first claim—that for every i there is an active interval I_i⊆A_i with V_i(I_i)≥1/n—is false as stated: A_i may contain several active intervals, each of value below 1/n, whose total value is at least 1/n, and the redistribution argument in case (2) does not make V_i(A_i)<1/n because the total value of each active interval is already fixed. The equality |A_i|=1/n can instead be obtained from completeness and proportionality under the uniform responses (each length at least 1/n and sum 1). The rest of the active-interval argument for each A_j then yields the Ω(n^2) bound. Please rewrite this step.","section":"§5, Theorem 5"},{"comment":"The derivation of the admissible ε' is algebraically inconsistent. From the definition of d, q^d=ε̃ n/2 for q=1/(n+1), but the displayed inequality replaces 1−q^d by 1−q·ε̃n/2; solving the displayed inequality either gives a negative bound or a value of order 1/n^2+ε̃/n, not the fraction printed. Since the stated ε'∈Θ(ε/n^2) is used in the query bound O(n^5/ε · ln(1/ε)/ln n), please re-derive the parameter condition and state the correct Θ constant.","section":"§6, Theorem 7 (parameter choice)"}],"minor_comments":[{"comment":"Claim 1 states CHB-k does not imply CHB-(k+1) for 1≤k≤n−1, but CHB-(n−1)=CHB-n; the range should be 1≤k≤n−2.","section":"§3.1, Claim 1"},{"comment":"The sentence saying \"there exist perfect allocations that are not super envy-free\" contradicts the stated chain Prop⊋EF⊋Super-EF⊋Perf, since every perfect allocation is super envy-free. The intended sentence should list examples witnessing strict containments in the opposite direction.","section":"§2.2"},{"comment":"The algorithms use 4n/3 and n/3 without addressing integrality; please state floor/ceiling conventions or assume n divisible by 3.","section":"§4, Algorithm 1"},{"comment":"The reduction concludes that CLB-2 implies exact division with k=⌊n/2⌋+1 pieces and weights 1/n and 2/n, while the cited Robertson–Webb impossibility is for two pieces with equal weights; please add a reduction or citation showing the multi-piece unequal-weight version is also unbounded.","section":"§5, Theorem 6"},{"comment":"The statement that each exiting agent \"takes with her two pieces of combined value at most 1/n\" from a remaining agent's perspective should be justified explicitly by the left-most mark property; as written it appears to appeal to the exiting agent's own valuation.","section":"§4, Correctness proof"}],"recommendation":"major_revision","confidential_remarks":"The most serious risk is the unproved O(n^2)-interval assertion for the Brânzei–Miltersen protocol. If that property cannot be established, the main upper bound would need a different argument. The Theorem 5 proof issue and the Theorem 7 parameter derivation are fixable in revision, but they must be addressed carefully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, read this one if you care about the query complexity of cake cutting between proportionality and envy-freeness. The paper's real contribution is two new hierarchies, CHB-k and CLB-k, and it proves an O(n^4) Robertson-Webb protocol for CHB-n, an Omega(n^2) lower bound for CHB-2, and unbounded query complexity for CLB-2, hence for super envy-freeness. The definitions are natural and the hierarchy relations, including CLB-n = super-EF and the incomparability of CLB-k with EF in the middle range, are worked out carefully. The main proofs are sound: Algorithm 1's correctness argument is complete, the CHB-2 lower bound adapts Procaccia's active-interval machinery correctly, and the CLB-2 lower bound reduces to exact division cleanly. This is a genuine step in mapping the intermediate landscape, not just a repackaging of known results.\n\nThe soft spots are real but mostly cosmetic. Claim 1 is stated for 1 <= k <= n-1, but it cannot hold at k=n-1 because CHB-(n-1)=CHB-n; it is only needed for k <= n-2. The Section 6 derivation has a sign typo in the displayed formula for d; the final Theta bound is right. More substantively, Theorem 4 assumes that the Brânzei-Miltersen epsilon-perfect construction produces O(n^2) intervals, and the paper asserts this without proof or a specific citation. That interval bound is load-bearing: it is how the paper charges O(n^3) Eval queries for the V_i(B_j) values, and the same assumption appears again in Section 6. I believe the claim is probably true, fitting the necklace-splitting structure of BM, but a referee should demand a lemma instead of an assertion. The super-query simulation in Section 6 also needs a slightly clearer accounting of when interval values are known; it is probably right, just under-specified.\n\nBottom line: the central claims look correct and the paper deserves a serious referee. Send it out, and ask for a fix to Claim 1's range, a proof or citation for the BM interval bound, and cleanup of the d formula. None of these should change the main conclusions.","headline":"A useful map of the proportionality-to-envy-freeness gap, with a mostly sound O(n^4) CHB-n protocol and a clean CLB-2 unboundedness proof; the main open issue is a load-bearing unproved interval bound.","tokens_in":20186,"tokens_out":7558,"would_cite":true,"duration_ms":85979,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new cake-cutting protocol computes CHB-n allocations in O(n^4) queries, while CLB-2 requires unboundedly many.","keywords":["cake cutting","fair division","Robertson-Webb model","query complexity","envy-freeness","super envy-freeness","proportionality","exact division"],"falsifier":"Instrument Algorithm 1 on an instance where the residue R has Θ($n^{2}$) disjoint intervals and count the actual Cut and Eval queries needed to implement one cut on R; if the per-mark cost grows with the number of intervals, the O($n^{4}$) upper bound fails. On the lower-bound side, if a bounded Robertson-Webb protocol for exact division with two valuation functions and two equal pieces were found, the CLB-2 unboundedness proof would collapse.","tokens_in":19122,"feed_emoji":"🍰","tokens_out":7967,"duration_ms":87852,"temperature":0.7,"pith_summary":"The paper introduces two hierarchies of fairness notions for cake cutting—Complement Harmonically Bounded (CHB-k) and Complement Linearly Bounded (CLB-k)—that interpolate between proportionality and envy-freeness (CHB) or between proportionality and super envy-freeness (CLB). Its central claim is that one level of the CHB hierarchy, CHB-n, is computationally accessible despite being strictly weaker than envy-freeness: there is a Robertson-Webb protocol that computes a complete CHB-n allocation using O($n^{4}$) Cut and Eval queries. The same CHB hierarchy is not free, since CHB-2 requires Ω($n^{2}$) queries. The CLB hierarchy is much harder: computing CLB-2, hence every CLB-k for k≥2, cannot be done in any bounded number of queries, which settles super envy-freeness as computationally unbounded. If these results hold, envy-freeness sits between an easy fairness notion and an impossible one, giving a concrete map of the complexity gap between proportionality and perfection.","feed_headline":"O(n^4) protocol finds CHB-n fair allocations","feed_subtitle":"A stricter neighbor, CLB-2, needs unbounded queries, sharpening the map between proportionality and envy-freeness.","key_machinery":"The carrying mechanism is a two-phase protocol. Phase one uses an ϵ-perfect allocation algorithm on an enlarged instance of 4n/3 agents, keeping n pieces and merging the phantom agents' pieces into a residue R; because the partition is (1/4n)-perfect, every real agent values every kept piece at least 1/(2n). Phase two runs a Last Diminisher loop on R: each remaining agent marks the point where her value for the residue prefix equals 1/n minus her value for her favorite remaining kept piece, the left-most marker takes that prefix plus her favorite piece, and the last agent receives the rest. The proof that the output is CHB-n uses the fact that a complete proportional allocation with all cross-values at least 1/(2n) satisfies every CHB-n constraint. The lower bounds are carried by the active-interval gadget from [Pro09], which formalizes what the algorithm knows about each agent after a sequence of queries.","core_discovery":"In the paper's own terms, an allocation is CHB-k if for every subset S of at most k agents and every i∈S, agent i values the union of everyone else's pieces at most (n-|S|)/(n-|S|+1); CLB-k replaces this bound by (n-|S|)/n. CHB-1 and CLB-1 are exactly proportionality, CHB-n is a strict superset of envy-free allocations, and CLB-n coincides with super envy-freeness, requiring each agent to value her own piece at least 1/n and every other agent's piece at most 1/n. The paper's main result is Algorithm 1, a complete protocol that first computes a (1/4n)-perfect allocation for 4n/3 agents (including n/3 phantom agents) and then runs a cut-and-match Last Diminisher on the leftover residue, producing a complete CHB-n allocation with O($n^{4}$) queries. On the lower-bound side, it proves that CHB-2 needs Ω($n^{2}$) queries and that CLB-2—and therefore every stronger CLB level—cannot be computed with a bounded number of queries, by reducing CLB-2 to exact division, a known impossible task in the Robertson-Webb model.","pith_inferences":["The two hierarchies expose a threshold: replacing the harmonic bound (n-|S|)/(n-|S|+1) with the slightly tighter linear bound (n-|S|)/n flips feasibility from polynomial to unbounded; a natural conjecture is that the harmonic constant is the sharpest polynomial-time-achievable group complement bound.","Because the O(n^4) protocol depends on simulating cuts and evaluations on a non-contiguous residue with constant overhead, its practical query count may degrade on implementations that evaluate each interval separately; directly measuring this simulation cost is a concrete next step.","The CHB-n versus envy-freeness gap suggests that envy-freeness's difficulty does not come from collective complement constraints, but from the pairwise, per-agent comparisons that CHB ignores; one could test this by defining intermediate notions that add pairwise constraints one at a time and measuring query complexity.","The phantom-agent trick—treating extra arbitrary agents as a reservoir whose pieces become reallocatable residue—may transfer to other fair-division settings, such as producing near-perfect starting points for group fairness notions."],"forward_implications":["Complete CHB-n allocations give a polynomial-time fairness guarantee that is strictly weaker than envy-freeness but satisfies strong group-level complement bounds.","Super envy-freeness, previously open, is now known to have unbounded query complexity in the Robertson-Webb model, since it coincides with CLB-n and CLB-2 is already unbounded.","Any strengthening of proportionality that forces linear complement bounds (CLB-k, k≥2) is out of reach for bounded protocols, so the practical target becomes approximate δ-CLB-n, which the paper computes in O(n^6/δ · ln(1/δ)/ln n) queries.","The Ω(n^2) lower bound for CHB-2 means the easy CHB hierarchy is not uniformly easy; the first nontrivial level already needs quadratic queries.","If a super-polynomial lower bound for envy-freeness exists, it must come from a subproblem strictly harder than CHB-n, since CHB-n is polynomial-time solvable."],"supporting_citations":[{"why":"Supplies the ϵ-perfect allocation subroutine whose O(n^3/ϵ) query bound and O(n^2) interval count drive Algorithm 1's O(n^4) complexity.","marker":"[BM15]"},{"why":"Provides the active-interval definitions and lemmas that the CHB-2 Ω(n^2) lower bound builds on.","marker":"[Pro09]"},{"why":"Defines the Cut/Eval query model and proves exact division with two valuations and two equal pieces has no bounded protocol, which the CLB-2 unboundedness reduction uses.","marker":"[RW98]"},{"why":"Supplies the moving-knife division procedure that Algorithm 1's cut-and-match Last Diminisher loop adapts to allocate the residue.","marker":"[DS61]"},{"why":"Introduces the Last Diminisher method and the proportional allocation benchmark from which the new hierarchies depart.","marker":"[Ste48]"}],"fun_headline_variants":["New fairness tiers: CHB-n O(n^4), CLB-2 unbounded queries","CHB-n solvable in O(n^4); CLB-2 unsolvable in bounded queries","Cake cutting: CHB-n protocol O(n^4), CLB-2 impossible to bound","Fairness hierarchy: CHB-n easy, CLB-2 impossible in R-W model"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The O($n^{4}$) query bound holds only if each mark that an agent makes on the leftover residue—a finite union of disjoint intervals—can be simulated with a single Cut query plus arithmetic on interval values already known, without paying an extra Eval query for every interval.","fun_headline_variants_meta":{"raw":{"variants":["New fairness tiers: CHB-n O(n^4), CLB-2 unbounded queries","CHB-n solvable in O(n^4); CLB-2 unsolvable in bounded queries","Cake cutting: CHB-n protocol O(n^4), CLB-2 impossible to bound","Fairness hierarchy: CHB-n easy, CLB-2 impossible in R-W model"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000407,"raw_usage":{"total_tokens":2263,"prompt_tokens":1244,"completion_tokens":1019,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":860,"completion_tokens_details":{"reasoning_tokens":918}},"tokens_in":860,"tokens_out":1019,"duration_ms":10487,"temperature":1.0,"reasoning_tokens":918,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:42:34.883850+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument Algorithm 1 on an instance where the residue R has Θ($n^{2}$) disjoint intervals and count the actual Cut and Eval queries needed to implement one cut on R; if the per-mark cost grows with the number of intervals, the O($n^{4}$) upper bound fails. On the lower-bound side, if a bounded Robertson-Webb protocol for exact division with two valuation functions and two equal pieces were found, the CLB-2 unboundedness proof would collapse.","supporting_citations":[],"review_version":1}