Answer: Positive-threshold feasibility is in \(\mathrm{P}\): every valid instance with \(q>0\) is infeasible. For every encoded society and every \(N\ge 2\), \(g_N(T,\mu,f)=0\). Hence \(\liminf_{N\to\infty}g_N(T,\mu,f)=0\), and its infimum over all such societies is \(0\).
Corollary 1(b) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateBy examples (a)-(c) in Subsection 3.6: (a) PropE(Rectangle, 2, Rectangles) = 1 2, as is al- ready known from classic cake-cutting. (b) PropE(Square, 2, Squares) ≥ 1 4. Combining this with the upper bound of (Segal-Halevi, Hassidim, and Au- mann 2014), Prop(Square, 2, Squares) ≤ 1 4, gives an equality. (c) PropE(Plane, 2, Squares) = 1 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely encoded valuation types \(T\) with rational masses \(\mu_t\), and square land whose area scales with household count \(N\), compute envy-free allocations of non-overlapping whole square plots to households, maximizing the minimum type utility relative to per-capita cake value; determine the limiting guarantee as \(N\) grows.
A society is given by its support: \(T\) lists the \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a nonnegative rational piecewise-constant density \(f_t\) on a common partition of \([0,1]^2\) into \(m\) axis-parallel rectangles with rational coordinates, normalized by \(\int f_t=1\).
For an integer population scale \(N\ge2\), the land is \(C_N=[0,\sqrt N]^2\), and \(V_{t,N}(A)=\int_{A/\sqrt N}f_t(x)\,dx\). Households form the nonatomic space \(H_N=\bigsqcup_{t\in T}\{t\}\times[0,N\mu_t]\), with Lebesgue mass.
An allocation measurably assigns each household one whole axis-parallel square contained in \(C_N\), or an empty plot; unused land is permitted. Square coordinates may be real, and utility is \(V_{t,N}\) of the assigned plot.
There must be a conull subset of households on which distinct households' plots have disjoint interiors and every household weakly prefers its own plot to every other household's plot.
Define \(g_N(T,\mu,f)=\sup_Q\min_{t\in T}\operatorname*{ess\,inf}_{h\in H_{N,t}}N V_{t,N}(Q_h)\), where the supremum ranges over these envy-free allocations. Thus utility is measured relative to per-capita cake value \(1/N\).
Positive-threshold feasibility asks whether such an allocation gives almost every household relative utility at least an input binary rational \(q>0\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\), and \(\log N\).
Is positive-threshold feasibility in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
What is \(\liminf_{N\to\infty}g_N(T,\mu,f)\) for a fixed encoded society, and its infimum over all such societies?
For two finite agents, a constructive envy-free square allocation guarantees \(1/4\) of each agent's cake value, and this universal guarantee is tight ([source](https://cdn.aaai.org/ojs/9309/9309-13-12837-1-2-20201228.pdf)).
For arbitrary finite \(n\), envy-free square allocations with value greater than \(1/(4n^2)\) per agent are known ([source](https://arxiv.org/pdf/1609.03938v2)). No result for this exact nonatomic-household model was located.
For the exact nonatomic-household model stated in the question, positive-threshold feasibility is in \(\mathrm{P}\): every valid instance with \(q>0\) is infeasible. Moreover, for every encoded society and every integer \(N\ge 2\),
\[ g_N(T,\mu,f)=0. \]
Consequently, both the requested lower limit and its infimum over societies equal \(0\).
The obstruction is assigning a whole square separately to each point of a nonatomic household space. It persists for every \(N\), every support size, and every permitted density. Below I also prove the stronger structural consequence of envy-freeness.
Fix \(N\) and any admissible allocation. Let \(S\subseteq H_N\) be the conull subset on which distinct households’ plots have disjoint interiors. Define
\[ A=\{h\in S:Q_h\text{ has positive area}\}. \]
Claim. \(A\) is countable.
Proof. Enumerate the rational points of the plane as \((r_j)_{j\ge 1}\). Every positive-area square has nonempty Euclidean interior, which therefore contains a rational point. For each \(h\in A\), let \(j(h)\) be the least index satisfying \(r_{j(h)}\in\operatorname{int}(Q_h)\).
If distinct households \(h,k\in A\) had \(j(h)=j(k)\), their plots’ interiors would intersect at that rational point, contradicting the defining property of \(S\). Thus \(h\mapsto j(h)\) is an injection into the positive integers. This proves the claim.
Every singleton household has Lebesgue mass zero, so the countable set \(A\) also has household mass zero. Since \(S\) is conull, almost every household receives an empty or zero-area plot.
For each type \(t\), the valuation is absolutely continuous with respect to planar Lebesgue measure. In particular, if a plot \(Q\) has area zero, then its scaled image \(Q/\sqrt N\) also has area zero and
\[ V_{t,N}(Q)=\int_{Q/\sqrt N}f_t(x)\,dx=0. \]
Together with Section 1, this proves that, for every \(t\in T\),
\[ N V_{t,N}(Q_h)=0 \quad\text{for almost every }h\in H_{N,t}. \]
Here the exceptional set remains null within each type interval because it is contained in the union of the globally null set \(H_N\setminus S\) and the countable set \(A\).
Each type interval has positive mass \(N\mu_t>0\), and utilities are nonnegative. Hence its essential infimum is exactly zero:
\[ \operatorname*{ess\,inf}_{h\in H_{N,t}}N V_{t,N}(Q_h)=0. \]
This conclusion already follows from interior-disjointness; envy-freeness is unnecessary for it.
There is a stronger conclusion for the allocations in the question.
Claim. For every envy-free allocation and its witnessing conull set \(S\),
\[ V_{t,N}(Q_h)=0 \quad\text{for every }t\in T\text{ and every }h\in S. \]
Proof. Fix \(t\in T\). Since \(S\cap H_{N,t}\) has positive mass and \(A\) has mass zero, choose a household \(h_t\in(S\cap H_{N,t})\setminus A\). Its own utility is zero.
For every other \(h\in S\), envy-freeness gives
\[ 0=V_{t,N}(Q_{h_t})\ge V_{t,N}(Q_h). \]
Nonnegativity gives the reverse inequality. The plot of \(h_t\) itself also has value zero, proving the claim for all \(h\in S\). Since \(t\) was arbitrary, the claim follows.
Conversely, an allocation satisfying interior-disjointness on a conull set is envy-free there whenever every assigned plot on that set has zero value to every supported type: all comparisons are between zeros.
Thus, positive-area squares can occur on the witnessing conull set only if every supported type values them at zero.
A quantitative packing bound makes the threshold obstruction explicit. Let \(M\) be the largest density value among all types and partition rectangles. The finite piecewise-constant encoding implies \(M<\infty\), and normalization implies \(M>0\).
For every physical plot \(Q\),
\[ N V_{t,N}(Q)\le M\,\operatorname{area}(Q). \]
Therefore a household whose relative utility is at least \(q>0\) must receive a square of physical area at least \(q/M\).
For any finite collection of such households in \(S\), disjoint interiors imply that their square areas sum to at most the land area \(N\). Consequently, the number of these households is at most
\[ \left\lfloor\frac{NM}{q}\right\rfloor. \]
Indeed, a larger collection would contain a finite subcollection violating this area bound. Thus only finitely many households in \(S\) can meet a fixed positive threshold. They have household mass zero, whereas \(H_N\) has mass \(N>0\).
The decision algorithm therefore returns NO on every valid input. Under the stated input promises, its decision time is \(O(1)\), independent of \(m,\tau,L,\log N\). If the complete encoding must first be read, the running time is \(O(L+\log N)\), or \(O(L)\) when \(L\) already includes the encoding of \(N\). No geometric computation or enumeration of households is required.
Section 2 proves that every admissible allocation has objective value zero. Assigning the empty plot to every household is measurable, interior-disjoint, and envy-free, and achieves zero. Therefore
\[ g_N(T,\mu,f)=0 \quad\text{for every integer }N\ge 2. \]
It follows immediately that
\[ \liminf_{N\to\infty}g_N(T,\mu,f)=0, \]
and the infimum of this quantity over all encoded societies is also \(0\).
The finite-agent guarantees cited in the question concern a different household space: finitely many agents can each receive a positive-area square. They therefore do not contradict this obstruction. See the [two-agent paper](https://cdn.aaai.org/ojs/9309/9309-13-12837-1-2-20201228.pdf) and the [finite-agent paper](https://arxiv.org/pdf/1609.03938v2). Replacing the nonatomic households with finitely many households would change the mathematical problem; increasing \(N\) within the stated model does not remove the obstruction.
⟨structured verdict parsed — rendered above⟩
The prover’s output is correct and resolves both requested questions for the household model as explicitly stated. No major or minor gaps were found. The zero-utility conclusion follows from the nonatomic household space and the requirement that individual households receive squares with pairwise disjoint interiors.
Fix an admissible allocation and its witnessing conull set \(S\). Every positive-area square has a nonempty Euclidean interior containing a rational point. Selecting the first such point in a fixed enumeration is well-defined.
Distinct households in \(S\) cannot select the same point, since that would place the point in both plot interiors. Thus the stated injection into the positive integers is valid, and the set \(A\) of positive-area recipients in \(S\) is countable.
Each singleton in the finite disjoint union of Lebesgue intervals has measure zero. Consequently, \(A\) is null. Together with the null complement of \(S\), this proves that almost every household receives an empty or zero-area plot. No measurability of the rational-point selection is needed for this countability argument.
Each valuation is given by integrating a nonnegative integrable density, so it vanishes on planar null sets. Scaling a zero-area plot by \(1/\sqrt N\) preserves its zero area. Empty plots also have zero utility.
The global exceptional set is null within each type interval. Hence, for every supported type \(t\), relative utility is zero almost everywhere on \(H_{N,t}\).
The hypothesis \(\mu_t>0\) ensures that each such interval has positive measure. Therefore its essential infimum is exactly zero. This establishes the objective value of every admissible allocation without using envy-freeness.
For each type \(t\), the set \((S\cap H_{N,t})\setminus A\) has measure \(N\mu_t>0\), so the chosen household \(h_t\) exists and has zero utility.
Envy-freeness on \(S\) implies that this household values every other household’s plot in \(S\) at most zero. Nonnegativity makes those values exactly zero. Its own plot already has zero value.
The universal conclusion over all supported types and all households in \(S\) follows. The converse is also valid: if every plot in the witnessing set has zero value to every supported type, every required preference comparison is an equality.
The maximum encoded density \(M\) is finite. Normalization ensures \(M>0\). The scaling in the displayed bound is correct: the scaled plot has area \(\operatorname{area}(Q)/N\), giving
\[
N V_{t,N}(Q)\le M\operatorname{area}(Q).
\]
Thus relative utility at least \(q>0\) requires physical area at least \(q/M\).
In any finite collection of assigned squares from \(S\), intersections can occur only on boundaries, which have planar measure zero. Their areas therefore sum to at most \(N\). The resulting cardinality bound \(\lfloor NM/q\rfloor\) is correct. Any larger set would contain a finite subcollection violating that bound.
Only finitely many households in \(S\) can meet the threshold. Adding households outside \(S\) still gives a null set, so almost-everywhere positive-threshold feasibility is impossible.
Returning NO on every promised valid input is a correct constant-time decision algorithm. The alternative bound for reading the encoding is also correct; validation of the input promises is not claimed.
The all-empty allocation is measurable, satisfies disjointness and envy-freeness, and attains zero. Combined with the upper conclusion for every allocation, this proves \(g_N=0\) for every permitted \(N\), and both requested asymptotic quantities are zero.
The obstruction uses the expressly specified nonatomic household model, rather than an unintended interpretation of an omitted assumption. The finite-agent results are not used as premises, so their external verification is unnecessary for this proof.
No additional clarification or repair is required.
⟨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.