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 n O ( 1 ) 2 n n^{O(1)}2^n n O ( 1 ) 2 n deterministic cake queries [18 ] and O ~ ( n 30 ) \widetilde{O}(n^{30}) 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 2 n log 2 n + O ( n ) 2^n\log_2 n+O(n) 2 n log 2 n + O ( n ) queries. For both cake and chores, we give a Las Vegas protocol using O ( n 12 log ( 2 n ) ) O(n^{12}\log(2n)) O ( n 12 log ( 2 n )) expected queries and O ( n 11 log ( 2 n ) ) O(n^{11}\log(2n)) O ( n 11 log ( 2 n )) 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 Ω ( n 2 ) \Omega(n^2) Ω ( 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] I = [ 0 , 1 ] . An allocation is a complete partition ( A 1 , … , A n ) (A_1,\ldots,A_n) ( A 1 , … , A n ) into finite unions of intervals. Cake values v i v_i v i and chore costs c i c_i c i are finite nonnegative nonatomic Borel measures. Envy-freeness means v i ( A i ) ≥ v i ( A j ) v_i(A_i) \ge v_i(A_j) v i ( A i ) ≥ v i ( A j ) for cake and c i ( A i ) ≤ c i ( A j ) c_i(A_i) \le c_i(A_j) c i ( A i ) ≤ c i ( A j ) for chores, for every i , j i,j i , j . For mixed cake and chores, v i v_i v 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] [ a , b ] and t ∈ [ 0 , v i ( [ a , b ] ) ] t \in[0,v_i([a,b])] t ∈ [ 0 , v i ([ a , b ])] and returns any x ∈ [ a , b ] x \in[a,b] x ∈ [ a , b ] with v i ( [ a , x ] ) = t v_i([a,x]) = t v i ([ a , x ]) = t . For signed measures the legal target interval is [ min { 0 , v i ( [ a , b ] ) } , max { 0 , v i ( [ a , b ] ) } ] [\min\{0,v_i([a,b])\},\max\{0,v_i([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 Q Q Q and Cut calls as C C C . 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}) ( Ω , F , 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 ≥ 3 n \ge3 n ≥ 3 finite nonnegative nonatomic chore costs, a deterministic Eval/Cut protocol returns a complete exactly envy-free allocation using
Q , C ≤ 2 n log 2 n + O ( n ) . Q, C \le2^{n^{\log_2 n+O(n)}}. Q , C ≤ 2 n l o g 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 ! 2 25 n + 18 n! \, 2^{25n+18} n ! 2 25 n + 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 2 O ( n ) 2^{O(n)} 2 O ( n ) bound, and in particular the n O ( 1 ) 2 n n^{O(1)}2^n n O ( 1 ) 2 n bound known for cake, remain open for chores.
Randomized cake and chores
Theorem 2.2. For every profile of n n n 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 ( n 12 log ( 2 n ) ) , E [ C ] = O ( n 11 log ( 2 n ) ) . \mathbb{E}[Q] = O(n^{12}\log(2n)), \qquad\mathbb{E}[C] = O(n^{11}\log(2n)). E [ Q ] = O ( n 12 log ( 2 n )) , E [ C ] = O ( n 11 log ( 2 n )) .
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 ≥ 2 n \ge2 n ≥ 2 and p ∈ ( 0 , 1 ] p \in(0,1] p ∈ ( 0 , 1 ] . Suppose a measurable randomized interval-query protocol returns a complete exactly envy-free allocation with probability at least p p p 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] [ 1/2 , 3/2 ] . Its unconditional expected query count on the uniform profile satisfies
E [ Q u n i f ] ≥ max { 0 , n ( n p − 1 ) 2 , n 2 p 4 − 1 } . \mathbb{E}[Q_{\mathrm{unif}}] \ge\max\left\{0,\frac{n(np-1)}{2},\frac{n^2p}{4}-1\right\}. E [ Q unif ] ≥ max { 0 , 2 n ( n p − 1 ) , 4 n 2 p − 1 } . 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 ( n 2 ) \Omega_p(n^2) Ω p ( n 2 ) for every fixed p > 0 p>0 p > 0 , with a coefficient linear in p p p . 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 < α ≤ 1 0 < \alpha\le1 0 < α ≤ 1 , by the relative-envy condition
v i ( A j ) − v i ( A i ) ≤ ( 1 − α ) max { ∣ v i ( A i ) ∣ , ∣ v i ( A j ) ∣ } ( 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)} v i ( A j ) − v i ( A i ) ≤ ( 1 − α ) max { ∣ v i ( A i ) ∣ , ∣ v i ( A j ) ∣ } ( i , j ∈ [ n ]) . (1)
This definition handles either sign and zero values without dividing by a net total. For nonnegative cake values it is the usual guarantee v i ( A i ) ≥ α v i ( A j ) v_i(A_i) \ge\alpha v_i(A_j) v i ( A i ) ≥ α v i ( A j ) [3 ] ; for nonnegative chore costs it is c i ( A i ) ≤ c i ( A j ) / α c_i(A_i) \le c_i(A_j)/\alpha c i ( A i ) ≤ c i ( A j ) / α . At α = 1 \alpha= 1 α = 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 v i ( I ) = 1 v_i(I) = 1 v i ( I ) = 1 , additive ε \varepsilon ε -envy-freeness means v i ( A i ) ≥ v i ( A j ) − ε v_i(A_i) \ge v_i(A_j) - \varepsilon v i ( A i ) ≥ v i ( A j ) − ε . This tolerance is in net-value units.
Theorem 2.4. Fix n ≥ 3 n \ge3 n ≥ 3 , a success probability p ∈ ( 0 , 1 ] p \in(0,1] p ∈ ( 0 , 1 ] , and a multiplicative factor α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] . For finite signed nonatomic measures, no measurable randomized protocol can guarantee both α \alpha α -multiplicative envy-freeness with probability at least p p p on every input and a uniform finite expected-query bound. This already holds when v i ( I ) = 1 v_i(I) = 1 v i ( I ) = 1 for every agent. On that normalized subclass, the same conclusion holds for additive ε \varepsilon ε -envy-freeness for every fixed 0 ≤ ε < 1 0 \le\varepsilon< 1 0 ≤ ε < 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 α v i ( A j ) − v i ( A i ) ≤ ε \alpha v_i(A_j) - v_i(A_i) \le\varepsilon α v i ( A j ) − v i ( A i ) ≤ ε , for 0 ≤ ε < α ≤ 1 0 \le\varepsilon< \alpha\le1 0 ≤ ε < α ≤ 1 . 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 d d d has capacity u ( d ) = 8 d − 1 d ! u(d)=8^{d-1}d! u ( d ) = 8 d − 1 d ! ; paying it multiplies this capacity by 2 ( d + 1 ) 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 + 1 d+1 d + 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) [ 2 ( a + 1 ) u ( a )] [ 2 ( b + 1 ) u ( b )] ≤ u ( a + b )
shows that contracting paid components preserves the capacity bound. Every package consequently has weight at most u ( n ) u(n) u ( n ) . There are only poly ( n ) 4 n \operatorname{poly}(n)4^n poly ( n ) 4 n possible classes of next operations, so n ! 2 O ( n ) n!2^{O(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 ! 2 O ( n ) = 2 n log 2 n + O ( n ) n!2^{O(n)}=2^{n\log_2 n+O(n)} n ! 2 O ( n ) = 2 n l o g 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 4 k 4k 4 k fractional coordinates, where k k k 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 4 k 4k 4 k 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) λ = Θ ( n ) , L = Θ ( n 4 log ( 2 n ) ) L=\Theta(n^4\log(2n)) L = Θ ( n 4 log ( 2 n )) witnesses per pair and batch, and m = Θ ( n 2 log ( 2 n ) ) m=\Theta(n^2\log(2n)) m = Θ ( n 2 log ( 2 n )) 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) n ( n − 1 ) . Every iteration uses an expected constant number of trials, each costing O ( n m ) O(nm) O ( nm ) queries and O ( m ) O(m) O ( m ) Cuts, including rejected work. This gives E [ Q ] = O ( n 12 log ( 2 n ) ) \mathbb{E}[Q] = O(n^{12}\log(2n)) E [ Q ] = O ( n 12 log ( 2 n )) and E [ C ] = O ( n 11 log ( 2 n ) ) \mathbb{E}[C] = O(n^{11}\log(2n)) E [ C ] = O ( n 11 log ( 2 n )) 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 / n 1/n 1/ 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 / 2 1/2 1/2 and 3 / 2 3/2 3/2 . The wider arc has length just above 1 / n 1/n 1/ n . Unless a recorded query endpoint meets it, all answers remain unchanged. A query detects the perturbation with probability at most approximately 2 / n 2 2/n^2 2/ 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 / n 2/n 2/ n , and the detection probability is at most approximately 4 / n 2 4/n^2 4/ 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 / n 1/n 1/ 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 ℓ < 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 j j j , 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 / n 1/n 1/ 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 / 2 p/2 p /2 on one fixed input. A protocol with success probability at least p p p must then exceed that horizon with probability at least p / 2 p/2 p /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 n O ( 1 ) 2 n n^{O(1)}2^n n 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.
Table 1. Four general query-complexity results. Q Q Q counts all queries and C C C 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 n n n 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 ≥ 3 n \ge3 n ≥ 3 , its query and cut counts satisfy
Q , C ≤ n ! 2 25 n + 18 ≤ 2 n log 2 n + 25 n + 18 . Q,C \le n! \, 2^{25n+18} \le2^{n\log_2 n+25n+18}. Q , C ≤ n ! 2 25 n + 18 ≤ 2 n l o g 2 n + 25 n + 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 − 1 n-1 n − 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 ≥ 3 n \ge3 n ≥ 3 and positive reference costs.
The Core of Theorem B.1 partitions its input into n n n 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 , u t,b,u t , 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)} u ≤ ( 1 − 1/ n ) t , u ≤ ( n − 1 ) ( t / n − b ) . (2)
Indeed, one allocated parent has cost t / n t/n t / n , and every other allocated prefix costs at least b b b to the cutter. If u > 0 u>0 u > 0 , the whole-parent recipient is a noncutter and her piece has cutter gap at least u / ( n − 1 ) u/(n-1) u / ( n − 1 ) .
Fix the integers J , H , L J,H,L J , H , L in Section A.6 before querying. Generate J J J Core snapshots on successive residues with one cutter c c c , unless a complete or zero-cost exit occurs. In snapshot s s s , let P s , p P_{s,p} P s , p be the actual prefix originally returned to agent p p p , and put b s , i = C i ( P s , i ) b_{s,i}=C_i(P_{s,i}) b s , i = C i ( P s , i ) . The larger initial cutter parents are not P s , p P_{s,p} P s , p . Record every equalizer
T s , p , i ⊆ P s , p , C i ( T s , p , i ) = b s , i , T_{s,p,i}\subseteq P_{s,p},\qquad C_i(T_{s,p,i})=b_{s,i}, T s , p , i ⊆ P s , p , C i ( T s , p , i ) = b s , i ,
using P s , p P_{s,p} P s , p itself for its owner. Original envy-freeness makes each target feasible. Keep all marks, including coincident and zero marks and marks of agents later declared ineligible. The differences between consecutive nested prefixes form at most n n n original atom sets per piece. An atom set can span several recorded intervals.
Track every original gap g s , i , p = C i ( P s , p ) − b s , i g_{s,i,p}=C_i(P_{s,p})-b_{s,i} g s , i , p = C i ( P s , p ) − b s , i and every observer’s value of every original atom. There are at most
V = J ( n 3 + n 2 ) V=J(n^3+n^2) V = J ( n 3 + n 2 )
observer–value pairs. Choose L L L so that H 2 ( ( n − 1 ) / n ) L ≤ 1 H^2((n-1)/n)^L\le1 H 2 (( n − 1 ) / n ) L ≤ 1 ; the explicit choice in Section A.6 has this property. While a tracked value v v v for observer i i i lies strictly between C i ( R ) / H C_i(R)/H C i ( R ) / H and H C i ( R ) HC_i(R) H C i ( R ) for the current outer residue, make L L L Core calls with cutter i i i . By (2) , v v v becomes large and remains large after every subsequent residue reduction. Each tracked pair triggers at most once, giving at most V L VL V L additional Core calls. These additional allocations remain fixed and do not enlarge the tracked universe.
Let R 0 R_0 R 0 be the resulting outer residue and set r i = C i ( R 0 ) > 0 r_i=C_i(R_0)>0 r i = C i ( R 0 ) > 0 . Every tracked value is either small, at most r i / H r_i/H r i / H , or large, at least H r i Hr_i H r i . Keep these reference costs fixed during the package stage. Set
E s , p = { i : g s , i , p ≤ r i / H } . (3) E_{s,p}=\{i:g_{s,i,p}\le r_i/H\}. \tag*{(3)} E s , p = { i : g s , i , p ≤ r i / H } . (3)
It contains p p p . Order its agents by decreasing equalizer-prefix containment, breaking geometric ties deterministically and putting p p p first at its whole prefix. We retain both each physical mark and its index in this local order.
Lemma A.2 (A common omitted pair). If H > n − 1 H>n-1 H > n − 1 and J = ( S − 1 ) ( n − 1 ) + 1 J=(S-1)(n-1)+1 J = ( S − 1 ) ( n − 1 ) + 1 , there are S S S original snapshots and a label p ∗ ≠ c p_* \ne c p ∗ = c such that c ∉ E s , p ∗ c\notin E_{s,p_*} c ∈ / E s , p ∗ in every selected snapshot.
Proof. Every original snapshot has a noncutter label whose cutter gap is at least its post-snapshot residual cost divided by n − 1 n-1 n − 1 . This is at least r c / ( n − 1 ) > r c / H r_c/(n-1)>r_c/H r c / ( n − 1 ) > r c / H , so separation makes the gap large. Color the snapshot by the least such noncutter label and apply the pigeonhole principle. Unselected original snapshots stay allocated unchanged.
Every later live root is one of these selected originals. The label p ∗ p_* p ∗ therefore always omits c c c , without synchronizing any other gap bit.
Paid permissions and physical packages
A package consists of one live original snapshot and zero or more frozen originals. Different packages contain disjoint originals. Every live root keeps its original identity allocation P s , p P_{s,p} P s , p ; it changes allocation only when it freezes. Frozen roots never change again. Unselected originals and all clearance allocations remain fixed outside the live pool.
Each live root has a directed permission graph containing the self edges. The maintained partition consists of strongly connected blocks, each with a representative. A block has at most one paid outgoing edge, from its representative to an agent outside that block. Normalize the partition by contracting directed cycles of these outgoing edges until its quotient is acyclic. The resulting blocks are the strongly connected components of the permission graph. Normalization changes only graph records: all permissions and all physical allocations remain unchanged. The component containing p ∗ p_* p ∗ always keeps p ∗ p_* p ∗ as representative. Other choices are fixed deterministically.
Write C s C_s C s for the resulting partition in root s s s . These partitions need not agree across roots. For each label p p p , maintain an allowed set R s , p R_{s,p} R s , p , a forbidden set F s , p F_{s,p} F s , p , and an eligible frontier prefix Z s , p Z_{s,p} Z s , p . The allowed set is exactly the outgoing-neighbor set in the permission graph. If C C C is the component of p p p , then
R s , p ⊆ E s , p R_{s,p} \subseteq E_{s,p} R s , p ⊆ E s , p and F s , p ⊆ C F_{s,p} \subseteq C F s , p ⊆ C are disjoint;
every allowed equalizer contains Z s , p Z_{s,p} Z s , p , and every atom between Z s , p Z_{s,p} Z s , p and P s , p P_{s,p} P s , p is small to every observer;
every eligible mark strictly before the frontier in the decreasing prefix order belongs to C C C ;
allowed recipients lie in C C C , except possibly the single paid outgoing target, which is the frontier’s eligible agent.
Initially R s , p = { p } R_{s,p} = \{p\} R s , p = { p } , F s , p = ∅ F_{s,p} = \varnothing F s , p = ∅ , and Z s , p = P s , p Z_{s,p} = P_{s,p} Z s , p = P s , p . Contracting components preserves these properties. In particular, for a component with no paid outgoing edge its representative has only internal allowed recipients and an internal frontier.
A frozen root has a permutation π s \pi_s π s of the recipients and an allocated prefix Y s , p ⊆ P s , p Y_{s,p} \subseteq P_{s,p} Y s , p ⊆ P s , p at each label. All but possibly one label use the matched original equalizer. At the exceptional donor label, the prefix is the complement of an actual suffix returned by SubCore; its recipient’s own cost is at most her original baseline. For a live root, π s \pi_s π s is the identity and Y s , p = P s , p Y_{s,p} = P_{s,p} Y s , p = P s , p . Put U s , p = P s , p ∖ Y s , p U_{s,p} = P_{s,p} \setminus Y_{s,p} U s , p = P s , p ∖ Y s , p . The entire unallocated domain is
U = R_0 \mathbin{\mathaccent\cdot\cup} \bigsqcup_s U_{s,p}. \tag*{(4)}
where \mathaccent\cdot\cup denotes disjoint union. Thus live roots have empty physical complements, although their paid permissions can carry nonzero reserves.
For distinct observer and recipient i , j i, j i , j , define
h s ( i , j , p ) = { [ b s , i − C i ( T s , p , j ) ] + , j ∈ R s , p , 0 , j ∈ F s , p , [ b s , i − C i ( Z s , p ) ] + , otherwise. (5) h_s(i,j,p) =
\begin{cases}
[b_{s,i} - C_i(T_{s,p,j})]^+, & j \in R_{s,p},\\
0, & j \in F_{s,p},\\
[b_{s,i} - C_i(Z_{s,p})]^+, & \text{otherwise.}
\end{cases} \tag*{(5)} h s ( i , j , p ) = ⎩ ⎨ ⎧ [ b s , i − C i ( T s , p , j ) ] + , 0 , [ b s , i − C i ( Z s , p ) ] + , j ∈ R s , p , j ∈ F s , p , otherwise. (5)
For each package, let D i , j , p D_{i,j,p} D i , j , p be the sum of the frozen roots’ actual negative deviations at label p p p allocated to j j j , and let L i , p L_{i,p} L i , p be the sum of their actual own-cost reductions at that label:
D i , j , p = ∑ s f r o z e n 1 { π s ( p ) = j } [ b s , i − C i ( Y s , p ) ] + , L i , p = ∑ s f r o z e n 1 { π s ( p ) = i } ( b s , i − C i ( Y s , p ) ) . D_{i,j,p} = \sum_{s\ \mathrm{frozen}} \mathbf{1}_{\{\pi_s(p)=j\}}[b_{s,i}-C_i(Y_{s,p})]^+,\qquad
L_{i,p} = \sum_{s\ \mathrm{frozen}} \mathbf{1}_{\{\pi_s(p)=i\}}(b_{s,i}-C_i(Y_{s,p})). D i , j , p = s frozen ∑ 1 { π s ( p ) = j } [ b s , i − C i ( Y s , p ) ] + , L i , p = s frozen ∑ 1 { π s ( p ) = i } ( b s , i − C i ( Y s , p )) .
The invariant is
L i , p ≥ D i , j , p + h s ( i , j , p ) ( i ≠ j ) , (6) L_{i,p} \ge D_{i,j,p} + h_s(i,j,p) \qquad(i \ne j), \tag*{(6)} L i , p ≥ D i , j , p + h s ( i , j , p ) ( i = j ) , (6)
where s s s is the live root. For a closed package the reserve is zero. All quantities vanish initially.
Lemma A.3 (Physical margins). For a valid package, let A i A_i A i be its actual bundle for i i i and B i = ∑ s b s , i B_i = \sum_s b_{s,i} B i = ∑ s b s , i . Then
C i ( A i ) = B i − ∑ p L i , p , (7) C_i(A_i) = B_i - \sum_p L_{i,p}, \tag*{(7)} C i ( A i ) = B i − p ∑ L i , p , (7) and, for every i ≠ j i \ne j i = j ,
C i ( A j ) − C i ( A i ) ≥ ∑ s [ C i ( A s , j ) − b s , i ] + . (8) C_i(A_j) - C_i(A_i) \ge\sum_s [C_i(A_{s,j}) - b_{s,i}]^+. \tag*{(8)} C i ( A j ) − C i ( A i ) ≥ s ∑ [ C i ( A s , j ) − b s , i ] + . (8) Closing a live root at its identity allocation preserves these claims. They also hold after summing disjoint packages.
Proof. Each equalizer gives its recipient exactly her original baseline; only actual donor complements reduce own cost. This proves (7) . The total negative deviation of a rival’s bundle is at most ∑ p ( D i , j , p + h s ( i , j , p ) ) \sum_p(D_{i,j,p}+h_s(i,j,p)) ∑ p ( D i , j , p + h s ( i , j , p )) , and hence at most ∑ p L i , p \sum_p L_{i,p} ∑ p L i , p . Subtracting (7) leaves all its positive deviations. A live identity allocation has no negative deviation and no own reduction. Closing it therefore only removes its nonnegative reserve.
Paying one source component
In a normalized root choose a component with no paid outgoing edge; such a component exists because the quotient is acyclic. Let p p p be its representative and C C C its vertex set. Scan the recorded original atoms through the first eligible agent q ∉ C q\notin C q ∈ / C , or through the last eligible mark if there is no such agent. The scan has three outcomes: an all-small outside suffix, a first large atom, or exhaustion. The frontier properties ensure that any previously passed atoms are small. All tests use cached values.
Suppose d + 1 d+1 d + 1 live roots agree on ( p , C ) (p,C) ( p , C ) , where d = ∣ C ∣ d=|C| d = ∣ C ∣ , and all have the first outcome. Their outside agents q s q_s q s and all other components may differ. Offer the original suffixes
W s = P s , p ∖ T s , p , q s . W_s=P_{s,p}\setminus T_{s,p,q_s}. W s = P s , p ∖ T s , p , q s .
Each W s W_s W s consists of at most n n n atoms small to every observer. For any i ∉ C i\notin C i ∈ / C ,
C i ( W s ) ≤ g s , i , p . (9) C_i(W_s)\le g_{s,i,p}. \tag*{(9)} C i ( W s ) ≤ g s , i , p . (9)
Indeed, an eligible outside agent has its equalizer at or below the first outside mark. An ineligible agent has gap at least H r i Hr_i H r i , whereas the suffix costs at most n r i / H nr_i/H n r i / H ; use H 2 > n H^2>n H 2 > n .
Apply clipped Offset SubCore with participants C C C to these d + 1 d+1 d + 1 parents, using utilities [ C i ( D ) − g s , i , p ] + [C_i(D)-g_{s,i,p}]_+ [ C i ( D ) − g s , i , p ] + on suffixes of parent W s W_s W s . It assigns distinct nominal donor roots s j s_j s j to j ∈ C j\in C j ∈ C and leaves one root w w w unused. For the actual retained suffix D j ⊆ W s j D_j\subseteq W_{s_j} D j ⊆ W s j , put a j = [ C j ( D j ) − g s j , j , p ] + a_j=[C_j(D_j)-g_{s_j,j,p}]_+ a j = [ C j ( D j ) − g s j , j , p ] + . Its guarantees are
a i ≥ [ C i ( D j ) − g s j , i , p ] + ( i , j ∈ C ) , (10) a_i\ge[C_i(D_j)-g_{s_j,i,p}]_+ \qquad(i,j\in C), \tag*{(10)} a i ≥ [ C i ( D j ) − g s j , i , p ] + ( i , j ∈ C ) , (10)
a i ≥ [ C i ( W w ) − g w , i , p ] + ( i ∈ C ) . (11) a_i\ge[C_i(W_w)-g_{w,i,p}]_+ \qquad(i\in C). \tag*{(11)} a i ≥ [ C i ( W w ) − g w , i , p ] + ( i ∈ C ) . (11)
The offset primitive operates on recorded finite unions; locating a target uses cached component totals and a genuine original Cut in one interval. Every new endpoint is recorded for the active observers. We use the conservative complete recorded-call bound 5 n 2 2 n + 1 5n^{2^{2n+1}} 5 n 2 2 n + 1 below, including retained-piece records and unsuccessful primitive trials.
Lemma A.4 (Deferred payment). The d + 1 d+1 d + 1 input packages can be replaced by one package with live root w w w . The survivor keeps its original allocation, while its source component acquires the paid edge p → q w p\to q_w p → q w . The physical margin and frontier invariants are preserved.
Proof. If a j > 0 a_j>0 a j > 0 , use an allowed simple path j → p j\to p j → p in donor root s j s_j s j . Together with the new edge p → j p\to j p → j it gives a permutation cycle; use self edges elsewhere. Give j j j the actual complement P s j , p ∖ D j P_{s_j,p}\setminus D_j P s j , p ∖ D j , and give every other changed recipient its matched equalizer. For j = p j=p j = p the permutation is the identity. The actual own reduction is
b s j , j = C j ( P s j , p ∖ D j ) = C j ( D j ) − g s j , j , p = a j . b_{s_j,j}=C_j(P_{s_j,p}\setminus D_j)=C_j(D_j)-g_{s_j,j,p}=a_j. b s j , j = C j ( P s j , p ∖ D j ) = C j ( D j ) − g s j , j , p = a j .
If a j = 0 a_j=0 a j = 0 , make no modification and freeze that nominal donor at its original identity allocation. Thus a negative affine value is never executed or counted as a credit. Every nominal donor freezes, including those with zero credit, and all its frozen ancestors enter the output package once. On the unused root change only the permission records:
R w , p ′ = R w , p ∪ { q w } , F w , p ′ = F w , p ∪ ( C ∖ R w , p ) , Z w , p ′ = T w , p , q w . R'_{w,p}=R_{w,p}\cup\{q_w\},\qquad F'_{w,p}=F_{w,p}\cup(C\setminus R_{w,p}),\qquad Z'_{w,p}=T_{w,p,q_w}. R w , p ′ = R w , p ∪ { q w } , F w , p ′ = F w , p ∪ ( C ∖ R w , p ) , Z w , p ′ = T w , p , q w .
The old frontier and every allowed equalizer contain the new frontier; all newly passed atoms are small. The new target is outside C C C , while all earlier eligible marks belong to C C C . This proves the updated frontier properties without changing the survivor’s allocation.
For completeness, fix i ≠ j i\ne j i = j and let e i , j , p e_{i,j,p} e i , j , p be the additional deficit of the modified donor assigned to j j j , or zero if that assignment is absent or stripped. Extend a i a_i a i by zero outside C C C . Let D ^ , L ^ \widehat{D},\widehat{L} D , L be the sums of the input frozen ledgers. Every other new frozen contribution uses an old allowed edge, so
D i , j , p ′ ≤ D ^ i , j , p + ∑ s ≠ w h s ( i , j , p ) + e i , j , p , L i , p ′ = L ^ i , p + a i . (12) D'_{i,j,p}\le\widehat{D}_{i,j,p}+\sum_{s\ne w}h_s(i,j,p)+e_{i,j,p},\qquad L'_{i,p}=\widehat{L}_{i,p}+a_i. \tag*{(12)} D i , j , p ′ ≤ D i , j , p + s = w ∑ h s ( i , j , p ) + e i , j , p , L i , p ′ = L i , p + a i . (12)
If i , j ∈ C i,j\in C i , j ∈ C , (10) pays e i , j , p e_{i,j,p} e i , j , p , and the new reserve at an internal recipient is at most the old reserve. If i ∈ C i\in C i ∈ C and j ∉ C j\notin C j ∈ / C , no donor is assigned to j j j ; the new reserve is the threshold in (11) . If i ∉ C i\notin C i ∈ / C , (9) makes every new deficit and the new frontier reserve zero. At every other label there is no new own credit or extra deficit; any equalizer deficit is covered by that donor’s old reserve. Consequently
e i , j , p + h w ′ ( i , j , p ) ≤ a i + h w ( i , j , p ) . e_{i,j,p}+h'_w(i,j,p)\le a_i+h_w(i,j,p). e i , j , p + h w ′ ( i , j , p ) ≤ a i + h w ( i , j , p ) .
Adding the input inequalities (6) to (12) proves the output invariant. In particular, no credit is spent simultaneously on a donor deficit and an increased survivor reserve.
Every changed root is partitioned into its actual retained prefixes and complements within the same original pieces. All released ordinary material lies in passed small atoms. This proves the physical identity (4) , including zero-credit assignments.
A paid edge may complete a directed cycle of components. Contract that cycle, remove its now-internal pending edges from the component quotient, and retain them in the permission graph. The merged component is unpaid. This changes neither the physical allocation nor any reserve. No roots outside the current group are discarded or synchronized.
A factorial capacity and a sufficient pool
Define unpaid and paid component capacities by
u ( k ) = 8 k − 1 k ! , v ( k ) = 2 ( k + 1 ) u ( k ) ( k ≥ 1 ) . u(k)=8^{k-1}k!,\qquad v(k)=2(k+1)u(k)\qquad(k\ge1). u ( k ) = 8 k − 1 k ! , v ( k ) = 2 ( k + 1 ) u ( k ) ( k ≥ 1 ) .
For a live package K K K , let w ( K ) w(K) w ( K ) be its number of original snapshots, including frozen ancestors. Its capacity Φ ( K ) \Phi(K) Φ ( K ) is the product of u ( ∣ C ∣ ) u(|C|) u ( ∣ C ∣ ) over unpaid components and v ( ∣ C ∣ ) v(|C|) v ( ∣ C ∣ ) over paid components in its live root. We maintain w ( K ) ≤ Φ ( K ) w(K)\le\Phi(K) w ( K ) ≤ Φ ( K ) .
Lemma A.5 (Capacity under payment and contraction). For positive a , b a,b a , b , v ( a ) v ( b ) ≤ u ( a + b ) v(a)v(b)\le u(a+b) v ( a ) v ( b ) ≤ u ( a + b ) . Contracting a cycle of paid components does not decrease capacity. Every live root has Φ ( K ) ≤ u ( n ) \Phi(K)\le u(n) Φ ( K ) ≤ u ( n ) . Paying an unpaid component of size d d d multiplies its capacity by 2 ( d + 1 ) 2(d+1) 2 ( d + 1 ) .
Proof. The inequality ( a + 1 ) ! ( b + 1 ) ! ≤ 2 ( a + b ) ! (a+1)!(b+1)!\le2(a+b)! ( a + 1 )! ( b + 1 )! ≤ 2 ( a + b )! is equality at b = 1 b=1 b = 1 ; increasing b b b multiplies its left-hand side by b + 2 b+2 b + 2 and its right-hand side by a + b + 1 ≥ b + 2 a+b+1\ge b+2 a + b + 1 ≥ b + 2 . It implies v ( a ) v ( b ) ≤ u ( a + b ) v(a)v(b)\le u(a+b) v ( a ) v ( b ) ≤ u ( a + b ) directly. Repeatedly combine components, using u ( k ) ≤ v ( k ) u(k)\le v(k) u ( k ) ≤ v ( k ) , to obtain ∏ t v ( k t ) ≤ u ( ∑ t k t ) \prod_t v(k_t)\le u(\sum_t k_t) ∏ t v ( k t ) ≤ u ( ∑ t k t ) whenever there are at least two components. This proves both the cycle-contraction claim and the global bound for a partition with at least two components. A single full component has no external target, so it is unpaid and has capacity u ( n ) u(n) u ( n ) . The payment multiplier follows from the definition of v v v .
Group weights into buckets 2 b ≤ w ( K ) < 2 b + 1 2^b \le w(K) < 2^{b+1} 2 b ≤ w ( K ) < 2 b + 1 . If d + 1 d+1 d + 1 packages lie in one bucket and K w K_w K w is the unused root selected by SubCore, then
∑ K w ( K ) < 2 ( d + 1 ) w ( K w ) ≤ 2 ( d + 1 ) Φ ( K w ) . (13) \sum_K w(K) < 2(d+1)w(K_w) \le2(d+1)\Phi(K_w). \tag*{(13)} K ∑ w ( K ) < 2 ( d + 1 ) w ( K w ) ≤ 2 ( d + 1 ) Φ ( K w ) . (13)
Thus the output of Lemma A.4 satisfies its capacity bound when the survivor’s source component is marked paid. Subsequent contractions preserve that bound. Initially each package has weight and capacity one.
Since u ( n ) ≤ 2 4 n 2 u(n) \le2^{4n^2} u ( n ) ≤ 2 4 n 2 , only 4 n 2 + 1 4n^2+1 4 n 2 + 1 buckets are needed. Normalize each root, choose a deterministic unpaid component, and perform its scan. Classify the root as follows:
an ordinary class records ( p , C , b ) (p,C,b) ( p , C , b ) , where p p p is the source representative, C C C its component, and b b b the weight bucket;
an atomic class records ( p , A , B ) (p,A,B) ( p , A , B ) , where A A A is the set of eligible marks preceding the first large atom and B B B is its nonempty large-value mask;
an exhausted class records ( p , A ) (p,A) ( p , A ) , where A = E s , p A=E_{s,p} A = E s , p .
The terminal operations for the last two classes are proved next. There are at most
Λ = n 2 n ( 4 n 2 + 1 ) + n 4 n + n 2 n (14) \Lambda= n2^n(4n^2+1)+n4^n+n2^n \tag*{(14)} Λ = n 2 n ( 4 n 2 + 1 ) + n 4 n + n 2 n (14)
classes in total. Choose
S = n Λ u ( n ) + 1. (15) S=n\Lambda u(n)+1. \tag*{(15)} S = n Λ u ( n ) + 1. (15)
Lemma A.6 (Existence of a next operation). Starting with S S S selected snapshots, every nonterminal pool contains a class with at least n + 1 n+1 n + 1 live roots. An ordinary operation reduces the number of live roots. Hence at most S S S ordinary operations precede a terminal class.
Proof. Ordinary operations combine their input packages into one output package; they do not discard any package outside the group. The total weight of the live pool therefore remains S S S . Each package has weight at most u ( n ) u(n) u ( n ) by Lemma A.5. If every class had at most n n n live roots, the total weight would be at most n Λ u ( n ) < S n\Lambda u(n)<S n Λ u ( n ) < S , a contradiction. Choose any d + 1 d+1 d + 1 members of a populated ordinary class, where d = ∣ C ∣ d=|C| d = ∣ C ∣ , and apply Lemma A.4. Inequality (13) preserves the weight invariant. This freezes d ≥ 1 d\ge1 d ≥ 1 live roots and leaves one survivor. Normalization is finite because every cycle contraction reduces its root’s component count. The stated bound on ordinary operations follows. A populated terminal class supplies all its required roots, since its participant set has size at most n n n . □
This counting argument requires neither equal package sizes nor agreement on whole component partitions. In particular, it has no loss from retaining a largest common target class and no repeated synchronization factor.
Terminal classes and the entire remaining domain
For a terminal class with source label p p p and participant set A A A , select ∣ A ∣ + 1 |A|+1 ∣ A ∣ + 1 roots. In each root, A A A lies inside that root’s chosen source component; those source components need not be equal. Use affine Offset SubCore, with utility C i ( D ) − g s , i , p C_i(D)-g_{s,i,p} C i ( D ) − g s , i , p , on the full suffixes described below. Every participant’s whole offered parent has nonnegative utility. The primitive supplies distinct donor roots, envy-free affine utilities, and at least one whole assigned parent. Install each donor’s p → j p \to j p → j cycle using its own internal allowed return path. Execute every affine assignment, including zero-own and empty ones. Close the unused root and all live packages outside the selected group at their unchanged identity allocations, retaining every frozen ancestor. Thus every package is closed.
The ledger proof is the same donor calculation as (12) , but there is no surviving reserve. Affine envy-freeness pays participants’ rival deficits. Eligible nonparticipants have their equalizers below the offered suffix boundary; ineligible nonparticipants are protected by their large original gap and the small-atom bound, apart from the explicitly extracted large atom below. The scan boundary ensures that they too have nonpositive offered affine utility. Thus all actual deficits are paid, and (8) holds for the full closed allocation.
Lemma A.7 (Atomic extraction). For a populated atomic class ( p , A , B ) (p,A,B) ( p , A , B ) , a terminal call produces an actual unallocated domain X X X with
C i ( X ) ≥ H r i ( i ∈ B ) , C i ( X ) ≤ n 2 r i / H ( i ∉ B ) . (16) C_i(X) \ge H r_i \quad(i \in B), \qquad C_i(X) \le n^2 r_i/H \quad(i \notin B). \tag*{(16)} C i ( X ) ≥ H r i ( i ∈ B ) , C i ( X ) ≤ n 2 r i / H ( i ∈ / B ) . (16) Both A A A and B B B are nonempty proper subsets of the agents. The remaining unallocated domain R = U ∖ X R = U \setminus X R = U ∖ X is disjoint from X X X and satisfies
r i ≤ C i ( R ) ≤ ( 1 + J n 2 / H ) r i . (17) r_i \le C_i(R) \le(1 + Jn^2/H)r_i. \tag*{(17)} r i ≤ C i ( R ) ≤ ( 1 + J n 2 / H ) r i . (17)
Proof. Let F s F_s F s be the first large atom in each selected root. Offer the entire original suffix through its left boundary. The eligible agents whose marks are at or to the right of its right boundary are exactly A A A . They include p p p and lie in the chosen component. Their whole affine utilities are nonnegative. Every other eligible mark lies at or to the left of the left boundary. For an ineligible observer whose mark were strictly to its right, the gap would consist only of the already passed small atoms, contradicting H 2 > n H^2 > n H 2 > n . These facts justify the terminal ledger calculation for every observer.
Let X X X be the union of the actual assigned suffixes. The whole assigned parent contains an entire F s F_s F s , giving the lower bound for every i ∈ B i \in B i ∈ B . For i ∉ B i \notin B i ∈ / B , every offered parent consists of at most n n n atoms small to i i i , and at most n n n parents are assigned. This gives the upper bound. The affine whole-parent guarantee is essential: no assignment is stripped merely because its own affine value is zero.
The scan ends at an eligible mark at or below the large atom’s left boundary. This agent is outside A A A , and its small original gap contains the atom, so it is outside B B B as well. Thus both sets are proper, while p ∈ A p \in A p ∈ A and the definition of a large atom gives B ≠ ∅ B \ne\varnothing B = ∅ .
Each live root was physically unchanged before this terminal call. Its actual retained prefix and actual removed suffix partition each original piece. At the donor label all removed material belongs to X X X ; all other newly released material uses passed small atoms. Previously frozen complements also use small atoms. Charge each original atom once to this physical union. There are at most J n 2 Jn^2 J n 2 such atoms, while R 0 R_0 R 0 remains untouched and lies in R R R . This proves (17) and the exact disjoint decomposition of all remaining material. □ \square □
Lemma A.8 (Exhausted termination). For a populated exhausted class ( p , A ) (p,A) ( p , A ) , A A A is nonempty and proper. After its terminal call, every observer outside A A A has a margin against every recipient in A A A at least ( H − n / H ) r i (H-n/H)r_i ( H − n / H ) r i . The entire unallocated domain satisfies (17) and can be recursively divided among the strictly smaller population N ∖ A N \setminus A N ∖ A .
Proof. Offer the complete suffix through the last eligible mark. Here p ∈ A ⊆ C s p \in A \subseteq C_s p ∈ A ⊆ C s in every selected root, and every offered suffix is all-small. If one selected source component is proper, then A A A is proper. Otherwise the representative is p ∗ p_{\ast} p ∗ , and the omitted cutter c c c from Lemma A.2 does not belong to A A A .
For i ∉ A i \notin A i ∈ / A and each assigned j ∈ A j \in A j ∈ A , the distinct donor root s j s_j s j has g s j , i , p ≥ H r i g_{s_j,i,p} \ge Hr_i g s j , i , p ≥ H r i . Its removed suffix costs at most n r i / H nr_i/H n r i / H . Its actual retained piece assigned to j j j therefore has positive deviation at least ( H − n / H ) r i (H-n/H)r_i ( H − n / H ) r i from observer i i i ’s baseline. Lemma A.3 preserves this deviation as an aggregate margin, including all frozen ancestors. All released material is small, so the same atom count as above proves (17) .
Our parameters give H ≥ J n 2 H \ge Jn^2 H ≥ J n 2 and H − n / H ≥ 2 H-n/H \ge2 H − n / H ≥ 2 . Each margin thus covers the entire remaining domain. Recursively divide that exact domain among N ∖ A N \setminus A N ∖ A . Their internal comparisons follow by adding envy-free allocations; comparisons to A A A are paid by these whole-domain margins. Agents in A A A receive nothing further, so their comparisons cannot worsen.
Completion and full query accounting
Set S S S as in (15) and choose
J = ( S − 1 ) ( n − 1 ) + 1 , H = 2 n + 5 J n 3 , L = n ( 2 n 2 + 28 n + 16 ) . J=(S-1)(n-1)+1,\qquad H=2^{n+5}Jn^3,\qquad L=n(2n^2+28n+16). J = ( S − 1 ) ( n − 1 ) + 1 , H = 2 n + 5 J n 3 , L = n ( 2 n 2 + 28 n + 16 ) .
These choices give H > n − 1 H>n-1 H > n − 1 , H 2 > n H^2>n H 2 > n , H ≥ J n 2 H\ge Jn^2 H ≥ J n 2 , and H ≥ n + 2 H\ge n+2 H ≥ n + 2 . The estimates below also give H 2 ≤ 2 2 n 2 + 28 n + 16 H^2\le2^{2n^2+28n+16} H 2 ≤ 2 2 n 2 + 28 n + 16 . Since ( ( n − 1 ) / n ) n ≤ 1 / 2 \left((n-1)/n\right)^n\le1/2 ( ( n − 1 ) / n ) n ≤ 1/2 for n ≥ 2 n\ge2 n ≥ 2 , this L L L satisfies the clearance requirement H 2 ( ( n − 1 ) / n ) L ≤ 1 H^2\left((n-1)/n\right)^L\le1 H 2 ( ( n − 1 ) / n ) L ≤ 1 .
In the atomic branch put α = 2 n + 2 \alpha=2^{n+2} α = 2 n + 2 . The scale satisfies H ≥ 2 α H\ge2\alpha H ≥ 2 α and H ≥ n 2 α H\ge n^2\alpha H ≥ n 2 α . Hence (16) and (17) imply
C i ( X ) ≥ α C i ( R ) ( i ∈ B ) , C i ( R ) ≥ α C i ( X ) ( i ∉ B ) . C_i(X)\ge\alpha C_i(R)\quad(i\in B),\qquad C_i(R)\ge\alpha C_i(X)\quad(i\notin B). C i ( X ) ≥ α C i ( R ) ( i ∈ B ) , C i ( R ) ≥ α C i ( X ) ( i ∈ / B ) .
Apply the two-group completion of Lemma E.2 to these actual disjoint recorded domains. Its preparation uses at most 19 ⋅ 2 n 19\cdot2^n 19 ⋅ 2 n cuts and 19 n 2 n 19n2^n 19 n 2 n recorded queries; its two children have positive complementary populations strictly smaller than n n n . The exhausted branch has one strictly smaller child. Attaching the fixed clearance allocations then covers the full input domain without envy.
We give conservative counts for the physical implementations, including all endpoint records. The Core bound n 2 + n 3 [ 2 n − 2 n − 1 − 1 ] ≤ 2 n 3 4 n n^2+n^3\left[\frac{2n-2}{n-1}-1\right]\le2n^34^n n 2 + n 3 [ n − 1 2 n − 2 − 1 ] ≤ 2 n 3 4 n , together with its initial partition and equalizer records, bounds a complete snapshot by 5 n 5n 5 n times that Core allowance, hence by 10 n 4 4 n 10n^44^n 10 n 4 4 n queries. The recorded offset primitive, including its masks and final retained-piece tables, costs at most 5 n 2 2 n + 1 5n^22^{n+1} 5 n 2 2 n + 1 . Preprocessing makes at most N s n a p = J + J ( n 2 + n 3 ) L N_{\mathrm{snap}}=J+J(n^2+n^3)L N snap = J + J ( n 2 + n 3 ) L snapshot calls. The physical prefix and terminal batch use at most S + 1 S+1 S + 1 offset calls. From (14) –(15) ,
S ≤ 8 n 4 32 n n ! , J ≤ 8 n 5 32 n n ! , H ≤ 256 n 8 64 n n ! ≤ n ! 2 14 n + 8 . S\le8n^432^nn!,\qquad J\le8n^532^nn!,\qquad H\le256n^864^nn!\le n!2^{14n+8}. S ≤ 8 n 4 3 2 n n ! , J ≤ 8 n 5 3 2 n n ! , H ≤ 256 n 8 6 4 n n ! ≤ n ! 2 14 n + 8 .
Using n ! ≤ n n ≤ 2 n 2 n!\le n^n\le2^{n^2} n ! ≤ n n ≤ 2 n 2 gives the stated bound on H 2 H^2 H 2 and L ≤ 46 n 3 L\le46n^3 L ≤ 46 n 3 . Consequently, for n ≥ 3 n\ge3 n ≥ 3 ,
N s n a p ≤ 93 J n 6 , N_{\mathrm{snap}}\le93Jn^6, N snap ≤ 93 J n 6 ,
N s n a p Q s n a p ≤ 7440 n 15 128 n n ! ≤ n ! 2 22 n + 13 , N_{\mathrm{snap}}Q_{\mathrm{snap}}\le7440n^{15}128^nn!\le n!2^{22n+13}, N snap Q snap ≤ 7440 n 15 12 8 n n ! ≤ n ! 2 22 n + 13 ,
( S + 1 ) Q o f f ≤ 160 n 7 64 n n ! ≤ n ! 2 13 n + 8 , (S+1)Q_{\mathrm{off}}\le160n^764^nn!\le n!2^{13n+8}, ( S + 1 ) Q off ≤ 160 n 7 6 4 n n ! ≤ n ! 2 13 n + 8 ,
19 n 2 n ≤ n ! 2 2 n + 5 . 19n2^n\le n!2^{2n+5}. 19 n 2 n ≤ n ! 2 2 n + 5 .
Their sum is at most E ( n ) = n ! 2 22 n + 15 E(n)=n!2^{22n+15} E ( n ) = n ! 2 22 n + 15 . The same local allowance bounds cuts, since every cut is a counted query. All masks, graph tests, contractions, weight buckets, and cached suffix values require no further queries.
It remains to include the actual recursive calls. If a child of size k k k is executed inside a population of size m m m , charge its native query count plus m m m records for each of its new Cut endpoints. Its endpoint provenance ensures that inherited endpoints require no new query. Thus a child with native bounds ( Q k , C k ) (Q_k,C_k) ( Q k , C k ) costs at most Q k + m C k Q_k+mC_k Q k + m C k queries and C k C_k C k cuts to its parent. This charges all ambient observer recording.
The recursion has at most 2 n − 1 2n-1 2 n − 1 nodes: two-child steps partition the active population, and one-child steps discard at least one agent. Along an ancestor chain the population strictly decreases, so the total recording charge per native cut is at most n 2 n^2 n 2 . Since E E E is monotone, the recursive query count is therefore at most
( 2 n − 1 ) ( E ( n ) + n 2 E ( n ) ) ≤ n ! 2 25 n + 17 . (2n-1)(E(n)+n^2E(n)) \le n!2^{25n+17}. ( 2 n − 1 ) ( E ( n ) + n 2 E ( n )) ≤ n ! 2 25 n + 17 .
The direct one- and two-agent cases fit the same allowance. Finally, recording the initial n n n total costs adds n n n Eval queries, absorbed in n ! 2 25 n + 18 n!2^{25n+18} n ! 2 25 n + 18 . Every output coordinate is an input endpoint or an actual Cut reply. Assigning the left endpoint to one fixed agent adds no query and changes no cost by nonatomicity. This proves Theorem A.1 on the closed interval.
Canonical prefix states and deterministic chore primitives
We give the prefix Core used in the deterministic chore construction, its cached compensation interface, and a whole-cell near-equal partition primitive. Costs throughout this section are finite, nonnegative, nonatomic measures. All queries are individual ordinary interval queries. A Cut may return any legal root, including any point of a plateau. An ordered finite union is represented by its component intervals and their recorded costs. Its prefix consists of initial components and, possibly, a prefix of one further component. Endpoint costs are recorded for every observer in the enclosing call. No query to a difference of measures, an infinitesimally perturbed measure, or a moving window is used.
Theorem B.1 (Chore Core). Let n ≥ 2 n \ge2 n ≥ 2 , let R R R be a recorded ordered finite union, and fix a cutter c c c . There is a deterministic protocol with the following alternatives. If some agent has zero cost for R R R , it gives R R R to that agent and empty bundles to the others, completing an envy-free allocation. Otherwise it cuts R R R into n n n parents of equal cutter cost and returns an envy-free allocation of one prefix from each of the n n n distinct parents, with at least one parent allocated whole. The residue is the exact complementary union of suffixes. Writing
T n = n 2 ( 2 n − 2 n − 1 − 1 ) , T_n=n^2\left(\frac{2n-2}{n-1}-1\right), T n = n 2 ( n − 1 2 n − 2 − 1 ) , the protocol uses at most n − 1 + T n n-1+T_n n − 1 + T n Cut queries and n 2 + n T n n^2+nT_n n 2 + n T n total queries, including all exploratory queries and endpoint recording. In the prefix alternative, if R ′ R' R ′ is the residue, then
C c ( R ′ ) ≤ n − 1 n C c ( R ) . C_c(R') \le\frac{n-1}{n}C_c(R). C c ( R ′ ) ≤ n n − 1 C c ( R ) . If j j j receives a whole parent and A i A_i A i denotes agent i i i ’s returned bundle, then
C c ( A j ) − C c ( A c ) ≥ C c ( R ′ ) n − 1 . C_c(A_j)-C_c(A_c) \ge\frac{C_c(R')}{n-1}. C c ( A j ) − C c ( A c ) ≥ n − 1 C c ( R ′ ) . The bounds assume that inherited component costs are cached; uncached input components must be evaluated separately.
The proof uses continuous existence only to certify the success of a finite dynamic program. The protocol does not compute a fixed point. Its Cut bound is O ( n 3 / 24 n ) O(n^{3/24^n}) O ( n 3/2 4 n ) and its total query bound is O ( n 5 / 24 n ) O(n^{5/24^n}) O ( n 5/2 4 n ) ; these are bounds for this primitive, not for a complete single-exponential fair-division protocol.
Hungry existence and an anchored order
A cost is hungry on a parent if it is positive on every nondegenerate subinterval in its component order. For this existence argument, parameterize each parent by [ 0 , 1 ] [0,1] [ 0 , 1 ] . Its prefix-cost functions are then continuous and strictly increasing. The parents need not have equal costs.
Lemma B.2 (Local matching). Let a bipartite graph on k k k agents and k k k parents contain a perfect matching . For every permitted pair ( i , j ) (i,j) ( i , j ) let f i j : [ 0 , δ ] → R ≥ 0 f_{ij}:[0,\delta]\to\mathbb{R}_{\ge0} f ij : [ 0 , δ ] → R ≥ 0 be continuous and strictly increasing, with f i j ( 0 ) = 0 f_{ij}(0)=0 f ij ( 0 ) = 0 , where δ > 0 \delta>0 δ > 0 . There are nonnegative y j y_j y j with ∑ j y j = δ \sum_j y_j=\delta ∑ j y j = δ and a perfect matching π \pi π of permitted pairs such that π ( i ) \pi(i) π ( i ) minimizes f i j ( y j ) f_{ij}(y_j) f ij ( y j ) among agent i i i ’s permitted parents.
Proof. Relabel an existing perfect matching as ( i , i ) (i,i) ( i , i ) . Let
Y = { y ≥ 0 : ∑ j y j = δ } , D = { d ≥ 0 : ∑ j d j = k } . Y=\{y\ge0:\sum_j y_j=\delta\},\qquad D=\{d\ge0:\sum_j d_j=k\}. Y = { y ≥ 0 : j ∑ y j = δ } , D = { d ≥ 0 : j ∑ d j = k } . For y ∈ Y y\in Y y ∈ Y , allow each agent to choose any probability distribution supported on her permitted minimizers of f i j ( y j ) f_{ij}(y_j) f ij ( y j ) , and let D ( y ) D(y) D ( y ) be the set of resulting column sums. This correspondence is nonempty, compact, convex-valued, and upper hemicontinuous. Indeed, finite continuous minimization has a closed graph, row distributions lie in compact simplices, and projecting the compact graph of their product preserves the closed-graph property. The same properties hold for
Y ( d ) = arg max z ∈ Y ∑ j z j d j . Y(d)=\operatorname*{arg\,max}_{z\in Y}\sum_j z_jd_j. Y ( d ) = z ∈ Y arg max j ∑ z j d j . Kakutani’s theorem [Kak41], applied on Y × D Y\times D Y × D to ( y , d ) ↦ Y ( d ) × D ( y ) (y,d)\mapsto Y(d)\times D(y) ( y , d ) ↦ Y ( d ) × D ( y ) , gives y ∈ Y ( d ) y\in Y(d) y ∈ Y ( d ) and d ∈ D ( y ) d\in D(y) d ∈ D ( y ) .
Put Z = { j : y j = 0 } Z=\{j:y_j=0\} Z = { j : y j = 0 } and P = { j : y j > 0 } P=\{j:y_j>0\} P = { j : y j > 0 } . Each of the ∣ Z ∣ |Z| ∣ Z ∣ agents whose original matched parent is in Z Z Z can attain incremental cost zero, whereas every permitted parent in P P P has positive incremental cost. Those agents place all demand in Z Z Z , so ∑ j ∈ Z d j ≥ ∣ Z ∣ \sum_{j\in Z}d_j\ge|Z| ∑ j ∈ Z d j ≥ ∣ Z ∣ . Since y y y maximizes the linear form, every j ∈ P j\in P j ∈ P has d j = M = max ℓ d ℓ d_j=M=\max_\ell d_\ell d j = M = max ℓ d ℓ . Hence
k = ∣ P ∣ M + ∑ j ∈ Z d j ≥ ∣ P ∣ M + ∣ Z ∣ . k=|P|M+\sum_{j\in Z}d_j\ge|P|M+|Z|. k = ∣ P ∣ M + j ∈ Z ∑ d j ≥ ∣ P ∣ M + ∣ Z ∣. Because P P P is nonempty, M ≤ 1 M\le1 M ≤ 1 . The average column sum is one, so every column sum equals one. The row distributions therefore form a doubly stochastic matrix supported on permitted minimizers. Its support satisfies Hall’s condition: for any set of rows, its unit total per row must be carried by neighbouring columns of capacity one. A perfect matching in the support proves the claim.
An envy-free prefix state on equally sized agent and parent sets consists of one prefix from each parent and a bijection of these prefixes to the agents. Every assigned prefix must minimize its owner’s cost among all prefixes in the state. Call such a state anchored if its agents admit an order in which each nonwhole assigned prefix has the same cost, to its owner, as an earlier assigned prefix. Whole prefixes need no earlier anchor.
Lemma B.3 (Anchored existence). For any balanced finite sets of hungry agents and parents, an anchored envy-free prefix state exists.
Proof. For each bijection, the envy-free constraints define a closed subset of the cube of prefix endpoints. The finite union over bijections is compact and nonempty, since all-empty prefixes are feasible. Choose a state maximizing the sum of its endpoints.
Suppose a nonempty group S S S of owners has only nonwhole prefixes and every member strictly prefers her own prefix to every prefix outside S S S . Write b i b_i b i for each member’s current own cost. Inside S S S , permit ( i , j ) (i,j) ( i , j ) exactly when parent j j j ’s current prefix costs b i b_i b i to agent i i i ; the current ownership is a perfect matching. If the old endpoint of j j j is x j x_j x j , use
f i j ( y ) = C i ( P j ( x j + y ) ) − b i f_{ij}(y) = C_i(P_j(x_j+y))-b_i f ij ( y ) = C i ( P j ( x j + y )) − b i
on permitted pairs. Choose δ > 0 \delta> 0 δ > 0 below all available endpoint slack and small enough that moving any endpoint by at most δ \delta δ changes any relevant cost by less than half of every positive old comparison gap from a member of S S S to a nontied internal or outside prefix. There are finitely many gaps, and continuity provides this choice; when there are none, only endpoint caps need be respected.
Lemma B.2 now enlarges these prefixes by a total of δ \delta δ and reassigns them along old tie edges. Its minimum condition preserves comparisons on the old ties. The choice of δ \delta δ preserves strict comparisons. Outside owners retain their own prefixes and see every changed prefix enlarge, so their envy-free inequalities persist by nonnegativity. This contradicts maximality.
Consequently at least one prefix is whole: otherwise S S S could be all owners. List all whole-prefix owners first. If some owners remain, their group cannot satisfy the preceding strict-separation condition. Since the state is envy-free, some remaining owner must tie an already listed prefix. Append that owner and repeat. This produces the required anchored order.
Canonical states on balanced subsets
The following finite arguments also apply to lexicographically ordered formal costs. They require only that every observer’s cost increase strictly along each parent’s ordered prefix states. For a prefix vector x x x , write b i ( x ) = min p C i ( x p ) b_i(x)=\min_p C_i(x_p) b i ( x ) = min p C i ( x p ) , which is independent of the chosen envy-free matching.
Lemma B.4 (Sign classes and lattice). Let x , y x,y x , y be envy-free states on the same balanced sets, with matchings π x , π y \pi_x,\pi_y π x , π y . Put
J + = { p : x p < y p } , A = { i : b i ( x ) < b i ( y ) } . J_+ = \{p:x_p<y_p\},\qquad A=\{i:b_i(x)<b_i(y)\}. J + = { p : x p < y p } , A = { i : b i ( x ) < b i ( y )} . Then π x ( A ) = π y ( A ) = J + \pi_x(A)=\pi_y(A)=J_+ π x ( A ) = π y ( A ) = J + . Coordinatewise minimum and maximum of the two prefix vectors are envy-free; their own costs are respectively the minimum and maximum of the two old own costs.
Proof. For i ∈ A i\in A i ∈ A , envy-freeness implies
C i ( x π x ( i ) ) = b i ( x ) < b i ( y ) ≤ C i ( y π x ( i ) ) , C_i(x_{\pi_x(i)})=b_i(x)<b_i(y)\le C_i(y_{\pi_x(i)}), C i ( x π x ( i ) ) = b i ( x ) < b i ( y ) ≤ C i ( y π x ( i ) ) , so π x ( A ) ⊆ J + \pi_x(A)\subseteq J_+ π x ( A ) ⊆ J + . Conversely, for p ∈ J + p\in J_+ p ∈ J + and i = π y − 1 ( p ) i=\pi_y^{-1}(p) i = π y − 1 ( p ) , strict within-parent increase gives
b i ( x ) ≤ C i ( x p ) < C i ( y p ) = b i ( y ) . b_i(x)\le C_i(x_p)<C_i(y_p)=b_i(y). b i ( x ) ≤ C i ( x p ) < C i ( y p ) = b i ( y ) . Thus π y − 1 ( J + ) ⊆ A \pi_y^{-1}(J_+)\subseteq A π y − 1 ( J + ) ⊆ A . Bijection and finite cardinality force equality in both inclusions. Swapping x , y x,y x , y gives the same identity for B = { i : b i ( y ) < b i ( x ) } B=\{i:b_i(y)<b_i(x)\} B = { i : b i ( y ) < b i ( x )} and J − = { p : y p < x p } J_-=\{p:y_p<x_p\} J − = { p : y p < x p } . The remaining agents are matched to equal-coordinate parents by both matchings.
For the coordinatewise maximum, use π y \pi_y π y on A A A and π x \pi_x π x on the other agents. Its images partition the parents into the three sign classes, and each assigned cost is max { b i ( x ) , b i ( y ) } \max\{b_i(x),b_i(y)\} max { b i ( x ) , b i ( y )} . Every other
maximum prefix costs at least both old minima. For the coordinatewise minimum, use π x \pi_x π x on A A A , π y \pi_y π y on B B B , and π x \pi_x π x on the remaining agents. Its assigned cost is the smaller old minimum; every other minimum prefix costs at least that value. These are the required envy-free matchings.
Lemma B.5 (Anchored maximality). An anchored envy-free prefix vector is coordinatewise at least every envy-free prefix vector on the same balanced subsets. In particular, all anchored states on those subsets have the same prefix vector.
Proof. Let x x x be anchored and y y y be any envy-free state. If some parent grows from x x x to y y y , the sign-class identity says that its original x x x -owner i i i satisfies b i ( y ) > b i ( x ) b_i(y) > b_i(x) b i ( y ) > b i ( x ) . Its old prefix cannot have been whole. Let p ′ p' p ′ be an earlier anchor, so C i ( x p ′ ) = b i ( x ) C_i(x_{p'}) = b_i(x) C i ( x p ′ ) = b i ( x ) . Then
C i ( y p ′ ) ≥ b i ( y ) > b i ( x ) = C i ( x p ′ ) , C_i(y_{p'}) \ge b_i(y) > b_i(x) = C_i(x_{p'}), C i ( y p ′ ) ≥ b i ( y ) > b i ( x ) = C i ( x p ′ ) ,
and p ′ p' p ′ also grows. Repeating with the original owner of this anchor gives a strictly decreasing sequence of positions in the anchoring order. Its first position is a whole prefix, which cannot grow. This contradiction proves y ≤ x y \le x y ≤ x . Applying the conclusion in both directions proves uniqueness for two anchored vectors.
Strictness is essential here. We do not claim that coordinatewise maximum preserves envy-freeness for arbitrary unperturbed plateau states. Nor do we discard arbitrary smaller partial states in favor of larger ones. The states retained below are anchored and hence canonical.
The dynamic program and its hungry correctness
On n n n labeled parents and n n n agents, store one state for every nonempty pair ( I , P ) (I, P) ( I , P ) of equally sized subsets. Process the pairs in increasing size. A singleton state assigns its sole parent whole. For a state of size k ≥ 2 k \ge2 k ≥ 2 , try each ( i , p ) ∈ I × P (i,p) \in I \times P ( i , p ) ∈ I × P in a fixed order:
Read the stored state on ( I ∖ { i } , P ∖ { p } ) (I \setminus\{i\}, P \setminus\{p\}) ( I ∖ { i } , P ∖ { p }) . Let t t t be agent i i i ’s minimum cost of its prefixes.
If C i ( P p ) ≤ t C_i(P_p) \le t C i ( P p ) ≤ t , use P p P_p P p whole. Otherwise obtain a prefix of P p P_p P p costing exactly t t t to $i.
Retain the smaller state’s matching, append the new pair, and test all envy-free inequalities. Store the first successful candidate.
Every stored state is anchored: retain the smaller state’s order, append i i i , and, when its prefix is not whole, use an earlier minimizer attaining t t t as its anchor. Every comparison uses recorded costs.
Lemma B.6 (Hungry dynamic program). For hungry costs, every state succeeds and stores the canonical anchored prefix vector for its two subsets.
Proof. Induct on the subset size. By Lemma B.3 , choose an anchored witness for the present subsets and let ( i , p ) (i,p) ( i , p ) be its last pair. Deleting that pair leaves an anchored envy-free state on the smaller subsets. Lemma B.5 identifies its prefix vector with the stored smaller vector.
The stored smaller matching can differ from the witness restriction. This does not change any old agent’s own cost: it is the minimum of the identical collection of prefixes. Thus all comparisons of old agents to the new prefix have the witness values, independently of that matching.
If the last witness prefix is whole, its cost to i i i is at most every earlier prefix, and the whole-parent branch reproduces it. Otherwise its anchor and envy-freeness imply that t t t equals its witness own cost. Hunger makes the target root unique, so the trimming branch reproduces the same prefix. The candidate for ( i , p ) (i,p) ( i , p ) therefore succeeds. Every successful candidate is anchored, and Lemma B.5 completes the induction.
Persistent records for arbitrary legal roots
For each parent maintain one ordered list of prefix records, shared by all states and failed candidates. A record has a physical endpoint, all actual prefix costs, and one rational secondary label θ i \theta_i θ i for each observer. Compare costs lexicographically as
( C i ( physical prefix ) , θ i ( record ) ) . (C_i(\text{physical prefix}),\theta_i(\text{record})). ( C i ( physical prefix ) , θ i ( record )) .
Physical endpoints are nondecreasing along the list. Formal costs increase strictly for every observer. Initialize the empty record with ( 0 , 0 ) (0,0) ( 0 , 0 ) and the whole record with ( C i ( P ) , 1 ) (C_i(P),1) ( C i ( P ) , 1 ) . Distinct records may have the same physical endpoint, including on physically empty parents. The whole and empty records remain distinct formal records even in that case.
Run the dynamic program using formal costs. Its trim targets are formal costs of already stored records. Such a target is never below the empty record. When a whole-parent comparison fails, the target lies below the whole record. If the parent already has the target formal cost for the trimming observer, reuse that record. Otherwise find adjacent records strictly bracketing it. Let their physical endpoints be l ≤ r l \le r l ≤ r and let v v v be the target’s real cost.
If a neighbor has real cost v v v , reuse that physical endpoint and insert a new formal record between the two neighbors. Otherwise their real costs strictly bracket v v v . Cached component costs locate a component containing the target; one ordinary Cut obtains a physical root, with existing component-boundary roots reused when available. Nonnegativity and strict bracketing imply that every legal returned root lies between l l l and r r r . Record its cost for every observer. Give the trimming observer exactly the target secondary label. For each other observer, choose a rational label that makes its new formal value strictly intermediate between its two neighbors: a midpoint when all three real values tie, a label above or below the tied neighbor when only one ties, and any rational label when the real value lies strictly between. Such a choice always exists.
The secondary labels are arbitrary rationals, not restricted to [ 0 , 1 ] [0,1] [ 0 , 1 ] . Existing labels never change. An insertion at a previously recorded physical coordinate needs no additional evaluation. This procedure preserves the record invariants, including for zero-cost observers and duplicate physical coordinates. A formally envy-free allocation is physically envy-free because a lexicographic inequality implies the corresponding weak inequality of real costs.
Lemma B.7 (Simultaneous finite realization). The formal-record dynamic program succeeds for arbitrary nonnegative nonatomic costs and every legal sequence of ordinary Cut replies.
Proof. Suppose the first failed subset state has been fully tried. At that point the global table contains finitely many records. Choose one ϵ > 0 \epsilon> 0 ϵ > 0 such that all numbers
C i ( physical prefix ) + ϵ θ i ( record ) (18) C_i(\text{physical prefix})+\epsilon\theta_i(\text{record}) \tag*{(18)} C i ( physical prefix ) + ϵ θ i ( record ) (18)
preserve every formal comparison and equality between records, including records on different parents. This is possible: pairs with unequal real parts have finitely many positive separations, while their secondary parts form a finite set; equal real parts are ordered exactly by their secondary parts.
On a new abstract interval for each parent, place all its records at distinct ordered positions. Interpolate the displayed prefix values linearly between consecutive records, separately for every observer. The empty value is zero, and formal strictness makes every increment positive. This defines a single hungry profile realizing the entire finite table. The construction is permitted even when several old records shared a physical endpoint, since the new intervals are used only in this contradiction. Replay the ordinary hungry dynamic program on this profile. Every earlier state, candidate order, minimum, whole-parent branch, and envy-free decision is reproduced. Every target root is also reproduced: the stored trimming record copied both parts of its target exactly, and hungry roots are unique. Later insertions never changed an earlier record. Consequently this is one simultaneous replay of every completed state and attempted candidate, not separate realizations chosen for separate trials.
It follows that the hungry program first fails at the same state, contradicting Lemma B.6 . The protocol itself never constructs or queries the hungry profile and does not need to know ϵ \epsilon ϵ .
Query ledger and cutter progress
There are ( n k ) 2 \binom{n}{k}^{2} ( k n ) 2 balanced subset pairs of size k k k , with at most k 2 k^{2} k 2 last-pair trials each. Each trial requires at most one new Cut. Therefore the number of trim requests, including failed candidates, is at most
∑ k = 2 n k 2 ( n k ) 2 = n 2 ∑ j = 1 n − 1 ( n − 1 j ) 2 = n 2 ( ( 2 n − 2 n − 1 ) − 1 ) = T n . \sum_{k=2}^{n} k^{2}\binom{n}{k}^{2}
= n^{2}\sum_{j=1}^{n-1}\binom{n-1}{j}^{2}
= n^{2}\left(\binom{2n-2}{n-1}-1\right)=T_n. k = 2 ∑ n k 2 ( k n ) 2 = n 2 j = 1 ∑ n − 1 ( j n − 1 ) 2 = n 2 ( ( n − 1 2 n − 2 ) − 1 ) = T n .
Here k ( n k ) = n ( n − 1 k − 1 ) k\binom{n}{k}=n\binom{n-1}{k-1} k ( k n ) = n ( k − 1 n − 1 ) and the final equality is Vandermonde’s identity. The number of nonempty subset states is ( 2 n n ) − 1 \binom{2n}{n}-1 ( n 2 n ) − 1 .
A new physical trim requires one Cut and at most n − 1 n-1 n − 1 recording Evals: the trimmer’s cost is already fixed by the Cut target. Reused coordinates need no new query. All subsequent comparisons, matching data, and anchors use these records. For disconnected input parents, known component costs locate the component of a trim arithmetically; a union-value query is not charged as one interval query.
For the full Core, a zero-total row gives the complete exit in the theorem. Otherwise cut R R R into n n n equal-cost parents for c c c , recording the n − 1 n-1 n − 1 new endpoints. These initial cuts and at most n n n initial total evaluations cost at most n ( n − 1 ) + n = n 2 n(n-1)+n=n^{2} n ( n − 1 ) + n = n 2 queries. All parent costs then follow from the recorded components and endpoints. Apply the prefix program. It returns a formally envy-free anchored state, so some allocated parent is whole. Prefixes on distinct parents are disjoint, and their suffix complements exactly constitute R ′ R' R ′ .
Put a = C c ( R ) / n a=C_c(R)/n a = C c ( R ) / n and b = C c ( A c ) b=C_c(A_c) b = C c ( A c ) . Every allocated prefix costs at least b b b to c c c , and one costs a a a . Thus
C c ( R ′ ) ≤ n a − ( a + ( n − 1 ) b ) = ( n − 1 ) ( a − b ) . C_c(R')\le na-\bigl(a+(n-1)b\bigr)=(n-1)(a-b). C c ( R ′ ) ≤ na − ( a + ( n − 1 ) b ) = ( n − 1 ) ( a − b ) .
which proves the claimed gap. Allocating that whole parent also gives C c ( R ′ ) ≤ ( n − 1 ) a C_c(R')\le(n-1)a C c ( R ′ ) ≤ ( n − 1 ) a . Together with the query ledger, this proves Theorem B.1 .
Cached many-parent compensation
Corollary B.8 (Cached SubCore contract). Let K ≥ 1 K\ge1 K ≥ 1 participants have nonnegative nonatomic costs, now treated as cake values, on more than K K K recorded ordered parents. Start with zero benchmarks and distinct empty inherited suffixes, using coherent empty and whole formal labels 0 0 0 and 1 1 1 . With N N N enclosing observers, the many-parent SubCore returns distinct suffix parents, cake envy-freeness, comparison with every unused whole parent, and at least one whole assigned parent. Its residue is the exact complementary collection of prefixes and unused parents. With cached input component costs it uses at most
S K = 2 K + 1 − 2 K − 2 Cuts , N S K total queries. S_K = 2^{K+1} - 2K - 2 \text{ Cuts}, \qquad NS_K \text{ total queries.} S K = 2 K + 1 − 2 K − 2 Cuts , N S K total queries.
Proof. Apply the many-parent routine proved in Lemma C.1 . The stated fresh-zero initialization is coherent for its persistent suffix records and does not assume an arbitrary positive external benchmark can be initialized for free. Its recurrence, from the distinct recursive selected-set sizes, is
S 0 = S 1 = 0 , S K = S K − 1 + K ( K − 1 ) + ∑ j = 1 K − 2 S j = 2 S K − 1 + 2 ( K − 1 ) . S_0 = S_1 = 0, \qquad S_K = S_{K-1} + K(K-1) + \sum_{j=1}^{K-2} S_j = 2S_{K-1} + 2(K-1). S 0 = S 1 = 0 , S K = S K − 1 + K ( K − 1 ) + j = 1 ∑ K − 2 S j = 2 S K − 1 + 2 ( K − 1 ) .
It solves to the displayed expression. The K = 1 K=1 K = 1 call chooses a greatest whole parent using cached costs and makes no cut. Every new endpoint in a larger call requires at most N − 1 N-1 N − 1 additional observer evaluations beyond its Cut response. The full chain argument, unused-parent comparison, and ordinary-root implementation are included in Lemma C.1 ; no optimized SubCore statement beyond that in-paper proof is needed here. □
Whole-cell multicolor rounding
The discrepancy finisher needs a positive lower share for each observer and color, rather than an exactly preserved designated row. The following rounding argument is the multicolor discrepancy principle of Glaßer–Reitwießner–Witek [10 Theorem 2, full-version Theorem 3.1] , following Doerr–Srivastav [7 ] . We include its finite-kernel proof for real recorded weights and its ordinary-query implementation. We make no bit-complexity claim.
Lemma B.9 (Whole-cell rounding). Let finitely many cells have nonnegative weights w i ( Q ) w_i(Q) w i ( Q ) for r ≥ 1 r \ge1 r ≥ 1 observers, with ∑ Q w i ( Q ) = 1 \sum_Q w_i(Q) = 1 ∑ Q w i ( Q ) = 1 and w i ( Q ) ≤ 1 / K w_i(Q) \le1/K w i ( Q ) ≤ 1/ K . For any integer m ≥ 2 m \ge2 m ≥ 2 , exact finite linear algebra assigns each cell wholly to one of m m m colors so that
∣ ∑ Q : color ( Q ) = j w i ( Q ) − 1 m ∣ ≤ 2 r K for every i , j . \left|\sum_{Q:\,\operatorname{color}(Q)=j} w_i(Q) - \frac{1}{m}\right| \le\frac{2r}{K}
\qquad\text{for every } i,j. Q : color ( Q ) = j ∑ w i ( Q ) − m 1 ≤ K 2 r for every i , j . Proof. Start with variables x Q j = 1 / m x_{Qj}=1/m x Q j = 1/ m . Always preserve the cell equations ∑ j x Q j = 1 \sum_j x_{Qj}=1 ∑ j x Q j = 1 and nonnegativity. Initially also maintain all r m rm r m observer/color equations ∑ Q w i ( Q ) x Q j = 1 / m \sum_Q w_i(Q)x_{Qj}=1/m ∑ Q w i ( Q ) x Q j = 1/ m . A zero variable never returns; a cell with one positive variable is integral and fixed forever.
Let C C C be the number of fractional cells, V V V their positive variables, and D D D the currently maintained observer/color equations. Then V ≥ 2 C V \ge2C V ≥ 2 C . If a nonzero direction on these variables preserves all cell sums and maintained equations, move a positive distance along it until some positive variable reaches zero. A nonzero direction with zero sums in its affected cells has both signs. Thus this move exists, eliminates a variable, and keeps all variables in [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Otherwise the constraint matrix on the V V V variables has independent columns, so V ≤ C + D V \le C+D V ≤ C + D and hence D ≥ V / 2 D \ge V/2 D ≥ V /2 . Each variable appears in at most r r r observer/color equations, one per observer for its own color. Total incidence is at most r V rV r V , so some maintained equation contains at most 2 r 2r 2 r positive fractional variables. Drop that equation.
At the time of dropping, the equation is exact. All its integral-cell contributions remain fixed, its zero variables never return, and at most 2 r 2r 2 r remaining variables can change. Each changes by at most one and has weight at most 1 / K 1/K 1/ K , so its final discrepancy is at most 2 r / K 2r/K 2 r / K . Equations
never dropped stay exact. Every step reduces either positive support or the number of maintained equations, and one of the two steps is available whenever a fractional cell remains. The procedure therefore terminates with an integral color assignment and the stated bounds.
Lemma B.10 (Near-equal physical partition). Let U U U be a recorded ordered finite union, let m ≥ 2 m \ge2 m ≥ 2 , and let designated observers have nonnegative nonatomic costs. Let r r r be the number of those observers with positive total cost for U U U , and let N N N be the number of enclosing observers whose endpoint costs are recorded. A deterministic ordinary-query procedure partitions all of U U U into m m m finite unions P 1 , … , P m P_1,\ldots,P_m P 1 , … , P m satisfying, for every designated observer i i i ,
C i ( U ) 2 m ≤ C i ( P j ) ≤ 3 C i ( U ) 2 m . \frac{C_i(U)}{2m} \le C_i(P_j) \le\frac{3C_i(U)}{2m}. 2 m C i ( U ) ≤ C i ( P j ) ≤ 2 m 3 C i ( U ) . If r = 0 r = 0 r = 0 , it makes no cuts. Otherwise it uses at most r ( 4 r m − 1 ) r(4rm-1) r ( 4 r m − 1 ) Cuts and N r ( 4 r m − 1 ) Nr(4rm-1) N r ( 4 r m − 1 ) total queries beyond the cached input costs.
Proof. A zero-total observer has zero cost on every subset and needs no constraint. If all designated totals are zero, assign all of U U U to one color and leave the others empty. Otherwise normalize each positive row by its known total and set K = 4 r m K = 4rm K = 4 r m . For each of the r r r rows make its K − 1 K - 1 K − 1 positive quantile cuts and merge all their boundaries. Nonnegativity makes the row’s quantile endpoints monotone for every choice of plateau roots. Each cell in the common refinement has normalized cost at most 1 / K 1/K 1/ K to every row. Component joins can be retained as cell boundaries; their costs are already recorded.
Record every new endpoint for all N N N observers and apply Lemma B.9 to the normalized cell weights. Its error is 2 r / K = 1 / ( 2 m ) 2r/K = 1/(2m) 2 r / K = 1/ ( 2 m ) . Assign every cell whole to its chosen color. This yields the two displayed bounds, is a complete physical partition, and introduces no further cuts. A color may be a disconnected union of recorded cells. Each quantile requires at most one Cut and N − 1 N - 1 N − 1 additional Evals; locating its component uses the cached component costs. This proves the ledger.
The splitter does not preserve any designated row exactly. The finisher uses only its displayed lower bounds; any other caller needing an exact designated share requires a different interface.
The many-parent cake SubCore primitive
This appendix includes the inherited primitive proof underlying our compensation routine. It follows the Aziz–Mackenzie SubCore framework [1 ] , with the tie and equal-value-chain conventions of Ye–Bai [18 Appendix F] . All parent component values are cached, and a strict prefix or suffix target is located from those component totals and implemented by one ordinary interval Cut; zero, full, and previously recorded targets reuse endpoints. Every fresh endpoint is recorded for the enclosing observers. Null material remains part of the domain.
We temporarily interpret the same nonnegative measures as values to maximize. The following subroutine supplies the removed pieces in the chore compensation argument.
Lemma C.1 (Many-parent SubCore). Given k ≥ 1 k \ge1 k ≥ 1 participants and m > k m > k m > k disjoint recorded ordered parents, there is a deterministic procedure assigning each participant a suffix of a distinct parent such that: the assignments are cake envy-free; every participant weakly prefers her assignment to every wholly unused parent; and at least one assigned parent is whole. The other m − k m-k m − k parents remain whole and unused. For k = 1 k = 1 k = 1 no cut is required. For k ≥ 2 k \ge2 k ≥ 2 at most 2 k + 1 − 2 k − 2 2^{k+1} - 2k - 2 2 k + 1 − 2 k − 2 cuts are required, independent of m m m . With N ≥ k N \ge k N ≥ k enclosing observers and cached parent component values,
at most N ( 2 k + 1 − 2 k − 2 ) N(2^{k+1}-2k-2) N ( 2 k + 1 − 2 k − 2 ) queries record the new endpoints. The result permits zero-valued or empty parents and every legal Cut reply.
We prove the more general recursive interface used by the procedure. The input additionally supplies benchmarks b i b_i b i and a cake envy-free allocation H H H giving every agent a suffix of a distinct input parent of value exactly b i b_i b i . The output meets the benchmarks and all the conclusions of the lemma. Initially b i = 0 b_i=0 b i = 0 and H H H consists of distinct empty suffixes.
First suppose all suffix comparisons are strictly monotone along each parent. Process participants in a fixed order 1 , … , k 1,\ldots,k 1 , … , k , maintaining a tentative allocation of those already processed. If the new agent’s favorite whole input parent is unallocated, give it to her. Otherwise at stage t t t let X X X be the tentative allocation of the first t − 1 t-1 t − 1 agents. Its t − 1 t-1 t − 1 parents are contested ; all other input parents are uncontested . For each i ≤ t i\le t i ≤ t put
β i = max { b i , max P u n c o n t e s t e d V i ( P ) } . \beta_i=\max\{b_i,\max_{P\ \mathrm{uncontested}}V_i(P)\}. β i = max { b i , P uncontested max V i ( P )} .
Ask each processed agent to trim every contested parent of value at least β i \beta_i β i to a suffix of value β i \beta_i β i . On each contested parent select a rightmost trimmer, favoring its owner in the inherited allocation H H H when she ties. Let T T T be the set of selected agents. Give each member of T T T one suffix from a parent on which she was selected. Such choices use distinct parents, since each parent selected only one agent.
While ∣ T ∣ < t − 1 |T|<t-1 ∣ T ∣ < t − 1 , ignore the original trims of T T T and form C ′ C' C ′ by retaining on each contested parent the suffix at its rightmost remaining trim, or the whole parent if no trim remains. Recursively run SubCore on T T T and C ′ C' C ′ , with their current own values as benchmarks and their current suffixes as inherited allocation. Let its output be Y Y Y . If an unused member of C ′ C' C ′ has a remaining trim, give it to one of its rightmost remaining trimmers. Otherwise perform the chain operation proved next to free such a parent, and give that parent to its rightmost remaining trimmer. Add this agent to T T T and update its members’ benchmarks to their own current values. When ∣ T ∣ = t − 1 |T|=t-1 ∣ T ∣ = t − 1 , keep these assignments and give the sole remaining agent among 1 , … , t 1,\ldots,t 1 , … , t her favorite uncontested parent. There is no additional recursive call after ∣ T ∣ = t − 1 |T|=t-1 ∣ T ∣ = t − 1 .
Lemma C.2 (Equal-value chain). During a recursive stage above, if an unused parent P ∈ C ′ P\in C' P ∈ C ′ has no remaining trim, agents in T T T can be reassigned without changing their own values so that P P P becomes allocated and a parent with a remaining trim becomes unused. Cake envy-freeness and comparisons with unused parents are preserved.
Proof. Every owner in X X X trimmed her own parent, because its value is at least her initial β i \beta_i β i . Let i 0 i_0 i 0 own P P P in X X X , and let i r + 1 i_{r+1} i r + 1 be the owner in X X X of the parent assigned to i r i_r i r in Y Y Y . Stop at the first i h ∉ T i_h\notin T i h ∈ / T . Initially i 0 ∈ T i_0\in T i 0 ∈ T , since P P P has no remaining trim. The chain has no repeated agent: X X X and Y Y Y are injective assignments and P P P is unallocated in Y Y Y . It therefore terminates outside T T T .
Walking backwards, we claim Y i r − 1 ⊆ X i r Y_{i_{r-1}}\subseteq X_{i_r} Y i r − 1 ⊆ X i r for 1 ≤ r ≤ h 1\le r\le h 1 ≤ r ≤ h . At r = h r=h r = h the outside agent’s remaining trim lies within X i h X_{i_h} X i h , and the entire parent in C ′ C' C ′ begins at or after that trim. At an earlier index, induction and envy-freeness of X X X give
V i r ( Y i r ) ≤ V i r ( X i r + 1 ) ≤ V i r ( X i r ) . V_{i_r}(Y_{i_r})\le V_{i_r}(X_{i_{r+1}})\le V_{i_r}(X_{i_r}). V i r ( Y i r ) ≤ V i r ( X i r + 1 ) ≤ V i r ( X i r ) .
If X i r ⊆ Y i r − 1 X_{i_r}\subseteq Y_{i_{r-1}} X i r ⊆ Y i r − 1 , strict monotonicity along the same parent would make Y i r − 1 Y_{i_{r-1}} Y i r − 1 more valuable than Y i r Y_{i_r} Y i r , contradicting envy-freeness of Y Y Y . This proves the claim.
Now walk forwards. The unused-parent guarantee for Y Y Y gives V i 0 ( Y i 0 ) ≥ V i 0 ( P ) ≥ V i 0 ( X i 0 ) V_{i_0}(Y_{i_0})\ge V_{i_0}(P)\ge V_{i_0}(X_{i_0}) V i 0 ( Y i 0 ) ≥ V i 0 ( P ) ≥ V i 0 ( X i 0 ) . Together with the preceding inequalities this forces equality, hence X i 0 = P X_{i_0}=P X i 0 = P and Y i 0 = X i 1 Y_{i_0}=X_{i_1} Y i 0 = X i 1 . If Y i r − 1 = X i r Y_{i_{r-1}} = X_{i_r} Y i r − 1 = X i r , envy-freeness of Y Y Y and the same upper bounds give equality again: agent i r i_r i r is indifferent between X i r X_{i_r} X i r and Y i r Y_{i_r} Y i r , and Y i r = X i r + 1 Y_{i_r} = X_{i_{r+1}} Y i r = X i r + 1 . Finally Y i h − 1 = X i h Y_{i_{h-1}} = X_{i_h} Y i h − 1 = X i h equals its parent in C ′ C' C ′ , since that parent lies between it and the outside agent’s trim. It has a remaining trim. Give each i r i_r i r , r < h r < h r < h , her suffix X i r X_{i_r} X i r . Their own values are unchanged. The multiset of allocated suffixes adds only P P P and removes X i h X_{i_h} X i h ; every agent weakly preferred her old assignment to both these whole parents. All required comparisons persist.
Correctness and complexity of Lemma C.1 . Induct on the participant count and, within a call, on t t t . The easy branch gives the new agent a favorite whole parent, meeting her benchmark; previous agents did not envy an unused parent. In a contested stage, every old owner has V i ( X i ) ≥ β i V_i(X_i) \ge\beta_i V i ( X i ) ≥ β i and so trims her own parent; every contested parent has at least one trim. A nontrimmer values that parent below her β i \beta_i β i . Consequently every selected rightmost suffix is worth at most β i \beta_i β i to every agent i ≤ t i \le t i ≤ t , and its selected owner values it exactly β i \beta_i β i . The initial allocation of T T T is envy-free.
An agent i i i whose benchmark exceeds every uncontested value must lie in T T T . Her inherited suffix H i H_i H i belongs to a contested parent; she trims that parent exactly to H i H_i H i . Every other agent j j j values H i H_i H i at most b j ≤ β j b_j \le\beta_j b j ≤ β j by envy-freeness of H H H , so no trim is to its right. The specified tie rule selects i i i . Such agents never leave T T T .
At a recursive stage, ignoring more original trims only enlarges parents, so the current allocation is a valid inherited allocation. Every agent outside T T T retains her original β i \beta_i β i and values each parent in C ′ C' C ′ at most β i \beta_i β i . The recursive result meets the current benchmarks and compares favorably to unused parents. The chain lemma, when necessary, frees a parent at a remaining trim. Its new outside owner values it exactly β i \beta_i β i , and the enlarged allocation is envy-free in both directions. Updating the benchmarks can only increase them.
At the end all contested parents are assigned to T T T . The sole outside agent can meet her benchmark on an uncontested parent by the preceding necessity argument. She receives value β i \beta_i β i and values every contested suffix at most β i \beta_i β i . Every member of T T T receives at least her initial β i \beta_i β i , so does not envy any uncontested parent. This proves all comparisons, the benchmarks, and the whole-parent guarantee. Every produced suffix is whole or starts at a recorded trim.
For nonnegative measures use persistent suffix records with formal values ( V i ( P ) , θ i ) (V_i(P), \theta_i) ( V i ( P ) , θ i ) . On each original parent initialize the whole record with secondary value 1 and the empty suffix with 0, even when the parent is physically empty. Formal values decrease strictly in the ordered list from whole to empty. A formal trim reuses its target record or inserts one between adjacent records by the bracketed endpoint procedure for persistent prefix records in Appendix § 7 . All old records persist in descendants; new records copy the trimming agent’s target secondary value and choose intermediate rational values for other observers. The proof just given uses only ordering, strict monotonicity within a parent, and exact trim targets. It therefore applies to these formal records verbatim. In particular equality along the chain identifies the same suffix record. Formal envy-freeness implies real envy-freeness, and a whole input record is physically whole. No positive-benchmark initialization is required at the top level: distinct empty records provide the inherited allocation at formal benchmark ( 0 , 0 ) (0,0) ( 0 , 0 ) .
Let S ( k ) S(k) S ( k ) bound all cuts in a call with k k k agents, uniformly over its number of parents. The first k − 1 k-1 k − 1 stages cost at most S ( k − 1 ) S(k-1) S ( k − 1 ) . At stage k k k , there are at most k ( k − 1 ) k(k-1) k ( k − 1 ) initial trims. During its while loop the selected set strictly grows, so each recursive cardinality j ∈ { 1 , … , k − 2 } j \in\{1,\ldots,k-2\} j ∈ { 1 , … , k − 2 } occurs at most once; the last same-size call is omitted and the chain operation uses no query. Thus the original generic source recurrence [18 Appendix F.4] is
S ( 0 ) = S ( 1 ) = 0 , S ( k ) ≤ S ( k − 1 ) + k ( k − 1 ) + ∑ j = 1 k − 2 S ( j ) . S(0) = S(1) = 0,\qquad S(k) \le S(k-1) + k(k-1) + \sum_{j=1}^{k-2} S(j). S ( 0 ) = S ( 1 ) = 0 , S ( k ) ≤ S ( k − 1 ) + k ( k − 1 ) + j = 1 ∑ k − 2 S ( j ) .
The equality envelope obeys S ( k ) = 2 S ( k − 1 ) + 2 ( k − 1 ) S(k) = 2S(k-1) + 2(k-1) S ( k ) = 2 S ( k − 1 ) + 2 ( k − 1 ) and therefore S ( k ) = 2 k + 1 − 2 k − 2 S(k) = 2^{k+1} - 2k - 2 S ( k ) = 2 k + 1 − 2 k − 2 . Induction bounds every actual call by this envelope. Favorite scans and the chain use recorded values. Each genuine new trim requires one Cut and at most N − 1 N-1 N − 1 recording evaluations. Reused endpoints require no query. This proves the stated bound, including exploratory cuts. □
Corollary C.3 (Threshold guarantee). If at least k k k offered parents have value at least z i z_i z i for participant i i i , then her SubCore assignment has value at least z i z_i z i .
Proof. If one such parent is unused, compare with it. Otherwise exactly k k k parents are assigned, all of them have value at least z i z_i z i , and one is assigned whole. Cake envy-freeness supplies the comparison with that share. The high-parent sets may differ between participants. □
SubCore with parent-dependent cost offsets
This appendix supplies the compensation primitive used by the component batches. The transformation is an implementation of the many-parent SubCore of Aziz–Mackenzie and Ye–Bai, rather than a new valuation oracle. The full source algorithm, equal-value-chain argument, and fresh-zero interface are given in Lemma C.1; see also Ye and Bai [18 Algorithm 6 and Appendix F] .
Let W 1 , … , W m W_1,\ldots,W_m W 1 , … , W m be disjoint recorded ordered suffix parents and let k < m k < m k < m agents participate. There are N ≥ k N \ge k N ≥ k enclosing observers whose costs at new endpoints are recorded. Their original costs C i C_i C i are finite, nonnegative, and nonatomic. For each observer and parent, a known constant g s i ≥ 0 g_{si} \ge0 g s i ≥ 0 is given. On suffixes D ⊆ W s D \subseteq W_s D ⊆ W s define
u i ( s , D ) = C i ( D ) − g s i , v i ( s , D ) = max { u i ( s , D ) , 0 } . u_i(s,D) = C_i(D) - g_{si},\qquad v_i(s,D) = \max\{u_i(s,D),0\}. u i ( s , D ) = C i ( D ) − g s i , v i ( s , D ) = max { u i ( s , D ) , 0 } .
The transformed utilities are compared only on individual parent suffixes. They are not asserted to be additive on unions of different parents. Original costs account for every physical allocation and complement.
Theorem D.1 (Offset SubCore). The following two deterministic routines permit every legal ordinary Cut reply, including arbitrary plateau roots.
(i) For the utilities v v v , the routine returns one suffix D i D_i D i to each participant, from distinct parents, with
v i ( D i ) ≥ v i ( D j ) for all participants i , j , v_i(D_i) \ge v_i(D_j)\qquad\text{for all participants }i,j, v i ( D i ) ≥ v i ( D j ) for all participants i , j , and
v i ( D i ) ≥ v i ( W s ) for every wholly unused parent s . v_i(D_i) \ge v_i(W_s)\qquad\text{for every wholly unused parent }s. v i ( D i ) ≥ v i ( W s ) for every wholly unused parent s . At least one returned suffix is its entire offered parent.
(ii) Suppose u i ( W s ) ≥ 0 u_i(W_s) \ge0 u i ( W s ) ≥ 0 for every participant i i i and every offered whole parent s s s . The same guarantees hold for u u u , and every returned own utility u i ( D i ) u_i(D_i) u i ( D i ) is nonnegative. A whole output with affine own utility zero is a physical output and remains assigned.*
Each routine uses at most
S k = 2 k + 1 − 2 k − 2 Cuts , N S k total queries S_k = 2^{k+1} - 2k - 2 \quad\text{Cuts}, \qquad NS_k \quad\text{total queries} S k = 2 k + 1 − 2 k − 2 Cuts , N S k total queries
beyond the cached input component costs and offsets. In both cases the unallocated material is exactly the complementary prefixes and the unused whole parents. No cut to a difference measure or perturbed measure is used.
The monotone-parent source interface
The recursive SubCore interface supplies an inherited cake envy-free suffix assignment H H H on distinct parents, with benchmarks b i b_i b i equal to the inherited own utilities. At a contested stage it trims a parent for agent i i i to the target
β i = max { b i , max W u n c o n t e s t e d utility i ( W ) } . \beta_i = \max\left\{b_i,\ \max_{W\ \mathrm{uncontested}} \operatorname{utility}_i(W)\right\}. β i = max { b i , W uncontested max utility i ( W ) } .
The algorithm and its proof use comparisons of individual suffix utilities, monotonicity along one parent, exact target equalities, and suffix containment. In the equal-value chain, the backwards step deduces containment by comparing two suffixes of the same parent. The forwards step uses envy-freeness and comparison with unused parents to prove equality of own utilities. Neither step adds utilities from different parents or identifies a difference of utilities with the utility of a set difference. Thus the proof of Lemma Lemma C.1 applies to strictly increasing continuous parent utility functions with a coherent inherited assignment.
For weak monotonicity, retain the source’s permanent formal suffix records. A record consists of a physical endpoint, its actual utility to every observer, and rational secondary labels. Compare utilities lexicographically. For every observer they decrease strictly as the suffix’s left endpoint moves right through the record list. Distinct formal records may share a physical endpoint. All records, including exploratory records, persist; old values and labels never change.
A formal trim target is the formal utility of an existing record. Reuse a matching record if available. Otherwise find adjacent records bracketing it. If one endpoint has the target primary utility, reuse that physical endpoint and insert a new record. Give the trimming observer the target secondary label. For another observer, choose a rational intermediate label: a midpoint when both neighboring primary values tie, a value above or below the single tied neighbor when only one ties, and any rational value when the new primary value is strictly intermediate. These choices are always possible. Secondary labels need not lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] .
This strict-order implementation supports the same finite source proof. Alternatively, after any finite completed table, a constant row shift and one sufficiently small common ϵ > 0 \epsilon> 0 ϵ > 0 realize all formal values as hungry additive suffix values on abstract parents. Each record’s value is its shifted primary value plus ϵ \epsilon ϵ times its secondary label. There are finitely many comparisons, so one ϵ \epsilon ϵ preserves them all; linear interpolation between distinct abstract record positions gives positive densities. Existing records are immutable, so this is one realization of the whole table. It is used only in the proof, not by the physical protocol. The two implementations below specify the actual original-measure query for every formal trim.
Clipped utilities and physical zero targets
For v v v , physical empty has value zero for every observer. Initialize its secondary label to zero and the whole-parent label to one, also for zero utility or physically empty parents. This supplies the fresh-zero inherited assignment on distinct parents.
Suppose a formal trim has primary target t t t . If it cannot reuse a bracketing physical endpoint, its primary value lies strictly between the neighbors. Necessarily t > 0 t > 0 t > 0 , because all clipped values are nonnegative and a primary-zero target always has a zero-valued neighbor. The desired suffix then satisfies precisely
C i ( D ) = g s i + t . (19) C_i(D) = g_{si} + t. \tag*{(19)} C i ( D ) = g s i + t . (19)
Its original cost is strictly bracketed by the two neighboring original suffix costs. Let a a a be the left bracket endpoint. In the usual left-to-right Cut convention, request prefix cost
C i ( suffix starting at a ) − ( g s i + t ) . C_i(\text{suffix starting at } a) - (g_{si} + t). C i ( suffix starting at a ) − ( g s i + t ) .
Every legal returned root lies inside the strict bracket and leaves a suffix of the desired original cost. For an ordered union, cached component costs first locate the component containing this target; only one ordinary interval Cut is required. The trimmer’s original endpoint cost is already known from the target. At most N − 1 N - 1 N − 1 further Evals record the other observers. Reusing a physical coordinate needs no new query.
Consequently a clipped primary-zero trim needs neither a query to a signed utility nor an extremal root. The source’s formal envy-free, unused-parent, and whole-parent guarantees imply their primary, physical counterparts. This proves the output claims in part (i).
Affine utilities: virtual bottom and nonnegative targets
For u u u , physical empty has value − g s i -g_{si} − g s i , which can be negative and parent dependent. It cannot be declared to have common benchmark zero. For each observer set
M i = − 1 − max s g s i . M_i = -1 - \max_s g_{si}. M i = − 1 − s max g s i .
Place on every parent a virtual empty record with formal value ( M i , 0 ) (M_i, 0) ( M i , 0 ) , strictly below all its physical affine values. Keep a separate record for physical empty, with primary value − g s i -g_{si} − g s i . The virtual record has no physical material; its bookkeeping coordinate may equal the empty endpoint, but its value is explicitly virtual. Initialize the inherited assignment on distinct virtual records with benchmark M i M_i M i . It is coherently envy-free because each observer sees the same virtual value on all parents.
Lemma D.2 (Nonnegative affine targets). Every actual trim target and every returned own utility in this execution has primary value at least zero. No output or queried root lies in the interior of a virtual segment.
Proof. At the top-level call, every offered whole parent has nonnegative primary utility for each participant. At every contested stage an uncontested whole parent exists, since m > k m > k m > k . Its utility in the displayed maximum therefore makes β i ≥ 0 \beta_i \ge0 β i ≥ 0 . An easy favorite-whole assignment is also nonnegative.
Recursive calls require a different justification. A recursive parent can have negative whole utility to some participant. However, its inherited assignment has already been formed from physical assignments of nonnegative own utility. Its inherited benchmark thus has primary value b i ≥ 0 b_i \ge0 b i ≥ 0 . Every recursive contested target satisfies β i ≥ b i ≥ 0 \beta_i \ge b_i \ge0 β i ≥ b i ≥ 0 . In an easy branch the favorite whole parent meets the benchmark: the participant’s inherited suffix belongs to an offered parent, whose whole utility is at least that suffix’s utility, and the favorite whole is at least as good. Benchmark updates use current own utilities, and equal-value-chain reassignments preserve them. Induction over calls and stages proves the claimed nonnegativity.
The assertion concerns primary values; a primary-zero target may have any secondary label. If a neighboring physical endpoint has the target primary value, reuse it and insert a label. Otherwise a genuine trim is again exactly the original suffix target g s i + t g_{si} + t g s i + t , now with t ≥ 0 t \ge0 t ≥ 0 . In particular, t = 0 t = 0 t = 0 can require a positive original cost g s i g_{si} g s i . It is not generally the physical empty set.
No nonnegative target lies strictly inside the virtual segment below physical empty, whose primary values are below − g s i ≤ 0 -g_{si} \le0 − g s i ≤ 0 . When g s i = 0 g_{si} = 0 g s i = 0 and a primary-zero target’s secondary label lies below the physical-empty label, reuse the same physical empty endpoint with a different formal record. Thus every actual trim and output is physical. □
The ordinary Cut conversion and strict-bracket argument are the same as for clipped positive targets. For a finite strict realization, shift observer i i i ’s row by − M i -M_i − M i . This changes no utility comparison or target relation. The virtual bottom becomes zero, and all physical values are positive. The finite-record interpolation described above then realizes the source’s strict monotone interface. Lemma D.2 ensures that the physical simulator never queries or returns any artificial interior. The source output is therefore physically envy-free for u u u , dominates every unused whole parent, and includes an original offered parent whole. Every own affine value is nonnegative, including on the whole output. This proves part (ii).
Query count and exact material accounting
The source’s recursive selected sets have distinct sizes at a stage, and its final same-size recursive call is omitted. The chain repair makes no query. The number of cuts is bounded by the envelope defined by
S 0 = S 1 = 0 , S k = S k − 1 + k ( k − 1 ) + ∑ j = 1 k − 2 S j = 2 S k − 1 + 2 ( k − 1 ) = 2 k + 1 − 2 k − 2. S_0 = S_1 = 0,\qquad S_k = S_{k-1} + k(k-1) + \sum_{j=1}^{k-2} S_j = 2S_{k-1} + 2(k-1) = 2^{k+1} - 2k - 2. S 0 = S 1 = 0 , S k = S k − 1 + k ( k − 1 ) + j = 1 ∑ k − 2 S j = 2 S k − 1 + 2 ( k − 1 ) = 2 k + 1 − 2 k − 2.
Each request is either an endpoint reuse or at most one original Cut and N − 1 N - 1 N − 1 Evals. Computing offsets, virtual bottoms, and transformed comparisons uses the cached input values. The k = 1 k = 1 k = 1 call chooses a greatest whole parent without a cut. This proves the query bounds in Theorem D.1 .
Each assigned suffix has one distinct original parent. Its physical prefix complement, together with the wholly unused parents, is exactly the residual domain. This assertion uses original sets and costs; no additivity of u u u or v v v across parents is invoked. Null components and null tails remain in their physical assigned or complementary sets. Uncached input components require their actual separate evaluation costs; a disconnected union is not treated as one free interval Eval.
What zero stripping does and does not preserve
Lemma D.3 (Clipped-zero stripping). Consider the nominal clipped output. If v j ( D j ) = 0 v_j(D_j) = 0 v j ( D j ) = 0 , then v j ( D i ) = 0 v_j(D_i) = 0 v j ( D i ) = 0 for every nominal assigned suffix, and v j ( W s ) = 0 v_j(W_s) = 0 v j ( W s ) = 0 for every wholly unused parent. If the caller executes only the nominal outputs with positive own clipped utility, every executed participant’s affine own utility equals its clipped own utility. All its pairwise comparisons against the retained outputs remain valid. Any nonnegative rank threshold paid by a stripped observer is zero.
Proof. Clipped utilities are nonnegative. The nominal envy-free and unused-parent inequalities with left side zero force every indicated right side to zero. A rank threshold is at most the nominal own value, so a nonnegative such threshold is zero. On a positive clipped own value, max { u i ( D i ) , 0 } = u i ( D i ) > 0 \max\{u_i(D_i),0\} = u_i(D_i) > 0 max { u i ( D i ) , 0 } = u i ( D i ) > 0 . Removing other nominal outputs does not invalidate any surviving comparison. □
The physical caller must reserve all nominally selected parent roots, including stripped proposals, and freeze an omitted root at its actual old allocation while charging its old reserves. Omitting a donor operation removes its proposed deficit; it cannot supply the credit or whole-parent material of that unexecuted operation. Those physical obligations are proved in the component-batch argument, not by the utility lemma alone.
Stripping can destroy the whole-parent guarantee. With one participant, two parents of original cost one, and offset two on both, every clipped utility is zero but a whole output has affine utility minus one. Such an output cannot be used as an actual donor. Atomic extraction and closed terminal batches consequently use the affine part of Theorem D.1 , whose nonnegative-whole assumption permits every zero-affine output to remain physical and retains the whole-parent certificate.
Whole-piece augmentation and two-group completion
Let N N N be a population of n n n agents with finite nonnegative nonatomic Borel costs, let B B B be a nonempty proper subset, and let X X X , R R R be disjoint recorded finite-union domains, with all component values already recorded. Put α = 2 n + 2 \alpha= 2^{n+2} α = 2 n + 2 . The separated-domain hypothesis is
C i ( X ) ≥ α C i ( R ) ( i ∈ B ) , C i ( R ) ≥ α C i ( X ) ( i ∈ N ∖ B ) . (20) C_i(X) \ge\alpha C_i(R)\ (i \in B), \qquad C_i(R) \ge\alpha C_i(X)\ (i \in N \setminus B). \tag*{(20)} C i ( X ) ≥ α C i ( R ) ( i ∈ B ) , C i ( R ) ≥ α C i ( X ) ( i ∈ N ∖ B ) . (20)
We give the full completion procedure to specify its physical complements and zero-cost behavior. Lemma B.10 partitions a recorded domain U U U into m m m pieces, each of cost at least C i ( U ) / ( 2 m ) C_i(U)/(2m) C i ( U ) / ( 2 m ) for each of r r r observers, with at most r ( 4 r m − 1 ) r(4rm-1) r ( 4 r m − 1 ) cuts. It uses only this lower bound, not exact equality for a designated observer. Zero-total observers impose no restriction.
Lemma E.1 (Whole-piece augmentation). Given k ≥ 1 k \ge1 k ≥ 1 recipients and m = 2 k + 1 m = 2^{k+1} m = 2 k + 1 disjoint recorded pieces, there is a partial chore-envy-free allocation giving each recipient a bundle containing one whole input piece. The exact unallocated complement is retained. At most 2 k − 1 2^k-1 2 k − 1 cuts are made.
Proof. Number the recipients 1 , … , k 1,\ldots,k 1 , … , k and set a i = 2 i − 1 a_i = 2^{i-1} a i = 2 i − 1 . In forward order, i i i reserves her a i a_i a i most costly available original pieces, breaking ties by labels. The remaining 2 k + 1 2^k+1 2 k + 1 pieces are public bundles, initially one whole piece each. Reserved pieces are not public choices; public identities never change.
Process agents in reverse order. Let v i v_i v i be the ( a i + 1 ) (a_i+1) ( a i + 1 ) -st smallest current public-bundle cost for i i i , and designate a set D i D_i D i of exactly a i a_i a i smallest public bundles. Attach to each a prefix from a distinct i i i -reserved piece, of cost equal to v i v_i v i minus the current bundle cost. A zero supplement is empty but its designation stays in D i D_i D i . Keep all unused reserved tails in the complement.
Before i i i acts, larger-index agents have touched at most ∑ j > i a j = 2 k − 2 i \sum_{j>i}a_j = 2^k-2^i ∑ j > i a j = 2 k − 2 i public bundles. At least 2 i + 1 2^i+1 2 i + 1 original public pieces remain intact. Each was available when i i i reserved her most costly pieces, so it costs no more to i i i than any of her reserves. There are more than a i + 1 a_i+1 a i + 1 such candidates; hence v i v_i v i is bounded by the cost of each reserve and every supplement fits.
After this augmentation all public bundles cost at least v i v_i v i to i i i , and every member of D i D_i D i costs exactly v i v_i v i . Later augmentations only add cost. Now agents choose in forward order, each taking a remaining minimum-cost bundle, preferring her own D i D_i D i in a tie. Inductively earlier choices belong to their own designated sets. Since ∣ D i ∣ > ∑ j < i ∣ D j ∣ |D_i| > \sum_{j<i}|D_j| ∣ D i ∣ > ∑ j < i ∣ D j ∣ , some member of D i D_i D i was neither touched by a smaller-index augmenter nor chosen earlier. It still costs v i v_i v i . The choice therefore belongs to D i D_i D i and has cost v i v_i v i , while every other chosen bundle costs at least v i v_i v i to this observer. This is envy-free.
Every chosen bundle contains its original whole public piece. Distinct reserved pieces supply disjoint supplements. Unchosen public bundles, unused reserves and every reserved tail form the exact complement. There are at most ∑ i a i = 2 k − 1 \sum_i a_i = 2^k - 1 ∑ i a i = 2 k − 1 supplement cuts, including all tie and zero-designation cases.
Lemma E.2 (Two-group completion). Suppose (18) holds. Recursive calls on strictly smaller populations suffice to divide X ∪ R X \cup R X ∪ R completely and without envy. The preparation uses at most 19 ⋅ 2 n 19 \cdot2^n 19 ⋅ 2 n cuts and 19 n 2 n 19n2^n 19 n 2 n recorded ordinary queries.
Proof. Put D = N ∖ B D = N \setminus B D = N ∖ B , b = ∣ B ∣ b = |B| b = ∣ B ∣ and c = ∣ D ∣ c = |D| c = ∣ D ∣ . Partition X X X for the b b b observers in B B B into m D = 2 c + 1 m_D = 2^{c+1} m D = 2 c + 1 pieces by Lemma B.10, and augment them for the c c c recipients in D D D using Lemma E.1. Symmetrically, partition R R R for the observers in D D D into m B = 2 b + 1 m_B = 2^{b+1} m B = 2 b + 1 pieces and augment them for recipients in B B B . Keep both partial outputs tentative until both are ready. Let X D ⊆ X X_D \subseteq X X D ⊆ X and R B ⊆ R R_B \subseteq R R B ⊆ R be their exact complements, including all unspent reservation tails. Recursively divide X D X_D X D among D D D and R B R_B R B among B B B , then add those allocations.
Within either group, the two allocations are envy-free and have disjoint domains. For i ∈ B i \in B i ∈ B her entire new bundle lies in R R R , whereas every recipient in D D D retains a whole original near-equal X X X piece of cost at least
C i ( X ) / ( 2 m D ) ≥ C i ( R ) , C_i(X)/(2m_D) \ge C_i(R), C i ( X ) / ( 2 m D ) ≥ C i ( R ) ,
since 2 m D ≤ 2 n + 1 ≤ α 2m_D \le2^{n+1} \le\alpha 2 m D ≤ 2 n + 1 ≤ α . Thus cross-group envy is absent. The symmetric argument applies to i ∈ D i \in D i ∈ D . This gives envy-freeness on all of X ∪ R X \cup R X ∪ R , independently of earlier allocations. Every domain is exactly its partial allocation plus its recursive complement. Both child groups are nonempty and smaller than n n n .
The two splits and augmentations make at most
8 ( b 2 2 c + c 2 2 b ) + 2 b + 2 c − n − 2 8(b^2 2^c + c^2 2^b) + 2^b + 2^c - n - 2 8 ( b 2 2 c + c 2 2 b ) + 2 b + 2 c − n − 2
cuts. For positive integers t t t , t 2 / 2 t ≤ 9 / 8 t^2/2^t \le9/8 t 2 / 2 t ≤ 9/8 , and 2 b + 2 c ≤ 2 n 2^b + 2^c \le2^n 2 b + 2 c ≤ 2 n . Therefore this count is at most 19 ⋅ 2 n 19 \cdot2^n 19 ⋅ 2 n . Each new endpoint costs at most n n n queries with current-observer recording. All input totals and resulting color values are cached sums, so there is no additional initial-evaluation term. Zero observers can only reduce the count.
Improved randomized allocation for general measures
We prove an expected polynomial query bound using ordinary individual Robertson–Webb queries. Queries in every rejected attempt are counted.
Theorem F.1. For n n n finite nonnegative nonatomic Borel measures, interpreted as cake values or chore costs, a randomized protocol returns a complete exactly envy-free allocation into finite unions of intervals almost surely, with
E [ Q ] = O ( n 12 log ( 2 n ) ) , E [ C ] = O ( n 11 log ( 2 n ) ) . \mathbb{E}[Q] = O\left(n^{12}\log(2n)\right), \qquad\mathbb{E}[C] = O\left(n^{11}\log(2n)\right). E [ Q ] = O ( n 12 log ( 2 n ) ) , E [ C ] = O ( n 11 log ( 2 n ) ) . The bounds hold uniformly over profiles and legal measurable nonanticipating Cut-response policies, including arbitrary legal replies on plateaus. The protocol uses exact real arithmetic and independent uniform real draws. No time or finite-bit implementation bound is asserted.
We use the physical compensation framework of Mackenzie and Suzuki [MS26]. Three changes yield the smaller sample bound. A deterministic selection of witness cells leaves a large compensation domain. Its maximum-determinant selection rule is stable under deletion of an unselected sample, which controls interpolation at fresh correction endpoints. Iterated rounding then reduces whole-cell discrepancy from quadratic to linear in the active population. A finite sequence of fresh correction attempts converts a constant local success probability into a uniform trial guarantee without multiplying the endpoint-error bound by the number of attempts. We give the construction and its full accounting.
For nonnegative measures μ i \mu_i μ i , use margins
g i j ( X ) = μ i ( X i ) − μ i ( X j ) for cake , g i j ( X ) = μ i ( X j ) − μ i ( X i ) for chores . g_{ij}(X) = \mu_i(X_i) - \mu_i(X_j) \quad\text{for cake}, \qquad g_{ij}(X) = \mu_i(X_j) - \mu_i(X_i) \quad\text{for chores}. g ij ( X ) = μ i ( X i ) − μ i ( X j ) for cake , g ij ( X ) = μ i ( X j ) − μ i ( X i ) for chores .
Thus exact envy-freeness means g i j ( X ) ≥ 0 g_{ij}(X) \ge0 g ij ( X ) ≥ 0 . All conditional statements include the complete preceding query history. Fixed tie rules and finite linear-algebra, assignment, and matching algorithms make the choices measurable. The original population is n n n ; the active population k ≤ n k \le n k ≤ n may decrease, but the parameters and endpoint records always refer to the original population.
Ordinary queries and fixed interpolation tables
Every domain is a finite ordered union of intervals with recorded component values. Record every new endpoint for all n n n original observers, including frozen observers; one Cut and these records use at most n + 1 ≤ 2 n n+1 \le2n n + 1 ≤ 2 n queries. Cached component sums locate a cumulative target. At a recorded cumulative value reuse its endpoint. Otherwise the residual target lies strictly between zero and the value of one component [ a , b ] [a,b] [ a , b ] , and a single ordinary Cut from a a a realizes it. Every legal root lies inside ( a , b ) (a,b) ( a , b ) : at b b b the cumulative value already strictly exceeds the residual target, and nonnegativity prevents it from decreasing afterward. No sum-measure or union-cut oracle is assumed.
Concatenate the components into a virtual interval. Logical cells can cross already recorded joins; those old coordinates need not refine every new sampling grid. The physical sets remain unions of the corresponding subintervals, with gaps excluded. Empty/full targets and literal complements retain all null fragments.
We use the following elementary circular law. On a recorded union S S S with ν ( S ) > 0 \nu(S)>0 ν ( S ) > 0 , a uniform start in the ν \nu ν -value circle followed by an arc of length t t t gives a piece C C C of exact value t t t with at most two endpoints. Each endpoint has conditional marginal law ν ∣ S / ν ( S ) \nu|_S/\nu(S) ν ∣ S / ν ( S ) before their shared start. Each fixed point of S S S has inclusion probability t / ν ( S ) t/\nu(S) t / ν ( S ) . Consequently, for any finite signed nonatomic measure ξ \xi ξ fixed before the start,
E [ ξ ( C ) ∣ H ] = t ν ( S ) ξ ( S ) , E [ ∣ ξ ( C ) ∣ ∣ H ] ≤ t ν ( S ) ∣ ξ ∣ ( S ) . (21) \mathbb{E}[\xi(C)\mid\mathcal{H}] = \frac{t}{\nu(S)}\xi(S), \qquad\mathbb{E}[|\xi(C)|\mid\mathcal{H}] \le\frac{t}{\nu(S)}|\xi|(S). \tag*{(21)} E [ ξ ( C ) ∣ H ] = ν ( S ) t ξ ( S ) , E [ ∣ ξ ( C ) ∣ ∣ H ] ≤ ν ( S ) t ∣ ξ ∣ ( S ) . (21)
This remains valid when ξ \xi ξ charges cutter-null intervals. Indeed, if F F F is the continuous nondecreasing cumulative function and Y Y Y is a uniform target, any legal root X X X satisfies X ≤ x X \le x X ≤ x exactly when Y ≤ F ( x ) Y \le F(x) Y ≤ F ( x ) except at Y = F ( x ) Y=F(x) Y = F ( x ) . Membership of a fixed point in a rotated arc is membership of its cumulative coordinate in that value arc. Tonelli proves (21) . Nonunique-root levels are countable, since each nontrivial level interval contains a distinct rational point, and fresh random targets and their fixed circular shifts avoid them almost surely. Distinct target levels have ordered roots. A circular partition into a specified nonnegative masses similarly uses at most a a a endpoints and covers the entire domain. Zero amounts are empty, and a full amount takes the whole domain, including null fragments. No independence is asserted within one circular group.
Normalize the k k k active measures on a positive buffer B B B to ν i ( B ) = 1 \nu_i(B)=1 ν i ( B ) = 1 , and let μ = k − 1 ∑ i ν i ∣ B \mu= k^{-1}\sum_i \nu_i|_B μ = k − 1 ∑ i ν i ∣ B . An exact μ \mu μ -sample uses one ordinary Cut: choose an actual active agent uniformly and then a uniform own-value target. Fresh choices yield iid samples under every admitted response policy.
For fixed signed measures ξ 1 , … , ξ k \xi_1,\ldots,\xi_k ξ 1 , … , ξ k , a fixed permanent grid, and m m m independent μ \mu μ -samples, let P P P be their common grid. Write γ i j = ξ i − ξ j \gamma_{ij}=\xi_i-\xi_j γ ij = ξ i − ξ j , let F i j F_{ij} F ij be its cumulative function, and let F ^ i j \widehat{F}_{ij} F ij be its linear interpolant on P P P . Define
D i j = ∑ E ∈ P ∣ γ i j ( E ) ∣ , e i j ( x ) = ∣ F i j ( x ) − F ^ i j ( x ) ∣ , u P ( x ) = max i < j e i j ( x ) D i j + e i j ( x ) , D_{ij}=\sum_{E\in P}|\gamma_{ij}(E)|,\qquad e_{ij}(x)=|F_{ij}(x)-\widehat{F}_{ij}(x)|,\qquad u_P(x)=\max_{i<j}\frac{e_{ij}(x)}{D_{ij}+e_{ij}(x)}, D ij = E ∈ P ∑ ∣ γ ij ( E ) ∣ , e ij ( x ) = ∣ F ij ( x ) − F ij ( x ) ∣ , u P ( x ) = i < j max D ij + e ij ( x ) e ij ( x ) ,
using 0 / 0 = 0 0/0=0 0/0 = 0 . For the fixed-measure sampling step used later by Snapshot, the integrated interpolation estimate is
E [ ∫ u P ( x ) d μ ( x ) ] ≤ 2 ( k − 1 ) m + 1 . (22) \mathbb{E}\left[\int u_P(x)\,d\mu(x)\right]\leq\frac{2(k-1)}{m+1}. \tag*{(22)} E [ ∫ u P ( x ) d μ ( x ) ] ≤ m + 1 2 ( k − 1 ) . (22)
Here the underlying measures and permanent boundaries are fixed before sampling. We prove (22) , including its zero cases. For finite row vectors x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k put d i j = ∥ x i − x j ∥ 1 d_{ij}=\lVert x_i-x_j\rVert_1 d ij = ∥ x i − x j ∥ 1 and
s a = max i < j ∣ x i ( a ) − x j ( a ) ∣ d i j . s_a=\max_{i<j}\frac{|x_i(a)-x_j(a)|}{d_{ij}}. s a = i < j max d ij ∣ x i ( a ) − x j ( a ) ∣ .
Then ∑ a s a ≤ k − 1 \sum_a s_a\leq k-1 ∑ a s a ≤ k − 1 , a special case of the subspace sensitivity bound [12 Lemma 2.6] . To prove this elementary version, identify identical rows first, so all remaining edge distances are positive. If there is one row the assertion is immediate. Otherwise take a minimum spanning tree on the distinct rows. Every edge e e e on the path from i i i to j j j has d e ≤ d i j d_e\leq d_{ij} d e ≤ d ij , since replacing a longer edge by ( i , j ) (i,j) ( i , j ) would reduce the tree’s total length. Hence
∣ x i ( a ) − x j ( a ) ∣ d i j ≤ ∑ e ∈ path ( i , j ) ∣ x e − ( a ) − x e + ( a ) ∣ d e ≤ ∑ e ∈ T ∣ x e − ( a ) − x e + ( a ) ∣ d e . \frac{|x_i(a)-x_j(a)|}{d_{ij}}\leq\sum_{e\in\operatorname{path}(i,j)}\frac{|x_{e^-}(a)-x_{e^+}(a)|}{d_e}\leq\sum_{e\in T}\frac{|x_{e^-}(a)-x_{e^+}(a)|}{d_e}. d ij ∣ x i ( a ) − x j ( a ) ∣ ≤ e ∈ path ( i , j ) ∑ d e ∣ x e − ( a ) − x e + ( a ) ∣ ≤ e ∈ T ∑ d e ∣ x e − ( a ) − x e + ( a ) ∣ .
Taking the maximum and summing over coordinates gives one unit per tree edge, at most k − 1 k-1 k − 1 . Identical-row quotients are zero.
Now delete an interior point from a deterministic augmented grid. For a fixed pair let a , b a,b a , b be the signed differences on its two incident cells, put A = ∣ a ∣ + ∣ b ∣ A=|a|+|b| A = ∣ a ∣ + ∣ b ∣ , and let V V V be its total variation over the augmented cells. The interpolation error e e e at the deleted point is at most A A A . The remaining cell variation is D ( − z ) = V − A + ∣ a + b ∣ D^{(-z)}=V-A+|a+b| D ( − z ) = V − A + ∣ a + b ∣ . If V > 0 V>0 V > 0 , cross multiplication gives
e D ( − z ) + e ≤ A V , e ( V − A ) ≤ A ( V − A + ∣ a + b ∣ ) . \frac{e}{D^{(-z)}+e}\leq\frac{A}{V},\qquad e(V-A)\leq A(V-A+|a+b|). D ( − z ) + e e ≤ V A , e ( V − A ) ≤ A ( V − A + ∣ a + b ∣ ) .
The second inequality uses e ≤ A e\leq A e ≤ A and V − A ≥ 0 V-A\geq0 V − A ≥ 0 . If V = 0 V=0 V = 0 , both incident differences and the error vanish. The maximum normalized deletion error is therefore at most the sum of the two incident coordinate sensitivities. Each cell is incident to at most two deletion points, so the sum of these maxima over any subset of interior points is at most 2 ( k − 1 ) 2(k-1) 2 ( k − 1 ) .
Adjoin an independent ( m + 1 ) (m+1) ( m + 1 ) st μ \mu μ -sample. Atomlessness eliminates coincidences with other samples and the permanent boundaries almost surely. By exchangeability, each sampled point is equally likely to be the distinguished point removed from the augmented grid. Removing it gives precisely the interpolation error of the original experiment at an independent sample. Divide the deletion bound by m + 1 m+1 m + 1 and average to prove (22) . The same argument works conditional on any independent information that fixes the measures and permanent grid before sampling.
Lemma F.2 (Aggregate endpoint interpolation). After P P P , let adaptive groups of endpoints be generated. Before each group’s fresh randomness, its conditional endpoint marginal laws sum to at
most a predictable measure K g K_g K g . Suppose, pathwise, ∑ g \sum_g ∑ g reached K g ≤ Λ s u m μ K_g \le\Lambda_{\mathrm{sum}}\mu K g ≤ Λ sum μ , and let b > 0 b>0 b > 0 . Except with probability
2 ( k − 1 ) Λ s u m ( 1 + b ) b ( m + 1 ) , (23) \frac{2(k-1)\Lambda_{\mathrm{sum}}(1+b)}{b(m+1)}, \tag*{(23)} b ( m + 1 ) 2 ( k − 1 ) Λ sum ( 1 + b ) , (23)
every pair and every finite union E E E with boundaries in P P P or the generated list satisfy
∣ γ i j ( E ) − γ ~ i j ( E ) ∣ ≤ b D i j . |\gamma_{ij}(E)-\widetilde{\gamma}_{ij}(E)|\le bD_{ij}. ∣ γ ij ( E ) − γ ij ( E ) ∣ ≤ b D ij .
The estimate uses the original immutable grid. It includes zero disagreements, adaptive stopping, rejecting groups, and unions chosen after all values have been observed.
Proof. Before a group, u P u_P u P is a fixed nonnegative measurable function of its history. Conditional marginal domination bounds its expected endpoint charge by ∫ u P d K g \int u_P\,\mathrm{d}K_g ∫ u P d K g . Sum by conditional expectation, use the pathwise measure bound, and apply (22) :
E [ ∑ Z g e n e r a t e d u P ( Z ) ] ≤ 2 ( k − 1 ) Λ s u m m + 1 . \mathbb{E}\left[\sum_{Z\ \mathrm{generated}}u_P(Z)\right]\le\frac{2(k-1)\Lambda_{\mathrm{sum}}}{m+1}. E Z generated ∑ u P ( Z ) ≤ m + 1 2 ( k − 1 ) Λ sum .
For each pair put E i j ∗ = ∑ Z e i j ( Z ) E_{ij}^{*}=\sum_Z e_{ij}(Z) E ij ∗ = ∑ Z e ij ( Z ) . The common charge is at least E i j ∗ / ( D i j + E i j ∗ ) E_{ij}^{*}/(D_{ij}+E_{ij}^{*}) E ij ∗ / ( D ij + E ij ∗ ) . If any E i j ∗ > b D i j E_{ij}^{*}>bD_{ij} E ij ∗ > b D ij , that charge exceeds b / ( 1 + b ) b/(1+b) b / ( 1 + b ) , including when D i j = 0 D_{ij}=0 D ij = 0 . One Markov inequality proves (23) . Outside the event all E i j ∗ ≤ b D i j E_{ij}^{*}\le bD_{ij} E ij ∗ ≤ b D ij . Telescope cumulative errors at the endpoints of each union; original boundaries contribute zero. Reused endpoints are charged at their original generation. □
Stable witnesses and a large compensation domain
The input to Repair consists of disjoint recorded whole endowments W 1 , … , W k W_1,\ldots,W_k W 1 , … , W k and a disjoint positive buffer B B B , satisfying
g i j ( W ) ≥ − τ μ i ( B ) . (24) g_{ij}(W)\ge-\tau\mu_i(B). \tag*{(24)} g ij ( W ) ≥ − τ μ i ( B ) . (24)
There is no upper bound on endowment values relative to the buffer. Normalize ν i = μ i / μ i ( B ) \nu_i=\mu_i/\mu_i(B) ν i = μ i / μ i ( B ) , and draw m m m independent samples from μ = k − 1 ∑ i ν i ∣ B \mu=k^{-1}\sum_i\nu_i|_B μ = k − 1 ∑ i ν i ∣ B . Before sampling, take each row’s q q q equally spaced interior quantiles. Their common coarse grid has at most k q + 1 kq+1 k q + 1 logical cells, each of every row’s value at most σ = 1 / ( q + 1 ) \sigma=1/(q+1) σ = 1/ ( q + 1 ) . The sampled refinement has at most k q + m + 1 ≤ 2 m kq+m+1\le2m k q + m + 1 ≤ 2 m cells. All later interpolation uses this immutable refinement.
For each of k k k batches, each unordered row pair, and each of L L L repetitions, choose two representative cells among the coarse parents not previously removed. Remove the whole parents of both choices before the next request. Thus there are
r = k ( k 2 ) L r=k\binom{k}{2}L r = k ( 2 k ) L
requests and at most 2 r 2r 2 r removed parents. The selection rule below is applied to the original-buffer normalized vectors ( ν i ( E ) , ν j ( E ) ) (\nu_i(E),\nu_j(E)) ( ν i ( E ) , ν j ( E )) . Its conclusion holds for arbitrary later normalizations; the selected pair itself need not be invariant under rescaling the rows.
Lemma F.3 (Maximum-determinant witnesses). For a finite nonempty family of nonnegative vectors x E ∈ R 2 x_E\in\mathbb{R}^2 x E ∈ R 2 , choose an ordered pair ( F , G ) (F,G) ( F , G ) maximizing
( ∣ det ( x F , x G ) ∣ , ∥ x F ∥ 1 + ∥ x G ∥ 1 ) \left(|\det(x_F,x_G)|,\ \lVert x_F\rVert_1+\lVert x_G\rVert_1\right) ( ∣ det ( x F , x G ) ∣ , ∥ x F ∥ 1 + ∥ x G ∥ 1 )
lexicographically, with a fixed geometric tie rule; repeated cells are allowed. Every linear functional a a a satisfies
∣ a ( x E ) ∣ ≤ ∣ a ( x F ) ∣ + ∣ a ( x G ) ∣ ≤ 2 max { ∣ a ( x F ) ∣ , ∣ a ( x G ) ∣ } . |a(x_E)| \le|a(x_F)| + |a(x_G)| \le2\max\{|a(x_F)|, |a(x_G)|\}. ∣ a ( x E ) ∣ ≤ ∣ a ( x F ) ∣ + ∣ a ( x G ) ∣ ≤ 2 max { ∣ a ( x F ) ∣ , ∣ a ( x G ) ∣ } .
Deleting unchosen alternatives preserves the chosen pair.
Proof. If the maximum determinant is nonzero, Cramer’s rule writes x E = α x F + β x G x_E = \alpha x_F + \beta x_G x E = α x F + β x G , with ∣ α ∣ , ∣ β ∣ ≤ 1 |\alpha|, |\beta| \le1 ∣ α ∣ , ∣ β ∣ ≤ 1 by maximality. Apply a a a and the triangle inequality. If all determinants vanish, the nonnegative vectors lie on a common ray. The secondary criterion, which permits ( F , F ) (F,F) ( F , F ) , selects a vector of maximum total mass; every other vector is a scalar multiple in [ 0 , 1 ] [0,1] [ 0 , 1 ] of it. If that mass is zero, all vectors vanish. This proves the bound in every case. Deleting alternatives other than the selected pair preserves both its maximality and its position in the fixed tie order.
Let R R R be the union of the unremoved coarse parents. Since 4 r ≤ q + 1 4r \le q + 1 4 r ≤ q + 1 , every row satisfies
ν i ( R ) ≥ 1 − 2 r σ ≥ 1 2 . (25) \nu_i(R) \ge1 - 2r\sigma\ge\frac{1}{2}. \tag*{(25)} ν i ( R ) ≥ 1 − 2 r σ ≥ 2 1 . (25)
In particular, each selection has a nonempty available domain. Let P R \mathcal{P}_R P R be the finite family of refined grid cells retained in R R R . Put w i = μ i / μ i ( R ) w_i = \mu_i/\mu_i(R) w i = μ i / μ i ( R ) and
A i j = max E ∈ P R ∣ ( w i − w j ) ( E ) ∣ . A_{ij} = \max_{E\in\mathcal{P}_R}|(w_i-w_j)(E)|. A ij = E ∈ P R max ∣ ( w i − w j ) ( E ) ∣.
Every refined cell has w i w_i w i -value at most η = 2 / ( s 8 ℓ ) \eta= 2/(s^8\ell) η = 2/ ( s 8 ℓ ) under the parameters below; more precisely its value is at most 2 / ( q + 1 ) 2/(q+1) 2/ ( q + 1 ) . In each selected pair choose the cell with larger absolute ( w i − w j ) (w_i-w_j) ( w i − w j ) -value. Every final cell of R R R was available at each earlier selection. Lemma F.3 therefore provides L L L witnesses per row pair and batch, in distinct removed parents, with absolute signed value at least A i j / 2 A_{ij}/2 A ij /2 , and hence at least A i j / 3 A_{ij}/3 A ij /3 .
The following stability argument is needed because R R R and its normalizers depend on the sampled grid. A fixed-measure interpolation estimate cannot simply be conditioned on their realized values.
Lemma F.4 (Deletion stability). For each realized coarse-plus-sample grid there is a measurable set B B B of virtual coordinates such that
E [ μ ( B ) ] ≤ 4 r + 4 k 2 m + 1 . (26) \mathbb{E}[\mu(B)] \le\frac{4r+4k^2}{m+1}. \tag*{(26)} E [ μ ( B )] ≤ m + 1 4 r + 4 k 2 . (26) If z ∉ B z \notin B z ∈ / B lies in a retained refined cell E = [ a , b ] E = [a,b] E = [ a , b ] , then, simultaneously for every pair i , j i,j i , j and arbitrary positive normalizers defining w i , w j w_i,w_j w i , w j ,
∣ ( w i − w j ) ( [ a , z ] ) ∣ ≤ 2 A i j , ∣ ( w i − w j ) ( [ z , b ] ) ∣ ≤ 2 A i j . |(w_i-w_j)([a,z])| \le2A_{ij}, \qquad|(w_i-w_j)([z,b])| \le2A_{ij}. ∣ ( w i − w j ) ([ a , z ]) ∣ ≤ 2 A ij , ∣ ( w i − w j ) ([ z , b ]) ∣ ≤ 2 A ij . Here A i j A_{ij} A ij is the maximum full-cell disagreement on the retained original sampled grid. Original grid endpoints have zero interpolation error and may be omitted from the exceptional set.
Proof. Insert z z z into the sampled grid and run the same deterministic sequence of selections. Protect the four endpoint slots of every selected pair. After all removals, select one more maximum-determinant pair for each ordered row pair in the retained domain and protect its four endpoints. Define B B B by the event that the inserted coordinate is one of these protected endpoints. All selections are finite measurable comparisons, so this set and its dependence on the samples are measurable.
Suppose z z z is unprotected and its coarse parent is retained on the original grid. Deleting z z z merges two adjacent cells within that parent. At each selection, neither split cell was selected. Removing
those unchosen alternatives leaves the augmented-grid winner unchanged. If adding the merged cell changed the winner, that winner would contain the merged cell, and this coarse parent would be removed. At the first possible divergence this contradicts its survival in the original run. Induction therefore gives identical removed parents and identical earlier witnesses on the two grids. The protected final pair also avoids z z z ; its two cells survive unchanged on the original grid. Apply Lemma F.3 to either split cell, with the arbitrary normalizing coefficients. Both final witnesses have disagreement at most A i j A_{ij} A ij in the original retained grid, proving the two bounds.
For the expectation, adjoin an independent ( m + 1 ) (m+1) ( m + 1 ) st sample and regard each of the m + 1 m+1 m + 1 samples in turn as the inserted point. Atomlessness makes them distinct from one another and from fixed coarse endpoints almost surely. At most 4 r + 4 k 2 4r+4k^2 4 r + 4 k 2 of these coordinates can be protected. Exchangeability and integration over the distinguished point give (26) . No independence between the retained domain and the original samples is used.
Let F i F_i F i be the cumulative w i ∣ R w_i|_R w i ∣ R -value and let F ^ i \widehat{F}_i F i be its linear interpolant on the original grid. At a nonexceptional point, its pairwise interpolation error is a convex combination of the signed prefix and negative signed suffix discrepancies. Consequently
∣ ( F i − F j ) ( z ) − ( F ^ i − F ^ j ) ( z ) ∣ ≤ 2 A i j . (27) \left|(F_i-F_j)(z)-(\widehat{F}_i-\widehat{F}_j)(z)\right|\le2A_{ij}. \tag*{(27)} ( F i − F j ) ( z ) − ( F i − F j ) ( z ) ≤ 2 A ij . (27)
The statement is uniform over the normalization constants, so it applies to the actual sample-dependent R R R . Cells outside R R R have zero rows and zero error. Logical cells crossing recorded physical joins are interpreted using volume along the recorded domain, as in Section F.1.
Assignment slack and whole-cell payments
For each pair and batch, list its witnesses as E 1 , … , E L E_1,\ldots,E_L E 1 , … , E L and write γ a = ( w i − w j ) ( E a ) \gamma_a=(w_i-w_j)(E_a) γ a = ( w i − w j ) ( E a ) . Independently choose a uniform T ∈ { 0 , … , L } T\in\{0,\ldots,L\} T ∈ { 0 , … , L } . Start with the negative witnesses, add positive ones of index at most T T T , and remove negative ones of index at most T T T . The resulting signed value is
∑ γ a < 0 γ a + ∑ a ≤ T ∣ γ a ∣ . \sum_{\gamma_a<0}\gamma_a+\sum_{a\le T}|\gamma_a|. γ a < 0 ∑ γ a + a ≤ T ∑ ∣ γ a ∣.
Its successive increments are at least A i j / 3 A_{ij}/3 A ij /3 when A i j > 0 A_{ij}>0 A ij > 0 . Union the pair pieces within each batch, then apply an independent uniform permutation of batches to old labels to obtain seeds Z j Z_j Z j . All seeds are disjoint and lie outside R R R . Each seed has every w i w_i w i -value at most ( k 2 ) L η \binom{k}{2}L\eta ( 2 k ) L η ; all seeds together have every ν i \nu_i ν i -value at most r σ < 1 / 8 r\sigma<1/8 r σ < 1/8 . Their labeled distribution is exchangeable even when different batches have different distributions.
Set V i j = w i ( W j ∪ Z j ) V_{ij}=w_i(W_j\cup Z_j) V ij = w i ( W j ∪ Z j ) . Choose a maximum-sum assignment π \pi π for cake, a minimum-sum assignment for chores. Cake has edge j → i j\to i j → i of weight V i , π ( j ) − V i , π ( i ) + 2 λ A i j V_{i,\pi(j)}-V_{i,\pi(i)}+2\lambda A_{ij} V i , π ( j ) − V i , π ( i ) + 2 λ A ij ; chores has edge i → j i\to j i → j of weight V i , π ( i ) − V i , π ( j ) + 2 λ A i j V_{i,\pi(i)}-V_{i,\pi(j)}+2\lambda A_{ij} V i , π ( i ) − V i , π ( j ) + 2 λ A ij . Reject a positive cycle. We now prove that its conditional probability, for every preparation, is at most
k 2 ( k − 1 ) [ 12 λ ln ( 2 k ) + 1 ] L + 1 . (28) \frac{k^2(k-1)[12\lambda\ln(2k)+1]}{L+1}. \tag*{(28)} L + 1 k 2 ( k − 1 ) [ 12 λ ln ( 2 k ) + 1 ] . (28)
For an unordered pair { i , h } \{i,h\} { i , h } and column j j j , let Φ i j \Phi_{ij} Φ ij be the optimum after deleting row i i i and column j j j , using the same maximization or minimization convention. Define
d i h , j = ∣ V i j + Φ i j − V h j − Φ h j ∣ . d_{ih,j}=\left|V_{ij}+\Phi_{ij}-V_{hj}-\Phi_{hj}\right|. d ih , j = ∣ V ij + Φ ij − V hj − Φ hj ∣ .
Condition on the batch permutation and every threshold except that of pair { i , h } \{i,h\} { i , h } in the batch assigned to column j j j . The deleted-column scores do not depend on this threshold. The signed comparison changes monotonically, with step at least A i h / 3 A_{ih}/3 A ih /3 . For A i h > 0 A_{ih}>0 A ih > 0 , any interval of length 4 λ A i h / u 4\lambda A_{ih}/u 4 λ A ih / u therefore contains at most 12 λ / u + 1 12\lambda/u+1 12 λ / u + 1 possible scores. Set
X i h , j = min { 1 , 2 λ A i h / d i h , j } , Z i h , j = ( X i h , j − 1 / ( 2 k ) ) + , X_{ih,j}=\min\{1,2\lambda A_{ih}/d_{ih,j}\},\qquad Z_{ih,j}=(X_{ih,j}-1/(2k))_+, X ih , j = min { 1 , 2 λ A ih / d ih , j } , Z ih , j = ( X ih , j − 1/ ( 2 k ) ) + ,
where a zero gap gives X = 1 X=1 X = 1 ; set both variables to zero when A i h = 0 A_{ih}=0 A ih = 0 . For 0 < u ≤ 1 0<u\le1 0 < u ≤ 1 , the conditional tail bound is
P [ X i h , j ≥ u ] ≤ ( 12 λ / u + 1 ) / ( L + 1 ) . \mathbb{P}[X_{ih,j}\ge u]\le(12\lambda/u+1)/(L+1). P [ X ih , j ≥ u ] ≤ ( 12 λ / u + 1 ) / ( L + 1 ) .
Integrating this bound from 1 / ( 2 k ) 1/(2k) 1/ ( 2 k ) to one and averaging over the conditioning gives
E [ Z i h , j ] ≤ 12 λ ln ( 2 k ) + 1 − 1 / ( 2 k ) L + 1 . (29) \mathbb{E}[Z_{ih,j}]\le\frac{12\lambda\ln(2k)+1-1/(2k)}{L+1}. \tag*{(29)} E [ Z ih , j ] ≤ L + 1 12 λ ln ( 2 k ) + 1 − 1/ ( 2 k ) . (29)
If a positive cycle exists, choose a simple one. Let Δ ≥ 0 \Delta\ge0 Δ ≥ 0 be the loss in assignment value for cake, or increase in assignment cost for chores, when each row takes the column specified by the cycle. Optimality makes this quantity nonnegative. The ordinary edge weights sum to − Δ -\Delta − Δ , so positivity implies Δ < 2 λ ∑ c y c l e A i h \Delta<2\lambda\sum_{\mathrm{cycle}}A_{ih} Δ < 2 λ ∑ cycle A ih . For an edge transferring column j j j from its current recipient h h h to i i i , the chosen assignment is optimal among those assigning j j j to h h h , while the cyclic competitor is feasible among those assigning j j j to i i i . In the maximizing case this gives
O P T − Δ ≤ V i j + Φ i j ≤ O P T = V h j + Φ h j . \mathrm{OPT}-\Delta\le V_{ij}+\Phi_{ij}\le\mathrm{OPT}=V_{hj}+\Phi_{hj}. OPT − Δ ≤ V ij + Φ ij ≤ OPT = V hj + Φ hj .
In the minimizing case all inequalities reverse after replacing O P T − Δ \mathrm{OPT}-\Delta OPT − Δ by O P T + Δ \mathrm{OPT}+\Delta OPT + Δ . In either case d i h , j ≤ Δ d_{ih,j}\le\Delta d ih , j ≤ Δ . If Δ > 0 \Delta>0 Δ > 0 , then
∑ c y c l e X i h , j ≥ ∑ c y c l e min { 1 , 2 λ A i h / Δ } ≥ 1. \sum_{\mathrm{cycle}}X_{ih,j}\ge\sum_{\mathrm{cycle}}\min\{1,2\lambda A_{ih}/\Delta\}\ge1. cycle ∑ X ih , j ≥ cycle ∑ min { 1 , 2 λ A ih /Δ } ≥ 1.
If Δ = 0 \Delta=0 Δ = 0 , some cycle edge has A i h > 0 A_{ih}>0 A ih > 0 and gap zero, so the same conclusion follows. The cycle has at most k k k edges; its Z Z Z -sum is at least 1 / 2 1/2 1/2 . Its pair-column triples are distinct: even a two-cycle uses different columns. The sum over all k ( k 2 ) k\binom{k}{2} k ( 2 k ) triples must therefore be at least 1 / 2 1/2 1/2 . Markov and (29) prove (28) . No winning-assignment event was conditioned on.
If there is no positive cycle, add a dummy source with zero-weight edges to all vertices and let t i t_i t i be the maximum weight of a simple path ending at i i i , including the zero path. Appending an edge to a maximizing path and deleting any resulting nonpositive cycles cannot decrease its weight. Thus these nonnegative potentials give the ideal payment inequalities
{ V i , π ( i ) + t i − V i , π ( j ) − t j ≥ 2 λ A i j , cake , V i , π ( j ) + t j − V i , π ( i ) − t i ≥ 2 λ A i j , chores . (30) \begin{cases}
V_{i,\pi(i)}+t_i-V_{i,\pi(j)}-t_j\ge2\lambda A_{ij}, & \text{cake},\\
V_{i,\pi(j)}+t_j-V_{i,\pi(i)}-t_i\ge2\lambda A_{ij}, & \text{chores}. \tag*{(30)}
\end{cases} { V i , π ( i ) + t i − V i , π ( j ) − t j ≥ 2 λ A ij , V i , π ( j ) + t j − V i , π ( i ) − t i ≥ 2 λ A ij , cake , chores . (30)
Initial R R R -normalized envy is at most 2 τ = 1 / ( 2 s 2 ) 2\tau=1/(2s^2) 2 τ = 1/ ( 2 s 2 ) , by (25) . Each seed has value at most 1 / ( 4 s 2 ) 1/(4s^2) 1/ ( 4 s 2 ) . For cake put M i = max j V i j M_i=\max_j V_{ij} M i = max j V ij . The identity assignment has total shortfall at most 3 k / ( 4 s 2 ) 3k/(4s^2) 3 k / ( 4 s 2 ) from these row maxima, so a maximizing assignment satisfies
∑ i ( M i − V i , π ( i ) ) ≤ 3 k / ( 4 s 2 ) . \sum_i(M_i-V_{i,\pi(i)})\le3k/(4s^2). i ∑ ( M i − V i , π ( i ) ) ≤ 3 k / ( 4 s 2 ) .
The ordinary part of an edge entering i i i is bounded by its assigned shortfall. For chores, put m i = min j V i j m_i=\min_j V_{ij} m i = min j V ij . A minimizing assignment similarly satisfies ∑ i ( V i , π ( i ) − m i ) ≤ 3 k / ( 4 s 2 ) \sum_i(V_{i,\pi(i)}-m_i)\le3k/(4s^2) ∑ i ( V i , π ( i ) − m i ) ≤ 3 k / ( 4 s 2 ) , and an ordinary edge leaving i i i is bounded by that row’s regret. A simple path charges each row once. Since A i j ≤ η A_{ij} \le\eta A ij ≤ η and 2 λ η ≤ 1 / ( 4 s 2 ) 2\lambda\eta\le1/(4s^2) 2 λ η ≤ 1/ ( 4 s 2 ) ,
0 ≤ t i ≤ 3 k / ( 4 s 2 ) + ( k − 1 ) 2 λ η < k / s 2 , ∑ i t i < k 2 / s 2 < 1 / 16. (31) 0 \le t_i \le3k/(4s^2) + (k-1)2\lambda\eta< k/s^2,\qquad\sum_i t_i < k^2/s^2 < 1/16. \tag*{(31)} 0 ≤ t i ≤ 3 k / ( 4 s 2 ) + ( k − 1 ) 2 λ η < k / s 2 , i ∑ t i < k 2 / s 2 < 1/16. (31)
This argument treats credits for cake and taxes for chores separately.
Lemma F.5 (Whole-cell payments). There are disjoint unions Y j Y_j Y j of retained grid cells such that
0 ≤ ϵ j = t j − w j ( Y j ) ≤ min { t j , η } , ∣ ( w i − w j ) ( Y j ) ∣ ≤ 4 k A i j . 0 \le\epsilon_j = t_j - w_j(Y_j) \le\min\{t_j,\eta\},\qquad|(w_i-w_j)(Y_j)| \le4kA_{ij}. 0 ≤ ϵ j = t j − w j ( Y j ) ≤ min { t j , η } , ∣ ( w i − w j ) ( Y j ) ∣ ≤ 4 k A ij . They are computable from the recorded finite table without further queries. The protocol may enumerate the finitely many cell-ownership tables and select the first satisfying these inequalities. The proof below establishes that such a table exists; this finite choice also makes the selection measurable.
Proof. Write a i E = w i ( E ) a_{iE}=w_i(E) a i E = w i ( E ) and start with the fractional allocation x E j = t j x_{Ej}=t_j x E j = t j and unused fraction x E 0 = 1 − ∑ j t j x_{E0}=1-\sum_j t_j x E 0 = 1 − ∑ j t j in every cell. Keep all cell-sum equations and the k k k owner equations ∑ E a j E x E j = t j \sum_E a_{jE}x_{Ej}=t_j ∑ E a j E x E j = t j . Initially also keep every discrepancy equation
∑ E ( a i E − a j E ) x E j = 0. \sum_E(a_{iE}-a_{jE})x_{Ej}=0. E ∑ ( a i E − a j E ) x E j = 0. Fix any coordinate that reaches zero or one. Float the remaining coordinates in a kernel direction until a new coordinate reaches a boundary, or until the remaining columns are independent.
Let v v v be the number of fractional coordinates, c c c the number of split cells, and d d d the number of discrepancy equations still kept. At a state with independent columns,
v ≤ c + k + d , 2 c ≤ v . v \le c+k+d,\qquad2c \le v. v ≤ c + k + d , 2 c ≤ v . Every fractional coordinate appears in at most k k k discrepancy equations, since its recipient is fixed. If v > 4 k v>4k v > 4 k , the displayed rank bound gives d ≥ v / 4 d\ge v/4 d ≥ v /4 . Summing supports therefore shows that some discrepancy equation involves at most 4 k 4k 4 k currently fractional coordinates. Drop that equation and continue floating. Its total eventual change, including all later rounding, is at most 4 k A i j 4kA_{ij} 4 k A ij : each remaining coefficient has magnitude at most A i j A_{ij} A ij , each coordinate changes by at most one, and all other real-color coordinates remain fixed forever. When at most 4 k 4k 4 k fractional coordinates remain, the same bound applies to each undropped equation. This process is finite: every step fixes a coordinate or drops an equation. All owner equations remain exact.
Round the remaining fractions using sorted slots [17 ] . For each recipient, sort fractional cells by decreasing own value, place their fractional amounts consecutively into unit slots, and require each full slot to receive one contributing cell. The fractional slot incidences satisfy Hall’s condition, since each cell has total capacity at most one. An integral matching therefore fills all full slots with distinct cells. Consecutive-slot comparison bounds each recipient’s load within one cell of its fractional target. If it exceeds that target, delete matched cells until it first falls below it; the resulting deficit is at most η \eta η . Keep all previously integral allocations.
Crucially, the matching uses only positive fractional incidences, so no zero real-color coordinate acquires a cell, and no fixed one-coordinate changes. The robust bound for every dropped equation therefore continues to hold after this rounding and trimming. Nonnegative loads also bound each deficit by t j t_j t j . This proves all three assertions.
Fresh correction attempts and their physical boundaries
Process recipients in a fixed order. Before correcting j j j , remove all pending whole-cell payments and completed accepted payments from R R R , leaving the actual domain S S S . A positive deficit is filled by a fresh circular piece C j ⊆ S C_j \subseteq S C j ⊆ S with exact own value ϵ j \epsilon_j ϵ j ; a zero deficit uses the empty piece. Put P j = Y j ∪ C j P_j = Y_j \cup C_j P j = Y j ∪ C j , record its endpoints, and check
w j ( P j ) = t j , ∣ w i ( P j ) − t j ∣ ≤ λ A i j ( i ∈ [ k ] ) . w_j(P_j)=t_j,\qquad|w_i(P_j)-t_j|\leq\lambda A_{ij}\quad(i\in[k]). w j ( P j ) = t j , ∣ w i ( P j ) − t j ∣ ≤ λ A ij ( i ∈ [ k ]) .
On failure restore the pre-attempt physical domain and make another fresh attempt for this recipient, retaining and charging every query already made. Stop at the first passing attempt, or reject the whole Repair trial after ℓ \ell ℓ unsuccessful attempts. A rejected attempt creates no physical hole. The analytic exceptional set B \mathcal{B} B is used only in the proof; no membership oracle for it is needed.
Pending payments satisfy w i ( Y j ) ≤ t j + 4 k A i j w_i(Y_j)\leq t_j+4kA_{ij} w i ( Y j ) ≤ t j + 4 k A ij ; accepted ones satisfy w i ( P j ) ≤ t j + λ A i j w_i(P_j)\leq t_j+\lambda A_{ij} w i ( P j ) ≤ t j + λ A ij . Our parameters give
∑ j t j < 1 / 16 , k λ η < 1 / 16 , 16 k ≤ λ . (32) \sum_j t_j<1/16,\qquad k\lambda\eta<1/16,\qquad16k\leq\lambda. \tag*{(32)} j ∑ t j < 1/16 , k λ η < 1/16 , 16 k ≤ λ . (32)
Thus w i ( S ) > 7 / 8 w_i(S)>7/8 w i ( S ) > 7/8 at every reached attempt, including one that fails. The target ϵ j ≤ t j < 1 / 16 \epsilon_j\leq t_j<1/16 ϵ j ≤ t j < 1/16 fits inside S S S . This is a physical supply invariant; it does not rely on successful interpolation.
Lemma F.6 (Maximum-cell envelope). For recipient j j j and retained cell E ∈ P R E\in\mathcal{P}_R E ∈ P R , let
H j ( E ) = max i : A i j > 0 ∣ ( w i − w j ) ( E ) ∣ A i j , h j ∣ E = H j ( E ) / ∣ E ∣ , H_j(E)=\max_{i:A_{ij}>0}\frac{|(w_i-w_j)(E)|}{A_{ij}},\qquad h_j|_E=H_j(E)/|E|, H j ( E ) = i : A ij > 0 max A ij ∣ ( w i − w j ) ( E ) ∣ , h j ∣ E = H j ( E ) /∣ E ∣ , with empty maximum zero and with volume interpreted on the recorded logical cell. For N ≤ 2 m N\leq2m N ≤ 2 m retained cells,
0 ≤ H j ( E ) ≤ 1 , ∫ R h j ≤ N , ∣ γ ^ i j ( C ) ∣ ≤ A i j ∫ C h j , (33) 0\leq H_j(E)\leq1,\qquad\int_R h_j\leq N,\qquad|\widehat{\gamma}_{ij}(C)|\leq A_{ij}\int_C h_j, \tag*{(33)} 0 ≤ H j ( E ) ≤ 1 , ∫ R h j ≤ N , ∣ γ ij ( C ) ∣ ≤ A ij ∫ C h j , (33) where γ ^ i j \widehat{\gamma}_{ij} γ ij is the interpolated signed measure. At every fresh attempt,
E [ ∫ C j h j ∣ H ] ≤ 2 ϵ j N ≤ 2 η N . (34) \mathbb{E}\left[\left.\int_{C_j}h_j\,\right|\,\mathcal{H}\right]\leq2\epsilon_jN\leq2\eta N. \tag*{(34)} E [ ∫ C j h j H ] ≤ 2 ϵ j N ≤ 2 η N . (34) Proof. Every cell ratio is at most one; integration bounds total envelope mass by the cell count. The absolute interpolated pairwise density is bounded by A i j h j A_{ij}h_j A ij h j , including A i j = 0 A_{ij}=0 A ij = 0 , when that density vanishes. The circular inclusion law (21) and w j ( S ) > 7 / 8 w_j(S)>7/8 w j ( S ) > 7/8 give the conditional expectation, even on cutter-null subintervals.
Only grid boundaries, the new circular endpoints, and endpoints of previous accepted corrections occur in the actual candidate’s virtual boundary. Whole-cell payments and removed coarse parents use grid boundaries. There are at most 2 k 2k 2 k non-grid endpoints altogether. This count includes inherited holes from every earlier accepted correction, but excludes physically restored rejecting attempts. If all these points avoid B \mathcal{B} B , telescoping (27) gives
∣ γ i j ( C j ) − γ ^ i j ( C j ) ∣ ≤ 4 k A i j . (35) |\gamma_{ij}(C_j)-\widehat{\gamma}_{ij}(C_j)|\leq4kA_{ij}. \tag*{(35)} ∣ γ ij ( C j ) − γ ij ( C j ) ∣ ≤ 4 k A ij . (35)
Counting only the latest two endpoints would not prove this estimate. If also ∫ C j h j < λ / 4 \int_{C_j}h_j<\lambda/4 ∫ C j h j < λ /4 , then
∣ w i ( P j ) − t j ∣ ≤ 4 k A i j + 4 k A i j + ( λ / 4 ) A i j ≤ λ A i j . (36) |w_i(P_j)-t_j|\leq4kA_{ij}+4kA_{ij}+(\lambda/4)A_{ij}\leq\lambda A_{ij}. \tag*{(36)} ∣ w i ( P j ) − t j ∣ ≤ 4 k A ij + 4 k A ij + ( λ /4 ) A ij ≤ λ A ij . (36)
Thus the actual check passes. The use of a maximum over observers in the envelope avoids an additional union bound over i i i .
We bound all retries without a factor ℓ \ell ℓ in the endpoint exception. Set δ 0 = 1 / ( 32768 k 2 ) \delta_0 = 1/(32768k^2) δ 0 = 1/ ( 32768 k 2 ) and suppose μ ( B ) ≤ δ 0 \mu(B) \le\delta_0 μ ( B ) ≤ δ 0 . Each fresh endpoint has conditional law at most ( 8 / 7 ) w j ∣ R ≤ ( 16 / 7 ) ν j ∣ B (8/7)w_j|_R \le(16/7)\nu_j|_B ( 8/7 ) w j ∣ R ≤ ( 16/7 ) ν j ∣ B . The two endpoints therefore hit B B B with conditional probability at most
a = ( 32 k / 7 ) δ 0 = 1 / ( 7168 k ) . a = (32k/7)\delta_0 = 1/(7168k). a = ( 32 k /7 ) δ 0 = 1/ ( 7168 k ) .
By Lemma F.6 and Markov, the probability that an attempt has no exceptional endpoint but fails its physical check is at most
b = 8 η N / λ ≤ 8 η ( 2 m ) / λ = 1 / 4. (37) b = 8\eta N/\lambda\le8\eta(2m)/\lambda= 1/4. \tag*{(37)} b = 8 η N / λ ≤ 8 η ( 2 m ) / λ = 1/4. (37)
These assertions hold after any previous attempts with no exceptional endpoint; their full query transcripts may affect later replies.
Before the first exceptional endpoint, continuation requires a good but rejected attempt, whose conditional probability is at most b b b . The probability of ever seeing a first exceptional endpoint in a recipient’s stopped sequence is consequently at most a / ( 1 − b ) ≤ 4 a / 3 a/(1-b) \le4a/3 a / ( 1 − b ) ≤ 4 a /3 . Formally, the bound B ∗ = 4 a / 3 B_* = 4a/3 B ∗ = 4 a /3 is invariant under the recurrence a + b B ∗ ≤ B ∗ a+bB_* \le B_* a + b B ∗ ≤ B ∗ . Exhausting ℓ \ell ℓ attempts without an exceptional endpoint has probability at most b ℓ ≤ 4 − ℓ b^\ell\le4^{-\ell} b ℓ ≤ 4 − ℓ by iterated conditioning. The first bad endpoint among all recipients, or exhaustion at some recipient before that event, therefore has probability at most
k ( 4 a / 3 + 4 − ℓ ) ≤ 1 / 5376 + k / ( 4 s 2 ) . (38) k(4a/3 + 4^{-\ell}) \le1/5376 + k/(4s^2). \tag*{(38)} k ( 4 a /3 + 4 − ℓ ) ≤ 1/5376 + k / ( 4 s 2 ) . (38)
All previous accepted endpoints are good on this event’s complement, which justifies the induction used in (35) . We do not condition on a winning assignment or a successful repair.
On acceptance, the ideal assignment inequalities and the checked payment errors imply, for X i = W π ( i ) ∪ Z π ( i ) ∪ P i X_i = W_{\pi(i)} \cup Z_{\pi(i)} \cup P_i X i = W π ( i ) ∪ Z π ( i ) ∪ P i ,
g i j ( X ) / μ i ( R ) ≥ λ A i j ≥ ∣ w i ( P j ) − t j ∣ . (39) g_{ij}(X)/\mu_i(R) \ge\lambda A_{ij} \ge|w_i(P_j)-t_j|. \tag*{(39)} g ij ( X ) / μ i ( R ) ≥ λ A ij ≥ ∣ w i ( P j ) − t j ∣. (39)
The seeds consume less than one eighth of the buffer in every active row. The disjoint accepted payments consume at most ∑ j t j + k λ η < 1 / 8 \sum_j t_j + k\lambda\eta< 1/8 ∑ j t j + k λ η < 1/8 of R R R in every normalized row, and R ⊆ B R \subseteq B R ⊆ B . Hence all additions consume less than one quarter of B B B . Unused parts of removed parents, as well as unused compensation material, remain in the literal final residue.
Parameters and the complete Repair bound
For the original population n n n fix
s = 2 40 max { 4 , n } , ℓ = ⌈ log 2 ( 2 s ) ⌉ , q = s 8 ℓ , m = s 9 ℓ / 128 , L = s 4 ℓ , σ = 1 / ( q + 1 ) , η = 2 / ( s 8 ℓ ) , λ = s , τ = 1 / ( 4 s 2 ) , ϵ 0 = s − 2 , K = 8 / τ , θ = τ / ( 768 m ) = 1 / ( 24 s 11 ℓ ) . (40) \begin{aligned}
s &= 2^{40}\max\{4,n\}, \qquad\ell= \lceil\log_2(2s)\rceil,\\
q &= s^8\ell, \qquad m = s^9\ell/128, \qquad L = s^4\ell,\\
\sigma&= 1/(q+1), \qquad\eta= 2/(s^8\ell), \qquad\lambda= s, \qquad\tau= 1/(4s^2),\\
\epsilon_0 &= s^{-2}, \qquad K = 8/\tau, \qquad\theta= \tau/(768m) = 1/(24s^{11}\ell). \tag*{(40)}
\end{aligned} s q σ ϵ 0 = 2 40 max { 4 , n } , ℓ = ⌈ log 2 ( 2 s )⌉ , = s 8 ℓ , m = s 9 ℓ /128 , L = s 4 ℓ , = 1/ ( q + 1 ) , η = 2/ ( s 8 ℓ ) , λ = s , τ = 1/ ( 4 s 2 ) , = s − 2 , K = 8/ τ , θ = τ / ( 768 m ) = 1/ ( 24 s 11 ℓ ) . (40)
Here q q q , m m m , L L L , ℓ \ell ℓ are integers; divisibility of s s s by 128 makes the formula for m m m exact. These parameters are kept when the active population shrinks. We have s ≥ 2 42 s \ge2^{42} s ≥ 2 42 , 1 ≤ ℓ ≤ s 1 \le\ell\le s 1 ≤ ℓ ≤ s , ln ( 2 k ) ≤ ℓ \ln(2k) \le\ell ln ( 2 k ) ≤ ℓ , and κ = k / s ≤ 2 − 40 \kappa= k/s \le2^{-40} κ = k / s ≤ 2 − 40 . In particular,
k q + 1 ≤ m , 4 r ≤ q + 1 , r σ ≤ k 3 / s 4 < 1 / 8 , L η = 2 / s 4 , ( k 2 ) L η ≤ 1 / ( 4 s 2 ) , 2 λ η ≤ 1 / ( 4 s 2 ) , k 2 / s 2 < 1 / 16 , k ℓ η < 1 / 16 , 16 k ≤ λ , 2 k ℓ ≤ m , 16 k ( k + 2 ) ≤ m , 32 k 4 ℓ ≤ m . \begin{aligned}
kq+1 &\le m, & 4r &\le q+1, & r\sigma&\le k^3/s^4 < 1/8,\\
L\eta&= 2/s^4, & \binom{k}{2}L\eta&\le1/(4s^2), & 2\lambda\eta&\le1/(4s^2),\\
k^2/s^2 &< 1/16, & k\ell\eta&< 1/16, & 16k &\le\lambda,\\
2k\ell&\le m, & 16k(k+2) &\le m, & 32k^4\ell&\le m.
\end{aligned} k q + 1 L η k 2 / s 2 2 k ℓ ≤ m , = 2/ s 4 , < 1/16 , ≤ m , 4 r ( 2 k ) L η k ℓ η 16 k ( k + 2 ) ≤ q + 1 , ≤ 1/ ( 4 s 2 ) , < 1/16 , ≤ m , r σ 2 λ η 16 k 32 k 4 ℓ ≤ k 3 / s 4 < 1/8 , ≤ 1/ ( 4 s 2 ) , ≤ λ , ≤ m .
These verify the deterministic supplies and query allowances above. Markov applied to (26) bounds the probability that μ ( B ) > δ 0 \mu(B)>\delta_0 μ ( B ) > δ 0 by
p g r i d ≤ 4 r + 4 k 2 ( m + 1 ) δ 0 ≤ 2 k 3 L ( m + 1 ) δ 0 ≤ 2 23 κ 5 . p_{\mathrm{grid}}\le\frac{4r+4k^2}{(m+1)\delta_0}\le\frac{2k^3L}{(m+1)\delta_0}\le2^{23}\kappa^5. p grid ≤ ( m + 1 ) δ 0 4 r + 4 k 2 ≤ ( m + 1 ) δ 0 2 k 3 L ≤ 2 23 κ 5 .
The assignment bound (28) , with λ = s \lambda=s λ = s and L = s 4 ℓ L=s^4\ell L = s 4 ℓ , is at most 13 κ 3 13\kappa^3 13 κ 3 . Together with (38) , this gives the unconditional estimate
p r e j e c t ≤ 2 23 κ 5 + 13 κ 3 + 1 / 5376 + k / ( 4 s 2 ) < 1 / 64. (41) p_{\mathrm{reject}}\le2^{23}\kappa^5+13\kappa^3+1/5376+k/(4s^2)<1/64. \tag*{(41)} p reject ≤ 2 23 κ 5 + 13 κ 3 + 1/5376 + k / ( 4 s 2 ) < 1/64. (41)
The final inequality already follows from κ ≤ 1 / 256 \kappa\le1/256 κ ≤ 1/256 and k / ( 4 s 2 ) ≤ 1 / 1024 k/(4s^2)\le1/1024 k / ( 4 s 2 ) ≤ 1/1024 . There is no random reserve-mass or reserve-count check. The analytic bad-grid event, assignment failure, and stopped correction events cover rejection for the actual finite trial.
The coarse quantiles and mixture samples use at most 2 m 2m 2 m Cuts. Every correction attempt uses at most two; all k ℓ k\ell k ℓ attempts therefore use at most m m m more. Recording each endpoint for all original observers gives at most 6 n m 6nm 6 nm total queries and 3 m 3m 3 m Cuts per trial, even when every correction batch exhausts its attempts.
Proposition F.7 (Repair interface). Fix the parameters (40) , an active set of 3 ≤ k ≤ n 3\le k\le n 3 ≤ k ≤ n agents, and the entire history before a fresh trial. Let W 1 , … , W k , B W_1,\ldots,W_k,B W 1 , … , W k , B be disjoint recorded finite unions, with μ i ( B ) > 0 \mu_i(B)>0 μ i ( B ) > 0 for every active i i i and g i j ( W ) ≥ − τ μ i ( B ) g_{ij}(W)\ge-\tau\mu_i(B) g ij ( W ) ≥ − τ μ i ( B ) for all active i , j i,j i , j . One Repair trial either rejects or returns a permutation π \pi π , disjoint additions Y i ⊆ B Y_i\subseteq B Y i ⊆ B , and the literal residue B ′ = B ∖ ⋃ i Y i B'=B\setminus\bigcup_iY_i B ′ = B ∖ ⋃ i Y i , such that
X i = W π ( i ) ∪ Y i is EF among active agents , μ i ( ⋃ j Y j ) ≤ 1 4 μ i ( B ) ( i active ) . X_i=W_{\pi(i)}\cup Y_i\ \text{is EF among active agents},\qquad
\mu_i\left(\bigcup_jY_j\right)\le\frac14\mu_i(B)\quad(i\ \text{active}). X i = W π ( i ) ∪ Y i is EF among active agents , μ i ( j ⋃ Y j ) ≤ 4 1 μ i ( B ) ( i active ) . In particular 3 μ i ( B ) / 4 ≤ μ i ( B ′ ) ≤ μ i ( B ) 3\mu_i(B)/4\le\mu_i(B')\le\mu_i(B) 3 μ i ( B ) /4 ≤ μ i ( B ′ ) ≤ μ i ( B ) . Every old endowment stays whole, all pieces have recorded endpoints, and the additions include both seeds and reserve payments. The conditional acceptance probability exceeds 63 / 64 63/64 63/64 ; every trial uses at most 3 m 3m 3 m Cuts and 6 n m 6nm 6 nm queries.
A rejection commits no allocation: the input sets are retained, although the query history grows. An accepted output is a proposed partition which the caller may retain without committing it. These conventions also apply to Snapshot and Shrink below.
Proof. Take Y i = Z π ( i ) ∪ P i Y_i=Z_{\pi(i)}\cup P_i Y i = Z π ( i ) ∪ P i in the physical construction. Equation (39) gives active EF; the seed and reserve spending estimate gives the displayed bound. The remainder is its literal complement, so no null fragments are lost. The rejection estimate (41) and the cost calculation above hold conditional on the entire history at the trial’s start, including rejected work. They use no completion invariant. Rejection discards the candidate allocation while retaining the already charged query transcript. ∎
Snapshot and prescribed shrinking
The geometric constructions below produce the two contracts used by completion. We first prove the contrast-preservation fact underlying Snapshot.
Lemma F.8 (Contrast preservation). Fix a valid repair input and its preceding history. Suppose that after every preparation, but before the fresh seed thresholds and their independent column permutation, one can select rows i , h i,h i , h and old labels u , v u,v u , v with
( w i − w h ) ( W u ) − ( w i − w h ) ( W v ) ≥ Λ (w_i-w_h)(W_u)-(w_i-w_h)(W_v)\ge\Lambda ( w i − w h ) ( W u ) − ( w i − w h ) ( W v ) ≥ Λ for a fixed Λ > 0 \Lambda>0 Λ > 0 . With probability at least 31 / 64 31/64 31/64 over the whole trial, repair returns an EF allocation X X X , residue T T T , and distinct a , b a,b a , b with g a b ( X ) ≥ ( Λ / 8 ) μ a ( T ) g_{ab}(X)\ge(\Lambda/8)\mu_a(T) g ab ( X ) ≥ ( Λ/8 ) μ a ( T ) .
Proof. Fix a preparation and its selected rows and labels. Exchanging seed columns u , v u,v u , v preserves their conditional distribution and reverses their contribution to the contrast. It is nonnegative with probability at least 1 / 2 1/2 1/2 , including ties. Let S S S denote this preservation event and G G G a repair return. Preparation is deterministic on each sampled table, and its mass guards always hold. Averaging the conditional symmetry and using the unconditional Repair bound gives
P [ S ∩ G ] ≥ 1 2 − P [ G c ] > 31 / 64. \mathbb{P}[S\cap G]\ge\frac{1}{2}-\mathbb{P}[G^{\mathrm{c}}]>31/64. P [ S ∩ G ] ≥ 2 1 − P [ G c ] > 31/64.
This inequality is over the whole trial; it does not assert likely success conditional on each selected table.
On G G G , set d i j = g i j ( X ) / μ i ( R ) d_{ij}=g_{ij}(X)/\mu_i(R) d ij = g ij ( X ) / μ i ( R ) , Δ = max i , j d i j \Delta=\max_{i,j}d_{ij} Δ = max i , j d ij , and e i j = w i ( P j ) − t j e_{ij}=w_i(P_j)-t_j e ij = w i ( P j ) − t j . By (39) , ∣ e i j ∣ ≤ d i j |e_{ij}|\le d_{ij} ∣ e ij ∣ ≤ d ij . The ideally paid matrix H i j = V i , π ( j ) + t j H_{ij}=V_{i,\pi(j)}+t_j H ij = V i , π ( j ) + t j has the row identities
H i j = w i ( X i ) − ( d i j + e i j ) for cake , H i j = w i ( X i ) + ( d i j − e i j ) for chores . H_{ij}=w_i(X_i)-(d_{ij}+e_{ij})\quad\text{for cake},\qquad H_{ij}=w_i(X_i)+(d_{ij}-e_{ij})\quad\text{for chores}. H ij = w i ( X i ) − ( d ij + e ij ) for cake , H ij = w i ( X i ) + ( d ij − e ij ) for chores .
In either case a row has range at most 2 Δ 2\Delta 2Δ . Column payments cancel in a two-row, two-column contrast, and column permutations preserve it. Thus on S ∩ G S\cap G S ∩ G , Λ ≤ 4 Δ \Lambda\le4\Delta Λ ≤ 4Δ . Choose a maximizing pair a , b a,b a , b . The retained-mass bound (25) and T ⊆ B T\subseteq B T ⊆ B give
g a b ( X ) = μ a ( R ) Δ ≥ ( 1 / 2 ) μ a ( B ) Λ / 4 ≥ ( Λ / 8 ) μ a ( T ) . g_{ab}(X)=\mu_a(R)\Delta\ge(1/2)\mu_a(B)\Lambda/4\ge(\Lambda/8)\mu_a(T). g ab ( X ) = μ a ( R ) Δ ≥ ( 1/2 ) μ a ( B ) Λ/4 ≥ ( Λ/8 ) μ a ( T ) .
Its strictly positive margin makes the pair distinct.
Proposition F.9 (Snapshot). Fix the parameters (40) and a recorded domain U U U with μ i ( U ) > 0 \mu_i(U)>0 μ i ( U ) > 0 for each of 3 ≤ k ≤ n 3\le k\le n 3 ≤ k ≤ n active agents. Conditional on the entire history before a fresh trial, Snapshot either rejects, returns a complete EF allocation of U U U among the active agents, or returns a partition ( X 1 , … , X k , T ) (X_1,\ldots,X_k,T) ( X 1 , … , X k , T ) of U U U with X X X EF among them, μ i ( T ) > 0 \mu_i(T)>0 μ i ( T ) > 0 for every active i i i , and g a b ( X ) ≥ θ μ a ( T ) g_{ab}(X)\ge\theta\mu_a(T) g ab ( X ) ≥ θ μ a ( T ) for distinct active a , b a,b a , b . All pieces are finite unions with recorded endpoints. Rejection commits no allocation, as in Proposition F.7 . The conditional acceptance probability exceeds 1 / 4 1/4 1/4 , and the deterministic cost cap is 6 m 6m 6 m Cuts and 12 n m 12nm 12 nm total queries, including all candidates and the possible inner Repair trial.
For Snapshot, normalize all active values on U U U to one, fix a cutter c c c before sampling, and build the ordinary coarse-plus-sample table. Let D j = ∑ E ∣ v j ( E ) − v c ( E ) ∣ D_j=\sum_E|v_j(E)-v_c(E)| D j = ∑ E ∣ v j ( E ) − v c ( E ) ∣ and D = max j D j D=\max_jD_j D = max j D j over M ≤ 2 m M\le2m M ≤ 2 m cells. Choose i ∗ i^* i ∗ attaining the maximum with a fixed tie rule. The comparison family is fixed before sampling even though its maximizing row is selected afterward.
Zero and small disagreement. If D = 0 D=0 D = 0 , a fresh circular cutter-equal partition is returned only after actual complete EF checks. Cell agreement is not itself used as a certificate of agreement between cells.
Suppose 0 < D < τ / 16 0<D<\tau/16 0 < D < τ /16 and put t = ( 1 − K D ) / k t=(1-KD)/k t = ( 1 − K D ) / k . Since K D < 1 / 2 KD<1/2 K D < 1/2 , 1 / ( 2 k ) < t ≤ 1 / k 1/(2k)<t\leq1/k 1/ ( 2 k ) < t ≤ 1/ k . The fixed signed estimate σ ^ = ν ^ i ∗ − ν ^ c \widehat{\sigma}=\widehat{\nu}_{i^*}-\widehat{\nu}_{c} σ = ν i ∗ − ν c has total mass zero and total variation D D D . Let S + S^+ S + be its positive cells and put u = ν c ( S + ) u=\nu_c(S^+) u = ν c ( S + ) . If u ≥ t u\geq t u ≥ t , take a fresh circular piece of cutter-value t t t in S + S^+ S + as W 1 W_1 W 1 . If u < t u<t u < t , take all of S + S^+ S + and fill the shortfall by a fresh circular piece of cutter-value t − u t-u t − u in its complement. With a second independent circular start, partition U ∖ W 1 U\setminus W_1 U ∖ W 1 into W 2 , … , W k W_2,\ldots,W_k W 2 , … , W k of cutter-value t t t and a buffer B B B of cutter-value K D KD K D . The amounts sum to 1 − t 1-t 1 − t , so this is a complete physical partition. The two groups need at most k + 2 k+2 k + 2 new endpoints. Record their values but retain the original interpolants.
Conditional on any fixed table and preceding candidate history, σ ^ ( S + ) = D / 2 \widehat{\sigma}(S^+)=D/2 σ ( S + ) = D /2 and σ ^ ( U ∖ S + ) = − D / 2 \widehat{\sigma}(U\setminus S^+)=-D/2 σ ( U ∖ S + ) = − D /2 . The circular inclusion law therefore gives
E [ σ ^ ( W 1 ) ] = { t D / ( 2 u ) , u ≥ t , D ( 1 − t ) / ( 2 ( 1 − u ) ) , u < t , ≥ t D / 2. \mathbb{E}[\widehat{\sigma}(W_1)]=
\begin{cases}
tD/(2u), & u\geq t,\\
D(1-t)/(2(1-u)), & u<t,
\end{cases}
\geq tD/2. E [ σ ( W 1 )] = { t D / ( 2 u ) , D ( 1 − t ) / ( 2 ( 1 − u )) , u ≥ t , u < t , ≥ t D /2.
The second case follows by adding the retained D / 2 D/2 D /2 to ( t − u ) / ( 1 − u ) (t-u)/(1-u) ( t − u ) / ( 1 − u ) times − D / 2 -D/2 − D /2 . The fresh second start gives
E [ σ ^ ( W 2 ) ∣ first-step history ] = − t 1 − t σ ^ ( W 1 ) . \mathbb{E}[\widehat{\sigma}(W_2)\mid\text{first-step history}]
=-\frac{t}{1-t}\widehat{\sigma}(W_1). E [ σ ( W 2 ) ∣ first-step history ] = − 1 − t t σ ( W 1 ) .
Thus χ = σ ^ ( W 1 ) − σ ^ ( W 2 ) \chi=\widehat{\sigma}(W_1)-\widehat{\sigma}(W_2) χ = σ ( W 1 ) − σ ( W 2 ) satisfies E [ χ ] ≥ D / ( 4 k ) \mathbb{E}[\chi]\geq D/(4k) E [ χ ] ≥ D / ( 4 k ) , while χ ≤ D \chi\leq D χ ≤ D because its two pieces are disjoint and the signed estimate has variation D D D . Consequently
D / ( 4 k ) ≤ E [ χ ] ≤ D / ( 8 k ) + D P [ χ ≥ D / ( 8 k ) ] . D/(4k)\leq\mathbb{E}[\chi]\leq D/(8k)+D\mathbb{P}[\chi\geq D/(8k)]. D / ( 4 k ) ≤ E [ χ ] ≤ D / ( 8 k ) + D P [ χ ≥ D / ( 8 k )] .
so the estimated witness event has conditional probability at least 1 / ( 8 k ) 1/(8k) 1/ ( 8 k ) .
Generate all 16 k 16k 16 k alternatives on the same table, recording every endpoint without changing the interpolants, and then select the first passing the actual checks below. Conditional on each table and the complete preceding candidate history, the estimated witness chance is at least p = 1 / ( 8 k ) p=1/(8k) p = 1/ ( 8 k ) . Iterated conditioning bounds failure of all candidates by ( 1 − p ) 16 k ≤ 1 / 4 (1-p)^{16k}\leq1/4 ( 1 − p ) 16 k ≤ 1/4 : Bernoulli’s inequality gives ( 1 − p ) 8 k ≤ 1 / ( 1 + 8 k p ) = 1 / 2 (1-p)^{8k}\leq1/(1+8kp)=1/2 ( 1 − p ) 8 k ≤ 1/ ( 1 + 8 k p ) = 1/2 , then square. No independence of candidate outcomes under a history-dependent root policy is assumed.
The first circular domain has cutter value at least t > 1 / ( 2 k ) t>1/(2k) t > 1/ ( 2 k ) when u ≥ t u\geq t u ≥ t , and at least 1 − t ≥ 2 / 3 1-t\geq2/3 1 − t ≥ 2/3 when u < t u<t u < t ; the second has value 1 − t 1-t 1 − t . Since ν c ≤ k μ \nu_c\leq k\mu ν c ≤ k μ , every endpoint has conditional marginal law at most 2 k 2 μ 2k^2\mu 2 k 2 μ before its group’s shared start, also for k = 3 k=3 k = 3 . The complete list has at most 16 k ( k + 2 ) ≤ 32 k 2 16k(k+2)\leq32k^2 16 k ( k + 2 ) ≤ 32 k 2 endpoints. Applying Lemma F.2 with the resulting pathwise bound Λ s u m ≤ 64 k 4 \Lambda_{\mathrm{sum}}\leq64k^4 Λ sum ≤ 64 k 4 and accuracy ε 0 \varepsilon_0 ε 0 gives exception probability
128 k 5 ( 1 + ε 0 ) ε 0 ( m + 1 ) ≤ 32768 k 5 s 7 ℓ ≤ 32768 s 2 < 1 / 64. (42) \frac{128k^5(1+\varepsilon_0)}{\varepsilon_0(m+1)}
\leq\frac{32768k^5}{s^7\ell}
\leq\frac{32768}{s^2}<1/64. \tag*{(42)} ε 0 ( m + 1 ) 128 k 5 ( 1 + ε 0 ) ≤ s 7 ℓ 32768 k 5 ≤ s 2 32768 < 1/64. (42)
This event counts rejecting alternatives and also covers the smaller zero branch. If D = 0 D=0 D = 0 , its conclusion gives exact zero cutter differences on every resulting piece, so the complete partition is actually equal for every observer. In the positive case an estimated-good alternative passes the actual checks
ν c ( W j ) = t , ν c ( B ) = K D , ν i ∗ ( W 1 ) − ν i ∗ ( W 2 ) ≥ D / ( 32 k ) , \nu_c(W_j)=t,\qquad\nu_c(B)=KD,\qquad\nu_{i^*}(W_1)-\nu_{i^*}(W_2)\geq D/(32k), ν c ( W j ) = t , ν c ( B ) = K D , ν i ∗ ( W 1 ) − ν i ∗ ( W 2 ) ≥ D / ( 32 k ) ,
( K − 2 ) D ≤ ν i ( B ) ≤ ( K + 2 ) D , max j ν i ( W j ) − min j ν i ( W j ) ≤ 4 D ≤ τ ν i ( B ) . (43) (K-2)D\leq\nu_i(B)\leq(K+2)D,\qquad\max_j\nu_i(W_j)-\min_j\nu_i(W_j)\leq4D\leq\tau\nu_i(B). \tag*{(43)} ( K − 2 ) D ≤ ν i ( B ) ≤ ( K + 2 ) D , j max ν i ( W j ) − j min ν i ( W j ) ≤ 4 D ≤ τ ν i ( B ) . (43)
Indeed, for row i i i the estimated cutter difference has zero total mass and variation D i ≤ D D_i \le D D i ≤ D , so it assigns any set absolute value at most D / 2 D/2 D /2 . Its actual difference is at most ( 1 / 2 + ε 0 ) D (1/2+\varepsilon_0)D ( 1/2 + ε 0 ) D . The buffer thus lies within 2 D 2D 2 D of K D KD K D , and two cutter-equal endowments differ by at most 4 D 4D 4 D . The witness loses at most 2 ε 0 D 2\varepsilon_0D 2 ε 0 D and retains at least D / ( 16 k ) > D / ( 32 k ) D/(16k)>D/(32k) D / ( 16 k ) > D / ( 32 k ) because 2 ε 0 ≤ 1 / ( 16 k ) 2\varepsilon_0 \le1/(16k) 2 ε 0 ≤ 1/ ( 16 k ) . Finally τ ( K − 2 ) D ≥ 4 D \tau(K-2)D \ge4D τ ( K − 2 ) D ≥ 4 D since K − 2 ≥ 4 / τ K-2 \ge4/\tau K − 2 ≥ 4/ τ .
The checked buffer is positive for every row and the range condition implies (24) for both preference directions. After every fresh repair preparation, the cutter still values W 1 , W 2 W_1,W_2 W 1 , W 2 equally, and therefore the contrast is
( w i ∗ − w c ) ( W 1 ) − ( w i ∗ − w c ) ( W 2 ) = ν i ∗ ( W 1 ) − ν i ∗ ( W 2 ) ν i ∗ ( R ) ≥ 1 48 k ( K + 2 ) . (w_{i^*}-w_c)(W_1)-(w_{i^*}-w_c)(W_2)=\frac{\nu_{i^*}(W_1)-\nu_{i^*}(W_2)}{\nu_{i^*}(R)}\ge\frac{1}{48k(K+2)}. ( w i ∗ − w c ) ( W 1 ) − ( w i ∗ − w c ) ( W 2 ) = ν i ∗ ( R ) ν i ∗ ( W 1 ) − ν i ∗ ( W 2 ) ≥ 48 k ( K + 2 ) 1 .
We used ν i ∗ ( R ) ≤ ν i ∗ ( B ) ≤ ( K + 2 ) D \nu_{i^*}(R)\le\nu_{i^*}(B)\le(K+2)D ν i ∗ ( R ) ≤ ν i ∗ ( B ) ≤ ( K + 2 ) D . Lemma F.8 now applies to that fresh repair after any checked candidate history.
Large disagreement. If D ≥ τ / 16 D\ge\tau/16 D ≥ τ /16 , the positive and negative recorded cutter differences of row i ∗ i^* i ∗ each sum to D / 2 D/2 D /2 . Choose cells F , G F,G F , G with
ν i ∗ ( F ) − ν c ( F ) ≥ D / ( 2 M ) , ν c ( G ) − ν i ∗ ( G ) ≥ D / ( 2 M ) . \nu_{i^*}(F)-\nu_c(F)\ge D/(2M),\qquad\nu_c(G)-\nu_{i^*}(G)\ge D/(2M). ν i ∗ ( F ) − ν c ( F ) ≥ D / ( 2 M ) , ν c ( G ) − ν i ∗ ( G ) ≥ D / ( 2 M ) .
They are distinct. Set W 1 = F W_1=F W 1 = F , W 2 = G W_2=G W 2 = G , and all other endowments empty, with buffer B = U ∖ ( F ∪ G ) B=U\setminus(F\cup G) B = U ∖ ( F ∪ G ) . Its every value is at least 1 − 2 σ ≥ 1 / 2 1-2\sigma\ge1/2 1 − 2 σ ≥ 1/2 , and the endowment range is at most σ ≤ τ / 2 \sigma\le\tau/2 σ ≤ τ /2 . Thus the input is valid deterministically, without new cuts.
After fresh repair preparation write r i = ν i ( R ) r_i=\nu_i(R) r i = ν i ( R ) and γ = ν i ∗ / r i ∗ − ν c / r c \gamma=\nu_{i^*}/r_{i^*}-\nu_c/r_c γ = ν i ∗ / r i ∗ − ν c / r c . If r i ∗ ≤ r c r_{i^*}\le r_c r i ∗ ≤ r c ,
γ ( F ) = ν i ∗ ( F ) − ν c ( F ) r i ∗ + ν c ( F ) ( 1 r i ∗ − 1 r c ) ≥ D 2 M r i ∗ ≥ D 3 M . \gamma(F)=\frac{\nu_{i^*}(F)-\nu_c(F)}{r_{i^*}}+\nu_c(F)\left(\frac{1}{r_{i^*}}-\frac{1}{r_c}\right)\ge\frac{D}{2Mr_{i^*}}\ge\frac{D}{3M}. γ ( F ) = r i ∗ ν i ∗ ( F ) − ν c ( F ) + ν c ( F ) ( r i ∗ 1 − r c 1 ) ≥ 2 M r i ∗ D ≥ 3 M D .
If r c ≤ r i ∗ r_c\le r_{i^*} r c ≤ r i ∗ , the same argument gives − γ ( G ) ≥ D / ( 3 M ) -\gamma(G)\ge D/(3M) − γ ( G ) ≥ D / ( 3 M ) . Both use r i ≤ ν i ( B ) ≤ 1 r_i\le\nu_i(B)\le1 r i ≤ ν i ( B ) ≤ 1 . Compare the chosen cell, with the appropriate orientation, to an empty third endowment. Such an endowment exists for every k ≥ 3 k\ge3 k ≥ 3 , so Lemma F.8 applies here as well.
Completion of Proposition F.9 . The small and large branches yield respective margins at least
μ a ( T ) 384 k ( K + 2 ) and D 24 M μ a ( T ) . \frac{\mu_a(T)}{384k(K+2)}\qquad\text{and}\qquad\frac{D}{24M}\mu_a(T). 384 k ( K + 2 ) μ a ( T ) and 24 M D μ a ( T ) .
Both are at least θ μ a ( T ) \theta\mu_a(T) θ μ a ( T ) , since
τ k ( K + 2 ) ≤ 10 k ≤ 2 m , D ≥ τ / 16 , M ≤ 2 m . \tau k(K+2)\le10k\le2m,\qquad D\ge\tau/16,\qquad M\le2m. τ k ( K + 2 ) ≤ 10 k ≤ 2 m , D ≥ τ /16 , M ≤ 2 m .
The first inequality handles the small branch, and the last two handle the large branch. The remaining geometric conditions follow from (40) :
K ≥ 6 , σ ≤ τ / 2 , 1 − 2 σ ≥ 1 / 2. K\ge6,\qquad\sigma\le\tau/2,\qquad1-2\sigma\ge1/2. K ≥ 6 , σ ≤ τ /2 , 1 − 2 σ ≥ 1/2.
A complete return or a checked positive input is obtained with probability at least 1 − 1 / 4 − 1 / 64 = 47 / 64 1-1/4-1/64=47/64 1 − 1/4 − 1/64 = 47/64 . The zero branch uses its actual check and interpolation; the small branch uses amplification and the same interpolation event; the large branch supplies a valid input deterministically. After selecting a checked positive input, use exactly one fresh repair. Its conditional contrast-success probability is at least 31 / 64 31/64 31/64 after the entire observed candidate history. Therefore Snapshot returns with probability at least ( 47 / 64 ) ( 31 / 64 ) > 1 / 4 (47/64)(31/64) > 1/4 ( 47/64 ) ( 31/64 ) > 1/4 . Return only after checking actual EF and completeness or the stated margin. A rejection commits none of the alternative partitions. Each noncomplete return leaves at least three quarters of its positive checked buffer, so its residue is positive for every active observer.
The table costs at most 2 m 2m 2 m cuts, all alternatives at most 16 k ( k + 2 ) ≤ m 16k(k+2) \le m 16 k ( k + 2 ) ≤ m , and its one inner repair at most 3 m 3m 3 m . Recording every endpoint gives the complete cap of 6 m 6m 6 m Cuts and 12 n m 12nm 12 nm queries, including all rejecting work.
Lemma F.10 (One-sided individual-query refinement). Let k k k measures be positive on a recorded domain U U U , normalized to ν i ( U ) = 1 \nu_i(U)=1 ν i ( U ) = 1 . For 0 ≤ f ≤ 1 / k 0 \le f \le1/k 0 ≤ f ≤ 1/ k and 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , one can construct disjoint pieces W 1 , … , W k W_1,\ldots,W_k W 1 , … , W k such that f − δ ≤ ν i ( W j ) ≤ f f-\delta\le\nu_i(W_j) \le f f − δ ≤ ν i ( W j ) ≤ f for all i , j i,j i , j , retaining their complement as a dummy. The number of Cuts is at most k 3 J k^3J k 3 J , and the total number of queries at most ( n + 1 ) k 3 J (n+1)k^3J ( n + 1 ) k 3 J , where
J = max { 0 , ⌈ log 2 ( k 2 / δ ) ⌉ } . J=\max\{0,\lceil\log_2(k^2/\delta)\rceil\}. J = max { 0 , ⌈ log 2 ( k 2 / δ )⌉} .
Proof. On each cell of the recorded ordered domain, initialize fraction f f f for each real color and fraction 1 − k f 1-kf 1 − k f for the dummy. Preserve the cell-sum equations and the k 2 k^2 k 2 real-color moments ∑ E ν i ( E ) x E j = f \sum_E \nu_i(E)x_{Ej}=f ∑ E ν i ( E ) x E j = f . Floating with fixed boundary coordinates works exactly as in the reserve plan: a nonzero homogeneous direction allows a finite move to the next boundary, and each move fixes a new coordinate. At a terminal floating state, a a a fractional cells give at least 2 a 2a 2 a fractional columns and at most a + k 2 a+k^2 a + k 2 independent equations. Hence at most k 2 k^2 k 2 cells remain fractional. Integral assignments stay fixed permanently.
Refine each fractional cell at every observer’s own median whenever that observer has positive mass there; skip zero-mass rows. Each median is a strict interior value target on a recorded ordered union and uses one ordinary Cut. Its union representation is handled by cached component sums. Every child lies on one side of every row’s median and has at most half that row’s parent value, regardless of plateaus and the chosen legal roots. A zero-mass row has the same property without a cut. Record each new endpoint for all original observers and give every child its parent’s fractional vector, which preserves all moments. Float again.
Repeat for J J J refinement rounds. Any cell still fractional at the end has passed through all J J J rounds, because integral cells never reenter. Each original cell has every normalized value at most one, so every surviving fractional cell has value at most 2 − J 2^{-J} 2 − J . There are at most k 2 k^2 k 2 of them; their union has each row’s value at most k 2 2 − J ≤ δ k^2 2^{-J} \le\delta k 2 2 − J ≤ δ . Give all remaining fractional cells to the dummy. Each real color loses a nonnegative amount at most δ \delta δ from its exact fractional moment f f f . This proves both one-sided inequalities and retains every physical fragment.
Each round refines at most k 2 k^2 k 2 cells by at most k k k individual Cuts. Recordings cost at most n n n evaluations per cut, proving the stated bounds. All floating operations are finite exact linear algebra. The depth can be computed by integer doubling and comparisons, without a logarithm oracle.
Proposition F.11 (Prescribed Shrink interface). Fix the parameters (40) , 3 ≤ k ≤ n 3 \le k \le n 3 ≤ k ≤ n active agents positive on a recorded domain U U U , and a factor
1 ≤ G ≤ ( 2 / θ ) ( 8 / τ ) k − 1 1 \le G \le(2/\theta)(8/\tau)^{k-1} 1 ≤ G ≤ ( 2/ θ ) ( 8/ τ ) k − 1 chosen before the fresh trial. One Shrink trial either rejects or returns a partition ( H 1 , … , H k , U ′ ) (H_1,\ldots,H_k,U') ( H 1 , … , H k , U ′ ) of U U U into recorded finite unions, where H H H is EF among the active agents and
3 8 G μ i ( U ) ≤ μ i ( U ′ ) ≤ 1 G μ i ( U ) ( i active ) . \frac{3}{8G}\mu_i(U) \le\mu_i(U') \le\frac{1}{G}\mu_i(U)\qquad(i\ \text{active}). 8 G 3 μ i ( U ) ≤ μ i ( U ′ ) ≤ G 1 μ i ( U ) ( i active ) .
Rejection commits no allocation. Conditional on the entire preceding history, acceptance has probability greater than 63 / 64 63/64 63/64 . Every trial, including its carving and inner Repair, costs at most 4 m 4m 4 m Cuts and 8 n m 8nm 8 nm queries.
Proof. Normalize ν i = μ i / μ i ( U ) \nu_i=\mu_i/\mu_i(U) ν i = μ i / μ i ( U ) . For the prescribed G G G , apply Lemma F.10 with f = ( 1 − 1 / ( 2 G ) ) / k f=(1-1/(2G))/k f = ( 1 − 1/ ( 2 G )) / k and δ = τ / ( 4 G ) \delta=\tau/(4G) δ = τ / ( 4 G ) . The physical buffer B = U ∖ ⋃ j W j B=U\setminus\bigcup_j W_j B = U ∖ ⋃ j W j then satisfies
1 2 G ≤ ν i ( B ) ≤ 1 2 G + k τ 4 G ≤ 1 G , \frac{1}{2G}\le\nu_i(B)\le\frac{1}{2G}+\frac{k\tau}{4G}\le\frac{1}{G}, 2 G 1 ≤ ν i ( B ) ≤ 2 G 1 + 4 G k τ ≤ G 1 ,
using k τ ≤ 2 k\tau\le2 k τ ≤ 2 . Each endowment range is at most δ ≤ ( τ / 2 ) ν i ( B ) \delta\le(\tau/2)\nu_i(B) δ ≤ ( τ /2 ) ν i ( B ) , so repair applies with positive buffer normalizations in both preference directions. A shrinking trial consists of this deterministic carving and one fresh trial of Proposition F.7 ; its failure probability is less than 1 / 64 1/64 1/64 . On return all endowments are allocated and at most one quarter of B B B was consumed, giving
3 8 G μ i ( U ) ≤ μ i ( U ′ ) ≤ 1 G μ i ( U ) . (44) \frac{3}{8G}\mu_i(U)\le\mu_i(U')\le\frac{1}{G}\mu_i(U). \tag*{(44)} 8 G 3 μ i ( U ) ≤ μ i ( U ′ ) ≤ G 1 μ i ( U ) . (44)
Rejected trials also pay for carving. It suffices to use depth
J 0 = max { 0 , ⌈ log 2 ( 4 k 2 G / τ ) ⌉ } . J_0=\max\{0,\lceil\log_2(4k^2G/\tau)\rceil\}. J 0 = max { 0 , ⌈ log 2 ( 4 k 2 G / τ )⌉} .
Only factors up to
G max = ( 2 / θ ) ( 8 / τ ) k − 1 G_{\max}=(2/\theta)(8/\tau)^{k-1} G m a x = ( 2/ θ ) ( 8/ τ ) k − 1
are used. Since 2 / θ ≤ s 32 2/\theta\le s^{32} 2/ θ ≤ s 32 , 8 / τ ≤ s 12 8/\tau\le s^{12} 8/ τ ≤ s 12 , and 4 k 2 / τ ≤ s 14 4k^2/\tau\le s^{14} 4 k 2 / τ ≤ s 14 , for the active populations k ≥ 3 k\ge3 k ≥ 3 used by the caller,
J 0 ≤ ( 12 k + 34 ) ℓ ≤ 32 k ℓ , k 3 ( 32 k ℓ ) ≤ m . (45) J_0\le(12k+34)\ell\le32k\ell,\qquad k^3(32k\ell)\le m. \tag*{(45)} J 0 ≤ ( 12 k + 34 ) ℓ ≤ 32 k ℓ , k 3 ( 32 k ℓ ) ≤ m . (45)
Use the fixed integer depth 32 k ℓ 32k\ell 32 k ℓ , which is at least J 0 J_0 J 0 . Thus every such shrinking trial costs at most 4 m 4m 4 m Cuts and 8 n m 8nm 8 nm queries. This is a logarithmic-precision carve, not an uncounted sequence of repairs.
Global completion, zero residues, and the total bound
A committed state consists of recorded finite unions ( W 1 , … , W n , U ) (W_1,\ldots,W_n,U) ( W 1 , … , W n , U ) partitioning [ 0 , 1 ] [0,1] [ 0 , 1 ] , with W W W globally EF, a nonempty active set A A A , and frozen set F = [ n ] ∖ A F=[n]\setminus A F = [ n ] ∖ A . Every old active bundle remains a movable whole label; frozen bundles stay fixed. The guards are
g f i ( W ) ≥ μ f ( U ) for cake , g i f ( W ) ≥ μ i ( U ) for chores ( f ∈ F , i ∈ A ) . (46) g_{fi}(W)\ge\mu_f(U)\quad\text{for cake},\qquad g_{if}(W)\ge\mu_i(U)\quad\text{for chores}\qquad(f\in F,i\in A). \tag*{(46)} g f i ( W ) ≥ μ f ( U ) for cake , g i f ( W ) ≥ μ i ( U ) for chores ( f ∈ F , i ∈ A ) . (46)
Initially U = [ 0 , 1 ] U=[0,1] U = [ 0 , 1 ] , all bundles are empty, and everyone is active. Over all original observers define
D i ( W , U ) = { j ≠ i : g i j ( W ) ≥ μ i ( U ) } , Φ ( W , U ) = ∑ i ∣ D i ( W , U ) ∣ ≤ n ( n − 1 ) . D_i(W,U)=\{j\ne i:g_{ij}(W)\ge\mu_i(U)\},\qquad\Phi(W,U)=\sum_i |D_i(W,U)|\le n(n-1). D i ( W , U ) = { j = i : g ij ( W ) ≥ μ i ( U )} , Φ ( W , U ) = i ∑ ∣ D i ( W , U ) ∣ ≤ n ( n − 1 ) .
Proposition F.12 (Composition and completion). For n ≥ 3 n\ge3 n ≥ 3 with parameters (40) , start from the initial state above. For either preference direction, the Repair, Snapshot, and Shrink interfaces of Propositions F.7 , F.9 , and F.11 yield a protocol that preserves the committed-state invariant and returns a complete EF allocation almost surely. It uses at most n ( n − 1 ) n(n-1) n ( n − 1 ) nontrivial iterations. Conditional on the history starting any such iteration, its expected number of full trials is less than eight, and
E [ Q ] ≤ 100 n 3 m , E [ C ] ≤ 49 n 2 m . \mathbb{E}[Q]\le100n^3m,\qquad\mathbb{E}[C]\le49n^2m. E [ Q ] ≤ 100 n 3 m , E [ C ] ≤ 49 n 2 m . Here a full trial is one Snapshot attempt, one Shrink attempt, or one standalone Repair attempt; the first two include their inner Repair, and all rejected work is counted.
Proof. First, an EF partial allocation L L L of U U U among the active agents can be added under its original owners. Active margins then add. For cake, active own values do not decrease, while a frozen observer’s guarded margin toward recipient i i i loses at most μ f ( L i ) ≤ μ f ( U ) − μ f ( U ∖ ⋃ j L j ) \mu_f(L_i) \le\mu_f(U) - \mu_f\left(U \setminus\bigcup_j L_j\right) μ f ( L i ) ≤ μ f ( U ) − μ f ( U ∖ ⋃ j L j ) . For chores, frozen observers see only nonnegative additions to active bundles, while an active observer’s guarded margin toward a frozen agent loses at most its own added cost, with the same residue bound. Thus global EF and the guards persist with the literal new residue. This argument also applies to a complete additive return.
The active nondomination graph has edge i → j i \to j i → j for distinct active agents exactly when j ∉ D i j \notin D_i j ∈ / D i . If it has a proper sink strongly connected component S S S , freeze S S S for cake and its active complement for chores. The absent outgoing nondomination edges are precisely the newly required guards. No material moves, the active population decreases, and Φ \Phi Φ is unchanged. This extends the domination framework of [16 ] using total old bundles.
Handle active zero residues at committed EF states before normalization. If μ i ( U ) = 0 \mu_i(U) = 0 μ i ( U ) = 0 for a chore agent, giving all of U U U to that agent is itself an EF allocation of U U U , so the additive argument completes. A zero-value cake agent can freeze with its old bundle when at least two agents remain: its new guard is g i j ( W ) ≥ 0 = μ i ( U ) g_{ij}(W) \ge0 = \mu_i(U) g ij ( W ) ≥ 0 = μ i ( U ) . Apply the one-agent base before freezing the last recipient. If all remaining active measures vanish, give the residue to one of them. The additive argument protects frozen observers even when they value that residue. One active agent takes everything left. Two divide the ordered residue into cutter-equal halves; the other chooses a larger half for cake or a smaller half for chores. Add these pieces under their original owners. This is complete EF and needs at most one new Cut and its records.
Apply these reductions until completion or until a nontrivial iteration starts at a saved EF anchor ( W , U ) (W,U) ( W , U ) with k ≥ 3 k \ge3 k ≥ 3 , positive active residue values, and a strongly connected active graph. Obtain an accepted Snapshot X X X on U U U by fresh retries of Proposition F.9 , retaining the same domain after each rejection. A complete return is added to W W W and finishes. Otherwise let T T T be its positive residue and d i j = g i j ( X ) d_{ij} = g_{ij}(X) d ij = g ij ( X ) , with certificate d a j ≥ ψ a ( T ) d_{aj} \ge\psi_a(T) d aj ≥ ψ a ( T ) . The saved anchor is not changed by this partial return or by the following Shrink returns; they are retained as temporary disjoint partitions until the final Repair has passed.
At most two successful prescribed shrinking requests produce a snapshot permutation α \alpha α , final residue values ρ i > 0 \rho_i > 0 ρ i > 0 , and an edge ( b , h ) (b,h) ( b , h ) of the saved graph such that
d i , α ( i ) ≤ τ ρ i , d b , α ( h ) ≥ 2 ρ b . (47) d_{i,\alpha(i)} \le\tau\rho_i,\qquad d_{b,\alpha(h)} \ge2\rho_b. \tag*{(47)} d i , α ( i ) ≤ τ ρ i , d b , α ( h ) ≥ 2 ρ b . (47)
To see this, in certificate column j j j consider x i = d i j / μ i ( T ) ≥ 0 x_i = d_{ij}/\mu_i(T) \ge0 x i = d ij / μ i ( T ) ≥ 0 and the k k k factors G e = ( 2 / θ ) ( 8 / τ ) e G_e = (2/\theta)(8/\tau)^e G e = ( 2/ θ ) ( 8/ τ ) e , 0 ≤ e < k 0 \le e < k 0 ≤ e < k . A row forbids only a factor with 3 τ / 8 < G e x i < 2 3\tau/8 < G_e x_i < 2 3 τ /8 < G e x i < 2 . This interval has multiplicative width smaller than 8 / τ 8/\tau 8/ τ , so each row forbids at most one factor, and the diagonal row forbids none. Choose a safe factor and use Proposition F.11 on T T T , retrying the same factor and domain after a rejection. Write ρ i \rho_i ρ i for the accepted residue values at this stage. The two alternatives obey
G x i ≤ 3 τ / 8 ⟹ d i j ≤ 3 τ 8 G μ i ( T ) ≤ τ ρ i , Gx_i \le3\tau/8 \Longrightarrow d_{ij} \le\frac{3\tau}{8G}\mu_i(T) \le\tau\rho_i, G x i ≤ 3 τ /8 ⟹ d ij ≤ 8 G 3 τ μ i ( T ) ≤ τ ρ i ,
G x i ≥ 2 ⟹ d i j ≥ 2 G μ i ( T ) ≥ 2 ρ i . Gx_i \ge2 \Longrightarrow d_{ij} \ge\frac{2}{G}\mu_i(T) \ge2\rho_i. G x i ≥ 2 ⟹ d ij ≥ G 2 μ i ( T ) ≥ 2 ρ i .
The certificate row is large because G x a ≥ 2 Gx_a \ge2 G x a ≥ 2 , and the diagonal row is small. On a saved-graph path from a a a to j j j , choose an edge i → h i \to h i → h crossing from a large to a small row. If h = j h = j h = j , identity suffices. Otherwise take a simple path j = u 0 → ⋯ → u t = h j = u_0 \to\cdots\to u_t = h j = u 0 → ⋯ → u t = h . If each path edge has snapshot loss d u r , u r + 1 ≤ τ ρ u r d_{u_r,u_{r+1}} \le\tau\rho_{u_r} d u r , u r + 1 ≤ τ ρ u r , set α ( u r ) = u r + 1 \alpha(u_r) = u_{r+1} α ( u r ) = u r + 1 for r < t r < t r < t , α ( h ) = j \alpha(h) = j α ( h ) = j , and fix the other labels. The closing own loss is small because h h h is a small row in column j j j ; hence all own losses are small, and ( b , h ) = ( i , h ) (b,h) = (i,h) ( b , h ) = ( i , h ) is the desired large comparison. If some path edge p → q p \to q p → q has loss greater than τ ρ p \tau\rho_p τ ρ p , instead apply Shrink once more to the current residue with factor 2 / τ 2/\tau 2/ τ , which is at most G max G_{\max} G m a x , and use identity. Its new residue values ρ i ′ \rho_i' ρ i ′ satisfy 0 < ρ i ′ ≤ τ ρ i / 2 0 < \rho_i' \le\tau\rho_i/2 0 < ρ i ′ ≤ τ ρ i /2 , so d p q > τ ρ p ≥ 2 ρ p ′ d_{pq} > \tau\rho_p \ge2\rho_p' d pq > τ ρ p ≥ 2 ρ p ′ ; take ( b , h ) = ( p , q ) (b,h)=(p,q) ( b , h ) = ( p , q ) and rename ρ ′ \rho' ρ ′ as ρ \rho ρ . No shrink follows a nonidentity transfer, so previously small losses are not inadvertently enlarged.
Let H i H_i H i be the sum of the EF shrinking allocations under their old owners and let T 0 T_0 T 0 be their final residue. Form
D i = W i ∪ H i ∪ X α ( i ) , ρ i = μ i ( T 0 ) . D_i = W_i \cup H_i \cup X_{\alpha(i)}, \qquad\rho_i = \mu_i(T_0). D i = W i ∪ H i ∪ X α ( i ) , ρ i = μ i ( T 0 ) .
The pieces H H H are EF among active agents, because their disjoint Shrink margins add. For either preference direction the exact identity is
g i r ( D ) = g i r ( W ) + g i r ( H ) + d i , α ( r ) − d i , α ( i ) . g_{ir}(D) = g_{ir}(W) + g_{ir}(H) + d_{i,\alpha(r)} - d_{i,\alpha(i)}. g i r ( D ) = g i r ( W ) + g i r ( H ) + d i , α ( r ) − d i , α ( i ) .
Consequently g i r ( D ) ≥ − τ ρ i g_{ir}(D) \ge-\tau\rho_i g i r ( D ) ≥ − τ ρ i and g b h ( D ) ≥ ( 2 − τ ) ρ b g_{bh}(D) \ge(2-\tau)\rho_b g bh ( D ) ≥ ( 2 − τ ) ρ b . These disjoint whole endowments and the positive buffer T 0 T_0 T 0 meet every precondition of Proposition F.7 ; no global EF assertion about D D D is needed. Retry that same Repair input until it returns Z i = D β ( i ) ∪ Y i Z_i=D_{\beta(i)}\cup Y_i Z i = D β ( i ) ∪ Y i . Extend f = β − 1 f=\beta^{-1} f = β − 1 by identity on frozen labels and put Z i = W i Z_i=W_i Z i = W i there. Here Y i Y_i Y i includes all final Repair additions. The exact physical identity is
Z f ( j ) = W j ∪ B j , B j = H j ∪ X α ( j ) ∪ Y f ( j ) ( j ∈ A ) , B j = ∅ ( j ∈ F ) . (48) Z_{f(j)} = W_j \cup B_j,\qquad B_j = H_j \cup X_{\alpha(j)} \cup Y_{f(j)} \ (j \in A),\qquad B_j = \varnothing\ (j \in F). \tag*{(48)} Z f ( j ) = W j ∪ B j , B j = H j ∪ X α ( j ) ∪ Y f ( j ) ( j ∈ A ) , B j = ∅ ( j ∈ F ) . (48)
These additions are disjoint and partition U ∖ U ′ U\setminus U' U ∖ U ′ . Thus, for every original observer, including frozen ones,
∑ j μ i ( B j ) + μ i ( U ′ ) = μ i ( U ) . (49) \sum_j \mu_i(B_j) + \mu_i(U') = \mu_i(U). \tag*{(49)} j ∑ μ i ( B j ) + μ i ( U ′ ) = μ i ( U ) . (49)
Active-active EF follows from Repair. Before claiming global EF, compare each active i i i only with the active recipient f ( i ) f(i) f ( i ) . For a frozen i i i , f ( i ) = i f(i)=i f ( i ) = i and B i = ∅ B_i=\varnothing B i = ∅ . We obtain for every original observer
μ i ( Z i ) ≥ μ i ( W i ) + μ i ( B i ) for cake , μ i ( Z i ) ≤ μ i ( W i ) + μ i ( B i ) for chores . (50) \mu_i(Z_i) \ge\mu_i(W_i) + \mu_i(B_i) \quad\text{for cake},\qquad
\mu_i(Z_i) \le\mu_i(W_i) + \mu_i(B_i) \quad\text{for chores}. \tag*{(50)} μ i ( Z i ) ≥ μ i ( W i ) + μ i ( B i ) for cake , μ i ( Z i ) ≤ μ i ( W i ) + μ i ( B i ) for chores . (50)
For chores this allows own cost to increase by at most the old label’s additions. Frozen-frozen comparisons are unchanged. For cake, the own-value bound preserves active comparisons to frozen bundles. A frozen observer comparing to f ( j ) f(j) f ( j ) has margin at least μ f ( U ) − μ f ( B j ) ≥ μ f ( U ′ ) \mu_f(U)-\mu_f(B_j)\ge\mu_f(U') μ f ( U ) − μ f ( B j ) ≥ μ f ( U ′ ) , preserving its guard. For chores, frozen observers see only nonnegative additions to active old bundles, so their comparisons persist. By the own-cost bound, an active observer’s margin toward any frozen agent is at least μ i ( U ) − μ i ( B i ) ≥ μ i ( U ′ ) \mu_i(U)-\mu_i(B_i)\ge\mu_i(U') μ i ( U ) − μ i ( B i ) ≥ μ i ( U ′ ) . Both residue inequalities use (49) and nonnegativity. This proves global EF and both guards before committing ( Z , U ′ ) (Z,U') ( Z , U ′ ) and counting targets.
For any original observer and old proper target j j j , these same own inequalities and (48) give
g i , f ( j ) ( Z ) ≥ { μ i ( U ) − μ i ( B j ) ≥ μ i ( U ′ ) , cake , μ i ( U ) − μ i ( B i ) ≥ μ i ( U ′ ) , chores . g_{i,f(j)}(Z) \ge
\begin{cases}
\mu_i(U)-\mu_i(B_j) \ge\mu_i(U'), & \text{cake},\\
\mu_i(U)-\mu_i(B_i) \ge\mu_i(U'), & \text{chores}.
\end{cases} g i , f ( j ) ( Z ) ≥ { μ i ( U ) − μ i ( B j ) ≥ μ i ( U ′ ) , μ i ( U ) − μ i ( B i ) ≥ μ i ( U ′ ) , cake , chores .
If the new row residue is positive, the image cannot be its observer, so injectivity preserves all proper-target counts. If it is zero, global EF saturates that count at m − 1 m-1 m − 1 instead; an old target may then map to its observer and must not be counted as a proper image. For the witness, compare Z b Z_b Z b with the active recipient f ( b ) f(b) f ( b ) of D b D_b D b . For cake this gives μ b ( Z b ) ≥ μ b ( D b ) \mu_b(Z_b)\ge\mu_b(D_b) μ b ( Z b ) ≥ μ b ( D b ) ; for chores it gives μ b ( Z b ) ≤ μ b ( D b ) + μ b ( Y f ( b ) ) \mu_b(Z_b)\le\mu_b(D_b)+\mu_b(Y_{f(b)}) μ b ( Z b ) ≤ μ b ( D b ) + μ b ( Y f ( b ) ) . Since Z f ( b ) = D b ∪ Y f ( b ) Z_{f(b)}=D_b\cup Y_{f(b)} Z f ( b ) = D b ∪ Y f ( b ) , nonnegativity and the final Repair bound μ b ( ⋃ i Y i ) ≤ ρ b / 4 \mu_b(\bigcup_i Y_i)\le\rho_b/4 μ b ( ⋃ i Y i ) ≤ ρ b /4 give in both cases
g b , f ( b ) ( Z ) ≥ ( 7 / 4 − τ ) ρ b ≥ ρ b ≥ μ b ( U ′ ) . g_{b,f(b)}(Z) \ge(7/4-\tau)\rho_b \ge\rho_b \ge\mu_b(U'). g b , f ( b ) ( Z ) ≥ ( 7/4 − τ ) ρ b ≥ ρ b ≥ μ b ( U ′ ) .
Repair leaves μ b ( U ′ ) ≥ 3 ρ b / 4 > 0 \mu_b(U') \ge3\rho_b/4 > 0 μ b ( U ′ ) ≥ 3 ρ b /4 > 0 . The target is proper and new, because h h h was outside the anchor’s target set and f f f is injective. Thus the global potential increases by at least one. This comparison is with the saved anchor, not with a potentially larger temporary potential after the separate Snapshot/Shrink pieces were added under their old owners.
All normalizations are positive when used. Noncomplete Snapshot returns a positive checked buffer after quarter spending, Shrink has (44) , and final repair leaves three quarters of its input buffer. A complete return is committed additively and saturates targets. The protocol performs zero-residue reductions only at committed EF anchors. The lower bounds above exclude an active zero residue inside the pending iteration; in particular, no zero exit is applied to the uncorrected transferred endowments.
Each nontrivial iteration begins with a proper nondomination edge and thus an unsaturated potential. Each nonterminal iteration increases the same integer potential, while a terminal iteration completes from an unsaturated state. Hence there are at most n ( n − 1 ) n(n-1) n ( n − 1 ) iterations over all population changes. Each request fixes its input before retrying and uses the uniform conditional acceptance bound of its interface after the entire preceding history: greater than 1 / 4 1/4 1/4 for Snapshot and 63 / 64 63/64 63/64 for Shrink or Repair. For a bound p p p , iterated conditioning gives P [ N > r ∣ H ] ≤ ( 1 − p ) r \mathbb{P}[N > r \mid\mathcal{H}] \le(1-p)^r P [ N > r ∣ H ] ≤ ( 1 − p ) r for the number N N N of attempts, and hence E [ N ∣ H ] ≤ 1 / p \mathbb{E}[N \mid\mathcal{H}] \le1/p E [ N ∣ H ] ≤ 1/ p . Thus every request returns almost surely, without independence between requests or attempts. One iteration requests one Snapshot, at most two shrinks, and one final repair, so its expected trial count conditional on its starting history is at most
4 + 3 ( 64 / 63 ) = 148 / 21 < 8. 4 + 3(64/63) = 148/21 < 8. 4 + 3 ( 64/63 ) = 148/21 < 8.
Every full trial has deterministic cap 6 m 6m 6 m Cuts and 12 n m 12nm 12 nm queries, including all rejected work and any inner repair. Therefore
E [ Q ] ≤ 100 n 3 m , E [ C ] ≤ 49 n 2 m . (51) \mathbb{E}[Q] \le100n^3m,\qquad\mathbb{E}[C] \le49n^2m. \tag*{(51)} E [ Q ] ≤ 100 n 3 m , E [ C ] ≤ 49 n 2 m . (51)
More explicitly, the full ordinary-query implementation satisfies
E [ Q ] ≤ 96 n 2 ( n − 1 ) m + ( n + 1 ) ( n ( n − 1 ) + 1 ) + 2 n , E [ C ] ≤ 48 n ( n − 1 ) m + n ( n − 1 ) + 1. \begin{aligned}
\mathbb{E}[Q] &\le96n^2(n-1)m + (n+1)(n(n-1)+1) + 2n,\\
\mathbb{E}[C] &\le48n(n-1)m + n(n-1) + 1.
\end{aligned} E [ Q ] E [ C ] ≤ 96 n 2 ( n − 1 ) m + ( n + 1 ) ( n ( n − 1 ) + 1 ) + 2 n , ≤ 48 n ( n − 1 ) m + n ( n − 1 ) + 1.
The additional terms cover initialization and normalization at every reached committed boundary, including its possible final two-agent split. For m ≥ 1 m \ge1 m ≥ 1 these quantities are at most the bounds in (51) . Summing conditional iteration bounds over at most n ( n − 1 ) n(n-1) n ( n − 1 ) reached iterations justifies the expectation even when their inputs depend on all earlier accepted and rejected trials.
All internal computation in a finite trial terminates: floating fixes a new coordinate or drops an equation at each step, refinement depth is explicitly bounded, and the remaining operations are finite linear algebra and graph or matching algorithms. Every accepted partition has finitely many recorded endpoints. Old bundle values are sums of cached components; rejected queries remain in the charged transcript even when their tentative pieces are restored. Almost sure termination therefore produces a complete allocation into finite unions, including all null fragments.
For n ≥ 1 n \ge1 n ≥ 1 , s ≤ 2 42 n s \le2^{42}n s ≤ 2 42 n and ℓ ≤ 45 log 2 ( 2 n ) \ell\le45\log_2(2n) ℓ ≤ 45 log 2 ( 2 n ) . Thus
m ≤ c 0 n 9 log 2 ( 2 n ) , c 0 = ( 2 42 ) 9 45 / 128. m \le c_0 n^9 \log_2(2n),\qquad c_0 = (2^{42})^9 45/128. m ≤ c 0 n 9 log 2 ( 2 n ) , c 0 = ( 2 42 ) 9 45/128.
The full bounds are consequently E [ Q ] ≤ 100 c 0 n 12 log 2 ( 2 n ) \mathbb{E}[Q] \le100c_0n^{12}\log_2(2n) E [ Q ] ≤ 100 c 0 n 12 log 2 ( 2 n ) and E [ C ] ≤ 49 c 0 n 11 log 2 ( 2 n ) \mathbb{E}[C] \le49c_0n^{11}\log_2(2n) E [ C ] ≤ 49 c 0 n 11 log 2 ( 2 n ) . Proposition F.12 proves Theorem F.1 ; the direct bases cover n = 1 , 2 n = 1,2 n = 1 , 2 .
A lower bound linear in the success probability
Fix n ≥ 2 n \ge2 n ≥ 2 and p ∈ ( 0 , 1 ] p \in(0,1] p ∈ ( 0 , 1 ] . Consider a jointly measurable ordinary Eval/Cut protocol whose probability of returning a complete exactly envy-free allocation is at least p p p on every normalized finite-step profile with densities in [ 1 / 2 , 3 / 2 ] [1/2,3/2] [ 1/2 , 3/2 ] . Returned shares may have arbitrarily many components, provided each return uses finitely many intervals. The protocol’s random tape is drawn independently of the input from an arbitrary probability space. In this appendix, let Q Q Q count only answered calls on the uniform profile. The resulting lower bound also applies to the paper’s total query count, which is at least Q Q Q .
Theorem G.1. For cake and for chores,
E [ Q ] ≥ max { 0 , n ( n p − 1 ) 2 , n 2 p 4 − 1 } . \mathbb{E}[Q] \ge\max\left\{0,\frac{n(np-1)}{2},\frac{n^2p}{4}-1\right\}. E [ Q ] ≥ max { 0 , 2 n ( n p − 1 ) , 4 n 2 p − 1 } . In particular, for every fixed p > 0 p>0 p > 0 the bound is Ω p ( n 2 ) \Omega_p(n^2) Ω p ( n 2 ) , with a coefficient linear in p p p .
The expectation is unconditional. No termination assumption is made on unsuccessful tapes. For p = 1 p=1 p = 1 , the first term gives n ( n − 1 ) / 2 n(n-1)/2 n ( n − 1 ) /2 . The classical deterministic cake lower bound of Procaccia [15 ] has the same quadratic order; the theorem extends the guarantee to randomized failure, chores, and unrestricted finite fragmentation.
Replay and the uniform baseline
We stop at the first illegal request. This preserves every correct return and cannot increase the cost. Each answered Eval contributes its queried interval to a determining list. An answered Cut starting at a a a and returning z z z contributes [ a , z ] [a,z] [ a , z ] . Strict positivity makes the root unique, so preserving that integral preserves the answer and legality. A reported unavailable target contributes its bracket; such a flag is charged as an answer. If an illegal unavailable-target request is instead uncounted, retain its bracket as one additional determining interval. Valuation-independent syntax errors need no such interval.
For a cutoff T T T , write S T S_T S T for a correct return by the cutoff, s T = P [ S T ] s_T=\mathbb{P}[S_T] s T = P [ S T ] , and J T J_T J T for the indicator of an uncounted illegal terminal request before the cutoff. If e i e_i e i is row i i i ’s number of determining intervals, then
∑ i e i ≤ Q + J T , E [ J T ] ≤ 1 − s T . \sum_i e_i \le Q+J_T,\qquad\mathbb{E}[J_T]\le1-s_T. i ∑ e i ≤ Q + J T , E [ J T ] ≤ 1 − s T .
Equal values on this list preserve the entire capped execution on the same tape, including its terminal request and returned output. This follows by induction on the answered history. If E [ Q ] = ∞ \mathbb{E}[Q]=\infty E [ Q ] = ∞ , there is nothing to prove. Otherwise the probability e T e_T e T of still having a pending request at the cutoff tends to zero. Terminal query-free divergence is already a retained failure.
A narrow bump inside a wider moat
Identify the endpoints only to define arcs on the unit circle; queries and allocations remain ordinary subsets of [ 0 , 1 ] [0,1] [ 0 , 1 ] . Fix
1 n < w < 1 , 0 < h < w . \frac{1}{n}<w<1,\qquad0<h<w. n 1 < w < 1 , 0 < h < w .
Independently of the tape, choose a uniform center X X X . Let B h ( X ) B_h(X) B h ( X ) and W w ( X ) W_w(X) W w ( X ) be the concentric circular arcs of lengths h h h and w w w , and put
d X = 1 2 1 B h ( X ) + h 2 w 1 W w ( X ) . (52) d_X=\frac{1}{2}\mathbf{1}_{B_h(X)}+\frac{h}{2w}\mathbf{1}_{W_w(X)}. \tag*{(52)} d X = 2 1 1 B h ( X ) + 2 w h 1 W w ( X ) . (52)
The two terms have equal integral. Both 1 + d X 1+dX 1 + d X and 1 − d X 1-dX 1 − d X are normalized finite-step densities in [ 1 / 2 , 3 / 2 ] [1/2,3/2] [ 1/2 , 3/2 ] . The plus sign is used for cake and the minus sign for chores.
In the first experiment choose one independent uniform row I I I and replace its density by this perturbed density. In the second choose a uniform row and its cyclic successor and perturb both identically. Every fixed profile in either experiment belongs to the promised input class.
An interval whose endpoints avoid W w ( X ) W_w(X) W w ( X ) contains either all or none of this arc, up to endpoints. Its deviation integral is therefore zero. A fixed endpoint belongs to W w ( X ) W_w(X) W w ( X ) with probability w w w . Let D D D be the event that a determining interval in a perturbed row has an endpoint in the moat. For every fixed baseline tape,
P [ D ∣ ω ] ≤ 2 w n ( Q ( ω ) + J T ( ω ) ) in the one-row experiment, \mathbb{P}[D \mid\omega] \le\frac{2w}{n}\bigl(Q(\omega)+J_T(\omega)\bigr) \quad\text{in the one-row experiment,} P [ D ∣ ω ] ≤ n 2 w ( Q ( ω ) + J T ( ω ) ) in the one-row experiment,
and the coefficient is 4 w / n 4w/n 4 w / n in the two-row experiment. This is a union bound over the complete baseline transcript; it does not condition an adaptive query on earlier nondetection. Outside D D D , the all-outcome replay argument applies exactly.
Decoding a successful uniform allocation
Every successful uniform allocation has all bundle lengths equal to 1 / n 1/n 1/ n . Suppose the narrow bump avoids the finitely many output boundaries, and let a a a be its owner. For a perturbed row i ≠ a i \ne a i = a , write M j = ∣ A j ∩ W w ( X ) ∣ M_j = |A_j \cap W_w(X)| M j = ∣ A j ∩ W w ( X ) ∣ . In the cake orientation,
v i ( A a ) − v i ( A i ) = h 2 − h 2 w M a + h 2 w M i ≥ h 2 ( 1 − 1 n w ) > 0. v_i(A_a)-v_i(A_i)=\frac{h}{2}-\frac{h}{2w}M_a+\frac{h}{2w}M_i\ge\frac{h}{2}\left(1-\frac{1}{nw}\right)>0. v i ( A a ) − v i ( A i ) = 2 h − 2 w h M a + 2 w h M i ≥ 2 h ( 1 − n w 1 ) > 0.
The reversed density gives the same strictly positive gap v i ( A i ) − v i ( A a ) v_i(A_i)-v_i(A_a) v i ( A i ) − v i ( A a ) for chores. Thus every perturbed row must own X X X if the old allocation remains correct. A single independent uniform row owns X X X with probability 1 / n 1/n 1/ n ; two distinct rows cannot both own it.
The strict inequality w > 1 / n w>1/n w > 1/ n avoids any exceptional case in which a bundle coincides with the moat. We take w ↓ 1 / n w \downarrow1/n w ↓ 1/ n only after completing the argument.
Retaining failures and choosing one width
For every measurable set A A A ,
∣ ∫ A d x ∣ ≤ h / 2. \left|\int_A dx\right|\le h/2. ∫ A d x ≤ h /2.
Indeed, the positive and negative terms separately have total mass h / 2 h/2 h /2 . Every envy comparison therefore changes by at most h h h , including in the two-row experiment: each comparison uses only one observer’s valuation.
On a complete but incorrect uniform return, let Δ > 0 \Delta>0 Δ > 0 be the difference between the longest and shortest bundle lengths. A shortest owner’s comparison with a longest bundle witnesses this gap for cake; a longest owner’s comparison with a shortest bundle does so for chores. If Δ > h \Delta>h Δ > h , the replayed output remains incorrect. Malformed returns and nonreturns remain failures by replay.
The endpoint list on each returned tape is finite, although its expected length need not be finite. If it has length N N N , the probability that the narrow bump meets it is at most min { 1 , h N } \min\{1,hN\} min { 1 , h N } . Dominated convergence gives a total endpoint loss tending to zero as h ↓ 0 h\downarrow0 h ↓ 0 . The probability of an incorrect uniform return with 0 < Δ ≤ h 0<\Delta\le h 0 < Δ ≤ h also tends to zero. Consequently, for each fixed w w w and any η > 0 \eta>0 η > 0 , one deterministic h ∈ ( 0 , w ) h\in(0,w) h ∈ ( 0 , w ) loses probability at most η \eta η in both tests. The width is fixed before the center, perturbed rows, and tape are drawn.
Expected query accounting
The fixed-input success guarantee integrates to success at least p p p under either hard distribution. At any fixed cutoff, the preceding argument, with geometric loss at most η \eta η , gives
p ≤ s T n + 2 w n ( E [ Q ] + 1 − s T ) + η + e T and p ≤ 4 w n ( E [ Q ] + 1 − s T ) + η + e T . p \le\frac{s_T}{n}+\frac{2w}{n}\left(\mathbb{E}[Q]+1-s_T\right)+\eta+e_T
\quad\text{and}\quad
p \le\frac{4w}{n}\left(\mathbb{E}[Q]+1-s_T\right)+\eta+e_T. p ≤ n s T + n 2 w ( E [ Q ] + 1 − s T ) + η + e T and p ≤ n 4 w ( E [ Q ] + 1 − s T ) + η + e T .
The losses can be removed without assuming that s T s_T s T is fixed across cutoffs. Indeed, for 0 ≤ s ≤ 1 0 \le s \le1 0 ≤ s ≤ 1 , n ≥ 2 n \ge2 n ≥ 2 , and w ≥ 1 / n w \ge1/n w ≥ 1/ n ,
s n + 2 w n ( q + 1 − s ) ≤ 1 n + 2 w n q + 2 ( w − 1 / n ) n . \frac{s}{n}+\frac{2w}{n}(q+1-s)\le\frac{1}{n}+\frac{2w}{n}q+\frac{2(w-1/n)}{n}. n s + n 2 w ( q + 1 − s ) ≤ n 1 + n 2 w q + n 2 ( w − 1/ n ) .
After multiplication by n 2 n^2 n 2 , the difference is ( n − 2 ) ( 1 − s ) + 2 ( n w − 1 ) s ≥ 0 (n-2)(1-s)+2(nw-1)s \ge0 ( n − 2 ) ( 1 − s ) + 2 ( n w − 1 ) s ≥ 0 . First choose a cutoff with e T e_T e T arbitrarily small, then choose one sufficiently narrow bump at that cutoff. Letting both losses vanish yields
p ≤ 1 n + 2 w n E [ Q ] + 2 ( w − 1 / n ) n , p ≤ 4 w n ( E [ Q ] + 1 ) . p \le\frac{1}{n}+\frac{2w}{n}\mathbb{E}[Q]+\frac{2(w-1/n)}{n},
\qquad
p \le\frac{4w}{n}\left(\mathbb{E}[Q]+1\right). p ≤ n 1 + n 2 w E [ Q ] + n 2 ( w − 1/ n ) , p ≤ n 4 w ( E [ Q ] + 1 ) .
Finally let w ↓ 1 / n w \downarrow1/n w ↓ 1/ n . The two inequalities become E [ Q ] ≥ n ( n p − 1 ) / 2 \mathbb{E}[Q] \ge n(np-1)/2 E [ Q ] ≥ n ( n p − 1 ) /2 and E [ Q ] ≥ n 2 p / 4 − 1 \mathbb{E}[Q] \ge n^2p/4-1 E [ Q ] ≥ n 2 p /4 − 1 . Taking their maximum with zero proves the theorem.
All events used here are measurable. Circular arc membership is a Borel distance test; actual density values and cumulative integrals are jointly measurable in their center and endpoints. Strictly positive cumulative functions give measurable unique Cut replies. Finite transcript and finite-output spaces are countable disjoint unions of their fixed-length Borel parameter spaces. Endpoint-loss, output-gap, and comparison events are therefore measurable. Tonelli justifies integration first over the tape or first over the fixed input. No regular conditional probability on the tape space is required.
Bounded-error lower bounds for mixed resources
We prove Theorem 2.4 for an oracle that always returns the leftmost legal root. Reflection gives the always-rightmost case. The hard input has a final interval that every acceptable allocation must split. The construction moves the beginning of that interval past the coordinates used by many executions, while preserving all their query answers.
Lemma H.1 (Relative approximation on positive-net profiles). For 0 < α ≤ 1 0 < \alpha\le1 0 < α ≤ 1 , the signed relative comparison
y − x ≤ ( 1 − α ) max { ∣ x ∣ , ∣ y ∣ } y-x \le(1-\alpha)\max\{|x|,|y|\} y − x ≤ ( 1 − α ) max { ∣ x ∣ , ∣ y ∣ } is equivalent to x ≥ α y x \ge\alpha y x ≥ α y if y ≥ 0 y \ge0 y ≥ 0 , and to x ≥ y / α x \ge y/\alpha x ≥ y / α if y < 0 y < 0 y < 0 . It always holds when x ≥ y x \ge y x ≥ y . For a complete allocation with v i ( I ) > 0 v_i(I)>0 v i ( I ) > 0 for all i i i , condition (1) is equivalent to v i ( A i ) ≥ α v i ( A j ) v_i(A_i) \ge\alpha v_i(A_j) v i ( A i ) ≥ α v i ( A j ) for all i , j i,j i , j .
Proof. If x ≥ y x \ge y x ≥ y , the left side is nonpositive and the right side is nonnegative. The corresponding threshold is at most y y y , so it is also satisfied. Suppose x < y x < y x < y . If 0 ≤ x < y 0 \le x < y 0 ≤ x < y , the maximum is y y y , and the comparison is exactly x ≥ α y x \ge\alpha y x ≥ α y . If x < y ≤ 0 x < y \le0 x < y ≤ 0 , the maximum is − x -x − x , and the comparison is exactly x ≥ y / α x \ge y/\alpha x ≥ y / α . If x < 0 < y x < 0 < y x < 0 < y , neither condition can hold: y − x y-x y − x exceeds max { ∣ x ∣ , ∣ y ∣ } \max\{|x|,|y|\} max { ∣ x ∣ , ∣ y ∣ } , whereas α y > 0 > x \alpha y > 0 > x α y > 0 > x . The zero endpoints follow from the same inequalities.
For the allocation statement, positive total value implies that some bundle has positive value to each observer. Relative EF then forces that observer’s own value to be positive. Comparisons with nonnegative bundles are the usual cake inequalities, and comparisons with negative bundles hold automatically. Conversely, the cake inequalities force a positive own value and imply every relative comparison. Summing them also gives v i ( A i ) ≥ α v i ( I ) / ( n − 1 + α ) v_i(A_i) \ge\alpha v_i(I)/(n-1+\alpha) v i ( A i ) ≥ α v i ( I ) / ( n − 1 + α ) .
Model and finite-horizon statement
Fix n ≥ 3 n \ge3 n ≥ 3 and 0 ≤ ε < α ≤ 1 0 \le\varepsilon< \alpha\le1 0 ≤ ε < α ≤ 1 . Each valuation v i v_i v i is a finite atomless signed Borel measure on [ 0 , 1 ] [0,1] [ 0 , 1 ] , normalized by v i ( [ 0 , 1 ] ) = 1 v_i([0,1]) = 1 v i ([ 0 , 1 ]) = 1 . Write F i ( x ) = v i ( [ 0 , x ] ) F_i(x) = v_i([0,x]) F i ( x ) = v i ([ 0 , x ]) . An allocation is correct if
α v i ( A j ) − v i ( A i ) ≤ ε ( i , j ∈ [ n ] ) . (53) \alpha v_i(A_j) - v_i(A_i) \le\varepsilon\qquad(i,j \in[n]). \tag*{(53)} α v i ( A j ) − v i ( A i ) ≤ ε ( i , j ∈ [ n ]) . (53)
By Lemma H.1 , ε = 0 \varepsilon= 0 ε = 0 gives the signed multiplicative guarantee; α = 1 \alpha= 1 α = 1 gives additive ε \varepsilon ε -EF. There is no common bound on total variation.
An Eval query returns one interval value. A signed query Cut ( i , a , b , t ) \operatorname{Cut}(i,a,b,t) Cut ( i , a , b , t ) is legal when
0 ≤ a ≤ b ≤ 1 , min { 0 , F i ( b ) − F i ( a ) } ≤ t ≤ max { 0 , F i ( b ) − F i ( a ) } . (54) 0 \le a \le b \le1,\qquad\min\{0,F_i(b)-F_i(a)\} \le t \le\max\{0,F_i(b)-F_i(a)\}. \tag*{(54)} 0 ≤ a ≤ b ≤ 1 , min { 0 , F i ( b ) − F i ( a )} ≤ t ≤ max { 0 , F i ( b ) − F i ( a )} . (54)
It returns the least x ∈ [ a , b ] x \in[a,b] x ∈ [ a , b ] satisfying F i ( x ) − F i ( a ) = t F_i(x)-F_i(a)=t F i ( x ) − F i ( a ) = t . Continuity ensures that this root exists. The rule is fixed independently of the protocol and its random tape.
We use the measurability assumptions of § 2 : on each fixed profile, the existence, coordinates and replies of every numbered call, and the event and finite encoding of a return, are measurable.
A pointwise-legal partial strategy makes only legal calls on every profile and tape. It may abort, return an incorrect allocation, or fail to return. Malformed outputs are discarded. Every retained output is a complete allocation into finite unions of intervals, with no restriction on its number of endpoints. Endpoints themselves have zero value; a fixed half-open convention makes their ownership immaterial.
Theorem H.2 (Finite-horizon hardness for leftmost roots). Let A \mathcal{A} A be a measurable pointwise-legal partial strategy making at most h h h oracle calls on every profile and tape. For every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , there is one profile of finite piecewise-constant signed densities, with all net totals one, such that
P [ A returns a correct allocation ] ≤ δ \mathbb{P}[\mathcal{A}\text{ returns a correct allocation}] \le\delta P [ A returns a correct allocation ] ≤ δ under the always-leftmost oracle. Output endpoints may be chosen freely and need not have been queried.
The profile may depend on the strategy, its tape law, h h h , α \alpha α , ε \varepsilon ε , and δ \delta δ . It is fixed before the tape used to execute the protocol is drawn. We establish the theorem by finitely many changes to the profile.
A final interval that must be split
Set K = 1 + 1 / α K = 1 + 1/\alpha K = 1 + 1/ α . Maintain a number ℓ < 1 \ell< 1 ℓ < 1 , called the frontier , and a finite partition of [ 0 , ℓ ] [0,\ell] [ 0 , ℓ ] into intervals with constant density vectors d = ( d 1 , … , d n ) d = (d_1,\ldots,d_n) d = ( d 1 , … , d n ) . On each such interval, either every d i ≤ 0 d_i \le0 d i ≤ 0 , or one entry is p > 0 p > 0 p > 0 and every other entry is at most − K p -Kp − K p . On the remaining interval ( ℓ , 1 ] (\ell,1] ( ℓ , 1 ] , every density is constant and strictly positive. All net totals are one, and
F i ( x ) < 1 ( x < 1 ) , F i ( 1 ) = 1. (55) F_i(x) < 1 \quad(x < 1),\qquad F_i(1)=1. \tag*{(55)} F i ( x ) < 1 ( x < 1 ) , F i ( 1 ) = 1. (55)
Uniform densities with ℓ = 0 \ell= 0 ℓ = 0 satisfy these conditions.
Lemma H.3 (Unsplit final interval). Every allocation that assigns ( ℓ , 1 ] (\ell,1] ( ℓ , 1 ] to one agent violates (53) . This holds even if the intervals in [ 0 , ℓ ] [0,\ell] [ 0 , ℓ ] are divided into arbitrary measurable pieces.
Proof. Let c c c own ( ℓ , 1 ] (\ell,1] ( ℓ , 1 ] and consider the average
E c = 1 n − 1 ∑ i ≠ c ( α v i ( A c ) − v i ( A i ) ) . E_c=\frac{1}{n-1}\sum_{i\ne c}\left(\alpha v_i(A_c)-v_i(A_i)\right). E c = n − 1 1 i = c ∑ ( α v i ( A c ) − v i ( A i ) ) .
Initially assigning the entire resource to c c c gives E c = α E_c=\alpha E c = α . For a constant-density interval J ⊆ [ 0 , ℓ ] J\subseteq[0,\ell] J ⊆ [ 0 , ℓ ] , let x J k x_{Jk} x J k be the fraction of its length assigned to k k k . Moving that fraction from c c c to k ≠ c k\ne c k = c decreases E c E_c E c by
x J k ∣ J ∣ n − 1 ( α ∑ i ≠ c d i + d k ) . (56) \frac{x_{Jk}|J|}{n-1}\left(\alpha\sum_{i\ne c}d_i+d_k\right). \tag*{(56)} n − 1 x J k ∣ J ∣ α i = c ∑ d i + d k . (56)
The parenthesized coefficient is nonpositive. This is immediate when all entries are nonpositive or the positive entry belongs to c c c . If the positive entry p p p belongs to k k k , there is another index different from c , k c,k c , k , since n ≥ 3 n\ge3 n ≥ 3 , and
α ∑ i ≠ c d i + d k ≤ ( α + 1 ) p − α K p = 0. \alpha\sum_{i\ne c}d_i+d_k\le(\alpha+1)p-\alpha Kp=0. α i = c ∑ d i + d k ≤ ( α + 1 ) p − α K p = 0.
If the positive entry belongs to a third agent, the coefficient is at most α p − ( α + 1 ) K p ≤ 0 \alpha p-(\alpha+1)Kp\le0 α p − ( α + 1 ) K p ≤ 0 . Summing (56) over intervals and recipients gives E c ≥ α E_c\ge\alpha E c ≥ α . Some nonowner therefore has comparison gap at least α > ε \alpha>\varepsilon α > ε .
Lemma H.4 (Advancing the frontier). For any ℓ < r < 1 \ell<r<1 ℓ < r < 1 and agent j j j , the frontier can be moved to r r r while preserving all the stated conditions, every cumulative value on [ 0 , ℓ ] ∪ { 1 } [0,\ell]\cup\{1\} [ 0 , ℓ ] ∪ { 1 } , and the entire valuation of agent j j j . There is also such an update that assigns every agent density − 1 -1 − 1 on ( ℓ , r ] (\ell,r] ( ℓ , r ] , without preserving a designated agent.
Proof. Let d j > 0 d_j>0 d j > 0 be agent j j j ’s current density on ( ℓ , 1 ] (\ell,1] ( ℓ , 1 ] . Keep this row unchanged. For every i ≠ j i\ne j i = j , use density − K d j -Kd_j − K d j on ( ℓ , r ] (\ell,r] ( ℓ , r ] , and density
1 − F i ( ℓ ) + K d j ( r − ℓ ) 1 − r > 0 \frac{1-F_i(\ell)+Kd_j(r-\ell)}{1-r}>0 1 − r 1 − F i ( ℓ ) + K d j ( r − ℓ ) > 0
on ( r , 1 ] (r,1] ( r , 1 ] . The new resolved interval has exactly the required density pattern. Each changed cumulative first decreases from a value below one, then increases linearly to one. Thus (55) persists. For the second update, use − 1 -1 − 1 on ( ℓ , r ] (\ell,r] ( ℓ , r ] for every row and restore its net total by a positive constant density on ( r , 1 ] (r,1] ( r , 1 ] . Both operations introduce one resolved interval and keep all densities finite.
Preserving every first-root reply
Call a query protected if its bracket endpoints and its returned root, when it is a Cut query, lie in [ 0 , ℓ ] ∪ { 1 } [0,\ell]\cup\{1\} [ 0 , ℓ ] ∪ { 1 } .
Lemma H.5 (First-root replay). Every protected query retains its legality and answer under subsequent frontier updates. For a fixed continuous cumulative function, the least-root response is a Borel function on the legal query domain.
Proof. All cumulative values at query endpoints remain fixed, so Eval answers, Cut bracket totals, and legality are preserved. Let z z z be an old least-root reply. If z ≤ ℓ z \le\ell z ≤ ℓ , the cumulative function on [ a , z ] [a,z] [ a , z ] is unchanged, so z z z remains the first root. If z = 1 z=1 z = 1 and a < 1 a<1 a < 1 , the target absolute cumulative level is one; by (55) , this level is never reached earlier. The degenerate query a = b = 1 , t = 0 a=b=1,t=0 a = b = 1 , t = 0 is unchanged directly. This covers negative targets, full-bracket targets, zero targets, and zero-total brackets.
For measurability, fix F F F . Its legal query domain is Borel. For rational q q q , existence of a root in [ a , min { b , q } ] [a,\min\{b,q\}] [ a , min { b , q }] is equivalent, when this interval is nonempty, to
min x ∈ [ a , min { b , q } ] ∣ F ( x ) − F ( a ) − t ∣ = 0. \min_{x\in[a,\min\{b,q\}]} \lvert F(x)-F(a)-t\rvert=0. x ∈ [ a , m i n { b , q }] min ∣ F ( x ) − F ( a ) − t ∣ = 0.
The minimum is continuous in its interval endpoints and target: substitute x = a + s ( u − a ) x=a+s(u-a) x = a + s ( u − a ) and minimize over the fixed compact interval s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] . The event that the least root is smaller than z z z is the union of these Borel events over rational q < z q<z q < z . □ \square □
A new query to agent j j j can always be protected. Compute its reply on the current profile and choose r < 1 r<1 r < 1 beyond all its coordinates smaller than one. The first update in Lemma H.4 keeps row j j j unchanged everywhere, so it preserves this new reply, as well as every earlier protected query.
Likewise, a finite output can be protected by moving the frontier past all its endpoints smaller than one using the all-negative update. The remaining interval then has one owner, so Lemma H.3 makes the output incorrect. Every later update preserves that output’s values: each interval endpoint lies in the fixed prefix or at one, where cumulative values are unchanged. This preservation of failures is essential when a protocol is allowed to fail with positive probability.
One fixed hard input for randomized protocols
Proof of Theorem H.2 . Fix the tape probability space. On each current profile, describe the k k k th call by its row and finite list of coordinates, including a Cut reply. If the k k k th call does not exist, use the formal descriptor Eval( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) . This is only notation for the analysis; the protocol does not detect nontermination or execute extra calls. The descriptors are measurable by the assumed measurability of call existence and transcripts. Identical real transcripts and tapes determine identical internal computation, including a return or a nonreturn after the last call.
Maintain a measurable set H H H of tapes whose executions already fail on the current profile. Their actual queries are protected, and the endpoints of any returned allocation are protected as well. All future frontier updates preserve these executions and their output values, so no tape in H H H becomes successful. Initially H = ∅ H=\varnothing H = ∅ .
Let S = Ω ∖ H S=\Omega\setminus H S = Ω ∖ H have mass u > 0 u>0 u > 0 . We capture a fixed fraction of this mass in one batch of at most h + 1 h+1 h + 1 updates. At stage k ∈ { 1 , … , h } k\in\{1,\ldots,h\} k ∈ { 1 , … , h } , the first k − 1 k-1 k − 1 descriptors of the surviving tapes are already protected. Evaluate their k k k th descriptors on the current profile. Some row j j j occurs on a measurable subset of at least 1 / n 1/n 1/ n of the surviving mass. On each tape in this subset, the maximum of ℓ \ell ℓ and the descriptor coordinates smaller than one is strictly less than one. Continuity from below of probability therefore gives a fixed r ∈ ( ℓ , 1 ) r\in(\ell,1) r ∈ ( ℓ , 1 ) that bounds these coordinates on at least half the subset. Retain those tapes and perform the update preserving row j j j .
The selected query’s answer is unchanged because its entire row is unchanged. Previous answers replay by Lemma H.5 . If the descriptor is formal, the preceding real transcript and tape already determine the absence of another call. Thus all first k k k descriptors are now protected. Each stage retains at least a 1 / ( 2 n ) 1/(2n) 1/ ( 2 n ) fraction of the current mass. After h h h stages, the surviving mass is at least u / ( 2 n ) h u/(2n)^h u / ( 2 n ) h , and every actual query on those executions is protected. For each surviving tape with a finite return, take the maximum of ℓ \ell ℓ and its output endpoints smaller than one; for a nonreturn, use ℓ \ell ℓ . These are measurable quantities strictly below one, even though the number of endpoints is unbounded. Choose a further fixed r < 1 r < 1 r < 1 that bounds them on at least half the surviving mass, and make the all-negative frontier update. All actual transcripts replay, so every finite output is unchanged and leaves ( r , 1 ] (r,1] ( r , 1 ] unsplit. It is incorrect by Lemma H.3 . Nonreturns remain nonreturns. Add the retained tapes to H H H . The newly captured mass is at least
γ u , γ = 1 2 ( 2 n ) h . (57) \gamma u,\qquad\gamma= \frac{1}{2(2n)^h}. \tag*{(57)} γ u , γ = 2 ( 2 n ) h 1 . (57)
The same argument applies when h = 0 h = 0 h = 0 , using only the output update.
After B B B batches, the uncaptured mass is at most ( 1 − γ ) B (1-\gamma)^B ( 1 − γ ) B . Choose a finite B B B for which this is at most δ \delta δ . There have been at most ( h + 1 ) B (h+1)B ( h + 1 ) B updates, so the final profile has finitely many constant-density intervals and finite total variation. At least 1 − δ 1-\delta 1 − δ of its tapes fail.
Every row choice and coordinate quantile was selected using the fixed tape law on one fixed intermediate profile. Only finitely many such profiles and measurable sets were used. The resulting input is fixed before the execution tape is drawn; no input is chosen in response to that realized tape. No measurability over a space of profiles or infinite limit of profiles is needed.
Expected queries and rightmost roots
Proof of Theorem 2.4 . Suppose the original protocol has probability at least p > 0 p > 0 p > 0 of a legal correct finite return on every input with the always-leftmost oracle. Let S S S be its success event and Q Q Q its number of attempted calls. Fix an integer q ≥ 0 q \ge0 q ≥ 0 .
Simulate the protocol, aborting before its ( q + 1 ) (q+1) ( q + 1 ) st attempted call. Reject malformed syntax, invalid rows, and invalid bracket endpoints. Before each simulated Cut, Eval its bracket and check (54) ; abort if the target is illegal, and otherwise issue the Cut. Hide the extra Eval reply from the simulated protocol. At a finite return, discard malformed allocations and normalize endpoint ownership, without testing any value inequality or limiting the number of endpoints. Permit all query-free computation after the q q q th call; a subsequent nonreturn is retained.
This is a pointwise-legal partial strategy with at most 2 q 2q 2 q actual calls. The fixed least-root rule returns exactly the original answers on legal simulated histories. Its correct-return event is therefore S ∩ { Q ≤ q } S \cap\{Q \le q\} S ∩ { Q ≤ q } . For any 0 < δ < p 0 < \delta< p 0 < δ < p , Theorem H.2 gives a fixed profile with
P [ S , Q ≤ q ] ≤ δ . \mathbb{P}[S,\, Q \le q] \le\delta. P [ S , Q ≤ q ] ≤ δ .
On that same profile, P [ S ] ≥ p \mathbb{P}[S] \ge p P [ S ] ≥ p , and hence
E [ Q ] ≥ ( q + 1 ) P [ S , Q > q ] ≥ ( q + 1 ) ( p − δ ) . (58) \mathbb{E}[Q] \ge(q+1)\mathbb{P}[S,\, Q > q] \ge(q+1)(p-\delta). \tag*{(58)} E [ Q ] ≥ ( q + 1 ) P [ S , Q > q ] ≥ ( q + 1 ) ( p − δ ) . (58)
Since q q q is arbitrary, no uniform finite bound on expected queries exists.
For an always-rightmost protocol, reflect the input by x ↦ 1 − x x \mapsto1-x x ↦ 1 − x . A Cut on [ a , b ] [a,b] [ a , b ] with target t t t corresponds to a Cut on [ 1 − b , 1 − a ] [1-b,1-a] [ 1 − b , 1 − a ] with target B − t B-t B − t , where B B B is the bracket value. The legal target interval is preserved and spatial order reverses. One Eval obtains B B B and one least-root Cut gives the greatest root on the reflected input. Eval queries and output intervals reflect directly. A uniformly bounded always-rightmost protocol would therefore yield an always-leftmost protocol with at most twice the query cost, the same fairness guarantee, and the same success probability, contradicting the preceding conclusion.
Taking ε = 0 \varepsilon= 0 ε = 0 proves the multiplicative claim; taking α = 1 \alpha= 1 α = 1 proves the additive claim. At ε ≥ α \varepsilon\ge\alpha ε ≥ α , assigning the entire resource to one agent satisfies (53) without queries, so the tolerance range is sharp on this normalization. The result concerns a uniform bound over inputs. It neither rules out a finite protocol on each individual input nor asserts that a single input must have infinite expected cost. The construction uses unbounded variation across inputs and gives no impossibility for a class with a fixed common variation bound or for variation-normalized error.
Formal verification artifact
The accompanying artifact [9 ] formalizes the four main results in Lean. The statements use adaptive Eval/Cut protocols and finite interval representations of allocations. The upper-bound developments construct the physical allocations and account for every oracle query; the lower-bound developments include the transcript and probability arguments establishing a fixed hard input.
Table 2.
The formal algorithms make conservative implementation choices: a fixed sufficient clearance length and explicit endpoint-recording costs for chores, and a separate charge for each normalization step in the randomized protocol. These choices preserve the main bounds. The artifact does not claim that every sharper auxiliary ledger in the paper is formalized verbatim. Its endpoint manifest identifies the public Lean statements corresponding to the four theorems; those statements record the precise hypotheses.
The source package pins Lean 4.35.0, mathlib, and the fixed-point library used for the chore construction. The verifier rejects proof placeholders and project axioms and checks every included theorem’s transitive axiom dependencies. Only propext, Classical.choice, and Quot.sound are allowed. The package includes build instructions, source hashes, and independent correspondence reviews.
AI methodology
OpenAI Codex, using the Astra model, materially supported literature discovery and comparison, conjecture and proof development, proof checks, exact experiments, Lean formalization, and drafting throughout this article. Fable 5.2 also contributed proposed upper-bound improvements that informed the revised proofs. The artifact preserves sources and review reports. Appendix § 14 describes the formal verification coverage.