betaFeedback

WorksComputer Science

The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources

Abstract

We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using 2nlog⁡2n+O(n)2^{n\log_2 n+O(n)} queries and cuts. For both cake and chores, a Las Vegas protocol uses O(n12log⁡(2n))O(n^{12}\log(2n)) expected queries and O(n11log⁡(2n))O(n^{11}\log(2n)) expected cuts. Conversely, every exact protocol with fixed positive success probability requires Ω(n2)Ω(n^2) expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

Introduction

Envy-free division seeks an allocation in which no agent prefers another agent’s share to its own. For cake, agents seek greater value; for chores, they seek smaller cost. A resource containing both desirable and undesirable parts requires signed valuations. When preferences are accessible through queries, the algorithmic question is how much information is needed to construct an envy-free allocation. We study complete allocations into finite unions of intervals and query bounds that depend only on the number of agents.

In the Robertson–Webb model, a query asks one agent either to evaluate an interval or to cut off a specified value. Aziz and Mackenzie [1] gave a bounded protocol for general cake cutting. Dehghani, Farhadi, Hajiaghayi, and Yami [6] established boundedness for chores. Recent preprints give nO(1)2nn^{O(1)}2^n deterministic cake queries [18] and O~(n30)\widetilde{O}(n^{30}) expected queries for exact randomized cake cutting [MS26]. The remaining questions include how far these bounds can be reduced, what randomization can achieve for chores, and whether bounded-query guarantees extend to signed valuations.

For chores, we give a deterministic exact protocol using 2nlog⁡2n+O(n)2^n\log_2 n+O(n) queries. For both cake and chores, we give a Las Vegas protocol using O(n12log⁡(2n))O(n^{12}\log(2n)) expected queries and O(n11log⁡(2n))O(n^{11}\log(2n)) expected cuts. These upper bounds apply to arbitrary finite nonnegative nonatomic measures, without density, common-support, or strict-positivity assumptions. The randomized bound improves the known cake bound and gives a polynomial expected-query guarantee for chores.

We also prove two lower bounds. For either cake or chores, every exact protocol with a fixed positive success probability requires Ω(n2)\Omega(n^2) expected queries in general, even with arbitrarily many output cuts at no query cost. The quantitative bound is linear in the required success probability. For mixed cake and chores, no uniform finite expected-query bound exists in the signed bracketed model, even with an oracle that always returns the leftmost root, or always returns the rightmost root. This impossibility holds for every fixed positive multiplicative approximation factor and success probability, and has an additive counterpart. It already applies when every agent values the whole resource at one; positive and negative values may have arbitrarily large total variation.

The deterministic chore bound comes from separating compensation from reassignment. Partial allocations can then be combined without requiring their entire permission graphs to agree; a factorial potential bounds the number of original allocations needed. For the randomized bound, we select compensation pieces by a rule stable under deletion of an unprotected sample, reduce rounding discrepancy to a linear dependence on the number of agents, and control exceptional endpoints across repeated correction attempts. Together these refinements reduce the sample budget needed to realize numerical compensation with disjoint pieces. The lower bounds preserve query transcripts while changing envy comparisons. For nonnegative valuations we use localized perturbations. For mixed valuations, a moving frontier separates the recorded query coordinates from a final interval that every acceptable allocation must split. A bound on the cumulative values preserves every first-root answer, including replies at the endpoint. Each refinement makes a positive fraction of the remaining executions fail permanently. Finitely many refinements give one fixed hard input, independently of the protocol’s realized random tape.

Model and main results

The resource is I=[0,1]I = [0,1]. An allocation is a complete partition (A1,…,An)(A_1,\ldots,A_n) into finite unions of intervals. Cake values viv_i and chore costs cic_i are finite nonnegative nonatomic Borel measures. Envy-freeness means vi(Ai)≥vi(Aj)v_i(A_i) \ge v_i(A_j) for cake and ci(Ai)≤ci(Aj)c_i(A_i) \le c_i(A_j) for chores, for every i,ji,j. For mixed cake and chores, viv_i is a finite signed nonatomic measure and larger values are preferred. Individual parts can be good for one agent and bad for another.

An Eval query asks for one agent’s value of a specified interval. For a nonnegative measure, a Cut query specifies [a,b][a,b] and t∈[0,vi([a,b])]t \in[0,v_i([a,b])] and returns any x∈[a,b]x \in[a,b] with vi([a,x])=tv_i([a,x]) = t. For signed measures the legal target interval is [min⁡{0,vi([a,b])},max⁡{0,vi([a,b])}][\min\{0,v_i([a,b])\},\max\{0,v_i([a,b])\}]. The signed oracle may return any legal root; it is not required to return an extremal root. Each lower-bound theorem specifies the allowed root policy. We count all oracle calls as QQ and Cut calls as CC. These counts are distinct from the number of boundaries in the final allocation. Exact real arithmetic and internal computation are uncharged. Our upper bounds are query bounds, without a polynomial bit-complexity claim.

A randomized success is a legal finite return satisfying the required fairness condition. Incorrect returns, illegal calls and nonreturn count as failures. Expected costs include unsuccessful trials. A Las Vegas protocol returns correctly almost surely. The positive algorithms use independent uniform-real samples and exact real computation; the lower bounds allow arbitrary measurable ideal-real randomness.

A measurable randomized protocol has an input-independent tape on a probability space (Ω,F,P)(\Omega,\mathcal{F},\mathbb{P}). Finite transcripts, query actions, and finite interval-output encodings have their standard Borel structures, using countable disjoint unions over lengths and types. The next-action rule is jointly measurable in the tape and the finite transcript. Its actions include requests, finite returns, and query-free nonreturn; this convention does not require nonreturn to be decidable.

Deterministic chores

Theorem 2.1. For n≥3n \ge3 finite nonnegative nonatomic chore costs, a deterministic Eval/Cut protocol returns a complete exactly envy-free allocation using

Q,C≤2nlog⁡2n+O(n).Q, C \le2^{n^{\log_2 n+O(n)}}.

The guarantee holds for every legal Cut response. The one- and two-agent cases have constant-size protocols.

Appendix § 6 gives the construction and the explicit bound n! 225n+18n! \, 2^{25n+18}. The construction defers reassignment until compensation has been paid and bounds the number of snapshots represented by each live allocation using a factorial potential. A 2O(n)2^{O(n)} bound, and in particular the nO(1)2nn^{O(1)}2^n bound known for cake, remain open for chores.

Randomized cake and chores

Theorem 2.2. For every profile of nn finite nonnegative nonatomic measures, interpreted as cake values or as chore costs, a Las Vegas Eval/Cut protocol returns a complete exactly envy-free allocation with

E[Q]=O(n12log⁡(2n)),E[C]=O(n11log⁡(2n)).\mathbb{E}[Q] = O(n^{12}\log(2n)), \qquad\mathbb{E}[C] = O(n^{11}\log(2n)).

The protocol uses exact real arithmetic and independent uniform-real samples. The bounds hold uniformly over profiles and legal measurable nonanticipating Cut policies, including all rejected work.

An oracle policy is a measurable function of the answered query transcript and the current query. The full proof is in Appendix § 11. For cake, the result improves a known polynomial expected-query bound. The same construction supplies a polynomial expected-query bound for chores.

A randomized lower bound

Theorem 2.3. Fix n≥2n \ge2 and p∈(0,1]p \in(0,1]. Suppose a measurable randomized interval-query protocol returns a complete exactly envy-free allocation with probability at least pp on every normalized finite-step cake profile, or on every such chore profile, whose densities lie in [1/2,3/2][1/2,3/2]. Its unconditional expected query count on the uniform profile satisfies

E[Qunif]≥max⁡{0,n(np−1)2,n2p4−1}.\mathbb{E}[Q_{\mathrm{unif}}] \ge\max\left\{0,\frac{n(np-1)}{2},\frac{n^2p}{4}-1\right\}.

The bound already holds for the expected number of answered oracle calls. The protocol may use ideal-real randomness and return allocations with arbitrarily many intervals, choosing their endpoints without oracle calls.

In particular, the lower bound is Ωp(n2)\Omega_p(n^2) for every fixed p>0p>0, with a coefficient linear in pp. The protocol must work on the entire stated class, although the expected cost is charged on the uniform input. The result covers unsuccessful and nonterminating executions. It extends the quadratic lower bound to randomized failure and chores without increasing its order. Appendix § 12 gives the proof.

Mixed cake and chores

For signed valuations, define α\alpha-multiplicative envy-freeness, where 0<α≤10 < \alpha\le1, by the relative-envy condition

vi(Aj)−vi(Ai)≤(1−α)max⁡{∣vi(Ai)∣,∣vi(Aj)∣}(i,j∈[n]).(1)v_i(A_j) - v_i(A_i) \le(1-\alpha)\max\{|v_i(A_i)|, |v_i(A_j)|\} \qquad(i,j \in[n]). \tag*{(1)}

This definition handles either sign and zero values without dividing by a net total. For nonnegative cake values it is the usual guarantee vi(Ai)≥αvi(Aj)v_i(A_i) \ge\alpha v_i(A_j) [3]; for nonnegative chore costs it is ci(Ai)≤ci(Aj)/αc_i(A_i) \le c_i(A_j)/\alpha. At α=1\alpha= 1 it is exact EF. Our hard instances have total value one for every agent. Any allocation satisfying the relative guarantee then gives each agent positive own value, so the condition is equivalent to the usual cake inequality. Lemma H.1 gives the proof. Hardness on this subclass suffices for the general signed domain.

We state additive approximation separately. On profiles normalized by vi(I)=1v_i(I) = 1, additive ε\varepsilon-envy-freeness means vi(Ai)≥vi(Aj)−εv_i(A_i) \ge v_i(A_j) - \varepsilon. This tolerance is in net-value units.

Theorem 2.4. Fix n≥3n \ge3, a success probability p∈(0,1]p \in(0,1], and a multiplicative factor α∈(0,1]\alpha\in(0,1]. For finite signed nonatomic measures, no measurable randomized protocol can guarantee both α\alpha-multiplicative envy-freeness with probability at least pp on every input and a uniform finite expected-query bound. This already holds when vi(I)=1v_i(I) = 1 for every agent. On that normalized subclass, the same conclusion holds for additive ε\varepsilon-envy-freeness for every fixed 0≤ε<10 \le\varepsilon< 1.

The oracle uses signed bracketed Eval/Cut queries. The impossibility holds when every Cut returns the leftmost root, and also when every Cut returns the rightmost root. No common total-variation ceiling is imposed. Ideal-real randomness is allowed, and output cut locations may be chosen without queries, with no bound on their number.

The theorem concerns the information needed to find an allocation. It does not rule out existence, bound the minimum number of output cuts, or require a single input to have infinite expected cost. It already holds for finite piecewise-constant densities. Appendix § 13 proves both approximation statements together through the inequality αvi(Aj)−vi(Ai)≤ε\alpha v_i(A_j) - v_i(A_i) \le\varepsilon, for 0≤ε<α≤10 \le\varepsilon< \alpha\le1. The absence of a common variation ceiling allows increasingly large positive and negative masses to cancel while every net total stays one. The root rule is prescribed before the input and random tape are chosen. The conclusion also rules out uniformly bounded protocols that must work for every legal root selector. It does not cover a class with a fixed common bound on total variation.

Proof overview

Deterministic chores: deferred compensation

A partial chore allocation leaves a residue that must eventually be assigned. Reassigning existing pieces can reduce an agent’s cost and create enough slack to absorb this residue. The difficulty is preserving every other agent’s envy comparison during the reassignment. We record these obligations relative to the original pieces and pay them before changing the allocation.

Each live partial allocation has a directed graph of permitted recipient changes. A package contains one such live allocation and the allocations already frozen to pay its obligations. Its weight is the number of original allocations it contains. A compensation step combines packages that agree on just one source component. Their other components may differ. An Offset SubCore call chooses the donors and the surviving live allocation; only the donors change their physical allocations. The survivor acquires a paid permission. A cycle of paid permissions can then be contracted without moving any material.

The key bound uses a capacity for each component. An unpaid component of size dd has capacity u(d)=8d−1d!u(d)=8^{d-1}d!; paying it multiplies this capacity by 2(d+1)2(d+1). A package’s capacity is the product over its components. Grouping package weights between consecutive powers of two ensures that combining d+1d+1 packages costs at most this multiplier, regardless of which package survives. The inequality

[2(a+1)u(a)][2(b+1)u(b)]≤u(a+b)[2(a+1)u(a)][2(b+1)u(b)]\le u(a+b)

shows that contracting paid components preserves the capacity bound. Every package consequently has weight at most u(n)u(n). There are only poly⁡(n)4n\operatorname{poly}(n)4^n possible classes of next operations, so n!2O(n)n!2^{O(n)} original allocations suffice to keep the process moving until a terminal class permits recursive completion.

The accounting uses actual cost reductions from the original baselines, rather than the whole costs of removed suffixes. Frozen allocations never change again, and every removed piece remains in the unallocated domain. The terminal margins therefore cover the entire remaining resource. Preprocessing, compensation, and recursive endpoint recording preserve the bound n!2O(n)=2nlog⁡2n+O(n)n!2^{O(n)}=2^{n\log_2 n+O(n)}.

Randomized upper bounds: exact repair

The randomized protocol alternates between repairing approximate envy-freeness and creating a comparison that remains safe after the remaining resource is allocated. Repair takes whole existing bundles and an unallocated buffer. An individual-agent quantile grid and independent mixture samples produce a finite value table. Small witness pieces perturb an assignment problem; a maximizing assignment for cake, or minimizing assignment for chores, determines credits or taxes. Disjoint physical payments then make that assignment exactly envy-free while leaving at least three quarters of the buffer. We use the compensation framework of Mackenzie–Suzuki [MS26], with the following improvements.

First, we retain a large compensation domain deterministically. For each row pair, maximize the absolute determinant of two cell-value vectors, then their total mass, allowing repeated cells. Remove their coarse parents from later selection. The two cells control every linear combination of the rows, including the normalizations determined after selection. The total removed value is small. Moreover, if an inserted point is unprotected in the augmented run and its coarse parent survives in the original run, deleting that point leaves the selections unchanged. An exchangeability argument bounds the measure of the exceptional coordinates by the number of protected endpoints divided by the sample count. Outside this set, partial-cell discrepancy is controlled by the largest whole-cell discrepancy. This avoids conditioning a fixed-measure sampling estimate on a domain selected from the same samples.

Second, whole-cell rounding incurs only linear discrepancy. Keep each recipient’s own-value equation exact, and drop a pairwise-discrepancy equation only when it has at most 4k4k fractional coordinates, where kk is the active population. A rank and incidence count guarantees such an equation whenever too many fractional coordinates remain. Supported sorted-slot rounding and trimming preserve fixed zero and one coordinates for real recipients, so each dropped equation stays within 4k4k times the largest cell disagreement. Fresh circular cuts fill the remaining own-value deficits. A maximum-cell envelope gives constant success probability per correction attempt; a stopped retry argument controls the first exceptional endpoint without a factor equal to the number of retries. All inherited boundaries of earlier accepted corrections enter the error estimate.

These changes allow separation parameter λ=Θ(n)\lambda=\Theta(n), L=Θ(n4log⁡(2n))L=\Theta(n^4\log(2n)) witnesses per pair and batch, and m=Θ(n2log⁡(2n))m=\Theta(n^2\log(2n)) samples per trial. No density, common-support, or hunger assumption is needed. An accepted Snapshot trial either completes the allocation or supplies an envy-free partial allocation with a certified positive margin. Prescribed shrinking and whole-bundle transfers turn that margin into a new domination comparison, following the global framework of Psomas [16]. A potential over all original observers increases at committed allocations and is at most n(n−1)n(n-1). Every iteration uses an expected constant number of trials, each costing O(nm)O(nm) queries and O(m)O(m) Cuts, including rejected work. This gives E[Q]=O(n12log⁡(2n))\mathbb{E}[Q] = O(n^{12}\log(2n)) and E[C]=O(n11log⁡(2n))\mathbb{E}[C] = O(n^{11}\log(2n)) for both cake and chores. Explicit zero-value and small-population cases give almost sure termination with a complete allocation.

Randomized lower bound: indistinguishable perturbations

On the uniform profile, every exact envy-free allocation gives each agent length 1/n1/n. We perturb a uniformly chosen agent’s density by a narrow bump inside a wider circular arc, subtracting the bump’s mass uniformly over that arc. The density remains normalized and between 1/21/2 and 3/23/2. The wider arc has length just above 1/n1/n. Unless a recorded query endpoint meets it, all answers remain unchanged. A query detects the perturbation with probability at most approximately 2/n22/n^2: it must query the perturbed agent and meet the arc with one of its endpoints.

If the narrow bump avoids output boundaries, its owner is well defined. Every other perturbed agent strictly envies that owner; reversing the perturbation gives the chore version. Perturbing two distinct agents removes the exception that the perturbed agent owns the bump. Each agent is then selected with probability 2/n2/n, and the detection probability is at most approximately 4/n24/n^2 per query.

One sufficiently small bump width preserves strictly unfair baseline returns and avoids finite output endpoint lists with arbitrarily high probability, even when their expected size is unbounded. Exact replay preserves the other failures. Averaging the success guarantee over the fixed perturbed inputs and then taking the wider arc’s length down to 1/n1/n gives the two terms of the lower bound. Retaining failed executions is essential: it makes the bound linear in the required success probability, rather than applying only to protocols that always succeed.

Mixed resources: signed cancellation

For signed valuations, a finite query history can conceal a final interval that every fair allocation must split. We construct such histories while requiring every Cut to return the leftmost root.

Maintain a frontier ℓ<1\ell< 1. The densities are constant on finitely many intervals before ℓ\ell, and all agents have positive constant density after it. Each resolved interval is either bad for everyone or good for only one agent and sufficiently bad for all the others. This condition ensures that, if one agent receives the entire final interval, the average envy of the other agents toward it exceeds the permitted tolerance. The earlier intervals may be divided arbitrarily; the obstruction does not depend on their remaining whole.

To answer a query to agent jj, leave that agent’s entire valuation unchanged and move the frontier beyond the query coordinates smaller than one. Give every other agent negative density on the newly resolved interval and restore its net total using a positive density on the remaining tail. All cumulative functions stay strictly below one before the endpoint. Earlier roots inside the resolved prefix are unchanged; an earlier root at one is still first because its absolute target level is one. Thus arbitrary legal brackets and negative targets are allowed.

For a randomized protocol, we perform the same construction on measurable sets of tapes. At each query, a row occurring on at least a 1/n1/n fraction of the current tapes is selected, and a fixed frontier captures at least half their coordinates. After a fixed number of queries, another coordinate quantile captures the endpoints of their finite outputs. Those outputs leave the remaining interval unsplit and hence fail. Their transcripts and bundle values remain fixed in all later refinements.

Each batch therefore makes a positive fraction of the remaining tapes fail permanently. Finitely many batches reduce the probability of a correct return within any prescribed query horizon below p/2p/2 on one fixed input. A protocol with success probability at least pp must then exceed that horizon with probability at least p/2p/2. This rules out a uniform finite expected-query bound. Reflection transfers the result to an always-rightmost oracle. The same argument supplies the multiplicative and additive comparisons by changing the density ratios in the resolved intervals.

Related work

Bounded protocols. The general cake protocol of Aziz and Mackenzie [1] and the chore protocol of Dehghani, Farhadi, Hajiaghayi, and Yami [6] establish boundedness with disconnected shares. Our deterministic construction uses the chore compensation framework and the cake SubCore primitive, with the order and tie conventions of Ye and Bai [18 Appendix F]. The latter preprint gives nO(1)2nn^{O(1)}2^n deterministic cake queries. Improving the chore bound to this scale remains open. The snapshot budgets in [6] count intermediate components of the protocol; Table 1 records its general boundedness guarantee.

SettingPrior benchmarkThis paper
Deterministic exact choresA bounded function of nn [6] (SODA 2018)Q,C≤2nlog⁡2n+O(n)Q, C \le2^{n \log_{2} n+O(n)}; Theorem 2.1.
Randomized exact cakeE[Q]=O~(n30)\mathbb{E}[Q] = \widetilde{O}(n^{30}) [MS26] (preprint)E[Q]=O(n12log⁡(2n))\mathbb{E}[Q] = O(n^{12}\log(2n)), E[C]=O(n11log⁡(2n))\mathbb{E}[C] = O(n^{11}\log(2n)); Theorem 2.2.
Randomized exact choresA bounded expected-query guarantee follows from [6]The same polynomial bounds as cake; Theorem 2.2.
Exact cake and chore lower boundsΩ(n2)\Omega(n^{2}) deterministic cake queries [15] (IJCAI 2009)E[Q]≥max⁡{n(np−1)/2,n2p/4−1}\mathbb{E}[Q] \ge\max\{n(np-1)/2, n^{2}p/4-1\}, even with arbitrarily many output cuts at no query cost; Theorem 2.3.
Mixed cake and choresConnected EF existence for signed valuations with positive net totals [5] (SODA 2026)No uniform finite E[Q]\mathbb{E}[Q], even for any fixed positive multiplicative factor and success probability; also for fixed additive ε<1\varepsilon< 1. Theorem 2.4.

Table 1. Four general query-complexity results. QQ counts all queries and CC counts Cut calls. Randomized upper bounds are Las Vegas and use ideal-real sampling. The mixed lower bound holds for both always-leftmost and always-rightmost Cut rules, net totals one, and no common total-variation ceiling. Theorems state the precise oracle and randomness assumptions.

Randomized upper bounds. Mackenzie and Suzuki [MS26, Theorem 1 and Remark 1.1] give a polynomial expected-query protocol for exact cake cutting. We retain its numerical compensation and physical realization framework, and handle both preference directions. Our smaller sample budget follows from stable compensation selection, linear-discrepancy rounding, and endpoint accounting across repeated correction attempts. The assignment sensitivity argument uses [12]; the rounding argument builds on the sorted-slot construction of Shmoys and Tardos [17]. Global completion uses the domination and bundle-transport framework of Psomas [16]. The three recent cake papers [MS26, YB26, Pso26] are cited as versioned preprints.

Lower bounds and approximation. Procaccia [15] proves a quadratic deterministic cake-query lower bound. Farhadi and Hajiaghayi [8] give a proportional chore lower bound in their model. Our exact EF lower bound permits randomized failure and arbitrary finite output fragmentation. A cubic lower bound is announced in [2 Footnote 2] and the thesis’s repository abstract [11]; the cited public thesis version omits the announced proof. We distinguish that announcement from the proved benchmarks in Table 1. For connected approximate cake division, Brânzei and Nisan [4] give query bounds for additive approximation, and Barman and Kulkarni [3] give polynomial-time algorithms with additive and multiplicative guarantees. Our positive upper bounds require exact EF and permit disconnected shares.

Signed valuations. Barman and Verma [5] establish connected envy-free existence for the relevant signed valuations with positive net totals. Our mixed theorem separates existence from uniformly bounded query complexity. The lower bound holds even with an always-leftmost or always-rightmost Cut oracle; its additive tolerance is measured in net-value units. It does not imply hardness for total-variation-normalized approximation. Protocols based on an initial decomposition into regions of constant sign [14] assume access to information that bounded interval queries need not reveal.

References

Deterministic chore division by deferred compensation

The protocol maintains a separate graph of paid permissions for each live snapshot. Paying a permission does not immediately change that snapshot’s allocation. This separates compensation from component contraction: roots can be combined when they agree on one source component, even if all their other components differ. A factorial capacity and grouping by powers of two bound the number of original snapshots that any live package can contain.

Theorem A.1. For nn finite nonnegative nonatomic Borel costs on an interval, a deterministic ordinary Eval/Cut protocol produces a complete exactly envy-free allocation into finite unions of intervals. For n≥3n \ge3, its query and cut counts satisfy

Q,C≤n! 225n+18≤2nlog⁡2n+25n+18.Q,C \le n! \, 2^{25n+18} \le2^{n\log_2 n+25n+18}.

The protocol permits every legal Cut reply and includes all preprocessing, unsuccessful primitive trials, and recursive calls. Exact comparisons and finite computation are free; no time or bit-complexity bound is asserted. For one or two agents, the standard direct protocols suffice.

The Core and near-equal splitter are proved in Appendix § 7. The source SubCore proof is Lemma C.1; the parent-dependent offset implementation is Theorem D.1. The whole-piece augmentation and two-group completion used below are proved in Appendix § 10.

Ordinary queries, preprocessing, and a protected label

All domains are recorded ordered finite unions, with a fixed convention assigning each shared endpoint to one part. Every new endpoint is recorded for the current observers. Cached component costs locate a strict prefix or suffix target in one physical interval. One ordinary Cut supplies the cutting observer’s value, and at most n−1n-1 Evals record the other observers. Zero, full, and known-endpoint targets reuse records. Null components remain present. Thus no disconnected domain is treated as a unit-cost interval query.

At a completed envy-free boundary, an agent with zero cost for the whole remaining domain can receive that domain: her additional own cost is zero, and every other agent’s rival cost only increases. An empty domain is finished immediately. One agent receives everything, and two agents use an equal-own-cost cut followed by cheaper choice. A continuing call thus has n≥3n \ge3 and positive reference costs.

The Core of Theorem B.1 partitions its input into nn equal-cost parents for a designated cutter and returns an envy-free allocation of one prefix of a distinct parent to each agent, including at least one whole parent. If the cutter’s input, own allocation, and residue have costs t,b,ut,b,u, respectively, then

u≤(1−1/n)t,u≤(n−1)(t/n−b).(2)u \le(1-1/n)t,\qquad u \le(n-1)(t/n-b). \tag*{(2)}

References

  1. [1][AM16] 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, pages 416–427, 2016. Corrected full version: arXiv:1604.03655v12, 27 August 2017. URL: https://arxiv.org/abs/1604.03655v12, doi:10.1109/FOCS.2016.52.
  2. [2][AM17] Haris Aziz and Simon Mackenzie. Bounded and envy-free cake cutting. ACM SIGecom Exchanges, 15(2):30–33, 2017. URL: https://www.cse.unsw.edu.au/~haziz/efcake_sigecom.pdf, doi:10.1145/3055589.3055593.DOI
  3. [3][BK23] Siddharth Barman and Pooja Kulkarni. Approximation algorithms for envy-free cake division with connected pieces. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:19, 2023. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.16, doi:10.4230/LIPIcs.ICALP.2023.16.DOI
  4. [4][BN22] Simina Brânzei and Noam Nisan. The query complexity of cake cutting. In Advances in Neural Information Processing Systems, volume 35, pages 37905–37919, 2022. URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/f7a7bb369e48f10e85fce85b67d8c516-Paper-Conference.pdf, doi:10.52202/068431–2747.arxiv.org/abs/1705.02946
  5. [5][BV26] Siddharth Barman and Paritosh Verma. Fair division beyond monotone valuations with applications to equitable graph partitioning. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 6613–6641, 2026. Full author version arXiv:2501.14609v4; Theorem 10 is cited with that version’s numbering. URL: https://arxiv.org/abs/2501.14609v4, doi:10.1137/1.9781611978971.236.
  6. [6][DFHY18] Sina Dehghani, Alireza Farhadi, Mohammadtaghi Hajiaghayi, and Hadi Yami. Envy-free chore division for an arbitrary number of agents. In Proceedings of SODA, pages 2564–2583, 2018. doi:10.1137/1.9781611975031.164.DOI
  7. [7][DS03] Benjamin Doerr and Anand Srivastav. Multicolour discrepancies. Combinatorics, Probability and Computing, 12(4):365–399, 2003. doi:10.1017/S0963548303005662.DOI
  8. [8][FH18] Alireza Farhadi and Mohammadtaghi Hajiaghayi. On the complexity of chore division. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pages 226–232, 2018. URL: https://www.ijcai.org/proceedings/2018/0031.pdf, doi:10.24963/ijcai.2018/31.
  9. [9][FH26] Alireza Farhadi and Mohammadtaghi Hajiaghayi. The query complexity of envy-free division: Lean proofs and supporting materials. Software and verification artifact, 2026. URL: https://github.com/farhadi94/envy-free-division.
  10. [10][GRW11] Christian Glaßer, Christian Reitwießner, and Maximilian Witek. Applications of discrepancy theory in multiobjective approximation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 13 of Leibniz International Proceedings in Informatics, pages 55–65, 2011. Full version: arXiv:1107.0634v1; Theorem 3.1. URL: https://arxiv.org/abs/1107.0634v1, doi:10.4230/LIPIcs.FSTTCS.2011.55. CHING/READINGSEMINAR/PAPERS/kakutanioriginal.pdf, doi:10.1215/S0012-7094-41-00838-4.
  11. [11]Simon Mackenzie. Upper bounds for cake cutting. PhD thesis, University of New South Wales, 2017. Public thesis version, 88 pages. URL: https://hdl.handle.net/1959.4/58448, doi:10.26190/unsworks/19831.
  12. [12]Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda. Active sampling for linear regression beyond the ℓ₂ norm, 2021. arXiv:2111.04888v1, Lemma 2.6. URL: https://arxiv.org/abs/2111.04888v1.
  13. [14]Yuki Okano and Yoshifumi Manabe. A three-player envy-free discrete division protocol for mixed manna. In Theory and Practice of Natural Computing, volume 12494 of Lecture Notes in Computer Science, pages 42–53. Springer, 2020. URL: https://www.ns.kogakuin.ac.jp/manabe/pdf/okanomanna.pdf, doi:10.1007/978-3-030-63000-3_4.
  14. [15]Ariel D. Procaccia. Thou shalt covet thy neighbor’s cake. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, pages 239–244, 2009. URL: https://ijcai.org/Proceedings/09/Papers/049.pdf.
  15. [16]Alexandros Psomas. Cutting a cake for human consumption: An elementary n-agent cake cutting protocol, 2026. arXiv:2610.30370v1, preprint. URL: https://arxiv.org/abs/2610.30370v1.
  16. [17]David B. Shmoys and Éva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62:461–474, 1993. URL: https://www.cs.cornell.edu/people/eva/Approx.Algorithm.Generalized.Assignment.Prob.pdf.DOI
  17. [18]Qilin Ye and Yannan Bai. Cutting down the tower: Single-exponential envy-free cake cutting, 2026. arXiv:2609.05191v2, preprint. URL: https://arxiv.org/abs/2609.05191v2.

Paper details

vlnc:W_ab2zzn4k
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents