Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe determination of an assignment x maximizing Sv(u(x)) is NP-hard, even if |L| = 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many agent types \(i\) with masses \(\mu_i\), item types \(j\) with per-capita supplies \(q_j\) summing to \(1\), ordinal utilities \(u_{ij}\in L\), and a succinct coordinatewise monotone capacity ν on mass vectors, find a feasible mass plan \(x_{ij}\ge 0\) satisfying \(\sum_j x_{ij}=\mu_i\) and \(\sum_i x_{ij}=q_j\) that maximizes \(\max_{\lambda\in L}\min\{\lambda,\nu(r^\lambda)\}\), where \(r_i^\lambda=\sum_{j:u_{ij}\succeq\lambda}x_{ij}\). Each individual receives one indivisible item; atomlessness allows a type cohort to be partitioned to realize its mass flows. What is the complexity of this optimization problem as a function of the type counts, |L|, rational bit lengths, and capacity-circuit size?
A society is given by its support: the list of \(\tau\) agent types with positive binary-rational masses \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\) item types with positive binary-rational supplies \(q_j\) satisfying \(\sum_jq_j=1\), and utilities \(u_{ij}\in\mathcal L\), where \(\mathcal L\) is an explicitly ordered finite ordinal scale with distinct endpoints \(\bot\) and \(\top\); ties are allowed.
A capacity is a map \(\nu:\prod_i[0,\mu_i]\to\mathcal L\), promised coordinatewise nondecreasing, with \(\nu(0)=\bot\) and \(\nu(\mu)=\top\). It is supplied by a Boolean circuit whose input predicates are rational affine comparisons \(a\cdot r\ge b\), with signed binary-rational coefficients, and whose output encodes a scale element. Let \(C\) be its size and \(L\) the total input bit length.
A feasible mass plan has real entries \(x_{ij}\ge0\), row sums \(\sum_jx_{ij}=\mu_i\), and column sums \(\sum_ix_{ij}=q_j\). Each individual receives one indivisible item; atomless type cohorts may be partitioned to realize these flows.
Define \(r_i^\lambda=\sum_{j:u_{ij}\succeq\lambda}x_{ij}\) and \(F(x)=\max_{\lambda\in\mathcal L}\min\{\lambda,\nu(r^\lambda)\}\), with minimum and maximum taken in the ordinal order.
Is finding a feasible mass plan maximizing \(F(x)\) solvable in polynomial time in \(m,\tau,|\mathcal L|,L,C\), or is it NP-hard?
Discrete one-to-one assignment maximizing the Sugeno integral is NP-hard even with two utility levels and polynomial-time capacity evaluation; capacities depending only on coalition cardinality admit polynomial-time optimization. [Drissi Oudghiri et al. (2016)](https://doi.org/10.3233/978-1-61499-672-9-1406)
No result settling this exact atomless problem with the specified capacity representation was identified in the literature search.
Finding an optimal feasible mass plan is \(\mathrm{NP}\)-hard. This holds even with only two utility levels, distinct utility vectors for all supported agent types, and a capacity computed by a monotone Boolean formula whose input predicates test whether individual coordinates equal their maximum masses.
We prove this by a polynomial reduction from satisfiability of formulas in conjunctive normal form with at most three literals per clause, a standard \(\mathrm{NP}\)-complete problem. See [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Let \(\varphi\) be such a formula on \(n\ge 1\) variables, with nonempty clauses. Choose a power of two \(N\) satisfying \(n\le N<2n\), and pad the variable list with unused variables. Put \(a=1/(4N)\).
Use the scale \(\mathcal L=\{\bot,\top\}\), ordered by \(\bot\prec\top\).
There are \(2N+1\) supported agent types:
Their masses sum to \(1/2+2Na=1\).
There are \(2N+2\) item types:
Their supplies sum to \(1/4+1/4+2Na=1\). All masses and supplies are positive dyadic rationals.
Specify utilities as follows:
The literal types have distinct utility vectors because their private items differ. The auxiliary type is distinct from every literal type because it assigns utility \(\bot\) to \(G\).
For \(r\) in the capacity’s domain, define Boolean predicates
\[ H(r)=[r_h\ge 1/2], \qquad Y_{i,s}(r)=[r_{i,s}\ge a]. \]
Here brackets denote the truth value of the enclosed comparison. Because the domain bounds are \(r_h\le 1/2\) and \(r_{i,s}\le a\), these predicates test whether the corresponding coordinate has reached its full mass.
Associate each literal \(\ell\) with a predicate \(Y_\ell\): the literal \(z_i\) uses \(Y_{i,+}\), and \(\neg z_i\) uses \(Y_{i,-}\).
Define the Boolean formula
\[ A(r)= H(r) \wedge \bigwedge_{i=1}^{N}\bigl(Y_{i,+}(r)\vee Y_{i,-}(r)\bigr) \wedge \bigwedge_{D\in\varphi}\left(\bigvee_{\ell\in D}Y_\ell(r)\right). \]
Set \(\nu(r)=\top\) when \(A(r)\) is true, and \(\nu(r)=\bot\) otherwise.
This capacity satisfies every representation promise:
The capacity uses only full-mass thresholds and monotone Boolean gates.
For the two-element scale, the term indexed by \(\bot\) in the Sugeno objective is always \(\bot\), whereas the term indexed by \(\top\) is \(\nu(r^\top)\). Consequently,
\[ F(x)=\nu(r^\top). \]
Thus achieving objective \(\top\) is equivalent to making \(A(r^\top)\) true.
Write \(r=r^\top\). Every type assigns utility \(\bot\) to \(B\). Using nonnegativity and the column-sum constraints gives
\[ \sum_t r_t = \sum_{j\ne B}\sum_{t:u_{tj}=\top}x_{tj} \le \sum_{j\ne B}\sum_t x_{tj} = \sum_{j\ne B}q_j = \frac34. \]
The index \(t\) ranges over all supported agent types. This bound holds for every feasible real mass plan.
Suppose a feasible plan satisfies \(F(x)=\top\). Then \(A(r)\) is true.
The auxiliary predicate forces \(r_h=1/2\). For each variable \(i\), at least one of \(r_{i,+}\) and \(r_{i,-}\) equals \(a\). Therefore,
\[ \sum_t r_t = r_h+\sum_{i=1}^{N}(r_{i,+}+r_{i,-}) \ge \frac12+Na = \frac34. \]
Together with the supply bound, this implies equality. More explicitly, each number \(r_{i,+}+r_{i,-}-a\) is nonnegative, and their sum is zero. Hence, for every \(i\),
\[ r_{i,+}+r_{i,-}=a. \]
At least one coordinate in this pair equals \(a\), so the other must equal zero. Thus exactly one of \(Y_{i,+}(r)\) and \(Y_{i,-}(r)\) is true.
Define a Boolean assignment by setting \(z_i\) true precisely when \(Y_{i,+}(r)\) is true. Under this assignment, \(Y_\ell(r)\) is true precisely when the literal \(\ell\) is satisfied. Every clause disjunction in \(A(r)\) is true, so this assignment satisfies \(\varphi\).
This argument allows arbitrary real entries in the plan: no integrality assumption was used.
Conversely, suppose \(\varphi\) is satisfiable. Extend a satisfying assignment arbitrarily to the padded variables. For each \(i\), let \(s_i\) denote its satisfied literal sign.
Construct a plan by the following allocations, setting all other entries to zero:
The auxiliary row receives \(2Na=1/2\), and each literal row receives \(a\). The columns for \(G\) and \(B\) each receive \(Na=1/4\), and every private column receives \(a\). Hence the plan is feasible.
Its top-utility masses are \(r_h=1/2\), \(r_{i,s_i}=a\), and zero for the opposite literal types. The auxiliary predicate, all variable-pair predicates, and all clause predicates are therefore true. Thus \(F(x)=\top\).
These rational flows can be realized by partitioning the atomless cohorts, exactly as allowed in the question.
The construction has support size \(\tau=2N+1\), item count \(m=2N+2\), and scale size \(|\mathcal L|=2\). Its utility table, capacity circuit, and numerical encodings all have size polynomial in the formula’s input length. In particular, the dyadic numbers require only logarithmically many bits in \(N\).
We have proved the equivalence
\[ \varphi\text{ is satisfiable} \quad\Longleftrightarrow\quad \max_{x\text{ feasible}}F(x)=\top. \]
An exact polynomial-time optimizer would therefore decide this satisfiability problem by evaluating the returned plan’s objective. Hence finding an optimal mass plan is \(\mathrm{NP}\)-hard, and a polynomial-time algorithm for all specified inputs would imply \(\mathrm{P}=\mathrm{NP}\).
Divisibility does not eliminate the hardness: the capacity’s full-mass thresholds and the tight supply bound force exactly one full literal cohort per variable.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes \(\mathrm{NP}\)-hardness for the exact atomless problem with the specified capacity representation. I found no mathematical gaps or false steps requiring repair.
The invoked theorem is that satisfiability of CNF formulas with at most three literals per clause is \(\mathrm{NP}\)-complete. This is the standard source problem; its formulation is also stated in these [university lecture notes](https://www.cs.sjsu.edu/~pollett/255.1.19s/Lec20190417.html).
Restricting to nonempty clauses and at least one variable does not compromise the hardness statement. No additional restriction on literal occurrences, signs, or distinctness is assumed or needed.
The choice \(n\le N<2n\) with \(N\) a power of two is valid for every \(n\ge1\). Consequently, \(a=1/(4N)\) is positive and dyadic.
The mass and supply calculations are correct:
\(1/2+2Na=1\) and \(1/4+1/4+2Na=1\).
Every supported type and item has strictly positive mass or supply.
The distinctness claim is also correct. Different literal types differ on their private-item utility coordinates. The auxiliary type differs from every literal type on \(G\). Thus the construction respects the task’s interpretation of \(\tau\) as support size, even if types are identified by their utility vectors.
Each predicate is a permitted affine comparison with rational coefficients. On the stated domain, \(H\) tests full auxiliary mass and \(Y_{i,s}\) tests full literal mass.
These predicates are coordinatewise nondecreasing, and their conjunctions and disjunctions preserve that property. The Boolean output therefore defines an ordinally nondecreasing capacity on the entire required domain.
Both endpoint conditions hold. At zero, \(H\) is false. At \(\mu\), every predicate is true, including every nonempty clause disjunction.
There is no hidden use of a negation gate: a negative SAT literal is represented by the separate coordinate predicate \(Y_{i,-}\). Hence the stronger claim about a monotone Boolean formula is justified.
With two scale elements, the term indexed by \(\bot\) is \(\bot\), and the term indexed by \(\top\) is \(\nu(r^\top)\). Thus \(F(x)=\nu(r^\top)\) is exact.
The supply inequality is valid for every feasible real plan. Since no type values \(B\) at \(\top\), every contribution to a top-utility mass comes from another column. Nonnegativity permits replacing each column’s top-valued allocations by its total allocations. The column constraints then yield
\(\sum_t r_t\le1-q_B=3/4\).
The calculation neither assumes integrality nor counts any allocation twice.
If \(F(x)=\top\), the capacity formula forces \(r_h=1/2\) and at least one full literal coordinate in each variable pair. Therefore,
\(\sum_t r_t\ge1/2+Na=3/4\).
Combining this with the supply bound forces equality. Each pair’s excess \(r_{i,+}+r_{i,-}-a\) is nonnegative, and the total excess is zero, so every pair sum equals \(a\).
Because at least one coordinate in each pair equals \(a>0\), the opposite coordinate must equal zero. Exactly one literal predicate per variable is true. The assignment defined in the output therefore makes a literal true exactly when its corresponding predicate is true. Each capacity clause disjunction consequently certifies satisfaction of the corresponding SAT clause.
This proves the claimed implication for arbitrary real plans; fractional allocations do not create an exception.
The proposed allocations satisfy every row and column constraint. In particular, the auxiliary type receives all private supplies, totaling \(2Na=1/2\), while the selected and opposite literal types consume \(Na=1/4\) from \(G\) and \(B\), respectively.
The resulting top-utility masses are exactly those asserted. A satisfying assignment makes every clause predicate true, and the auxiliary and variable-pair predicates are also true. Hence the constructed plan achieves \(\top\).
Realization by cohort partitions is explicitly permitted by the task, so no additional indivisibility argument is required.
Since \(N<2n\), both support size and item count are linear in the number of source variables. The explicitly represented utility table has quadratic size. The capacity formula has size polynomial in the source formula length, and its rational thresholds have logarithmic bit length in \(N\). Thus every relevant input parameter remains polynomially bounded.
The established equivalence between satisfiability and achievable objective \(\top\) proves hardness of the associated threshold decision problem. An exact polynomial-time optimizer would decide that problem by evaluating its returned plan with the supplied comparisons and circuit. The optimization hardness conclusion therefore follows.
The output appropriately claims hardness, without claiming membership in \(\mathrm{NP}\) or \(\mathrm{NP}\)-completeness. No additional clarification is necessary to verify the reduction.
⟨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.