Answer: Polynomial-time solvable; an EQ1 assignment always exists.
Theorem F.2 — class: algorithmic
Given household types \(t\in T\) with rational masses \(\mu_t\) summing to \(1\), a finite set \(K\) of item kinds with rational per-capita supplies \(q_k\), and objective valuation oracles \(v_t:\mathbb{Z}_{\ge 0}^{K}\to\mathbb{Z}\), compute a finite rational family \(y_{t,b}\ge 0\). Each bundle vector \(b\) must be integral, each kind must be universally a good or universally a chore, and the assignment must satisfy \(\sum_b y_{t,b}=\mu_t\) for every \(t\) and \(\sum_{t,b}y_{t,b}b_k=q_k\) for every \(k\). For every pair of positive-mass type–bundle classes \((t,b),(u,c)\) with \(v_t(b)<v_u(c)\), require either some \(k\) with \(b_k>0\) and \(v_t(b-e_k)\ge v_u(c)\), or some \(\ell\) with \(c_\ell>0\) and \(v_t(b)\ge v_u(c-e_\ell)\).
A society is given by its support: a list \(T\) of \(\tau\) household types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
There are \(m=|K|\) item kinds with binary-rational per-capita supplies \(q_k\geq0\). Bundles are vectors \(b\in\mathbb Z_{\geq0}^{K}\), including the empty bundle, with no imposed household capacity.
Each type has an integer-valued valuation \(v_t\) with \(v_t(0)=0\). A supplied partition \(K=G\mathbin{\dot\cup}C\) satisfies, for every \(t,b\), \(v_t(b+e_k)\geq v_t(b)\) for \(k\in G\) and \(v_t(b+e_k)\leq v_t(b)\) for \(k\in C\); universally indifferent kinds may be classified either way. Values may have either sign and need not be additive.
Valuations are supplied by finitely described evaluation oracles running in polynomial time in their description length and the binary length of the queried bundle. Let \(L\) be the total binary input length, including these descriptions.
An assignment is an explicitly listed finite family of binary-rational masses \(y_{t,b}\geq0\), with binary-encoded integral bundles, satisfying \(\sum_b y_{t,b}=\mu_t\) and \(\sum_{t,b}y_{t,b}b_k=q_k\).
It is EQ1 if every pair \((t,b),(u,c)\) with positive assigned mass and \(v_t(b)<v_u(c)\), including pairs with \(t=u\), satisfies either \(v_t(b-e_k)\geq v_u(c)\) for some \(k\) with \(b_k>0\), or \(v_t(b)\geq v_u(c-e_\ell)\) for some \(\ell\) with \(c_\ell>0\).
Can an EQ1 assignment be computed, or its nonexistence decided, in time polynomial in \(m,\tau,L\), or is this computational problem NP-hard?
For finite agents and explicitly listed indivisible items, normalized objective valuations always admit an EQ1 allocation, computable using \(O(m\log n+n)\) operations with constant-time valuation queries. This result does not classify the distributional problem above; no result for that exact formulation is provided.
The problem is polynomial-time solvable under the stipulated polynomial-time oracle model. An EQ1 assignment always exists, and one can compute an assignment with at most \(\tau+m\) positive entries.
The construction below handles binary-encoded supplies directly. It uses no additivity assumption.
Choose a common denominator \(D\) for all input masses and supplies. Taking the product of their denominators suffices, so \(D\) has binary length \(O(L)\). Define
\[
N_t=D\mu_t,\qquad Q_k=Dq_k.
\]
These are nonnegative integers, with \(N_t>0\) and \(\sum_tN_t=D\).
We represent a partial assignment by entries \((t_i,b_i,n_i)\), where \(n_i\) is a positive integer and the assigned mass is \(n_i/D\). We maintain:
Initially, list \((t,0,N_t)\) for every type. This assignment is EQ1 because every listed bundle has value zero.
We process each kind once. The central construction adds all copies of one kind while introducing at most one additional entry.
An assignment is EQ1 for valuations \(v_t\) if and only if it is EQ1 for valuations \(-v_t\).
Indeed, suppose \(v_t(b)<v_u(c)\). Under negation, the corresponding strict comparison is
\[
-v_u(c)<-v_t(b).
\]
A witness \(v_t(b-e_j)\geq v_u(c)\) becomes
\[
-v_u(c)\geq -v_t(b-e_j),
\]
which removes an item from the higher-valued bundle under the negated valuations. A witness \(v_t(b)\geq v_u(c-e_j)\) becomes
\[
-v_u(c-e_j)\geq -v_t(b),
\]
which removes an item from the lower-valued bundle. Negating again proves the converse.
Consequently, when processing a chore, we can negate all valuations and treat that kind as a good.
Consider a current EQ1 list \((t_i,b_i,n_i)\), indexed by \(i\in\{1,\ldots,s\}\), with \(\sum_i n_i=D\). Let \(k\) be the next kind, and write \(Q=Q_k\).
If \(Q=0\), leave the list unchanged. Otherwise, define
\[
w_t=
\begin{cases}
v_t,&k\in G,\\
-v_t,&k\in C.
\end{cases}
\]
The current list is EQ1 for \(w_t\), and adding copies of \(k\) weakly increases every \(w_t\).
Set \(B=Q+1\), and define the integer-valued nondecreasing sequences
\[
f_i(r)=w_{t_i}(b_i+r e_k),\qquad r\in\{0,\ldots,B\}.
\]
For an integer threshold \(h\), define the capped inverse
\[
d_i(h)=
\begin{cases}
\min\{r\in\{0,\ldots,B\}:f_i(r)\geq h\},&
\text{if this set is nonempty},\\
B,&\text{otherwise}.
\end{cases}
\]
Define the total demand
\[
R(h)=\sum_{i=1}^s n_i d_i(h).
\]
Both \(d_i\) and \(R\) are nondecreasing.
Let
\[
A=\min_i f_i(0),\qquad H=1+\max_i f_i(B).
\]
Then \(R(A)=0\), whereas
\[
R(H)=DB>Q.
\]
Binary search therefore finds an integer \(\alpha\) satisfying
\[
R(\alpha)\leq Q<R(\alpha+1).
\]
Put \(a_i=d_i(\alpha)\) and \(c_i=d_i(\alpha+1)\).
We need the following two properties, valid for every integer \(r\) with \(a_i\leq r\leq c_i\):
\[
f_i(r)\geq\alpha,
\qquad
r>0\ \Longrightarrow\ f_i(r-1)\leq\alpha.
\]
For the first property, \(n_i a_i\leq R(\alpha)\leq Q\), and \(n_i\geq1\), so \(a_i<B\). Thus \(a_i\) is an actual threshold attainment, rather than an unattained capped inverse: \(f_i(a_i)\geq\alpha\). Monotonicity gives the assertion for \(r\geq a_i\).
For the second property, every index strictly below \(c_i\) has value less than \(\alpha+1\). This holds whether \(c_i\) is an actual threshold attainment or the cap used when the threshold is unattained. Since \(r-1<c_i\) and values are integers, \(f_i(r-1)\leq\alpha\).
Giving every entry \(a_i\) additional copies consumes \(R(\alpha)\) copies in the integer representation. The remaining number is
\[
E=Q-R(\alpha).
\]
Since \(Q<R(\alpha+1)\),
\[
0\leq E<\sum_i n_i(c_i-a_i).
\]
Process the entries in any fixed order. Whenever the remaining \(E\) is at least \(n_i(c_i-a_i)\), give the whole entry \(c_i\) copies and subtract that quantity.
At the first entry where the remaining \(E\) is smaller than \(n_i(c_i-a_i)\), write
\[
E=n_i d+z,\qquad
d=\left\lfloor E/n_i\right\rfloor,\qquad
0\leq z<n_i.
\]
Replace this entry by:
Give all subsequent entries their lower quantities \(a_i\).
The two replacement weights sum to \(n_i\). Their additional consumption above the lower quantity is exactly \(n_i d+z=E\). Moreover,
\[
a_i\leq a_i+d\leq a_i+d+1\leq c_i.
\]
Thus the supply is met exactly, all weights remain integral, and at most one entry splits into two. The support increases by at most one.
All previously processed supplies remain unchanged: each replacement preserves both the total weight and every coordinate other than \(k\).
Every new entry has a bundle \(x=b_i+r e_k\), with \(a_i\leq r\leq c_i\). Section 3 gives
\[
w_{t_i}(x)\geq\alpha,
\qquad
r>0\ \Longrightarrow\
w_{t_i}(x-e_k)\leq\alpha.
\]
Consider any two positive-weight new entries, with bundles \(x=b_i+r e_k\) and \(z=b_j+p e_k\), such that
\[
w_{t_i}(x)<w_{t_j}(z).
\]
Case 1: \(p>0\). Deleting one newly added copy from the higher-valued bundle suffices:
\[
w_{t_j}(z-e_k)\leq\alpha\leq w_{t_i}(x).
\]
Case 2: \(p=0\). Here \(z=b_j\). Monotonicity gives
\[
w_{t_i}(b_i)\leq w_{t_i}(x)<w_{t_j}(b_j).
\]
Apply EQ1 to the corresponding old entries.
If its witness removes an item \(h\) from \(b_i\), then
\[
w_{t_i}(b_i-e_h)\geq w_{t_j}(b_j).
\]
Adding \(r\) copies of \(k\) preserves this inequality:
\[
w_{t_i}(x-e_h)
=w_{t_i}(b_i-e_h+r e_k)
\geq w_{t_i}(b_i-e_h)
\geq w_{t_j}(z).
\]
Otherwise, the old witness removes an item \(\ell\) from \(b_j\), giving
\[
w_{t_i}(b_i)\geq w_{t_j}(b_j-e_\ell).
\]
Hence
\[
w_{t_i}(x)\geq w_{t_i}(b_i)
\geq w_{t_j}(z-e_\ell).
\]
In either case a valid deletion witness exists. This proves EQ1 for the new list under \(w_t\). Section 2 then proves EQ1 under the original valuations.
The argument applies to every pair of entries, regardless of whether their types coincide.
Starting with \(\tau\) entries and increasing the support by at most one per kind produces at most \(\tau+m\) entries. Duplicate entries can be merged.
All weights remain positive integers with sum \(D\), so their binary lengths are \(O(L)\). Crucially, no new denominators arise: every output mass remains \(n_i/D\). If “binary-rational” specifically means dyadic rational, choose \(D\) to be a power of two; the construction then preserves that restriction as well.
For a processed kind \(k\), exact feasibility gives
\[
\sum_i n_i(b_i)_k=Q_k.
\]
Since every positive \(n_i\) is at least one, every listed coordinate satisfies \((b_i)_k\leq Q_k\). During threshold searches, the queried coordinate for the current kind is at most \(Q_k+1\). Each \(Q_k\) has binary length \(O(L)\), so every queried bundle has binary length \(O(mL)\).
Under the stipulated oracle model, evaluations on these bundles take polynomial time and return integers of polynomial binary length. Consequently:
There are \(m\) stages and at most \(\tau+m\) entries at any stage. The total running time and the explicit output length are therefore polynomial in \(m,\tau,L\).
The finite-agent objective-valuation theorem, discussed in [Bilò, Loebl and Vinci, Appendix E](https://arxiv.org/html/2503.05695v2), concerns an explicit population and explicit items. The construction above avoids enumerating the potentially exponential \(D\) agents or item copies, and establishes the bound for the representation in the question.
Every valid instance admits an EQ1 assignment. The algorithm above computes one in polynomial time, with at most \(\tau+m\) positive entries. Thus nonexistence never occurs under the stated hypotheses.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated distributional problem. Its construction preserves exact feasibility and EQ1, uses at most \(\tau+m\) positive entries, and runs in polynomial time under the stipulated evaluation model. I found no major or minor issues requiring repair.
The product of the input denominators has binary length bounded by their total encoding length, so the claimed \(O(L)\) bound for \(D\) is valid. Consequently, \(N_t=D\mu_t\) and \(Q_k=Dq_k\) are integers of polynomial binary length. Positivity of the supported masses gives \(N_t>0\), and normalization gives \(\sum_tN_t=D\).
The initial entries preserve every type’s mass. Their values are all zero by normalization, so no strict comparison triggers an EQ1 requirement. Unprocessed coordinates are initially zero and remain zero until their respective stages.
Negating all valuations reverses each strict comparison and exchanges the two permitted deletion alternatives exactly as written. The relevant item remains present in the same bundle, so witness admissibility is preserved. Applying negation twice establishes the converse.
For a chore \(k\), the supplied monotonicity condition makes \(-v_t\) weakly increasing in coordinate \(k\). The argument needs monotonicity only in this currently processed coordinate; negation’s effect on other coordinates causes no problem.
Each sequence \(f_i\) is integer-valued and nondecreasing. The capped inverse \(d_i(h)\) is nondecreasing in \(h\), including when the threshold is unattained, and therefore so is \(R(h)\).
At \(A=\min_i f_i(0)\), every inverse is zero. At \(H=1+\max_i f_i(B)\), every threshold is unattained and every inverse equals \(B\). Thus \(R(A)=0\) and \(R(H)=DB>Q\), since \(D\geq1\) and \(B=Q+1\). Integer binary search consequently produces the stated adjacent thresholds.
Both interval properties are justified:
These checks cover plateaus, skipped utility values, negative thresholds, and attainment exactly at the cap.
The residual satisfies \(0\leq E<\sum_i n_i(c_i-a_i)\). Therefore the scan necessarily encounters an entry whose available increment exceeds the current residual. Entries with zero available increment can simply pass through the full-increment branch.
At the stopping entry, the division \(E=n_i d+z\), with \(0\leq z<n_i\), gives precisely the claimed residual consumption. Because \(E<n_i(c_i-a_i)\), the stated upper bound \(a_i+d+1\leq c_i\) is valid.
The first replacement weight is positive because \(z<n_i\); the second is included only when positive. Both replacements retain the old type. Their weights sum to the original weight, preserving type masses and all coordinates other than \(k\). Including the baseline and preceding increments, consumption of \(k\) is exactly \(Q\).
The case \(E=0\) is also covered: the stopping entry receives its lower quantity and introduces no positive second entry.
The proof considers an arbitrary strict comparison between positive new entries, so it includes comparisons within one type and between descendants of the same old entry.
If the higher-valued entry has \(p>0\), coordinate \(k\) is present, and deleting it is admissible. The threshold inequalities directly give the required witness.
If \(p=0\), its bundle is unchanged. Monotonicity gives the strict comparison between the corresponding old entries, allowing application of the old EQ1 invariant.
Both possible old witnesses remain valid:
No additivity or monotonicity in the witness’s coordinate is assumed. These two cases exhaust the possibilities, and the negation equivalence correctly returns the invariant to the original valuations.
There are at most \(m\) updates, each introducing at most one entry, hence at most \(\tau+m\) positive entries. Merging identical type–bundle entries preserves feasibility and EQ1.
Every weight remains an integer between \(1\) and \(D\). Every output mass therefore has polynomial encoding length. The dyadic interpretation of binary-rational inputs is also covered by the proposed power-of-two denominator.
Exact feasibility and positive integer weights imply each processed coordinate is at most \(Q_k\). Since the currently processed coordinate was previously zero, threshold queries use that coordinate only up to \(Q_k+1\). Thus all queried bundles have polynomial binary length.
Polynomial-time evaluation entails polynomial-length explicit integer outputs. Accordingly, both the utility-threshold search and each inverse search have polynomially many iterations. Demand values involve only polynomial-length integer multiplication and summation. There is no loop over the numerical values of \(D\) or \(Q_k\), so the running-time argument is polynomial rather than merely pseudopolynomial.
Zero supplies are explicitly handled. With no item kinds, the initial assignment already completes the construction. Universally indifferent kinds produce constant sequences and are covered by the capped-inverse argument. Empty bundles require no inadmissible deletion: every deletion used in the proof has an explicit positive-coordinate justification.
The cited appendix concerns finite agents and individual items, consistent with the prover’s description. It is contextual and is not used as a premise for the distributional construction. [Bilò, Loebl and Vinci, Appendix E](https://arxiv.org/html/2503.05695v2#A5)
Feedback: No additional lemma, clarification, or correction is needed to verify the claimed result under the stated input and oracle model.
⟨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.