Answer: \(\mathrm{NP}\)-complete, even with one resource, unit goal requirements, identical integer per-person endowments, and exactly two acceptable goals per type.
Theorem 3.8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateChecking whether C is a Successful Coali- tion ( sc) is para −NP–hard when parameterizing by |R|.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite goal and resource sets \(G\) and \(R\), a finite support \(T\) with masses \(\mu_t>0\) summing to one, acceptable-goal sets \(A_t\subseteq G\), per-person endowments \(e_t\in\mathbb{Q}_{\ge0}^{R}\), and per-capita goal requirements \(q(g,r)\in\mathbb{Q}_{\ge0}\), decide whether there is a set \(H\subseteq G\) such that \(H\cap A_t\ne\varnothing\) for every \(t\in T\) and \(\sum_{g\in H}q(g,r)\le\sum_{t\in T}\mu_t e_t(r)\) for every \(r\in R\).
Given finite goal and resource sets \(G,R\), write \(m=|G|\) and \(d=|R|\). A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has an explicitly listed acceptable-goal set \(A_t\subseteq G\) and per-person endowment \(e_t\in\mathbb{Q}_{\ge0}^{R}\). Goal requirements \(q(g,r)\in\mathbb{Q}_{\ge0}\) are per unit of total population mass. All numerical inputs are binary rationals; let \(L\) be the total input bit length.
The entire society is the coalition under consideration. Goals are achieved as indivisible shared outcomes: achieving any one goal in \(A_t\) satisfies every person of type \(t\), with indifference among acceptable goals. Empty acceptable-goal sets and zero endowments or requirements are allowed.
Call the society successful if there exists a nonempty set \(H\subseteq G\) with \(H\cap A_t\ne\varnothing\) for every \(t\in T\), and \(\sum_{g\in H}q(g,r)\le\sum_{t\in T}\mu_t e_t(r)\) for every \(r\in R\).
Is deciding whether this society is successful solvable in time polynomial in \(m,\tau,d,L\), or is it \(\mathrm{NP}\)-hard?
For finite agents with nonnegative integer endowments and requirements, successful-coalition decision is \(\mathrm{NP}\)-hard even with one resource and the grand coalition specified ([Shrot–Aumann–Kraus](https://u.cs.biu.ac.il/~krauss/data/articles/shortetal-aamas09.pdf)). It is also \(\mathrm{W}[1]\)-hard parameterized by coalition size ([Chitnis–Hajiaghayi–Liaghat](https://arxiv.org/pdf/1105.0707)).
No result settling this exact normalized mass formulation was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even with one resource, unit goal requirements, identical integer per-person endowments, and exactly two acceptable goals per type. Thus a polynomial-time algorithm in \(m,\tau,d,L\) exists if and only if \(\mathrm{P}=\mathrm{NP}\).
A certificate is the incidence vector of a set \(H\subseteq G\), using \(m\) bits. The verifier checks that \(H\) is nonempty, intersects every explicitly listed \(A_t\), and satisfies every resource inequality.
These inequalities can be checked exactly in polynomial time. Each product \(\mu_t e_t(r)\) has numerator and denominator bit lengths at most \(2L\). Each relevant sum contains at most \(m+\tau\) terms. Using the product of their denominators as a common denominator gives intermediate integers with bit lengths polynomial in \(m,\tau,L\). Integer arithmetic and comparison therefore take polynomial time; there are \(d\) inequalities.
Hence the problem belongs to \(\mathrm{NP}\).
We use the standard \(\mathrm{NP}\)-complete Vertex Cover problem: given a finite simple graph \(F=(V,E)\) and a nonnegative integer \(k\), decide whether some \(C\subseteq V\) satisfies \(|C|\le k\) and intersects every edge. This is Karp’s “Node Cover” problem. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We may restrict to \(E\ne\varnothing\): an edgeless instance is always a yes-instance and can be replaced by a fixed yes-instance consisting of one edge with budget one.
Write \(E=\{f_1,\ldots,f_s\}\), where \(s\ge1\). Construct the society as follows:
Assign positive dyadic masses by
\(\displaystyle \mu_{t_i}=2^{-i}\quad(1\le i<s),\qquad \mu_{t_s}=2^{-(s-1)}.\)
Their sum is exactly one, because
\(\displaystyle \sum_{i=1}^{s-1}2^{-i}+2^{-(s-1)}=1.\)
For \(s=1\), the first sum is empty and the sole mass is one. Thus the construction is valid even if “binary rational” is interpreted as requiring a finite binary expansion.
The graph is simple, so distinct edges give distinct acceptable-goal sets. Consequently these are genuinely \(s\) distinct support types, and \(\tau=s\).
We have \(m=|V|\), \(\tau=|E|\), and \(d=1\). Each acceptable-goal set has two entries. Every endowment uses \(O(\log(k+1))\) bits. Each mass uses \(O(s)\) bits, so all masses together use \(O(s^2)\) bits. The construction therefore has polynomial output length and is computable in polynomial time.
The society’s total available resource is
\(\displaystyle \sum_{i=1}^{s}\mu_{t_i}e_{t_i}(r)=k\sum_{i=1}^{s}\mu_{t_i}=k.\)
For any \(H\subseteq G\), its total requirement is
\(\displaystyle \sum_{g\in H}q(g,r)=|H|.\)
Forward direction. Suppose \(C\subseteq V\) is a vertex cover with \(|C|\le k\). Set \(H=\{g_v:v\in C\}\). Every edge has an endpoint in \(C\), so \(H\) intersects every acceptable-goal set. Its requirement is \(|C|\le k\). Since the graph has an edge, every vertex cover is nonempty. Thus \(H\) witnesses success.
Reverse direction. Suppose \(H\) witnesses success. Set \(C=\{v\in V:g_v\in H\}\). Satisfaction of the type corresponding to each edge implies that \(C\) contains an endpoint of that edge. Hence \(C\) is a vertex cover. Resource feasibility gives \(|C|=|H|\le k\).
Therefore the graph has a vertex cover of size at most \(k\) if and only if the constructed society is successful. This proves \(\mathrm{NP}\)-hardness and, together with membership, \(\mathrm{NP}\)-completeness. Normalizing population mass does not remove the combinatorial difficulty of choosing indivisible shared goals.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The reduction establishes \(\mathrm{NP}\)-hardness for the exact normalized mass formulation, and the certificate argument establishes \(\mathrm{NP}\)-membership. No major or minor mathematical issues were found.
The rational arithmetic argument is sound. Multiplication adds numerator and denominator bit lengths, so the stated bound of \(2L\) is sufficient. Each inequality involves at most \(m+\tau\) rational terms. Taking their denominator product produces an integer of polynomial bit length; scaling and summing the numerators also preserves polynomial bit length. Exact comparison therefore takes polynomial time. Repeating this for \(d\) resources establishes the claimed membership.
Restricting to graphs with an edge is justified as written: every edgeless instance with nonnegative budget is a yes-instance, and replacing it by the fixed one-edge instance with budget one preserves its answer. Other instances remain unchanged. This is a polynomial transformation and ensures the subsequent construction always has \(s\ge1\).
Every assigned mass is positive. The displayed geometric-sum identity is correct, including \(s=1\), where the sole mass is one. All masses are dyadic rationals and therefore satisfy either interpretation of binary rational mentioned by the prover. Endowments \(k\) and requirements one satisfy the required nonnegativity and encoding conditions.
The claimed restricted \(\mathrm{NP}\)-completeness and the conditional statement about \(\mathrm{P}=\mathrm{NP}\) follow. No additional clarification or repair 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.