Answer: —
Corollary 6.9 — class: algorithmic
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a base rectangular estate \(L\), one integrable density \(f_t\) per type, and a fixed separation distance \(s\), consider each integer scale \(q\ge2\) for which \(q\mu_t\) is integral. Scale the estate to \(L_q=\sqrt q\,L\), extend each density by \(f_{t,q}(x,y)=f_t(x/\sqrt q,y/\sqrt q)\), and set \(m_q=\lceil h^{-1}(17\cdot2^{q-3})\rceil\), where \(h(m)=m/\log_2(2m)\). Can one compute \(q\mu_t\) axis-parallel rectangles for each type \(t\), all pairwise \(s\)-separated, such that each type-\(t\) household receives value at least \(\mathrm{MMS}^{m_q,s}_{t,q}-\varepsilon\), where \(\mathrm{MMS}^{m_q,s}_{t,q}\) is that type’s \(1\)-out-of-\(m_q\) maximin share on \(L_q\)?
A society is specified by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts listed types, not possible types.
The input includes a positive-area axis-parallel rectangle \(L\) with rational endpoints, a rational separation distance \(s\ge0\), and nonnegative densities \(f_t\), specified by rational constant values on a common partition of \(L\) into \(m\) rational rectangles. Density integrals are not normalized; let \(B\) denote the total binary input length.
An instance specifies an integer \(q\ge2\) with \(q\mu_t\in\mathbb Z\) for every type, and rational \(0<\varepsilon<1\). Set \(L_q=\sqrt q\,L\), \(f_{t,q}(x,y)=f_t(x/\sqrt q,y/\sqrt q)\), and \(v_{t,q}(R)=\int_R f_{t,q}\).
Usable plots are axis-parallel rectangles contained in \(L_q\), with the empty plot permitted and assigned value zero. Nonempty plots have positive area; their interiors are disjoint and their pairwise \(\ell_\infty\) distances are at least \(s\). Empty plots impose no separation constraint, and land may remain unallocated.
Define \(\mathrm{MMS}^{k,s}_{t,q}=\sup_{(R_1,\ldots,R_k)}\min_j v_{t,q}(R_j)\), over feasible lists of \(k\) plots under these same conventions. Put \(h(u)=u/\log_2(2u)\) for \(u\ge2\), and \(m_q=\lceil h^{-1}(17\cdot2^{q-3})\rceil\).
The allocation problem asks for \(q\mu_t\) plots for each type \(t\), jointly feasible, each worth at least \(\mathrm{MMS}^{m_q,s}_{t,q}-\varepsilon\) to that type; rectangle coordinates use standard binary real-algebraic encodings.
Can this additive ordinal guarantee be computed uniformly in time polynomial in \(m,\tau,B,q,\log(1/\varepsilon)\), or is computing such an allocation NP-hard?
For a finite list of a fixed number \(n\ge2\) of agents, the same guarantee with \(m_n\) is computable in time polynomial in \(\log(1/\varepsilon)\) in the rectangle Cut/Eval query model ([source](https://arxiv.org/html/2105.06669v3)).
No classification for the specified support encoding, variable scale, and binary density representation was located.
The full classification remains unresolved. I prove two additional uniform polynomial-time results:
$$ 17\cdot 2^{q-3}\ge 4(3q-2)^2m^2. $$
The first result narrows the unresolved range: every instance outside its sufficient condition satisfies
$$
q<32\quad\text{or}\quad q<4\log_2 m.
$$
I also give an explicit bit-length justification for the zero-separation algorithm discussed in the notes.
Write
$$
L=[a,b]\times[c,d],\qquad z=\sqrt q,\qquad \sigma=\frac{s}{z}.
$$
For a rectangle $R\subseteq L$, define
$$
\widetilde v_t(R)=q\int_R f_t.
$$
The change of variables $(x,y)=z(u,v)$ gives
$$
v_{t,q}(zR)=\widetilde v_t(R).
$$
Scaling multiplies distances by $z$. Thus the original problem is equivalent to allocating rectangles in $L$, with separation $\sigma$ and valuations $\widetilde v_t$.
Let
$$
N_t=q\mu_t.
$$
Each $N_t$ is a positive integer, and
$$
\sum_{t=1}^{\tau}N_t=q.
$$
Consequently, $\tau\le q$, and expanding type $t$ into $N_t$ recipients takes polynomial time in the requested parameters.
Put
$$
A_q=17\cdot2^{q-3}.
$$
The function
$$
h(u)=\frac{u}{\log_2(2u)}
$$
is strictly increasing on $[2,\infty)$, since
$$
h'(u)=
\frac{\ln 2\,(\ln(2u)-1)}{(\ln(2u))^2}>0.
$$
Also, $h(u)\le u$, so
$$
m_q=\left\lceil h^{-1}(A_q)\right\rceil\ge A_q.
$$
We will only need this lower bound, rather than an algorithm for computing $m_q$.
We also have $m_q\ge q$. Indeed, $A_2=17/2\ge2$, and $A_{q+1}=2A_q$ shows inductively that $A_q\ge q$.
Finally, the benchmarks are nonincreasing in their ordinal parameter: deleting rectangles preserves feasibility, including the empty-plot convention. Therefore,
$$
\mathrm{MMS}^{m_q,s}_{t,q}\le \mathrm{MMS}^{q,s}_{t,q}.
$$
For this section, work directly in the scaled land $L_q$, with separation $s$.
For a nonempty rectangle $P$, its $\ell_\infty$ diameter is the maximum of its two side lengths.
Lemma 1. Suppose there are $p\le q$ recipients. Recipient $i$ has a pool of
$$
r=3q-2
$$
rectangles. For each pool there is a number $d_i>0$ and a choice of coordinate axis such that:
One can select one rectangle from each pool so that the selected rectangles are jointly feasible.
Proof. Process recipients in nondecreasing order of $d_i$. For each recipient, select any candidate that is compatible with all previously selected rectangles, then delete incompatible candidates from the remaining pools.
We show that a selection deletes at most three candidates from any remaining pool.
Let $P$ be the selected rectangle, and consider a remaining pool with parameter $d$. By the processing order, the diameter of $P$ is at most $d$. Its projection onto this pool’s arrangement axis is therefore an interval $[u,v]$ with
$$
v-u\le d.
$$
The candidates’ projections are
$$
[a+j(d+s),\,a+j(d+s)+d],
\qquad j=0,\ldots,r-1.
$$
If $s>0$, incompatibility implies that these projected intervals have distance less than $s$. Hence the corresponding starting coordinate lies in
$$
(u-d-s,\,v+s).
$$
This interval has length at most
$$
(v-u)+d+2s\le2(d+s).
$$
Four distinct candidate starts span at least $3(d+s)$, so this interval contains at most three candidate starts.
If $s=0$, incompatibility means overlapping interiors. It implies overlapping interiors of the projections, so the candidate start lies in
$$
(u-d,\,v),
$$
whose length is at most $2d$. Again, at most three candidate starts can occur.
Before recipient number $j+1$ is processed, at most $3j$ candidates have been deleted from its pool. Since $j\le p-1\le q-1$, at least
$$
r-3j\ge(3q-2)-3(q-1)=1
$$
candidate remains. The procedure therefore succeeds. $\square$
This lemma is algorithmic: constructing the pools and testing pairwise compatibility requires polynomially many coordinate comparisons.
Let $C\subseteq L_q$ be a scaled partition cell. Denote its longer and shorter side lengths by $D$ and $E$, respectively.
Fix $r=3q-2$. Call $C$ eligible if
$$
D\ge2(r-1)s.
$$
For an eligible cell, define
$$
\ell=\frac{D-(r-1)s}{r},
\qquad
u=\min\{E,\ell\}.
$$
Place $r$ rectangles of side lengths $\ell$ and $u$ inside $C$, arranged along its longer side with gaps $s$. All rectangles use the same transverse interval.
They fit because
$$
r\ell+(r-1)s=D.
$$
Their $\ell_\infty$ diameter is $\ell$, so they satisfy Lemma 1.
The eligibility condition implies
$$
\ell\ge\frac{D}{2r}.
$$
Since $E\le D$, it also implies
$$
u=\min\{E,\ell\}\ge\frac{E}{2r}.
$$
Consequently, every candidate has area at least
$$
\ell u\ge\frac{DE}{4r^2}.
$$
If type $t$ has constant density $c_{t,C}$ on $C$, write
$$
V_t(C)=c_{t,C}DE
$$
for its value of the cell. Every candidate in this pool has value
$$
\beta_t(C)=c_{t,C}\ell u
\ge\frac{V_t(C)}{4r^2}.
$$
For each type, define
$$
\beta_t=\max_{C\text{ eligible}}\beta_t(C),
$$
taking $\beta_t=0$ if no eligible cell exists.
The algorithm assigns empty plots to recipients with $\beta_t=0$. Every other recipient receives a copy of the pool from a maximizing cell. Lemma 1 selects jointly feasible plots, each worth exactly $\beta_t$ to its recipient.
It remains to relate $\beta_t$ to the MMS benchmark.
Lemma 2. For every type $t$ and integer $k$ satisfying
$$
k\ge4r^2m^2,
$$
we have
$$
\beta_t\ge\mathrm{MMS}^{k,s}_{t,q}.
$$
Proof. Consider any feasible list of $k$ plots with minimum value $\alpha>0$ to type $t$. Every plot is then nonempty.
The $m$ cells partition the land up to boundaries of measure zero. For each plot $R_j$, at least one cell contributes at least $\alpha/m$ to its value:
$$
v_{t,q}(R_j\cap C)\ge\frac{\alpha}{m}.
$$
Choose one such cell for each $R_j$. By the pigeonhole principle, some cell $C$ is chosen by at least
$$
n\ge\frac{k}{m}
$$
plots.
Their intersections with $C$ are positive-area rectangles and remain jointly feasible, because taking subsets preserves separation and disjoint interiors.
We first show that $C$ is eligible. Suppose instead that
$$
D<2(r-1)s.
$$
This implies $s>0$. Both side lengths of $C$ are then less than $2(r-1)s$.
In each direction, use $2(r-1)$ half-open intervals of length $s$, beginning at the cell’s lower endpoint. Their Cartesian products cover $C$ and form
$$
4(r-1)^2
$$
bins. Two rectangle centers in one bin have $\ell_\infty$ distance strictly less than $s$. Centers belong to their rectangles, so centers of different feasible rectangles must have distance at least $s$. Thus each bin contains at most one center, yielding
$$
n\le4(r-1)^2.
$$
But
$$
n\ge\frac{k}{m}\ge4r^2m>4(r-1)^2,
$$
a contradiction. Hence $C$ is eligible.
The selected intersections have disjoint interiors. Since each contributes at least $\alpha/m$, nonnegativity gives
$$
V_t(C)\ge n\frac{\alpha}{m}
\ge\frac{k\alpha}{m^2}.
$$
The pool construction therefore gives
$$
\beta_t\ge\beta_t(C)
\ge\frac{V_t(C)}{4r^2}
\ge\frac{k\alpha}{4r^2m^2}
\ge\alpha.
$$
This holds for the minimum value of every feasible list with positive minimum. Lists with minimum zero cause no difficulty because $\beta_t\ge0$. Taking the supremum proves the claim. $\square$
No attainment assumption is needed in this argument.
Theorem 3. If
$$
17\cdot2^{q-3}\ge4(3q-2)^2m^2,
$$
the allocation problem has a uniform polynomial-time algorithm that gives every recipient of type $t$ value at least
$$
\mathrm{MMS}^{m_q,s}_{t,q},
$$
without additive loss.
Proof. The condition and Section 1 imply
$$
m_q\ge A_q\ge4r^2m^2.
$$
Lemma 2 gives $\beta_t\ge\mathrm{MMS}^{m_q,s}_{t,q}$. The allocation constructed in Section 3 therefore satisfies the asserted guarantee.
For the computational bound, scaled cell endpoints, side lengths, $\ell$, and $u$ belong to $\mathbb Q(\sqrt q)$. Their formulas use only a bounded number of arithmetic operations per cell, together with multiplication by integers bounded by $O(q)$. Candidate values also belong to this field and have polynomial encoding length.
There are at most $q$ active recipients, each with $O(q)$ candidates. Choosing maximizing cells and applying Lemma 1 uses polynomially many arithmetic operations and exact comparisons in $\mathbb Q(\sqrt q)$.
Arithmetic and order comparisons in this quadratic field have polynomial bit complexity. For example, the sign of $a+b\sqrt q$ is determined by sign checks and, when its two terms have opposite signs, a rational comparison of their squared magnitudes. The resulting coordinates have standard real-algebraic encodings of degree at most two and polynomial total length. $\square$
If the sufficient condition fails, then
$$
2^q<\frac{32}{17}(3q-2)^2m^2
<\frac{32}{17}(3q)^2m^2.
$$
Taking logarithms gives
$$
q<2\log_2m+2\log_2(3q)+\log_2(32/17).
$$
For $q\ge32$,
$$
2\log_2(3q)+\log_2(32/17)<\frac q2.
$$
To verify this, at $q=32$ the left side is less than $15$, whereas $q/2=16$. The difference between the right and left sides is increasing thereafter, since its derivative is
$$
\frac12-\frac{2}{q\ln2}>0.
$$
Thus failure of the sufficient condition, with $q\ge32$, implies
$$
q<4\log_2m.
$$
Accordingly, the cell-pool algorithm handles every instance except possibly those with
$$
q<32\quad\text{or}\quad q<4\log_2m.
$$
This restriction does not itself settle the complexity of the remaining instances.
Theorem 4. Suppose one side of $L_q$ has length at most $s$. Then the requested additive guarantee is computable uniformly in time polynomial in
$$
m,\tau,B,q,\log(1/\varepsilon).
$$
Proof. Rotate the coordinate roles if necessary so that the height of $L_q$ is at most $s$.
For two positive-area rectangles inside $L_q$, their vertical projections cannot have distance at least $s$: their positive lengths imply that the distance between them is strictly less than the land’s height, which is at most $s$.
For axis-parallel rectangles, the $\ell_\infty$ distance is the maximum of the distances between their two coordinate projections. Hence every feasible pair must have horizontal projection distance at least $s$.
It follows that every feasible positive-value list can be ordered horizontally. Extending each rectangle to the full land height preserves separation and can only increase its value. Conversely, separated full-height strips are permitted plots. Therefore, for every $k$, the two-dimensional MMS equals the corresponding one-dimensional separated-interval MMS.
Work now on the unscaled land. Its height is at most $\sigma$. Define the rational piecewise constant marginal
$$
g_t(x)=q\int_c^d f_t(x,y)\,dy
$$
and its cumulative value
$$
G_t(x)=\int_a^x g_t(u)\,du.
$$
The value of a full-height strip $[x,x']\times[c,d]$ is
$$
G_t(x')-G_t(x).
$$
Fix a positive rational threshold $\alpha$.
Starting at $x_0=a$, find the smallest endpoint $e_1$ satisfying
$$
G_t(e_1)-G_t(x_0)=\alpha.
$$
If it does not exist, declare failure. Otherwise, begin the next interval at
$$
x_1=e_1+\sigma,
$$
and repeat until $q$ intervals have been obtained or the procedure fails.
This greedy procedure succeeds exactly when $q$ separated intervals of value at least $\alpha$ exist.
To prove the nontrivial direction, suppose a feasible ordered list is
$$
[\ell_1,r_1],\ldots,[\ell_q,r_q].
$$
The greedy first interval begins no later than $\ell_1$. Nonnegativity implies
$$
G_t(r_1)-G_t(a)\ge\alpha,
$$
so its earliest endpoint satisfies $e_1\le r_1$. Therefore,
$$
e_1+\sigma\le r_1+\sigma\le\ell_2.
$$
Inductively, if the greedy interval $j$ begins no later than $\ell_j$, its endpoint is at most $r_j$, and the next greedy interval begins no later than $\ell_{j+1}$. All $q$ greedy intervals therefore exist.
Each successful interval has positive length, because its value is positive.
Let $M_t$ denote the one-dimensional $q$-piece MMS and let
$$
V_t=G_t(b).
$$
We have $0\le M_t\le V_t$.
Binary search on $[0,V_t]$, using the exact feasibility procedure, produces a rational feasible lower bound $\alpha_t$ such that
$$
M_t-\frac{\varepsilon}{2}\le\alpha_t\le M_t.
$$
The lower endpoint starts at zero, where empty intervals certify feasibility. Stop when the search interval has length at most $\varepsilon/2$.
The search uses
$$
O\!\left(1+\log^+\frac{V_t}{\varepsilon}\right)
$$
decisions. Since $V_t$ has polynomial binary encoding length, this number is polynomial in the required input parameters.
Recipients with $\alpha_t=0$ receive empty plots. Suppose $p\le q$ recipients remain.
Maintain a right-hand remaining interval and the following invariant: if $r$ recipients remain, every one of them has a feasible list of $r$ intervals inside it, each worth at least her threshold.
Initially, every active recipient has a feasible list of $q$ intervals, and deleting intervals establishes the invariant for $r=p$.
Each recipient marks the earliest endpoint of a prefix worth her threshold. Choose the leftmost mark $e$, allocate that prefix to its marker, and, if further recipients remain, retain the interval starting at $e+\sigma$.
For another recipient, let
$$
[\ell_1,r_1],\ldots,[\ell_r,r_r]
$$
be an invariant witness. Her earliest mark is at most $r_1$, and the chosen mark is no later. Consequently,
$$
e+\sigma\le r_1+\sigma\le\ell_2.
$$
Her last $r-1$ witness intervals remain available. This proves the invariant after the allocation.
The procedure produces separated full-height strips, each worth $\alpha_t$ to its recipient. Since the narrow-land geometry gives
$$
M_t=\mathrm{MMS}^{q,s}_{t,q},
$$
Section 1 yields
$$
\alpha_t
\ge\mathrm{MMS}^{q,s}_{t,q}-\frac{\varepsilon}{2}
\ge\mathrm{MMS}^{m_q,s}_{t,q}-\varepsilon.
$$
The polynomial bit-complexity justification follows in Section 6. $\square$
This section justifies the implementation in Theorem 4 and repairs the bit-growth issue identified in the notes.
All vertical partition endpoints are rational. Between consecutive endpoints, $g_t$ is constant and $G_t$ is affine:
$$
G_t(x)=a_jx+b_j.
$$
There are $O(m)$ such pieces. Their rational coefficients are obtained from sums and products of input rationals, so all coefficients have bit length bounded by a polynomial in $B+\log q$.
Suppose a greedy interval begins at $x$, lying in a piece with coefficients $a_i,b_i$. If its target endpoint $e$ lies in a positive-slope piece with coefficients $a_j,b_j$, then
$$
a_je+b_j=a_ix+b_i+\alpha,
$$
and hence
$$
e=\frac{a_i}{a_j}x+
\frac{b_i-b_j+\alpha}{a_j}.
$$
The next starting coordinate is
$$
e+\sigma.
$$
Thus each cut coordinate is obtained from one preceding coordinate by an affine operation with rational coefficients, followed by addition of the fixed quadratic number $\sigma$. The formula never multiplies two evolving coordinates.
For an explicit bound, let $P$ bound the numerator and denominator lengths of all rational coefficients appearing in these affine operations, including the current threshold $\alpha$. Represent an evolving coordinate as
$$
x=\frac{U+V\sqrt q}{D},
$$
with integers $U,V,D$ and $D>0$.
Multiplication by a rational of bit length at most $P$ increases these integer lengths by $O(P)$. Addition of a rational or a rational multiple of $\sqrt q$ of bit length at most $P$ does the same. A bounded number of these operations therefore increases the representation length by $O(P)$ per cut.
After at most $q$ cuts, the length is
$$
O(L_0+qP),
$$
where $L_0$ is the initial coordinate length. Both $L_0$ and $P$ are polynomial in
$$
B,q,\log(1/\varepsilon).
$$
Finding the relevant affine piece requires only scanning the breakpoints and performing exact comparisons in $\mathbb Q(\sqrt q)$. Binary search thresholds have polynomial bit length, and each feasibility test starts afresh. Hence the complete threshold searches and allocation procedure have uniform polynomial bit complexity.
For completeness, the same affine bound proves the implementation claim for $s=0$.
Let $V_i$ be recipient $i$’s value for the entire scaled land, and set
$$
\gamma_i=\frac{V_i}{q}.
$$
Give recipients with $V_i=0$ empty plots. With $r$ active recipients, maintain
$$
v_i(\text{remaining full-height strip})\ge r\gamma_i.
$$
Initially this holds because $r\le q$.
Each active recipient marks a prefix worth exactly $\gamma_i$. Allocate the leftmost marked prefix. Every other recipient loses at most her own $\gamma_i$, so the invariant continues with $r-1$ recipients.
These positive-value prefixes have positive area and disjoint interiors. The total-value bound gives
$$
\mathrm{MMS}^{m_q,0}_{t,q}\le\frac{V_t}{m_q}
\le\frac{V_t}{q}.
$$
Thus the algorithm satisfies the guarantee exactly. Its successive cuts have the affine form analyzed above, establishing polynomial bit complexity.
The new cell-pool argument handles arbitrary densities whenever $q$ is sufficiently large relative to the logarithm of the partition size. The narrow-land argument handles arbitrary densities when one scaled land dimension is at most $s$.
The remaining general case has positive separation, both land dimensions greater than $s$, and may be restricted to
$$
q<32\quad\text{or}\quad q<4\log_2m.
$$
Neither a uniform polynomial-time algorithm nor an NP-hardness reduction for that remaining allocation search problem is established here. The fixed-agent query result cited in the question does not settle this range, because a logarithmically growing number of recipients is still variable. Its relevant algorithmic bounds assume a fixed benchmark-piece count. [Elkind–Segal-Halevi–Suksompong, Section 6](https://arxiv.org/html/2105.06669v3#S6)
A hardness proof must constrain the task of finding any valid guaranteed allocation; hardness of computing an MMS benchmark alone would not establish that claim.
⟨structured verdict parsed — rendered above⟩
Assessment: partial, with sound substantive progress. The output establishes uniform polynomial-time algorithms for the stated large-$q$ regime, the narrow-land regime, and zero separation. It does not settle the general complexity classification requested in USER_TASK, and explicitly acknowledges this limitation. I found no false central mathematical step.
The remaining implementation clarifications are minor. They do not undermine the special-case results.
1. Scaling, support expansion, and benchmark comparisons
The change of variables is correct:
$$
v_{t,q}(\sqrt q\,R)=q\int_R f_t=\widetilde v_t(R).
$$
Distances scale by $\sqrt q$, so separation becomes $\sigma=s/\sqrt q$. Positive area, disjoint interiors, containment, and the empty-plot convention are preserved.
The support expansion is valid. Positivity and integrality give $N_t=q\mu_t\ge1$, and the masses summing to one gives
$$
\sum_tN_t=q.
$$
Thus $\tau\le q$, and explicitly representing all recipients is polynomial in the requested parameter $q$.
The derivative of $h$ is correct and positive throughout its specified domain. Its range contains every $A_q=17\cdot2^{q-3}$ under consideration. The bounds
$$
m_q\ge A_q\ge q
$$
are valid, including the base case $q=2$.
Deleting plots proves the claimed monotonicity of MMS. Empty plots ensure that feasibility remains meaningful even when no positive minimum is possible. No computation of $m_q$ is needed by the supplied algorithms.
2. Lemma 1: geometric selection
The processing order correctly ensures that the selected rectangle has diameter at most the remaining pool’s parameter $d$.
For $s>0$, incompatibility requires projection distance less than $s$, placing candidate starts in the stated open interval of length at most $2(d+s)$. Four starts would span at least $3(d+s)$, so the asserted upper bound of three deletions is valid.
For $s=0$, overlapping rectangle interiors implies overlapping projection interiors along the arrangement axis. The corresponding interval for starts has length at most $2d$, again supporting the conservative bound of three.
The final count is correct:
$$
(3q-2)-3(q-1)=1.
$$
It applies to every $p\le q$, including repeated pools assigned to recipients of the same type. Ties in processing order cause no difficulty.
Compatibility testing requires only coordinate comparisons. The lemma is both mathematically valid and algorithmic as claimed.
3. Cell-pool construction
For a positive-area eligible cell, the construction fits exactly because
$$
r\ell+(r-1)s=D.
$$
Eligibility implies the stated lower bounds on $\ell$ and $u$, hence the area and value bounds:
$$
\ell u\ge\frac{DE}{4r^2},
\qquad
\beta_t(C)\ge\frac{V_t(C)}{4r^2}.
$$
The candidates have diameter $\ell$ and satisfy Lemma 1.
Choosing a maximizing cell for each positive $\beta_t$ is valid. All candidates in that pool have the same value to the relevant recipient. Assigning empty plots when $\beta_t=0$ respects the task’s conventions.
Minor issue — zero-area partition cells. The task does not explicitly require every partition cell to have positive area. If degenerate cells are permitted, an eligible cell can have $E=0$, producing candidates that are not permitted nonempty plots. Such cells have zero value and cannot supply a positive maximizing pool, so this does not invalidate the allocation result.
Minimum clarification: explicitly restrict pool construction to positive-area cells, or state that the input partition contains only positive-area cells.
4. Lemma 2: comparison with MMS
Every step of the comparison is valid:
The packing argument for an ineligible cell is correct. The strict inequalities on its side lengths ensure that the half-open bins cover the entire cell. Two centers in one bin have distance strictly less than $s$, contradicting feasibility. The resulting contradiction uses the valid inequality
$$
n\ge4r^2m>4(r-1)^2.
$$
Summing the values of the disjoint intersections gives
$$
V_t(C)\ge\frac{k\alpha}{m^2},
$$
and the pool bound then yields $\beta_t\ge\alpha$.
Passing to the supremum is justified without assuming attainment. Lists with minimum zero are correctly covered separately. Lemma 2 stands.
5. Theorem 3 and the unresolved-range estimate
The sufficient condition implies the hypothesis of Lemma 2, so the exact ordinal guarantee follows.
The computational claims also hold. The quantities used belong to $\mathbb Q(\sqrt q)$; candidate values remain in this field because it is closed under multiplication. Their expressions have polynomial encoding length. There are polynomially many candidates and comparisons, and exact sign determination in this fixed-degree extension has polynomial bit complexity. The resulting coordinates admit the required real-algebraic encodings.
The sufficient condition itself can be tested within the claimed bound: the binary length of $2^q$ is linear in the allowed parameter $q$.
The algebra leading to
$$
q<32\quad\text{or}\quad q<4\log_2m
$$
is correct. At $q=32$, the logarithmic expression is approximately $14.08$, below $16$, and the stated derivative is positive thereafter.
This is a valid restriction on the uncovered instances. It is not a classification of them.
6. Theorem 4: narrow land
The geometric reduction is correct, including equality between the land height and $s$. Positive-length vertical projections have distance strictly less than the land height. Therefore, feasible positive-area rectangles must be separated horizontally. Extending them to full height preserves horizontal separation and cannot decrease value.
The equality of the two-dimensional and one-dimensional benchmarks is valid. Benchmarks equal to zero are consistent with the permitted empty plots.
For positive thresholds, the greedy feasibility proof is correct. Nonnegative density ensures that starting earlier cannot delay the earliest endpoint beyond a feasible witness endpoint. The induction preserves sufficient separation.
Binary search also handles nonattainment correctly: any threshold strictly below the supremum is feasible, and infeasible thresholds provide upper bounds. The initially feasible zero threshold is certified by empty plots. The decision count is polynomial because the total value has polynomial binary length.
The allocation invariant for different recipient thresholds is valid. The leftmost chosen mark is no later than each other recipient’s first witness endpoint, so their remaining witness intervals survive. Finally, benchmark monotonicity gives the required additive guarantee.
Minor issue — greedy searches leaving the land. A successful cut can produce a next starting coordinate $e+\sigma>b$. The write-up does not explicitly specify what happens then, although $G_t$ is defined only on $[a,b]$.
Minimum clarification: specify the endpoint search domain and the failure convention when a required next interval starts outside the land. This is a routine implementation clarification, not a gap in the greedy argument.
7. Successive-cut bit complexity
The affine formula is correct whenever the target endpoint uses a positive-slope piece:
$$
e=\frac{a_i}{a_j}x+\frac{b_i-b_j+\alpha}{a_j}.
$$
Only one evolving coordinate appears. Thus the claimed additive growth in numerator and denominator lengths is justified, rather than an uncontrolled recurrence involving products of evolving coordinates.
The rational coefficients, thresholds, and fixed quadratic separation have polynomial encoding length. Binary-search feasibility tests restart from the original endpoint, and the allocation performs at most $q$ successive cuts. The claimed uniform polynomial bit bound follows.
Minor issue — flat pieces and breakpoint endpoints. Marginal densities may vanish on intervals, and earliest target endpoints may be breakpoints. The implementation discussion conditions its formula on a positive slope without explicitly stating how these cases are represented.
Minimum clarification: state the breakpoint convention and explain how endpoint searches handle zero-slope pieces without dividing by zero. This requires only routine exposition.
8. Zero separation
The proportional-prefix invariant is correct. Every remaining recipient loses at most her own marked value when the leftmost prefix is allocated. Positive thresholds give positive-area strips, and their interiors are disjoint.
The total-value comparison
$$
\mathrm{MMS}^{m_q,0}_{t,q}\le\frac{V_t}{m_q}\le\frac{V_t}{q}
$$
is valid. Zero-valued recipients correctly receive empty plots. The preceding affine analysis supplies the claimed bit-complexity bound, subject to the minor endpoint clarification above.
9. Citation and scope
The citation supports the claimed distinction: Corollary 6.9 fixes the number of agents, while Theorem 6.3 fixes the guillotine-piece count and gives a running-time exponent depending on that count. These statements do not supply the requested uniform polynomial bound for variable $q$. [Source, Section 6](https://arxiv.org/html/2105.06669v3#S6)
No unverified external theorem is essential to the new special-case proofs.
Major unresolved requirement — full classification. Neither a uniform polynomial-time algorithm for all permitted inputs nor an NP-hardness reduction for the allocation search problem is established. The output accurately acknowledges this. Its special-case results constitute genuine progress, but they do not resolve USER_TASK.
Minimum additional work: settle the explicitly identified remaining regime. Hardness of benchmark computation alone would not suffice; the target concerns finding any allocation satisfying the guarantee.
⟨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.