Answer: \(\mathrm{NP}\)-hard, already with \(\tau=1\), exclusivity alone, and unit norm weights and costs.
Lemma 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe complexity of the maximum norm system problem is at least NP-Hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of institutional types \(T\), rational masses \(\mu_t\) summing to \(1\), and each type’s norm net, representation function \(\rho_t\), cost function \(c_t\), and per-capita budget \(b_t\), let \(\mathcal S_t\) be its sound norm systems. Choose masses \(y_{t,\Omega}\ge 0\) with \(\sum_{\Omega\in\mathcal S_t} y_{t,\Omega}=\mu_t\) and \(\sum_{\Omega\in\mathcal S_t} y_{t,\Omega}c_t(\Omega)\le\mu_t b_t\) for each type. Maximize \(\sum_{t\in T,\Omega\in\mathcal S_t}y_{t,\Omega}\rho_t(\Omega)\), breaking ties by minimizing aggregate cost.
A society is given by its support: a list \(T\) of \(\tau\) institutional types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a nonempty norm set \(N_t\), with \(m=\max_t|N_t|\), and three explicitly listed, pairwise disjoint relations: symmetric irreflexive exclusivity \(R_{x,t}\), symmetric irreflexive substitutability \(R_{s,t}\), and acyclic, transitively reduced direct generalisation \(R_{g,t}\), directed from general to specific norms.
Let \(S_t\) connect distinct norms joined by a substitutability path, and let \(C_t(n)=\{n':(n,n')\in R_{g,t}\}\). A system \(\Omega\subseteq N_t\) is sound if it contains no exclusive pair, no pair in \(S_t\), and no pair connected by a directed generalisation path; additionally, \(C_t(n)\nsubseteq\Omega\) whenever \(C_t(n)\ne\varnothing\). The empty system is allowed. Let \(\mathcal S_t\) denote this implicitly specified family.
The input supplies binary-rational norm weights \(r_t(n)\in\mathbb Q\), costs \(c_t(n)\in\mathbb Q_{\ge0}\), and budgets \(b_t\in\mathbb Q_{\ge0}\). Require \(r_t(n')\le r_t(n)\) whenever a generalisation path leads from \(n\) to \(n'\). Define \(\rho_t(\Omega)=\sum_{n\in\Omega}r_t(n)\) and \(c_t(\Omega)=\sum_{n\in\Omega}c_t(n)\). Let \(L\) be the total binary input length; sound systems are not enumerated in the input.
Choose real masses \(y_{t,\Omega}\ge0\) satisfying \(\sum_{\Omega\in\mathcal S_t}y_{t,\Omega}=\mu_t\) and \(\sum_{\Omega\in\mathcal S_t}y_{t,\Omega}c_t(\Omega)\le\mu_tb_t\) for every type. Maximize \(\sum_{t\in T}\sum_{\Omega\in\mathcal S_t}y_{t,\Omega}\rho_t(\Omega)\), breaking ties by minimizing \(\sum_{t\in T}\sum_{\Omega\in\mathcal S_t}y_{t,\Omega}c_t(\Omega)\).
Is this exact lexicographic optimization problem solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
The discrete maximum norm system problem is \(\mathrm{NP}\)-hard, already with exclusivity alone and unit representation weights and costs; its optimization encoding uses binary variables. [Discrete hardness and encoding](https://ifaamas.org/Proceedings/aamas2018/pdfs/p1294.pdf)
No result settling this precise mass-allocation problem was located in the literature search.
The exact lexicographic optimization problem is \(\mathrm{NP}\)-hard, already when \(\tau=1\), only exclusivity is present, and all norm weights and costs equal \(1\).
The cited paper’s Lemma 1 uses independent sets to establish discrete hardness. The proof below explicitly checks that allowing fractional mass allocations preserves hardness. [Serramia et al., *Moral Values in Norm Decision Making*](https://ifaamas.org/Proceedings/aamas2018/pdfs/p1294.pdf)
We reduce from the standard \(\mathrm{NP}\)-complete Independent Set decision problem: given a finite simple undirected graph \(G=(V,E)\) and an integer \(k\), determine whether \(G\) contains an independent set of cardinality at least \(k\). Here an independent set is a vertex subset containing no edge of \(G\).
We may restrict to instances with \(n=|V|\ge 1\) and \(1\le k\le n\), since instances outside these bounds are decided immediately.
Construct a society with one type \(t\), as follows:
This satisfies every input hypothesis. Exclusivity is symmetric and irreflexive because \(G\) is simple. The three relations are pairwise disjoint. The empty generalisation relation is acyclic and transitively reduced, and the weight monotonicity requirement is vacuous. All numerical data are admissible binary rationals.
Since substitutability and generalisation are absent, \(S_t=\varnothing\) and \(C_t(v)=\varnothing\) for every norm \(v\). Consequently, a system is sound exactly when it is an independent set of \(G\).
The construction has \(m=n\), \(\tau=1\), and binary input length polynomial in the graph instance’s encoding length. It can therefore be performed in polynomial time.
Write \(\alpha(G)\) for the maximum cardinality of an independent set of \(G\), and abbreviate \(y_{t,\Omega}\) to \(y_\Omega\).
For every sound system \(\Omega\), the unit weights and costs give
\(\rho_t(\Omega)=c_t(\Omega)=|\Omega|\).
Thus any feasible allocation satisfies
\[
\text{(equivalently, in inline notation)}\qquad
\]
\(\displaystyle \sum_{\Omega\in\mathcal S_t}y_\Omega=1,\qquad
\sum_{\Omega\in\mathcal S_t}y_\Omega|\Omega|\le k.\)
Define its primary objective value by
\(\displaystyle R(y)=\sum_{\Omega\in\mathcal S_t}y_\Omega|\Omega|.\)
Every sound system has cardinality at most \(\alpha(G)\). Nonnegativity and total mass \(1\) therefore imply
\(\displaystyle R(y)\le
\sum_{\Omega\in\mathcal S_t}y_\Omega\alpha(G)
=\alpha(G).\)
The budget also gives \(R(y)\le k\). Hence
\(\displaystyle R(y)\le\min\{\alpha(G),k\}.\)
This bound is attained in both possible cases:
It follows that the exact primary optimum is
\(\displaystyle R^*=\min\{\alpha(G),k\}.\)
Moreover, the total cost equals \(R(y)\) for every allocation. All primary maximizers therefore have the same total cost \(R^*\), so the secondary minimization leaves this optimum unchanged.
The reduction establishes the equivalence
\(\displaystyle G\text{ has an independent set of size at least }k
\quad\Longleftrightarrow\quad R^*=k.\)
Thus computing the exact lexicographic optimum would decide Independent Set. An algorithm polynomial in \(m,\tau,L\) would run in polynomial time on the constructed instances and imply \(\mathrm P=\mathrm{NP}\).
Fractional allocation does not invalidate the reduction: its primary objective is an average of independent-set cardinalities, and such an average cannot exceed \(\alpha(G)\). The budget caps that average at \(k\), and the proof establishes exactly when this cap is achievable.
⟨structured verdict parsed — rendered above⟩
The prover establishes the requested \(\mathrm{NP}\)-hardness. The reduction is valid, the exact fractional optimum is correctly calculated, and the secondary objective introduces no complication. There are no mathematical gaps or false steps. The only issue is a stray formatting fragment.
The prover states the standard \(\mathrm{NP}\)-complete Independent Set decision problem precisely: given a finite simple undirected graph and an integer threshold, decide whether an independent set meets that threshold. Restricting to \(n\ge1\) and \(1\le k\le n\) is legitimate because excluded instances are immediately decidable. This restriction preserves the hardness needed for the reduction.
Every constructed datum satisfies USER_TASK:
No additional restrictions from the cited paper are imported into the target problem.
With substitutability and generalisation absent, there are no forbidden pairs arising from either relation. Every child set is empty, so the condition imposed only on nonempty child sets is vacuous. Thus soundness is exactly the absence of a graph edge within the selected vertices. The claimed correspondence with independent sets holds in both directions, including the empty set.
There are \(n\) norms and \(2|E|\) explicitly listed exclusivity pairs. The remaining data consist of unit numerical values and the binary encoding of \(k\). Consequently, the construction is polynomial in the explicitly encoded graph instance, with \(m=n\) and \(\tau=1\). It does not enumerate sound systems.
Unit weights and costs imply that both primary value and total cost equal
\(R(y)=\sum_{\Omega\in\mathcal S_t}y_\Omega|\Omega|\).
Because all masses are nonnegative and sum to \(1\), and every independent set has size at most \(\alpha(G)\), the claimed bound \(R(y)\le\alpha(G)\) follows. The budget independently gives \(R(y)\le k\). Hence \(R(y)\le\min\{\alpha(G),k\}\).
This argument correctly uses an average-cost constraint; it does not mistakenly impose a separate budget restriction on every system receiving positive mass.
Both cases are correct:
The cases exhaust all possibilities, including equality. Therefore the exact primary optimum is \(R^*=\min\{\alpha(G),k\}\). Since cost equals primary value for every allocation, all primary maximizers have identical cost. The lexicographic tie-break leaves the established value unchanged.
The equivalence between a yes-instance of Independent Set and \(R^*=k\) follows directly from the established formula. Exact computation of the lexicographic optimal value therefore decides Independent Set in polynomial time if such an optimization algorithm exists. The conditional statement that this would imply \(\mathrm P=\mathrm{NP}\) is correct.
The contextual citation is also accurate: Lemma 1 of the [cited paper](https://ifaamas.org/Proceedings/aamas2018/pdfs/p1294.pdf) uses maximum independent sets, exclusivity, and unit weights and costs. The prover’s own argument supplies the necessary justification for fractional allocations.
Minor — formatting in “Exact value of the fractional optimum.” The displayed fragment containing “(equivalently, in inline notation)” has no mathematical content and interrupts the constraint statement. Delete it. The constraints immediately following it are complete and correct; no additional mathematical clarification is needed.
⟨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.