Answer: \(\mathrm{NP}\text{-hard}\), even for one additive type with unit mass and supply \(\tfrac12\) for every species.
Theorem 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor two agents with general assignment valuations, it is NP-hard to compute a leximin or MNW allocation. ACM Transactions on Economics and Computation, Vol. 37, No. 4, Article 111. Publication date: August 2021.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of complete weighted-OXS valuation types, rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), item species \(O\), and rational per-capita supplies \(b_o\), choose \(x_{t,S}\ge0\) for integral bundles \(S\subseteq O\) satisfying \(\sum_Sx_{t,S}=\mu_t\) and \(\sum_{t,S:o\in S}x_{t,S}\le b_o\). First maximize \(p=\sum_{t,S:v_t(S)>0}x_{t,S}\); among allocations attaining \(p\), compute one maximizing \(\sum_{t,S:v_t(S)>0}x_{t,S}\log v_t(S)\).
A weighted-OXS valuation is \(v_t(S)\), the maximum weight of a matching between the items in \(S\) and a finite member set \(M_t\), with nonnegative rational edge weights.
Given types \(T\) of masses \(\mu_t\), species \(O\) with supplies \(b_o\), choose \(x_{t,S}\ge0\) for \(S\subseteq O\), subject to \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:o\in S}x_{t,S}\le b_o\). Lexicographically maximize \(p=\sum_{t,S:v_t(S)>0}x_{t,S}\), then \(H=\sum_{t,S:v_t(S)>0}x_{t,S}\log v_t(S)\).
Target. Is computing such a lexicographic optimum polynomial-time solvable, or NP-hard?
Nearest known results. For two discrete agents with general assignment valuations, computing a leximin allocation or the positive-utility-refined MNW allocation is NP-hard.
No result for the mass-allocation problem above is assumed here.
Result. Computing an exact lexicographic optimum is \(\mathrm{NP}\)-hard, even with one type, an additive valuation, unit mass, and supply \(\tfrac12\) for every species.
Reduction. We reduce from PARTITION: given positive integers \(a_1,\ldots,a_n\), decide whether some subset sums to half their total. This problem is \(\mathrm{NP}\)-complete; restricting to \(n\ge2\) removes only trivial instances.
Write \(A=\sum_{i=1}^n a_i\). Construct one type of mass \(\mu=1\), species set \(O=\{1,\ldots,n\}\), supplies \(b_i=\tfrac12\), and valuation
\(v(S)=\sum_{i\in S}w_i,\qquad w_i=\frac{2a_i}{A}.\)
This is a weighted-OXS valuation: introduce members \(m_1,\ldots,m_n\), give edge \((i,m_i)\) weight \(w_i\), and give all other edges weight zero. The diagonal edges for items in \(S\) form a matching of weight \(v(S)\), and no matching can obtain more.
The construction has polynomial encoding length. All weights are positive rational numbers, and \(\sum_i w_i=2\). In particular, \(v(S)>0\) exactly when \(S\ne\varnothing\).
First objective. Suppress the type index and write \(x_S\) for the allocation variables. Since their total mass is one,
\(p=\sum_{S\ne\varnothing}x_S=1-x_{\varnothing}\le1.\)
Assigning mass \(\tfrac12\) to each of \(\{1\}\) and \(O\setminus\{1\}\) is feasible: both bundles are nonempty, and every item is consumed with mass exactly \(\tfrac12\). Thus \(p^\star=1\).
Consequently, the second-stage optimization is over feasible allocations satisfying \(x_{\varnothing}=0\).
Upper bound and equality condition. Fix any such allocation. Its average valuation satisfies
\(\displaystyle \sum_{S\ne\varnothing}x_Sv(S) =\sum_{i=1}^n w_i\sum_{S:i\in S}x_S \le\frac12\sum_{i=1}^n w_i =1. \)
For every positive real \(z\),
\(\log z\le z-1,\)
with equality exactly when \(z=1\). Indeed, the derivative of \(z-1-\log z\) is \(1-1/z\), so this function has its unique minimum, zero, at one.
Because the nonempty bundles have total mass one, it follows that
\(\displaystyle H=\sum_{S\ne\varnothing}x_S\log v(S) \le\sum_{S\ne\varnothing}x_S\bigl(v(S)-1\bigr) \le0. \)
Moreover, if \(H=0\), both inequalities must be equalities. The first inequality has slack
\(\displaystyle \sum_{S\ne\varnothing}x_S\bigl(v(S)-1-\log v(S)\bigr). \)
Every summand is nonnegative. Thus zero slack forces \(v(S)=1\) for every bundle with \(x_S>0\).
Equivalence with PARTITION. Suppose the PARTITION instance is a yes-instance, witnessed by \(R\subseteq O\) with \(\sum_{i\in R}a_i=A/2\). Then
\(v(R)=v(O\setminus R)=1.\)
Assigning mass \(\tfrac12\) to each of these complementary bundles is feasible and attains \((p,H)=(1,0)\). The established upper bounds show that this is lexicographically optimal.
Conversely, suppose a feasible allocation attains \((p,H)=(1,0)\). There is at least one bundle \(S\) with positive mass. The equality condition gives
\(\displaystyle 1=v(S)=\frac{2}{A}\sum_{i\in S}a_i, \)
so \(S\) witnesses a yes-instance of PARTITION.
An optimum exists: the feasible region has finitely many coordinates and is compact; its nonempty face defined by \(p=1\) is compact; and \(H\) is linear in those coordinates with finite coefficients. Therefore,
\(\text{PARTITION is yes}\quad\Longleftrightarrow\quad(p^\star,H^\star)=(1,0).\)
Computational conclusion. Deciding whether the optimal second-stage value is zero is therefore \(\mathrm{NP}\)-hard. The threshold is the rational number zero, so the reduction does not require encoding a transcendental threshold.
Computing an optimal allocation in the usual explicit support representation also decides PARTITION without evaluating logarithms: select any positive-mass bundle in the returned optimum and check whether its integer weights sum to \(A/2\). In a yes-instance every supported bundle passes this check; in a no-instance no bundle can pass.
Hence exact computation of the requested lexicographic optimum is \(\mathrm{NP}\)-hard already in the stated additive special case. This reduction does not assert strong hardness.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the target: exact computation is \(\mathrm{NP}\)-hard, already for the stated additive special case. No major or minor mathematical gaps were found. The allocation-recovery argument explicitly uses the usual representation listing supported bundles and their masses.
The stated version of PARTITION uses positive integers encoded in binary. Restricting to \(n\ge 2\) preserves its hardness because the excluded instances are trivial.
Since \(A>0\), every weight \(w_i=2a_i/A\) is well-defined and positive. Its numerator and denominator have polynomial bit length in the source input. There are polynomially many species, members, and edges, even if the zero-weight edges are explicitly listed. The construction therefore has polynomial encoding length.
The proposed matching representation realizes the additive valuation exactly. Each item has only one positive-weight incident edge, and those edges have distinct member endpoints. All diagonal edges corresponding to a bundle can consequently be used simultaneously. No matching can receive more than their total weight.
Thus the construction belongs to the required valuation class. Positivity of every \(w_i\) also establishes that precisely the nonempty bundles have positive valuation.
The identity \(p=1-x_{\varnothing}\le 1\) follows directly from unit total mass.
The proposed allocation to \(\{1\}\) and its complement is valid because \(n\ge 2\), so both bundles are nonempty. Each species belongs to exactly one of them and is consumed with mass \(1/2\). This proves feasibility and attainment of \(p^\star=1\).
Therefore imposing \(x_{\varnothing}=0\) correctly describes the second-stage feasible region.
The exchange of summations is valid because both index sets are finite. Applying each supply constraint with its positive coefficient \(w_i\) gives
\[
\sum_{S\ne\varnothing}x_Sv(S)\le \frac12\sum_iw_i=1.
\]
The normalization and constants are correct.
The inequality \(\log z\le z-1\), with equality precisely at \(z=1\), is correctly justified for positive \(z\). Every bundle appearing in the second-stage objective has positive valuation, so the inequality applies throughout.
Since nonempty bundles have total mass one, the two displayed inequalities correctly imply \(H\le 0\).
If \(H=0\), the intermediate quantity must also equal zero. The first inequality’s slack is a finite sum of nonnegative terms. Consequently, every term corresponding to positive mass has zero logarithmic slack, forcing \(v(S)=1\). This conclusion applies to every supported bundle, as needed later.
For a yes-instance, a half-total subset and its complement both have valuation one. Both are nonempty because the integer weights are positive and \(A>0\). Assigning mass \(1/2\) to each satisfies every supply constraint and attains \((p,H)=(1,0)\).
Conversely, an allocation attaining that pair has at least one positive-mass bundle because its total mass is one. The established equality condition makes that bundle’s integer weight sum exactly \(A/2\).
Both directions are valid, including instances with odd \(A\).
The feasible region is closed and bounded in a finite-dimensional space. The second-stage region is nonempty by the earlier construction and remains compact. The objective has finite, fixed coefficients and is continuous.
Hence its maximum is attained. This justifies passing from the attainment equivalence to the claimed equivalence concerning the optimal value; a no-instance cannot merely approach zero without attaining it.
The reduction establishes hardness of deciding whether the second-stage optimum equals zero, using a rational threshold.
More directly, the explicit-support recovery procedure correctly decides PARTITION from an optimal allocation. In a yes-instance every supported bundle passes the integer sum test; in a no-instance no bundle can pass. This avoids any need to evaluate or compare logarithms computationally.
The conclusion is appropriately limited to exact computation. The proof does not claim strong hardness or approximation hardness.
No repair or additional clarification is needed for the stated conclusion and explicit-support interpretation.
⟨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.