Answer: \(\mathrm{NP}\)-hard; polynomial-time solvability would imply \(\mathrm{P}=\mathrm{NP}\). A deterministic algorithm runs in \(2^{2^{O(\tau)}}L^{O(1)}\) time.
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problems GRAND-COALITION-EXIST and MAX-MIN-EXIST are NP-complete. PROOF. Membership in NP follows from guessing and check- ing.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete peer-value types \(T\), rational population masses \(\mu_t\) summing to \(1\), and rational values \(a_{ts}\), define \(u_t(q)=\sum_{s\in T}a_{ts}q_s\) and \(g_t=\max\{0,u_t(\mu)\}\). Does there exist a finite family of coalition mass vectors \(q^j\ge 0\) such that \(\sum_j q_t^j\le\mu_t\), every type \(t\) with \(q_t^j>0\) satisfies \(u_t(q^j)\ge g_t\), and any unassigned mass belongs only to types with \(g_t=0\) and is assigned to singleton agents?
A society is given by its support: a nonempty list \(T\) of \(\tau\) 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. The input includes the complete matrix \(a\in\mathbb{Q}^{T\times T}\) of directed peer values, with arbitrary signs and no symmetry requirement; \(a_{tt}\) values other agents of the same type. Agents are nonatomic, and singleton utility is zero.
Define \(u_t(q)=\sum_{s\in T}a_{ts}q_s\) and the grand-coalition fairness threshold \(g_t=\max\{0,u_t(\mu)\}\); preferences compare utilities weakly, so equality is acceptable.
A feasible structure consists of finitely many nonzero vectors \(q^1,\ldots,q^k\in\mathbb{R}_{\geq0}^{T}\), allowing \(k=0\), such that \(\sum_{j=1}^{k}q_t^j\leq\mu_t\) and \(q_t^j>0\) implies \(u_t(q^j)\geq g_t\). Types may split among coalitions. Residual mass \(\mu_t-\sum_jq_t^j\) must be zero whenever \(g_t>0\); all residual agents form individual singletons. There is no input bound on \(k\).
Is deciding whether such a feasible structure exists solvable in polynomial time, or is it NP-hard? State running times in \(\tau\) and total input bit length \(L\); there is no separate \(m\) or other input parameter.
For finite additively separable hedonic games, existence of a grand-coalition fair partition is NP-complete, and max-min fairness coincides with grand-coalition fairness ([Nguyen–Rothe, 2016](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p232.pdf)). The extended result strengthens existence hardness to strong NP-completeness ([Kerkmann–Nguyen–Rothe, 2021, reproduced in the author's dissertation](https://ccc.cs.uni-duesseldorf.de/~rothe/DISSERTATION/DissKerkmann.pdf)).
No complexity result for exactly this mass formulation was located in the literature search.
Deciding feasibility is \(\mathrm{NP}\)-hard, even when all masses are equal dyadic rationals and every diagonal entry satisfies \(a_{tt}=0\). Consequently, there is no polynomial-time algorithm in the total input bit length \(L\) unless \(\mathrm{P}=\mathrm{NP}\).
A deterministic decision algorithm runs in \(2^{2^{O(\tau)}}L^{O(1)}\) time. Both claims are proved below.
Consider a finite additively separable hedonic game with players \(N=\{1,\ldots,n\}\), rational values \(v_i(j)\), and \(v_i(i)=0\). Put
\(b_i=\max\{0,\sum_{j\in N}v_i(j)\}\).
Its grand-coalition fairness problem asks whether there is a partition \(\pi\) of \(N\) satisfying
\(\sum_{j\in\pi(i)}v_i(j)\geq b_i\quad\text{for every }i\in N\).
This problem is \(\mathrm{NP}\)-complete by Theorem 7 of [Nguyen–Rothe (2016)](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p232.pdf). Their normalization and fairness definition give exactly the thresholds above.
Let \(r\) be the least power of two with \(r\geq n\). Add \(r-n\) players whose incoming and outgoing values are all zero. This preserves feasibility: added players can be singleton blocks, and deleting them from any fair partition leaves all original utilities unchanged. Write \(v\) for the padded valuation matrix and \(b_i\) for its thresholds.
For each padded player \(i\in\{1,\ldots,r\}\), create an original type \(x_i\) and a guard type \(h_i\). Set
\(T=\{x_1,\ldots,x_r,h_1,\ldots,h_r\},\qquad \tau=2r,\qquad \mu_t=1/\tau\).
These masses are positive dyadic rationals and sum to one.
Define the complete matrix by
\(a_{x_i x_j}=\tau v_i(j),\qquad a_{h_i x_i}=\tau\),
with all remaining entries zero. In particular, all diagonal entries vanish.
The resulting grand-coalition thresholds are
\(g_{x_i}=\max\{0,\sum_{j=1}^{r}\tau v_i(j)\mu_{x_j}\}=b_i\),
and
\(g_{h_i}=\tau\mu_{x_i}=1\).
Because \(r<2n\), the construction has \(\tau<4n\) types. Multiplication by \(\tau\) increases the encoding length of each valuation by only \(O(\log\tau)\) bits. Thus constructing the complete matrix takes polynomial time in the finite instance’s encoding length.
Lemma. In every feasible structure of the constructed instance, each pair \(x_i,h_i\) occurs together, with both types’ entire masses, in exactly one coalition.
Proof. Since \(g_{h_i}=1>0\), no guard mass may remain in singletons. Hence some coalition \(q^\ell\) has \(q^\ell_{h_i}>0\). Its guard constraint gives
\(u_{h_i}(q^\ell)=\tau q^\ell_{x_i}\geq1\).
The mass constraint also gives \(q^\ell_{x_i}\leq\mu_{x_i}=1/\tau\). Therefore
\(q^\ell_{x_i}=1/\tau=\mu_{x_i}\).
Nonnegativity and the total mass constraint imply \(q^j_{x_i}=0\) for every \(j\neq\ell\).
Any other coalition containing positive \(h_i\)-mass would likewise require the entire \(x_i\)-mass, which is impossible. Consequently all \(h_i\)-mass belongs to \(q^\ell\). Since its residual mass must vanish,
\(q^\ell_{h_i}=\mu_{h_i}=1/\tau\).
This proves the lemma. \(\square\)
Thus splitting is permitted by the formulation, but the constructed instance prevents it. Every nonzero coalition consists of entire original–guard pairs.
Suppose the padded finite game has a fair partition \(\pi\). For each block \(C\in\pi\), form a vector \(q^C\) containing mass \(1/\tau\) of both \(x_i\) and \(h_i\) for every \(i\in C\), and zero elsewhere.
Every type’s entire mass is assigned. For \(i\in C\),
\(u_{x_i}(q^C)=\sum_{j\in C}\tau v_i(j)(1/\tau)=\sum_{j\in C}v_i(j)\geq b_i=g_{x_i}\).
Also,
\(u_{h_i}(q^C)=\tau(1/\tau)=1=g_{h_i}\).
Therefore these vectors form a feasible structure.
Conversely, suppose the constructed mass instance is feasible. By the guard lemma, every padded player’s original–guard pair belongs entirely to one coalition. For each nonzero coalition \(q^\ell\), define
\(C_\ell=\{i:q^\ell_{x_i}>0\}\).
The sets \(C_\ell\) are nonempty and partition \(\{1,\ldots,r\}\): every original type is fully assigned to exactly one coalition, and every guard accompanies its original type.
For every \(i\in C_\ell\), feasibility gives
\(\sum_{j\in C_\ell}v_i(j)=u_{x_i}(q^\ell)\geq g_{x_i}=b_i\).
Hence the blocks \(C_\ell\) form a fair partition of the padded finite game. Deleting the added zero-valued players gives a fair partition of the original game.
The reduction is therefore a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness.
The following argument handles the absence of an input bound on the number of coalitions.
Define \(\operatorname{supp}(q)=\{t:q_t>0\}\). Suppose several feasible coalition vectors have the same nonempty support \(S\). Replace them by their sum \(Q\).
For every \(t\in S\), linearity and nonnegativity of the thresholds give
\(u_t(Q)=\sum_j u_t(q^j)\geq\sum_j g_t\geq g_t\).
The support remains \(S\), and total assigned masses remain unchanged. Thus merging preserves feasibility.
There are \(2^\tau-1\) nonempty supports. Consequently, every feasible instance has a feasible structure with at most \(2^\tau-1\) coalitions.
Enumerate every family \(\mathcal F\subseteq 2^T\setminus\{\varnothing\}\), including the empty family. For each \(\mathcal F\), introduce vectors \(q^S\), one for each \(S\in\mathcal F\), and solve the rational linear feasibility problem
\(q_t^S\geq0\quad(t\in S),\qquad q_t^S=0\quad(t\notin S),\)
\(\sum_{S\in\mathcal F}q_t^S\leq\mu_t\quad(t\in T),\)
\(\sum_{S\in\mathcal F}q_t^S=\mu_t\quad(t\in T\text{ with }g_t>0),\)
\(\sum_{s\in T}a_{ts}q_s^S\geq g_t\quad(S\in\mathcal F,\ t\in S).\)
Strict positivity inside \(S\) is unnecessary. If this linear program is feasible, discard zero vectors. Each remaining vector has actual support contained in its indexed set \(S\), so every type present satisfies its required utility constraint. The mass and residual conditions also hold.
Conversely, merge an existing feasible structure by identical supports and choose \(\mathcal F\) to be its resulting support family. Those merged vectors satisfy the corresponding linear program.
Therefore the algorithm accepts exactly the feasible instances.
There are \(2^{2^\tau-1}\) support families. Each linear program has at most \(\tau2^{\tau-1}\) variables and \(O(\tau2^\tau)\) constraints.
The thresholds are computable in polynomial time in \(L\). Each expanded linear program has encoding length \(2^{O(\tau)}L^{O(1)}\), so polynomial-time rational linear programming gives total running time
\(2^{2^\tau-1}\,2^{O(\tau)}L^{O(1)}=2^{2^{O(\tau)}}L^{O(1)}\).
This establishes fixed-parameter tractability in the support size \(\tau\), alongside \(\mathrm{NP}\)-hardness when \(\tau\) varies. Membership of the general problem in \(\mathrm{NP}\) is not needed for the requested classification and is not asserted here.
⟨structured verdict parsed — rendered above⟩
Result: proved. The reduction establishes \(\mathrm{NP}\)-hardness for the exact mass formulation in USER_TASK, including unrestricted splitting and an unbounded finite number of coalitions. The decision algorithm and its stated running time are also correct. No major or minor mathematical issues were found.
The source theorem applies as stated. Nguyen–Rothe consider additively separable hedonic games with rational valuations, normalized by \(v_i(i)=0\). Their Definition 2 compares each player’s assigned coalition weakly with the better of the singleton and the grand coalition. Thus the numerical threshold is exactly
\[
b_i=\max\left\{0,\sum_{j\in N}v_i(j)\right\}.
\]
Their Theorem 7 states that existence of a grand-coalition fair partition is \(\mathrm{NP}\)-complete. No symmetry or nonnegativity restriction interferes with the reduction. [Nguyen–Rothe (2016), Definition 2 and Theorem 7](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p232.pdf).
Consequently, the finite decision problem defined in Section 1 is a valid source of hardness.
Padding with players whose incoming and outgoing valuations are zero preserves all original players’ utilities and thresholds. Added players have threshold zero and can be singletons. Conversely, deleting added players from a fair partition preserves original utilities; any resulting empty blocks are omitted. The padding equivalence is correct.
For the least power of two \(r\geq n\), the inequalities \(n\leq r<2n\) hold for every positive \(n\), including \(n=1\). Therefore \(\tau=2r<4n\).
Since \(\tau\) is a power of two, each mass \(1/\tau\) is a positive dyadic rational. There are exactly \(\tau\) types, so the masses sum to one.
The specified matrix is complete once all unspecified entries are set to zero. Its diagonal vanishes: the original-type diagonal uses \(v_i(i)=0\), and every guard diagonal is unspecified and therefore zero.
The threshold calculations are exact:
\[
u_{x_i}(\mu)=\sum_{j=1}^{r}v_i(j),
\qquad
u_{h_i}(\mu)=1.
\]
Hence \(g_{x_i}=b_i\) and \(g_{h_i}=1\).
Multiplying rational valuations by the integer \(\tau\) adds at most \(O(\log\tau)\) bits per entry. Padding and writing the complete matrix increase its size polynomially in the source encoding length. The reduction is therefore polynomial time.
Every step of the guard lemma follows from the given feasibility conditions.
This argument does not presume indivisibility. It derives the claimed absence of splitting from the constraints.
Since every type is an original type or its guard, the lemma also justifies the assertion that every nonzero coalition consists entirely of whole original–guard pairs.
The forward construction assigns all masses exactly once. For each original type, its utility equals its finite-game utility in the corresponding block. Every guard receives utility exactly one. All utility and residual conditions therefore hold, including equality cases.
In the reverse direction, the guard lemma assigns every original type fully to exactly one coalition. Every nonzero coalition contains an original type, since a guard cannot occur without its original type. Thus the sets \(C_\ell\) are nonempty, disjoint, and cover all padded players.
The utility identity
\[
u_{x_i}(q^\ell)=\sum_{j\in C_\ell}v_i(j)
\]
is justified by the whole-mass conclusion and the zero valuations toward guards. Feasibility therefore yields precisely the finite fairness inequalities. Deleting padded players preserves them.
Both implications hold. The resulting many-one reduction proves the claimed restricted \(\mathrm{NP}\)-hardness, and hence hardness of the general problem.
The merging argument is valid even with arbitrary signed matrix entries.
For coalitions sharing support \(S\), every \(t\in S\) satisfies its utility constraint in every merged coalition. Linearity gives
\[
u_t(Q)=\sum_j u_t(q^j)\geq \sum_j g_t\geq g_t,
\]
where the final inequality uses \(g_t\geq0\) and a nonempty collection of coalitions.
Nonnegative coordinates preserve the support under summation. Total assigned masses, and therefore residual masses, remain unchanged. Thus merging preserves feasibility.
Because the original structure is finite, this operation produces at most one coalition per nonempty support, giving the claimed bound \(2^\tau-1\).
The linear programs correctly handle indexed supports that may be larger than actual supports.
Soundness: A positive coordinate can occur only within the indexed set \(S\), and every type in \(S\) has its utility inequality imposed. Thus every actually present type satisfies its required inequality. Discarding zero vectors changes neither assigned masses nor residual conditions.
Completeness: Merging a feasible structure by actual support gives a family enumerated by the algorithm. Its vectors satisfy every constraint in that family’s linear program.
The empty family is included. Its constraints accept exactly when every threshold is zero, which is precisely when the all-singleton structure is feasible. Zero vectors and weak utility inequalities introduce no discrepancy.
Therefore the enumeration accepts exactly the feasible instances.
After eliminating coordinates fixed to zero, the maximum number of variables is
\[
\sum_{\varnothing\neq S\subseteq T}|S|=\tau2^{\tau-1}.
\]
The number of constraints is \(O(\tau2^\tau)\), as claimed.
Threshold computation uses polynomially many rational operations and produces numbers of bit length polynomial in \(L\). Each expanded linear program consequently has encoding length \(2^{O(\tau)}L^{O(1)}\).
The invoked rational linear-programming fact is applicable: feasibility of a finite system of rational linear equalities and weak inequalities is decidable in time polynomial in its binary encoding length. No strict inequalities or irrational coefficients occur here.
Enumerating \(2^{2^\tau-1}\) families therefore gives the stated deterministic bound
\[
2^{2^\tau-1}\,2^{O(\tau)}L^{O(1)}
=
2^{2^{O(\tau)}}L^{O(1)}.
\]
This is fixed-parameter tractable in \(\tau\) and is consistent with \(\mathrm{NP}\)-hardness when \(\tau\) varies. The output appropriately avoids asserting general membership in \(\mathrm{NP}\).
Repair feedback: None required. The output resolves the assigned complexity question and supplies a valid running-time bound using only \(\tau\) and \(L\).
⟨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.