Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor FA preferences, computing the optimum is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of complete FA affinity types, a rational mass vector \(\mu \in \mathbb{Q}_{\geq 0}^T\) with \(\sum_t \mu_t = 1\), a directed friend relation \(F(t) \subseteq T\), a rational clone-scale parameter \(\eta > 0\), and a rational threshold \(B\), does there exist a finite typed coalition structure \(\lambda = \{(q_j,z_j)\}_j\) with \(q_j \in \mathbb{N}\), \(z_j \in \mathbb{Q}_{\geq 0}^T\), \(\sum_j q_j z_j = \mu\), and \(W_\eta(\lambda)=\sum_j q_j \sum_t z_j(t)\left(\sum_{r\in F(t)} z_j(r)-\eta \sum_{r\notin F(t)} z_j(r)\right)\ge B\), or what is the maximum \(W_\eta\)?
Definitions. An instance has a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), specified sets \(F_t,E_t\subseteq T\), and \(\lambda=1/N\) for \(N\in\mathbb{N}_{>0}\). A feasible outcome is a finite family \(z^1,\ldots,z^L\in\mathbb{R}_{\ge0}^{T}\) satisfying \(\sum_{\ell=1}^{L}z_t^\ell=\mu_t\) for every \(t\). Its welfare is \(W_\lambda=\sum_{\ell=1}^{L}\sum_{t\in T}z_t^\ell\left(\sum_{u\in F_t}z_u^\ell-\lambda\sum_{u\in E_t}z_u^\ell\right)\).
Target. Is exact optimization of \(W_\lambda\) over finite feasible outcomes solvable in polynomial time, or is it NP-hard?
Nearest known results. For finite-agent Friends Appreciation games with friend value \(1\) and enemy value \(-1/n\), computing a welfare-maximizing partition is NP-hard. Fractional hedonic games instead divide each agent's coalition value by coalition size, so their welfare-maximization results do not address this mass-vector objective.
Exact welfare optimization is \(\mathrm{NP}\)-hard. This remains true under the following restrictions:
The essential point is that, on these instances, fractional splitting of a type across several blocks never improves welfare.
Consider a finite Friends Appreciation instance with agent set \(A\), where \(n=|A|\). Every agent \(i\) has sets \(F_i,E_i\subseteq A\setminus\{i\}\), and the utility of \(i\) in coalition \(C\ni i\) is
\(\displaystyle u_i(C)=|F_i\cap C|-\frac{1}{n}|E_i\cap C|.\)
Thus, for a partition \(\Pi\) of \(A\), its utilitarian welfare is
\(\displaystyle \operatorname{SW}_{\mathrm{FA}}(\Pi)=\sum_{C\in\Pi}\sum_{i\in C}\left(|F_i\cap C|-\frac{1}{n}|E_i\cap C|\right).\)
This is the standard cardinal encoding of Friends Appreciation preferences [described here](https://ojs.aaai.org/index.php/AAAI/article/download/5565/5421). Computing a partition maximizing this welfare is \(\mathrm{NP}\)-hard; see, for example, Theorem \(2\) of [Flammini–Fomenko–Varricchio](https://arxiv.org/abs/2501.00976).
Suppose that \(t\notin F_t\cup E_t\) for every \(t\in T\). Then every finite feasible mass outcome can be transformed, without decreasing welfare, into an outcome in which every type places all its mass in one block.
Define
\(\displaystyle a_{tu}=\mathbf 1_{\{u\in F_t\}}-\lambda\mathbf 1_{\{u\in E_t\}}.\)
Then
\(\displaystyle W_\lambda(z^1,\ldots,z^L)=\sum_{\ell=1}^{L}\sum_{t,u\in T}a_{tu}z_t^\ell z_u^\ell.\)
Fix a type \(t\), and hold all coordinates \(z_u^\ell\) with \(u\neq t\) fixed. Write \(x_\ell=z_t^\ell\). Because \(a_{tt}=0\), the terms depending on \(x=(x_1,\ldots,x_L)\) are linear:
\(\displaystyle \sum_{\ell=1}^{L}b_\ell x_\ell,\)
where
\(\displaystyle b_\ell=\sum_{u\neq t}\left(a_{tu}+a_{ut}\right)z_u^\ell.\)
Feasibility requires \(x_\ell\geq 0\) and \(\sum_{\ell}x_\ell=\mu_t\). Choose \(\ell^\ast\) maximizing \(b_\ell\). Then
\(\displaystyle \sum_{\ell=1}^{L}b_\ell x_\ell\leq b_{\ell^\ast}\sum_{\ell=1}^{L}x_\ell=\mu_t b_{\ell^\ast}.\)
Consequently, replacing \(z_t^{\ell^\ast}\) by \(\mu_t\) and every other \(z_t^\ell\) by \(0\) does not decrease welfare.
Apply this operation successively to every type. Previously purified types remain concentrated because only the currently considered type is modified. At the end, each type belongs wholly to one block. Removing empty blocks yields a partition of \(T\). This proves the lemma. \(\square\)
In particular, although the feasible region permits arbitrary fractional splitting, splitting creates no integrality gap on self-neutral instances.
Given a finite Friends Appreciation instance on \(A\), construct the mass instance
\(\displaystyle T=A,\qquad \mu_i=\frac1n\ \text{for all }i,\qquad N=n,\qquad \lambda=\frac1n,\)
and retain the same sets \(F_i,E_i\). This construction has polynomial encoding length.
For a partition \(\Pi\) of \(A\), define the corresponding mass outcome by
\(\displaystyle z_i^C=\begin{cases}\frac1n,&i\in C,\\0,&i\notin C,\end{cases}\)
for every \(C\in\Pi\). Its welfare is
\(\displaystyle W_{1/n}(z)=\frac{1}{n^2}\operatorname{SW}_{\mathrm{FA}}(\Pi).\)
Indeed, every ordered friend pair contributes \(1/n^2\) to the mass welfare, while every ordered enemy pair contributes \(-1/n^3\), exactly \(1/n^2\) times its finite-agent contribution.
Conversely, let \(z\) be any finite feasible mass outcome. By the purification lemma, \(z\) is dominated by an unsplit outcome induced by some partition \(\Pi\). Therefore
\(\displaystyle W_{1/n}(z)\leq \frac{1}{n^2}\operatorname{SW}_{\mathrm{FA}}(\Pi).\)
It follows that the optimal values satisfy the exact identity
\(\displaystyle \operatorname{OPT}_{\mathrm{mass}}=\frac{1}{n^2}\operatorname{OPT}_{\mathrm{FA}}.\)
Hence a polynomial-time exact optimizer for the mass problem would compute the finite-agent optimum by multiplying its answer by \(n^2\). This contradicts the known \(\mathrm{NP}\)-hardness unless \(\mathrm{P}=\mathrm{NP}\).
Under the definitions as stated, a maximizing finite outcome need not exist when self-enmity is allowed.
Take \(T=\{t\}\), \(\mu_t=1\), \(F_t=\varnothing\), \(E_t=\{t\}\), and \(N=1\). Writing \(x_\ell=z_t^\ell\), every finite outcome satisfies
\(\displaystyle W_1=-\sum_{\ell=1}^{L}x_\ell^2<0.\)
On the other hand, splitting equally among \(L\) blocks gives \(W_1=-1/L\), which converges to \(0\). Thus the supremum is \(0\), but no finite feasible outcome attains it.
This does not weaken the hardness result: the reduction uses only self-neutral instances, for which the purification lemma guarantees attainment with at most \(|T|\) nonempty blocks.
The fractional mass formulation does not evade the finite-agent hardness. On the relevant reduction instances, its fractional relaxation is exact, and therefore exact optimization is \(\mathrm{NP}\)-hard.
⟨structured verdict parsed — rendered above⟩
The reduction and purification argument are mathematically sound. The prover establishes NP-hardness on a restricted family where every mass is positive and an optimum is attained. Two minor expositional gaps remain, neither affecting the hardness result.
The source instance uses \(n=|A|\), utility
\[ u_i(C)=|F_i\cap C|-\frac1n|E_i\cap C|, \]
and \(F_i,E_i\) partition \(A\setminus\{i\}\). This matches the claimed restricted target instances after setting \(T=A\) and \(N=n\).
The cited primary source does state as Theorem 2 that computing a social-welfare optimum for Friends Appreciation preferences is NP-hard, and its model assigns value \(1\) to friends and \(-1/n\) to enemies. Thus the cited theorem’s hypotheses match the reduction. See [Flammini–Fomenko–Varricchio, Theorem 2](https://arxiv.org/html/2501.00976#S4).
The expansion
\[ W_\lambda=\sum_{\ell=1}^{L}\sum_{t,u\in T}a_{tu}z_t^\ell z_u^\ell \]
is correct.
When all coordinates except those of type \(t\) are fixed, the coefficient of \(x_\ell=z_t^\ell\) receives contributions from both ordered pairs \((t,u)\) and \((u,t)\). Therefore
\[ b_\ell=\sum_{u\ne t}(a_{tu}+a_{ut})z_u^\ell \]
is correct.
The hypothesis \(t\notin F_t\cup E_t\) implies \(a_{tt}=0\), so no quadratic term \(a_{tt}x_\ell^2\) remains. Maximizing the resulting linear expression over
\[ x_\ell\ge0,\qquad \sum_\ell x_\ell=\mu_t \]
by concentrating all mass on an index maximizing \(b_\ell\) is valid.
Applying the operation successively is also valid: each step is welfare-nondecreasing relative to the current outcome, and later steps do not split types already purified.
There is one minor edge-case imprecision. If \(\mu_t=0\), the resulting nonzero supports do not literally determine which block contains \(t\), so “removing empty blocks yields a partition of \(T\)” requires an arbitrary assignment of zero-mass types. This does not affect the reduction, where every mass equals \(1/n>0\).
The construction has polynomial encoding length. In particular, \(1/n\) has logarithmic binary encoding length.
For a partition-induced mass outcome, each ordered friend pair contributes \(1/n^2\), while each ordered enemy pair contributes
\[ -\frac1n\cdot\frac1n\cdot\frac1n=-\frac1{n^3}. \]
Consequently,
\[ W_{1/n}(z)=\frac1{n^2}\operatorname{SW}_{\mathrm{FA}}(\Pi) \]
is exactly correct.
The two inequalities needed for equality of optimal values are both established:
Hence
\[ \operatorname{OPT}_{\mathrm{mass}} =\frac1{n^2}\operatorname{OPT}_{\mathrm{FA}} \]
follows.
The complexity conclusion is correct under the standard interpretation that exact optimization returns an exact optimal value or an exactly represented optimal outcome. The write-up should explicitly specify this output model. If an outcome is returned, its welfare must be evaluated exactly, or the constructive purification procedure must be applied before extracting the corresponding finite-agent solution.
For the one-type self-enemy instance,
\[ W_1=-\sum_{\ell=1}^{L}x_\ell^2<0 \]
for every finite feasible outcome, since nonnegative \(x_\ell\) summing to \(1\) cannot all vanish. Equal splitting gives \(-1/L\), so the supremum is \(0\) and is unattained. This is correct.
The caveat does not invalidate the reduction because all reduction instances are self-neutral, and purification guarantees an attaining partition-induced outcome.
No new mathematical ingredient 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.