Answer: —
Theorem 3 — class: algorithmic
Given rational type masses \(\mu\) over finitely many WWL monotone valuation types, a finite catalogue \(G\) of indivisible item classes with rational per-capita supplies \(q\), and integral bundles \(S \subseteq G\), output a finite-support rational allocation \(y_{t,S}\) satisfying \(\sum_S y_{t,S} = \mu_t\), \(\sum_{t,S:g \in S} y_{t,S} = q_g\), and, for every occupied \((t,S),(u,R)\) and every \(g \in R\), \(v_u(R \setminus \{g\}) \le v_t(S)\).
Definitions. Input: a finite catalogue \(K\) and binary-encoded rational values \(a_{t,k}\) for types \(t\in\{1,2\}\), with \(v_t(B)=\sum_{k\in B}a_{t,k}\), \(v_1(K)=v_2(K)\), and masses \(\mu_1=\mu_2=\tfrac12\). An allocation is rational \(y_{t,B}\ge0\), for \(B\subseteq K\), satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B:k\in B}y_{t,B}=\tfrac12\) for every \(k\in K\).
It is EQx if, for every occupied \((t,B)\), \((u,D)\), every \(k\in D\) with \(a_{u,k}>0\) satisfies \(v_u(D\setminus\{k\})\le v_t(B)\), and every \(k\in B\) with \(a_{t,k}<0\) satisfies \(v_t(B\setminus\{k\})\ge v_u(D)\).
Target. Is deciding whether such an EQx allocation exists solvable in polynomial time, or is it NP-hard?
Nearest known results. For integral partitions of indivisible items, deciding existence of an EQx allocation is NP-hard already for two agents with normalized additive valuations that may assign opposite signs to an item. That result concerns integral allocations, not the mass-allocation model above.
The target dichotomy is not fully resolved here. The following results are proved:
Thus the remaining issue is whether the endogenous EQx value window can be forced by a hardness construction, or exploited algorithmically.
For a type–bundle cell \( (t,B) \), define
\( \alpha_t(B)=\max\{v_t(B\setminus\{k\}):k\in B,\ a_{t,k}>0\} \),
with \( \alpha_t(B)=-\infty \) if \( B \) contains no positively valued item, and define
\( \beta_t(B)=\min\{v_t(B\setminus\{k\}):k\in B,\ a_{t,k}<0\} \),
with \( \beta_t(B)=+\infty \) if \( B \) contains no negatively valued item.
Let \( S \) be a nonempty collection of type–bundle cells. It is pairwise EQx-compatible if and only if
\( \max_{(t,B)\in S}\alpha_t(B)\le \min_{(t,B)\in S}v_t(B) \)
and
\( \max_{(t,B)\in S}v_t(B)\le \min_{(t,B)\in S}\beta_t(B) \).
Let
\( \ell=\min_{(t,B)\in S}v_t(B) \)
and
\( h=\max_{(t,B)\in S}v_t(B) \).
Suppose first that \( S \) is EQx-compatible. Fix \( (u,D)\in S \) and a positive item \( k\in D \). Applying EQx with \( (u,D) \) as the bundle from which \( k \) is removed gives
\( v_u(D\setminus\{k\})\le v_t(B) \)
for every \( (t,B)\in S \). Hence \( v_u(D\setminus\{k\})\le\ell \). Taking the appropriate maxima gives
\( \max_{(u,D)\in S}\alpha_u(D)\le\ell \).
Similarly, if \( k\in B \) is negative for type \( t \), EQx gives
\( v_t(B\setminus\{k\})\ge v_u(D) \)
for every \( (u,D)\in S \). Consequently \( v_t(B\setminus\{k\})\ge h \), and taking minima gives
\( \min_{(t,B)\in S}\beta_t(B)\ge h \).
Conversely, suppose the two displayed inequalities hold. For any \( (u,D),(t,B)\in S \) and positive \( k\in D \),
\( v_u(D\setminus\{k\})\le\alpha_u(D)\le\ell\le v_t(B) \).
For any negative \( k\in B \),
\( v_t(B\setminus\{k\})\ge\beta_t(B)\ge h\ge v_u(D) \).
These are exactly the two EQx conditions. \( \square \)
For numbers \( \ell\le h \), define the permitted configurations
\( \mathcal C_t(\ell,h)=\{B\subseteq K:\ell\le v_t(B)\le h,\ \alpha_t(B)\le\ell,\ \beta_t(B)\ge h\} \).
Lemma 1 implies that an EQx mass allocation exists if and only if there are \( \ell\le h \) and a feasible allocation supported on the cells \( (t,B) \) with \( B\in\mathcal C_t(\ell,h) \).
The mass-allocation EQx existence problem belongs to \( \mathrm{NP} \).
Suppose an EQx allocation exists, and let \( S \) be its finite support. On this fixed support, feasibility is the linear system
\( Ay=b,\qquad y\ge0 \),
where \( A \) has one row for each of the two type-mass constraints and one row for each item-supply constraint. Thus \( A \) has \( |K|+2 \) rows, all its entries belong to \( \{0,1\} \), and every entry of \( b \) equals \( 1/2 \).
Choose an extreme point of the nonempty polytope \( \{z\ge0:Az=b\} \), restricted to the columns in \( S \). An extreme point has at most
\( \operatorname{rank}(A)\le |K|+2 \)
positive coordinates. Removing the other support cells preserves EQx, because all remaining pairs were already EQx-compatible.
Every positive coordinate of this extreme point is obtained from a nonsingular square submatrix of \( A \). Cramer’s rule and Hadamard’s determinant bound show that its numerator and denominator require \( O(|K|\log |K|) \) bits.
A certificate therefore consists of at most \( |K|+2 \) cells, their bundles encoded as incidence vectors, and their rational masses. In polynomial time one can verify:
All arithmetic involves sums and comparisons of binary-encoded rationals of polynomial bit length. Hence verification is polynomial. \( \square \)
Consequently, any future \( \mathrm{NP} \)-hardness proof would establish \( \mathrm{NP} \)-completeness.
Assume temporarily that every \( a_{t,k} \) is an integer. Let
\( W=\max_{t\in\{1,2\}}\sum_{k\in K}|a_{t,k}| \).
All bundle values lie in \( [-W,W] \), so it suffices to enumerate the \( O(W^2) \) integer pairs \( \ell\le h \) in that interval.
Fix \( t,\ell,h \), and an integer \( s\in[\ell,h] \). A bundle of value \( s \) belongs to \( \mathcal C_t(\ell,h) \) precisely when:
Indeed, for a positive included item,
\( v_t(B\setminus\{k\})=s-a_{t,k}\le\ell \)
is equivalent to \( a_{t,k}\ge s-\ell \). The negative-item equivalence is analogous.
For each \( t,\ell,h,s \), construct the standard subset-sum directed acyclic graph whose states are \( (i,q) \), where \( i \) is the number of processed items and \( q\in[-W,W] \) is the current sum. There is always a skip arc. There is an include arc for item \( i+1 \) exactly when that item satisfies the eligibility condition above. Paths from \( (0,0) \) to \( (|K|,s) \) correspond bijectively to bundles in \( \mathcal C_t(\ell,h) \) having value \( s \).
Use nonnegative flow variables on these graphs. Impose:
A feasible mass allocation induces such flows. Conversely, every feasible flow decomposes into source-to-sink paths because the graphs are acyclic, and the path coefficients give a rational mass allocation supported on \( \mathcal C_t(\ell,h) \). Lemma 1 then gives EQx.
There are \( O(W) \) possible values of \( s \), and each graph has \( O(|K|W) \) states and arcs. Hence each fixed-window linear program has size polynomial in \( |K| \) and \( W \). Enumerating all windows yields:
For integer valuations, EQx mass-allocation existence is decidable in time polynomial in \( |K| \), \( W \), and the input bit length.
This is pseudopolynomial, not polynomial in the binary encoding. Rational valuations can be scaled to integers, but the resulting \( W \) can be exponentially large.
In particular, strong \( \mathrm{NP} \)-hardness on polynomially bounded integer values would contradict \( \mathrm{P}\ne\mathrm{NP} \).
Consider the auxiliary problem in which a window \( \ell=h=T \) is imposed externally and every occupied bundle must belong to \( \mathcal C_t(T,T) \).
Fixed-window mass feasibility is weakly \( \mathrm{NP} \)-complete, even for two identical types with positive integer valuations and total value \( 2T \).
Reduce from \( \mathrm{PARTITION} \). Given positive integers \( w_1,\ldots,w_n \) with total \( 2T \), set
\( a_{1,k}=a_{2,k}=w_k \).
Because all values are positive, a bundle belongs to \( \mathcal C_t(T,T) \) exactly when its value is \( T \): the removal inequalities are then automatic.
If \( S\subseteq K \) has value \( T \), so does \( K\setminus S \). Define
\( y_{1,S}=y_{1,K\setminus S}=y_{2,S}=y_{2,K\setminus S}=1/4 \).
Each type has total mass \( 1/2 \). Every item occurs once among \( S,K\setminus S \) for each type, so its total allocated mass is \( 1/2 \). Every occupied bundle has value \( T \).
Conversely, any feasible fixed-window allocation has at least one occupied bundle, and every occupied bundle has value \( T \). Such a bundle is a solution to the original \( \mathrm{PARTITION} \) instance. \( \square \)
This proposition does not prove hardness of the target problem: the target may choose another window \( [\ell,h] \).
Take the no-instance \( \{1,1,4\} \) of \( \mathrm{PARTITION} \), whose total is \( 6 \) but which has no subset of value \( 3 \). Apply the standard integral construction:
| Item | \( a_{1,k} \) | \( a_{2,k} \) |
|---|---:|---:|
| \( x_1 \) | \( 1 \) | \( -1 \) |
| \( x_2 \) | \( -1 \) | \( 1 \) |
| \( g_1 \) | \( 2 \) | \( 2 \) |
| \( g_2 \) | \( 2 \) | \( 2 \) |
| \( g_3 \) | \( 8 \) | \( 8 \) |
Both total valuations equal \( 12 \), so normalization holds.
Nevertheless, the following mass allocation is feasible:
\( y_{1,\{x_2,g_3\}}=y_{2,\{x_1,g_3\}}=1/4 \),
\( y_{1,\{x_1,g_1,g_2\}}=y_{2,\{x_2,g_1,g_2\}}=1/4 \).
Every type has mass \( 1/2 \), and every item occurs in total mass \( 1/2 \).
The first two bundles have value \( 7 \). For each, \( \alpha=-1 \) and \( \beta=8 \). The last two bundles have value \( 5 \), with \( \alpha=4 \) and \( \beta=+\infty \). Therefore the support has
\( \ell=5,\qquad h=7,\qquad \max\alpha=4\le5,\qquad \min\beta=8\ge7 \).
Lemma 1 proves that this is an EQx allocation.
Thus the reverse direction of the integral \( \mathrm{PARTITION} \) reduction fails in the mass model: fractional support can use different bundles of values \( 5 \) and \( 7 \) while satisfying all supply constraints.
The proven results isolate the unresolved point:
Accordingly, neither polynomial-time solvability nor \( \mathrm{NP} \)-hardness of the stated target problem is established by the present argument.
⟨structured verdict parsed — rendered above⟩
The prover correctly labels its output as partial. It establishes meaningful auxiliary results, but it does not answer the target dichotomy: neither a polynomial-time algorithm nor an NP-hardness proof for the original endogenous-window problem is provided.
No central assertion appears false. The NP-membership argument, the extreme-value characterization, and the counterexample to the integral reduction are sound. The pseudopolynomial algorithm is plausible but its flow formulation omits explicit terminal-flow constraints. The fixed-window NP-completeness statement also needs a small complexity-theoretic clarification.
Lemma 1 is correct.
For positive-item removals, pairwise EQx requires every removal value to be at most every occupied bundle value. This is equivalent to
\[ \max_{(t,B)\in S}\alpha_t(B)\le \min_{(t,B)\in S}v_t(B). \]
For negative-item removals, pairwise EQx requires every removal value to be at least every occupied bundle value, which is equivalent to
\[ \max_{(t,B)\in S}v_t(B)\le \min_{(t,B)\in S}\beta_t(B). \]
The conventions for cells without positive or negative items are consistent with the vacuous EQx conditions.
The subsequent permitted-configuration characterization is also valid: in the forward direction one may take \(\ell\) and \(h\) to be the minimum and maximum occupied bundle values, while the reverse direction follows directly from Lemma 1.
Proposition 2 is sound.
Restricting to the original support produces a nonempty bounded polytope: every column participates in exactly one type-mass row, so the type equations bound all variables. A basic feasible solution has no more than \(\operatorname{rank}(A)\le |K|+2\) positive entries.
The determinant estimate is sufficient. A square \(0\)-\(1\) submatrix of order at most \(|K|+2\) has determinant of bit length \(O(|K|\log |K|)\), and replacing one column by the half-integral right-hand side introduces only a constant additional denominator factor. Thus the masses admit polynomial-size rational encodings.
The proposed certificate can be verified in polynomial time. Although the verifier description only says “nonnegativity,” a valid certificate may list exactly the positive cells, so applying EQx to every listed pair causes no correctness problem.
The bundle eligibility equivalences are correct. For a bundle of value \(s\),
\[ v_t(B\setminus\{k\})\le\ell \]
for an included positive item is equivalent to \(a_{t,k}\ge s-\ell\), and the negative-item condition is equivalently \(-a_{t,k}\ge h-s\). Zero-valued items require no EQx removal condition and may be included without restriction.
All partial subset sums remain within \([-W,W]\), including with mixed signs, because \(W\) bounds the total absolute value. Since occupied bundle values are integers, enumerating integer endpoint values is sufficient: any existing allocation supplies a window whose endpoints are occupied bundle values.
There is, however, an omission in the flow formulation. Merely imposing flow conservation and total source flow does not state that flow in the graph indexed by \(s\) must terminate at \((|K|,s)\). The final layer contains states corresponding to other sums. Unless the graph has silently been restricted to source-to-\((|K|,s)\) paths, flow could terminate at another final state, and the resulting path would not represent a permitted bundle of value \(s\). The text also says “flow conservation in every graph” without distinguishing source and sink vertices.
This is a minor formulation gap because the intended single-sink subset-sum construction is evident and requires no new mathematical idea, but the LP is not fully specified as written. The prover must explicitly state the graph restriction or terminal-flow constraints before the converse flow-decomposition claim is verifiable.
The complexity estimate is otherwise adequate. There are polynomially many states and arcs in \(|K|\) and \(W\), polynomially many values of \(s\), and polynomially many windows. This yields a pseudopolynomial, not binary-polynomial, algorithm.
The conditional observation about strong NP-hardness on polynomially bounded integer instances is correct under the standard assumption \(\mathrm{P}\ne\mathrm{NP}\).
The reduction itself is correct for even-total \(\mathrm{PARTITION}\) instances. With positive valuations and \(\ell=h=T\), membership in \(\mathcal C_t(T,T)\) is exactly the condition \(v_t(B)=T\); all positive-removal inequalities are then automatic.
The proposed allocation from a partition satisfies both type-mass equations and every item-supply equation. Conversely, positive total type mass ensures at least one occupied bundle, and such a bundle directly gives a subset of value \(T\).
Two small justifications are omitted:
These are routine complexity clarifications rather than substantive mathematical defects.
The example is correct.
The instance \(\{1,1,4\}\) has total \(6\) and no subset of value \(3\). Both constructed type valuations sum to \(12\).
The four masses satisfy the type constraints. Each item appears in exactly two occupied cells of mass \(1/4\), so every supply is \(1/2\).
For the first two cells, the bundle value is \(7\), with \(\alpha=-1\) and \(\beta=8\). For the last two cells, the value is \(5\), with \(\alpha=4\) and \(\beta=+\infty\). Hence
\[ \max\alpha=4\le5=\ell \quad\text{and}\quad h=7\le8=\min\beta. \]
Lemma 1 therefore applies. This genuinely refutes the reverse implication of the stated integral-style construction in the mass model.
The original target remains unresolved. NP membership, pseudopolynomial solvability, fixed-window weak NP-completeness, and failure of one natural reduction do not imply either polynomial-time solvability or NP-hardness of the actual problem.
The minimum additional work needed to resolve the assignment is exactly one of the two missing central results identified by the prover: a valid hardness reduction for the endogenous-window problem, or a polynomial-time algorithm for it. Clarifying the two minor proof gaps above would make the auxiliary results rigorous but would not settle the target.
⟨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.