Answer: —
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe query complexity (in the Robertson-Webb model) of achieving an envy-free allocation is Ω(n2). 1There is a moving knife solution to the four agent envy-free cake-cutting problem with a bounded number of cuts [Brams et al., 1997], but there is no bounded solution for n > 4 even if moving knives are allowed. Notice that our result does not require any restrictions on the cake-cutting algorithm, apart from the implicit assump- tion that it is captured by the Robertson-Webb query model.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given total population mass \(N\), a rational distribution \(\mu\) over \(\tau\) complete valuation types with \(\sum_t \mu_t=1\), and a Robertson–Webb oracle for each type's normalized additive nonatomic valuation, what is the worst-case number of cut and evaluation queries needed to output a finite list \((t_j,q_j,X_j)_{j=1}^S\)? Require \(\sum_{j:t_j=t}q_j=N\mu_t\), \(\sum_j q_j\mathbf{1}_{x\in X_j}=1\) almost everywhere, and \(v_{t_j}(X_j)\ge v_{t_j}(X_k)\) for every pair of cohorts \(j,k\).
The cake is \([0,1]\). A society is given by its support: \(\tau\) complete valuation types, each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types. Total population mass is a binary rational \(N\ge1\), and \(L\) is the total bit length of these rational inputs.
Each type has a nonnegative additive nonatomic valuation \(v_t\), normalized by \(v_t([0,1])=1\), accessible only through truthful Robertson–Webb cut and evaluation queries. Any valid cut answer is permitted, and correctness must hold for every such answer.
An output is a finite list \((t_j,q_j,X_j)_{j=1}^S\), with \(t_j\in\{1,\ldots,\tau\}\), positive rational cohort masses \(q_j\), and pieces \(X_j\subseteq[0,1]\) that are finite unions of intervals; endpoints are immaterial.
Require \(\sum_{j:t_j=t}q_j=N\mu_t\) for every type, \(\sum_jq_j\mathbf1_{X_j}(x)=1\) Lebesgue-almost everywhere, and \(v_{t_j}(X_j)\ge v_{t_j}(X_k)\) for every pair of cohorts. Pieces may overlap subject to the weighted conservation equation.
Count cut and evaluation queries equally; protocols are deterministic and adaptive, and computation and output incur no query cost. Bounds use \(N,\tau,L\); there is no finite alternative-count parameter \(m\).
What is the optimal worst-case Robertson–Webb query complexity of this allocation problem as a function of \(N,\tau,L\)? Is a polynomial query bound possible, or must the worst-case complexity be superpolynomial, possibly admitting no finite uniform bound?
For ordinary partitions among \(n\) individual agents, [Procaccia](https://www.ijcai.org/Proceedings/09/Papers/049.pdf) proves an \(\Omega(n^2)\) query lower bound; [Aziz and Mackenzie](https://arxiv.org/abs/1604.03655) give a query bound depending only on \(n\).
No result settling the stated mass-cohort query problem was identified in the literature search.
A query bound polynomial in $N,\tau,L$ is impossible. In fact,
$$
Q_1(1+2^{-b})=2^b,
$$
where $Q_1(N)$ denotes the optimal worst-case query complexity for one supported type. These inputs have bounded $N$, $\tau=1$, and $L=\Theta(b)$.
The unrestricted problem remains partially resolved. The additional progress established below is:
I do not establish a finite uniform bound, or its impossibility, for arbitrary profiles with $\tau\ge3$.
Let $C=[0,1]$, let $\lambda$ denote Lebesgue measure, and write
$$
p_t=N\mu_t.
$$
For any admissible output, the function
$$
H(x)=\sum_jq_j\mathbf1_{X_j}(x)
$$
is constant on every open interval between consecutive output endpoints. Since $H=1$ Lebesgue-almost everywhere, it equals $1$ outside the finite set of output endpoints. Every nonatomic valuation assigns that finite set value zero. Therefore, for every type $t$,
$$
\sum_jq_jv_t(X_j)=1.
$$
This justifies integration of conservation even against singular nonatomic valuations.
For one supported type, envy-freeness in both directions forces all output pieces to have the same value, say $c$. Since the cohort masses sum to $N$,
$$
1=\sum_jq_jv(X_j)=Nc.
$$
Thus every output piece necessarily satisfies
$$
v(X_j)=\frac1N.
$$
When $N=1$, the general problem has a zero-query solution: output $(t,\mu_t,C)$ for every type. Henceforth, where needed, assume $N>1$.
Lemma. Suppose a correct deterministic one-type protocol terminates after $Q$ queries against $v=\lambda$. There is a subspace $F\subseteq L^2(\lambda)$ such that
$$
1\in F,\qquad \dim F\le Q+1,
$$
and every output indicator belongs to $F$.
Proof. Generate $F$ by the constant function $1$ and one interval indicator for each query:
Thus $\dim F\le Q+1$. If infeasible cut queries are allowed and report that the requested value exceeds the suffix value, use the suffix indicator for such a query; preserving its integral preserves infeasibility.
Suppose an output indicator $f=\mathbf1_{X_j}$ does not belong to $F$. Let
$$
h=f-P_Ff,
$$
where $P_F$ is orthogonal projection onto $F$. Then
$$
h\ne0,\qquad h\perp F,\qquad
\int h\,d\lambda=0,
$$
and
$$
\int fh\,d\lambda=\|h\|_2^2>0.
$$
The function $h$ is bounded: $f$ is bounded, and $P_Ff$ is a finite linear combination of bounded interval indicators and $1$. Choose $\varepsilon>0$ sufficiently small that $1+\varepsilon h$ is strictly positive, and define
$$
v_\varepsilon(A)=\int_A(1+\varepsilon h)\,d\lambda.
$$
This is a normalized, nonnegative, additive nonatomic valuation.
Orthogonality preserves every recorded interval integral. Consequently, all original evaluation answers remain correct and all original cut endpoints remain valid. Inductively, determinism permits exactly the same transcript and output under $v_\varepsilon$. This argument uses precisely the requirement that correctness hold for every valid cut answer.
By Section 1, the identical output must satisfy
$$
v_\varepsilon(X_j)=\lambda(X_j)=\frac1N.
$$
But
$$
v_\varepsilon(X_j)-\lambda(X_j)
=\varepsilon\int fh\,d\lambda
=\varepsilon\|h\|_2^2>0,
$$
a contradiction. Therefore every output indicator belongs to $F$. $\square$
Lemma. Let $g_1,\ldots,g_S$ be indicators on a probability space with measure $\nu$. Suppose
$$
\int g_j\,d\nu=\beta>0
$$
for every $j$, and positive weights $r_j$ satisfy
$$
\sum_jr_jg_j=1
$$
almost everywhere. If all $g_j$ belong to a finite-dimensional subspace $F\subseteq L^2(\nu)$, then
$$
\dim F\ge\frac1\beta.
$$
Proof. Let $e_1,\ldots,e_d$ be an orthonormal basis of $F$. Integrating coverage gives $\beta\sum_jr_j=1$. Since $\|g_j\|_2^2=\beta$,
$$
\sum_{\ell=1}^d\sum_jr_j\langle g_j,e_\ell\rangle^2
=\sum_jr_j\|g_j\|_2^2=1.
$$
Cauchy–Schwarz on the support of $g_j$ gives
$$
\langle g_j,e_\ell\rangle^2
\le \beta\int g_je_\ell^2\,d\nu.
$$
Hence, for each $\ell$,
$$
\sum_jr_j\langle g_j,e_\ell\rangle^2
\le
\beta\int\left(\sum_jr_jg_j\right)e_\ell^2\,d\nu
=\beta.
$$
Summing over $\ell$ proves $1\le d\beta$. $\square$
On the uniform transcript, write $f_j=\mathbf1_{X_j}$. Section 1 gives
$$
\int f_j\,d\lambda=\frac1N,\qquad
\sum_jq_jf_j=1.
$$
The dimension lemma implies $\dim F\ge N$.
The complement indicators $g_j=1-f_j$ also belong to $F$, and satisfy
$$
\int g_j\,d\lambda=\frac{N-1}{N},
\qquad
\sum_j\frac{q_j}{N-1}g_j=1.
$$
Applying the lemma again gives $\dim F\ge N/(N-1)$. Consequently,
$$
\boxed{
Q_1(N)\ge
\left\lceil\max\left\{N,\frac{N}{N-1}\right\}\right\rceil-1
\qquad(N>1).
}
$$
If a protocol does not terminate on the uniform valuation, its worst-case query count is already infinite. Thus nontermination does not evade this lower bound.
Write $N=A/B\ge1$, with positive integers $A,B$ and $B\le A$.
Ask $A-1$ cumulative cut queries with targets
$$
\frac1A,\frac2A,\ldots,\frac{A-1}{A}.
$$
Together with endpoints $0,1$, their answers form consecutive cells $C_0,\ldots,C_{A-1}$ of value $1/A$.
These endpoints are strictly ordered for every permitted choice of cut answers: if a larger target had an endpoint no farther right than a smaller target, monotonicity would contradict the target values.
For each $i$, with indices taken modulo $A$, output
$$
\left(1,\frac1B,X_i\right),
\qquad
X_i=\bigcup_{r=0}^{B-1}C_{i+r}.
$$
Every cell appears in exactly $B$ pieces. Therefore coverage is $1$, total cohort mass is $A/B=N$, and every piece has value
$$
\frac BA=\frac1N.
$$
This proves
$$
Q_1(A/B)\le A-1.
$$
Combining this construction with Section 2 yields
$$
Q_1(n)=n-1
\qquad\text{for integers }n\ge2,
$$
and
$$
Q_1\!\left(\frac{D+1}{D}\right)=D
\qquad\text{for integers }D\ge1.
$$
Taking $D=2^b$ gives
$$
Q_1(1+2^{-b})=2^b.
$$
The input length is $\Theta(b)$, while $1<N<2$ and $\tau=1$. Thus every proposed uniform bound polynomial in $N,\tau,L$ is contradicted by this family.
Three queries suffice. Cut at cumulative values $1/5,2/5,3/5$, obtaining cells with values
$$
v(C_0)=v(C_1)=v(C_2)=\frac15,
\qquad
v(C_3)=\frac25.
$$
Output $C_3$ with cohort mass $1$, and the three pairs
$$
C_0\cup C_1,\qquad C_0\cup C_2,\qquad C_1\cup C_2
$$
with cohort mass $1/2$ each. Every piece has value $2/5$, each cell has weighted coverage $1$, and total mass is $5/2$.
For the matching lower bound, suppose a correct protocol used at most two queries on the uniform valuation. Its transcript subspace $F$ has dimension at most $3$.
Partition $C$ at all endpoints of the interval generators of $F$, and retain the positive-length cells. Every output indicator is constant almost everywhere on these cells. Let $M$ be the binary incidence matrix whose columns are these indicators. Then
$$
\operatorname{rank}M\le3.
$$
Let $w$ be the vector of cell lengths. Since every output piece has length $2/5$,
$$
w^\mathsf TM=\frac25\mathbf1^\mathsf T,
\qquad
w^\mathsf T\mathbf1=1.
$$
Consider the nonempty polytope
$$
\mathcal P=\{z:Mz=\mathbf1,\ z\ge0\}.
$$
Every $z\in\mathcal P$ satisfies
$$
\frac25\sum_jz_j=w^\mathsf TMz=1,
$$
so $\sum_jz_j=5/2$. Hence $\mathcal P$ is compact.
At an extreme point, the columns corresponding to positive coordinates are linearly independent. Otherwise a nonzero dependence supported on those coordinates would permit sufficiently small perturbations in both directions, contradicting extremality. Thus its positive support has size $k\le3$.
Selecting $k$ independent rows produces an invertible binary matrix $R$ of order $k$ and a vector $a>0$ satisfying
$$
Ra=\mathbf1,\qquad \sum_i a_i=\frac52.
$$
No such matrix exists:
This contradiction proves that two queries cannot suffice. Therefore
$$
\boxed{Q_1(5/2)=3.}
$$
Proposition. Suppose $N=A/B>1$ and some type, denoted $t_0$, satisfies
$$
p_{t_0}\ge\max\{1,N-1\}.
$$
Then there is a correct deterministic protocol using at most
$$
\tau(A-1)
$$
queries.
This proposition allows arbitrarily small positive masses for all other types.
For integers $1\le B\le A$, every rational vector $z$ satisfying
$$
0\le z_i\le1,\qquad \sum_{i=0}^{A-1}z_i=B
$$
is a finite rational convex combination of indicators of $B$-element subsets of $\{0,\ldots,A-1\}$.
To prove this, if $z$ is not integral, it has at least two fractional coordinates: exactly one would contradict the integrality of its coordinate sum. Choose two fractional coordinates $i,j$ and put
$$
\delta_+=\min\{1-z_i,z_j\},
\qquad
\delta_-=\min\{z_i,1-z_j\}.
$$
Both are positive rationals. Define
$$
z^+=z+\delta_+(e_i-e_j),
\qquad
z^-=z-\delta_-(e_i-e_j).
$$
Both vectors remain feasible, each has fewer fractional coordinates, and
$$
z=
\frac{\delta_-}{\delta_++\delta_-}z^+
+
\frac{\delta_+}{\delta_++\delta_-}z^-.
$$
Recursive application terminates because the number of fractional coordinates decreases on every branch. Terminal vectors are binary and have exactly $B$ ones. All coefficients are rational. Fixed coordinate choices make the decomposition deterministic.
Let
$$
P=\sum_{t\ne t_0}p_t=N-p_{t_0}.
$$
The hypothesis implies
$$
p_{t_0}\ge1,\qquad P\le1.
$$
Type $t_0$ cuts $A$ consecutive cells of its own value $1/A$, using $A-1$ queries. For every other type, evaluate the first $A-1$ cells; normalization determines its value for the last cell. The total query count is at most $\tau(A-1)$.
For each $t\ne t_0$, choose a $B$-element set of cells $T_t$ maximizing its value, breaking ties by cell indices. Output
$$
\left(t,p_t,\bigcup_{i\in T_t}C_i\right).
$$
The coverage already supplied on cell $C_i$ is
$$
s_i=\sum_{t\ne t_0}p_t\mathbf1_{\{i\in T_t\}}.
$$
Since $P\le1$,
$$
0\le s_i\le1.
$$
Let $r_i=1-s_i$ be the remaining coverage. Then
$$
0\le r_i\le1\le p_{t_0},
$$
and
$$
\sum_i r_i
=A-BP
=BN-BP
=Bp_{t_0}.
$$
Consequently,
$$
z_i=\frac{r_i}{p_{t_0}}
$$
satisfies the rational decomposition lemma. Write
$$
z=\sum_J\theta_J\mathbf1_J,
$$
where each $J$ has size $B$, each retained coefficient is positive rational, and $\sum_J\theta_J=1$.
For each retained $J$, output
$$
\left(t_0,p_{t_0}\theta_J,\bigcup_{i\in J}C_i\right).
$$
These cohorts supply coverage $r_i$ on every cell, and their total mass is $p_{t_0}$.
Every output piece contains exactly $B$ cells. Type $t_0$ values every output piece at $B/A$. Every other type receives a maximizing $B$-cell union, so it weakly prefers its own piece to every output piece. Thus all envy inequalities hold.
All output pieces are finite unions of intervals, all cohort masses are positive rationals, and conservation holds outside the finite set of cell endpoints. The proof uses only the cell values, so it holds for every valid cut answer. $\square$
We use the following established external results.
Ordinary cake division. For every integer $n$, there is a bounded deterministic Robertson–Webb protocol producing a complete envy-free partition into finite unions of intervals. Denote a query bound by $F_{\mathrm g}(n)$. Aziz–Mackenzie establish boundedness in Theorem 4.10 and complete envy-freeness in Theorem 4.28; their model and tie handling appear in Section 2 and Section 3.1.1. [Aziz–Mackenzie](https://arxiv.org/html/1604.03655v12)
Ordinary chore division. For every integer $n$, there is a bounded deterministic Robertson–Webb protocol producing a complete partition with each agent’s own cost no greater than its cost for any other agent’s piece. Denote a query bound by $F_{\mathrm c}(n)$. This is the main result of Dehghani, Farhadi, HajiAghayi, and Yami; the oracle model is specified in Section 1.1 and the main protocol in Section 2. [Dehghani et al.](https://obj.umiacs.umd.edu/papers_for_stories/envy_free_chore_division_Hajiaghayi.pdf)
Both results allow nonnegative additive divisible valuations and disconnected pieces. Our nonatomic valuations satisfy divisibility: their cumulative values on an interval are continuous, so every intermediate target is attained. Neither result requires distinct valuations among agents. Their cut queries request an endpoint attaining a target, without requiring a canonical endpoint; fix their internal tie rules to obtain deterministic protocols under the allowed cut-answer convention.
Write
$$
N=\frac AB>1,\qquad
\mu_t=\frac{a_t}{b_t},
\qquad
D=\prod_{t=1}^{\tau}b_t.
$$
Define integers
$$
n=AD,\qquad n_t=AD\mu_t,\qquad
G=BD,\qquad H=(A-B)D.
$$
Then
$$
\sum_tn_t=n,\qquad
\frac{n_t}{G}=p_t,\qquad
\frac HG=N-1.
$$
Each virtual agent’s query is answered through its type oracle, at one query per ordinary interval query.
Assume $p_t\ge1$ for every type, equivalently $n_t\ge G$.
Run the ordinary cake protocol with $n_t$ virtual agents of type $t$. Let their partition pieces be $P_{t,i}$, indexed cyclically within each type.
Envy-freeness between identical virtual agents gives a common own-piece value $c_t$:
$$
v_t(P_{t,i})=c_t.
$$
Moreover, every virtual agent’s piece satisfies
$$
v_t(P_{u,k})\le c_t.
$$
For each $t,i$, output
$$
\left(t,\frac1G,X_{t,i}\right),
\qquad
X_{t,i}=\bigcup_{r=0}^{G-1}P_{t,i+r}.
$$
Because $n_t\ge G$, these unions contain $G$ distinct partition pieces. Each original piece occurs in exactly $G$ output unions. Therefore coverage is $1$, and type $t$ receives mass $n_t/G=p_t$.
Additivity gives
$$
v_t(X_{t,i})=Gc_t,
\qquad
v_t(X_{u,k})\le Gc_t.
$$
Thus the output is envy-free, using at most $F_{\mathrm g}(AD)$ queries.
Assume instead
$$
p_t\ge N-1
$$
for every type, equivalently $n_t\ge H$.
Run the ordinary chore protocol on the same $n$ virtual agents, using $v_t$ as type $t$’s cost measure. Let its partition pieces again be $P_{t,i}$.
Chore envy-freeness gives
$$
v_t(P_{t,i})=c_t,
\qquad
v_t(P_{u,k})\ge c_t.
$$
Define
$$
Y_{t,i}=\bigcup_{r=0}^{H-1}P_{t,i+r},
\qquad
X_{t,i}=C\setminus Y_{t,i},
$$
and output every $X_{t,i}$ with cohort mass $1/G$.
Each $Y_{t,i}$ contains $H$ distinct pieces. Hence
$$
v_t(Y_{t,i})=Hc_t,
\qquad
v_t(Y_{u,k})\ge Hc_t.
$$
Taking complements reverses the inequalities:
$$
v_t(X_{t,i})
=1-Hc_t
\ge v_t(X_{u,k}).
$$
Every original partition piece occurs in exactly $H$ of the sets $Y_{t,i}$. Consequently, outside partition endpoints,
$$
\sum_{t,i}\frac1G\mathbf1_{X_{t,i}}
=
\frac nG-\frac HG
=N-(N-1)=1.
$$
Type $t$’s total cohort mass is $n_t/G=p_t$. Complements of finite unions of intervals remain finite unions of intervals.
This proves a finite upper bound $F_{\mathrm c}(AD)$ for this class, which includes profiles where every type mass is below $1$.
Theorem. Every allowed input with $\tau\le2$ admits a finite uniform Robertson–Webb query bound.
Proof. The cases $N=1$ and $\tau=1$ were established above. Suppose $\tau=2$ and $N>1$.
Since $p_1+p_2=N$, the following cases exhaust all possibilities.
$$
p_t=N-p_{3-t}\ge N-1.
$$
Section 5.2 applies.
$$
p_{t_0}=N-p_{3-t_0}\ge N-1.
$$
Section 4 applies.
Thus, with the notation of Section 5, a valid upper bound is
$$
\boxed{
Q(N,\mu_1,\mu_2)
\le
\max\{2(A-1),F_{\mathrm g}(AD),F_{\mathrm c}(AD)\}.
}
$$
$\square$
The binary input length bounds
$$
\log A+\sum_t\log b_t=O(L),
$$
so $AD\le2^{O(L)}$. Taking a finite maximum of the ordinary protocol bounds over all integers up to this limit gives a bound depending only on $L$. Therefore the two-type conclusion is uniform over valuations and permitted oracle answers.
This establishes finiteness, not optimality. The exponential one-type lower bound still applies to the full problem.
The arguments establish finite uniform bounds in three general classes:
$$
\min_t p_t\ge1,
\qquad
\min_t p_t\ge N-1,
\qquad
\max_t p_t\ge\max\{1,N-1\}.
$$
Their union contains every profile with at most two supported types.
It does not contain all profiles with three supported types. For example, take
$$
N=\frac32,\qquad
(\mu_1,\mu_2,\mu_3)
=\left(\frac12,\frac38,\frac18\right).
$$
Then
$$
(p_1,p_2,p_3)
=\left(\frac34,\frac9{16},\frac3{16}\right).
$$
Every type mass is below $1$, the smallest is below $N-1=1/2$, and the largest is below $\max\{1,N-1\}=1$. This is merely an example outside the proved constructions; no impossibility result for it has been established.
Accordingly, the polynomial-bound question has a rigorous negative answer, but the optimal complexity over the entire input domain—and the existence of a finite uniform bound there—remain unsettled.
⟨structured verdict parsed — rendered above⟩
Overall assessment: partial, with substantial correct progress. The exponential one-type lower bound is rigorous and rules out every uniform query bound polynomial in $N,\tau,L$. The direct constructions and the reductions establish the stated sufficient conditions and finiteness for every profile with $\tau\le2$.
The output does not determine optimal complexity over the full input domain or settle whether a finite uniform bound exists for arbitrary profiles with $\tau\ge3$. It explicitly acknowledges this limitation. I found no central false mathematical step.
The conservation argument is correct.
Because the output is finite and every piece is a finite union of intervals, $H$ is constant on each open cell between consecutive output endpoints. Every such cell has positive Lebesgue measure, so almost-everywhere conservation forces its constant value to be $1$.
Thus conservation fails, if anywhere, only on a finite set. Nonatomic valuations assign that set zero value, including when the valuations are singular with respect to Lebesgue measure. Finite additivity therefore justifies
$$
\sum_j q_jv_t(X_j)=1.
$$
For one supported type, applying envy-freeness to both ordered pairs of any two cohorts forces their piece values to agree. Since the masses sum to $N$, their common value is exactly $1/N$.
The zero-query construction for $N=1$ also satisfies every requirement: each type receives its prescribed mass, all pieces are the whole cake, and their weighted coverage is $1$.
No issue.
The subspace lemma is correct.
Each successful query contributes at most one interval indicator, and normalization contributes the constant function. Hence
$$
\dim F\le Q+1.
$$
If an output indicator $f$ lies outside $F$, its projection residual $h$ is nonzero, orthogonal to every recorded interval indicator and to $1$, and bounded. Consequently, a sufficiently small positive perturbation produces a strictly positive normalized density.
Orthogonality preserves all recorded evaluation values and all cut-target equalities. Therefore the same cut endpoints remain valid. Inductively, determinism gives the same subsequent queries and output. Correctness for every valid cut answer is precisely what permits this transcript argument.
The perturbed value of $f$ changes by
$$
\varepsilon\|h\|_2^2>0,
$$
contradicting the necessary one-type value $1/N$.
The optional treatment of infeasible cuts is also valid under the stated failure-response convention.
No issue.
The calculation is correct. Integrating coverage gives
$$
\beta\sum_jr_j=1.
$$
Expansion in an orthonormal basis gives the total squared-coefficient sum $1$. Cauchy–Schwarz restricted to each indicator’s support bounds each basis coordinate’s weighted contribution by $\beta$. Therefore
$$
1\le(\dim F)\beta.
$$
The proof uses neither disjointness of the indicators nor equal weights, so it applies to the permitted overlapping outputs.
No issue.
The first application gives $\dim F\ge N$.
For $N>1$, the complement indicators belong to $F$, have common integral $(N-1)/N$, and satisfy the stated weighted conservation identity. The second application gives
$$
\dim F\ge\frac{N}{N-1}.
$$
Combining these inequalities with the integer dimension bound yields the displayed query lower bound with the correct ceiling and subtraction.
Minor issue: the sentence asserting that nontermination necessarily gives an infinite query count conflates computation with queries. An infinite computation can make only finitely many queries. This does not affect the lower bound for valid protocols.
Minimum clarification: exclude nonterminating procedures because they fail to output an allocation, or explicitly define their failure cost to be infinite.
The cyclic construction is correct.
Distinct positive cumulative targets force strictly increasing returned endpoints, regardless of flat portions of the valuation. The resulting cells each have value $1/A$. Each cyclic union contains $B$ distinct cells, and every cell occurs in exactly $B$ output pieces.
Thus the cohort mass, coverage, and common piece value are respectively
$$
\frac AB,\qquad 1,\qquad \frac BA.
$$
The construction uses exactly $A-1$ cuts. Combining it with the lower bound correctly establishes
$$
Q_1(n)=n-1
$$
and
$$
Q_1\!\left(\frac{D+1}{D}\right)=D.
$$
For positive integers $b$, the family $D=2^b$ has bounded $N$, one supported type, and input length $\Theta(b)$. Therefore its exact query complexity $2^b$ rules out a polynomial bound in $N,\tau,L$.
No substantive issue.
The three-query construction has the claimed values, coverage, and total mass.
The lower-bound argument also checks out:
In the singleton-row case for order $3$, positivity excludes rows combining the singleton coordinate with another coordinate. The remaining pair has sum $3/2$, so it cannot form a row either. The required singleton rows then force total $3$, as asserted.
Thus
$$
Q_1(5/2)=3
$$
is established.
The rational decomposition lemma is correct. Each perturbation preserves feasibility and makes at least one selected fractional coordinate integral. Recursive branching therefore terminates, and all coefficients remain rational.
The construction’s hypotheses imply
$$
P\le1,\qquad p_{t_0}\ge1.
$$
These inequalities ensure that residual coverage is nonnegative and that its normalized vector lies in the decomposition polytope. Its coordinate sum is correctly computed as $B$.
The resulting cohorts have positive rational masses and supply exactly the missing coverage. Every output piece contains $B$ cells. The dominant type values all such pieces equally, while every other type receives a maximizing $B$-cell union.
The query count is exactly the stated upper bound: $A-1$ cuts plus $(\tau-1)(A-1)$ evaluations.
No issue.
The cited results support the stated uses.
Aziz–Mackenzie’s model permits nonnegative additive divisible valuations and finite unions of intervals. The cited theorems establish bounded Robertson–Webb complexity and complete envy-freeness; the paper also supplies internal tie handling. Its cut definition asks for an endpoint attaining the target, without imposing a canonical endpoint. [Aziz–Mackenzie](https://arxiv.org/html/1604.03655v12)
The chore paper states a bounded envy-free protocol, uses normalized nonnegative additive divisible costs, and permits disconnected pieces. Its oracle definitions likewise request a target-attaining endpoint. These hypotheses match the stated use of each $v_t$ as a cost measure. [Dehghani et al.](https://obj.umiacs.umd.edu/papers_for_stories/envy_free_chore_division_Hajiaghayi.pdf)
Neither application requires distinct valuations. Nonatomic normalized valuation measures satisfy the needed interval divisibility through continuity of cumulative values.
The integrality identities are correct. Under $n_t\ge G$, each cyclic union contains $G$ distinct partition pieces.
Ordinary envy-freeness forces equal own-piece values for virtual agents of the same type and bounds every other partition piece by that common value. Additivity then gives the claimed cohort envy inequalities.
Coverage and type masses are correct.
Under $n_t\ge H$, the excluded unions contain $H$ distinct pieces. Chore envy-freeness gives the claimed lower bounds on excluded-piece values, and taking complements correctly reverses those inequalities.
Every original partition piece occurs in exactly $H$ excluded unions. Hence complement coverage is
$$
\frac nG-\frac HG=1.
$$
The type masses and finite-union output requirement are also satisfied.
No issue in either reduction.
The three cases exhaust all positive mass pairs summing to $N$, allowing harmless overlap at equality.
Each case satisfies its invoked construction’s hypotheses. Therefore the displayed maximum is a valid finite bound for every two-type profile, uniformly over valuations and permitted oracle answers.
Minor issue: the subsequent encoding estimate requires choosing $A,B,a_t,b_t$ from the input representations or in reduced form. The earlier instruction to “write” the rationals as these fractions does not explicitly impose this choice. Arbitrarily inflated representations need not satisfy the claimed estimate.
Minimum clarification: specify reduced fractions, or fractions taken directly from the binary input encoding. With that convention,
$$
AD\le2^{O(L)}
$$
and the finite-maximum argument is valid.
The example outside the three sufficient conditions is computed correctly:
$$
(p_1,p_2,p_3)=\left(\frac34,\frac9{16},\frac3{16}\right).
$$
It establishes only that those constructions do not cover every profile, exactly as the prover says.
Major scope issue: the requested optimal complexity and the unrestricted finite-bound question remain unanswered. This is incompleteness, not a refutation of the proved results.
The minimum remaining work needed to settle the full task is an argument addressing profiles outside the three sufficient conditions and determining whether they admit a finite uniform query bound. Determining optimal complexity additionally requires matching bounds beyond the exact one-type cases. No expositional clarification alone supplies those conclusions.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.