Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor simple symmetric FHGs, UTILITARIAN WELFARE and EGALITARIAN WELFARE are both NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\) with \(|T|=\tau\), a symmetric binary affinity matrix \(A\in\{0,1\}^{\tau\times\tau}\), and rational masses \(\mu\in\Delta_\tau\), choose coalition compositions \(p^j\in\Delta_\tau\) and masses \(s_j\ge0\) with \(\sum_j s_j=1\) and \(\sum_j s_jp^j=\mu\), maximizing \(\sum_j s_j(p^j)^\mathsf{T}Ap^j\).
A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_i\), where \(\sum_i\mu_i=1\); \(\tau\) counts supported types, not all possible types.
The input also contains a symmetric matrix \(A\in\{0,1\}^{\tau\times\tau}\) and a binary-rational threshold \(b\in[0,1]\). Entry \(A_{ik}\) is the affinity between distinct individuals of types \(i,k\), including when \(i=k\). Individual self-valuations are zero; individuals have zero mass.
Mass is divisible. An outcome consists of any finite number \(r\ge1\) of coalitions, with real masses \(s_j>0\) and compositions \(p^j\in\Delta_\tau\), satisfying \(\sum_{j=1}^r s_j=1\) and \(\sum_{j=1}^r s_jp^j=\mu\). A type may occur in several coalitions; there are no stability constraints.
A type-\(i\) individual in composition \(p\) has utility \((Ap)_i\); total utilitarian welfare is \(W=\sum_{j=1}^r s_j(p^j)^\mathsf{T}Ap^j\). The decision problem asks whether an outcome with \(W\ge b\) exists. Let \(L\) be the total binary input length; there is no separate candidate parameter \(m\).
Is this continuous utilitarian-welfare decision problem solvable in time polynomial in \(\tau\) and \(L\), or is it NP-hard?
For finite, indivisible agents, maximizing utilitarian welfare is NP-hard even with symmetric binary affinities and zero self-valuations ([Aziz et al.](https://www.ijcai.org/Proceedings/15/Papers/071.pdf)). No result settling the exact continuous problem above was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, even when \(A_{ii}=0\) for every type and all input masses and thresholds are dyadic rationals.
We prove this by a direct reduction from \(\mathrm{CLIQUE}\). The key construction allows us to insert a small coalition supported on a large clique and compensate for its population consumption exactly.
For a nonempty simple graph \(H\), let \(A_H\) be its adjacency matrix and let \(\omega(H)\) denote its maximum clique size. Then every composition \(p\) satisfies
\( p^{\mathsf T}A_Hp\le 1-\frac{1}{\omega(H)}. \)
Here is a self-contained proof of this standard Motzkin–Straus bound.
Suppose two nonadjacent vertices \(u,v\) have positive coordinates in \(p\). Hold all other coordinates fixed and write \(p_u=x\), \(p_v=t-x\), where \(t=p_u+p_v\). Because the diagonal entries and \(A_{uv}\) are zero, the quadratic objective is affine in \(x\):
\( p^{\mathsf T}A_Hp =C+2x\alpha_u+2(t-x)\alpha_v, \)
where \(\alpha_u=\sum_{w\notin\{u,v\}}A_{uw}p_w\), and similarly for \(\alpha_v\).
Moving all mass \(t\) to whichever endpoint has the larger coefficient does not decrease the objective and reduces the support size. Repeating this operation produces a composition supported on a clique, with objective at least the original value.
For a composition supported on a clique of size \(d\), Cauchy–Schwarz gives
\( p^{\mathsf T}A_Hp =1-\sum_i p_i^2 \le 1-\frac1d \le 1-\frac1{\omega(H)}. \)
This proves the bound. A uniform composition on a clique of size \(d\) has welfare exactly \(1-1/d\).
Fix an integer \(k\ge2\), and put \(m=2k+1\). Let \(F_k\) be the complement of the cycle on vertices indexed modulo \(m\).
An independent set in that cycle is disjoint from its set of successors. Thus its size is at most \(\lfloor m/2\rfloor=k\), so \(\omega(F_k)\le k\).
For each index \(j\), define
\( S_j=\{j,j+2,\ldots,j+2(k-1)\}\pmod m. \)
Each \(S_j\) is an independent set of size \(k\) in the cycle, hence a clique in \(F_k\). Consequently, \(\omega(F_k)=k\).
Let \(p^j\) be the uniform composition on \(S_j\), and let \(B\) be the matrix with columns \(p^j\). Every vertex belongs to exactly \(k\) of these sets, so
\( B\mathbf1=\mathbf1. \)
Moreover, \(S_{a+1}\) and \(S_{a+2}\) partition all gadget vertices except \(a\). Therefore
\( k(p^{a+1}+p^{a+2})=\mathbf1-e_a. \)
These identities give an explicit way to express any vector through the gadget compositions. For a vector \(z\in\mathbb R^m\), set \(t=\sum_a z_a\) and define
\( x_j=t-k(z_{j-1}+z_{j-2}), \)
with indices interpreted modulo \(m\). Then
\( Bx =t\mathbf1-k\sum_a z_a(p^{a+1}+p^{a+2}) =t\mathbf1-\sum_a z_a(\mathbf1-e_a) =z. \)
Also,
\( \sum_jx_j=(m-2k)t=t. \)
If \(z\) is coordinatewise nonnegative, then \(x_j\le t\). The coefficients \(x_j\) may be negative; this is harmless because we will subtract a small multiple of them from positive baseline coalition masses.
Take an instance \((G,t)\) of \(\mathrm{CLIQUE}\), where \(G\) has \(n\) vertices and \(3\le t\le n\). This restricted problem remains \(\mathrm{NP}\)-hard: excluded cases are directly decidable and can be mapped to fixed yes- or no-instances. We use the standard hardness of \(\mathrm{CLIQUE}\) established in [Karp’s *Reducibility among Combinatorial Problems*](https://doi.org/10.1007/978-1-4684-2001-2_9).
Let \(k\) be the smallest power of two satisfying \(k\ge t-1\). Add
\( h=k+1-t \)
new vertices that form a clique and are adjacent to every original vertex. Call the resulting graph \(G'\), and write \(n'=n+h\).
Every maximum clique of \(G'\) contains all the added vertices, so
\( \omega(G')=\omega(G)+h. \)
In particular,
\( \omega(G)\ge t \quad\Longleftrightarrow\quad \omega(G')\ge k+1. \)
Using a power of two for \(k\) will ensure dyadic input values.
For each vertex \(v\) of \(G'\), take a separate copy of \(F_k\), identifying its vertex indexed \(0\) with \(v\). Its other \(2k\) vertices are private to that gadget. Retain the edges of \(G'\), and add no other edges between gadgets. Denote the resulting graph by \(H\).
A clique containing a private vertex must lie entirely within its gadget, because that private vertex has no neighbors outside the gadget. A clique containing only distinguished vertices is a clique of \(G'\). Hence
\( \omega(H)=\max\{k,\omega(G')\}. \)
The society has one type per vertex of \(H\), and \(A=A_H\). Its number of types is
\( \tau=N=n'(2k+1). \)
Let \(p^{v,j}\) denote the uniform composition on the clique \(S_j\) in gadget \(v\). There are exactly \(N\) such compositions. Each has welfare
\( c=1-\frac1k. \)
Let \(D\) be the smallest power of two with \(D\ge N\). Assign baseline coalition masses \(\lambda_{v,j}\) as follows: initially assign \(1/D\) to every composition, then replace one chosen mass with \(1-(N-1)/D\).
Thus
\( \sum_{v,j}\lambda_{v,j}=1, \qquad \lambda_{v,j}\ge\frac1D. \)
Define the society’s prescribed masses by
\( \mu=\sum_{v,j}\lambda_{v,j}p^{v,j}. \)
Every type belongs to exactly \(k\) gadget compositions. Therefore
\( \mu_i\ge k\cdot\frac1D\cdot\frac1k=\frac1D>0. \)
Also, \(\sum_i\mu_i=1\). Since \(k\) and \(D\) are powers of two, every \(\mu_i\) is dyadic.
Finally, set
\( \varepsilon=\frac1{2D}, \qquad b=c+\frac{\varepsilon}{2k^2} =1-\frac1k+\frac1{4Dk^2}. \)
This threshold is dyadic and satisfies \(c<b<1\).
Suppose \(\omega(G)<t\). Then \(\omega(G')\le k\), and consequently \(\omega(H)=k\).
By the quadratic bound, every composition \(p\) satisfies
\( p^{\mathsf T}Ap\le c. \)
For any admissible finite outcome, its coalition masses sum to one. Therefore
\( W=\sum_j s_j(p^j)^{\mathsf T}Ap^j \le\sum_j s_jc =c<b. \)
Thus the constructed welfare instance is a no-instance, regardless of how many coalitions are used or how types are divided among them.
Suppose \(\omega(G)\ge t\). Then \(G'\) contains a clique of size \(k+1\). Let \(q\) be the uniform composition on such a clique, viewed as a composition on \(H\). Its welfare is
\( q^{\mathsf T}Aq=1-\frac1{k+1}. \)
We will insert a coalition of composition \(q\) and mass \(\varepsilon\), repairing the remaining population exactly.
For each gadget \(v\), restrict \(q\) to that gadget, obtaining \(z^v\). Let \(t_v\) be the sum of its coordinates. Applying the population-repair identity gives coefficients \(x_{v,j}\) satisfying
\( \sum_jx_{v,j}p^{v,j}=z^v, \qquad \sum_jx_{v,j}=t_v, \qquad x_{v,j}\le t_v\le1. \)
Because the gadgets partition the type set,
\( \sum_{v,j}x_{v,j}p^{v,j}=q, \qquad \sum_{v,j}x_{v,j}=1. \)
Define the repaired baseline masses by
\( y_{v,j}=\lambda_{v,j}-\varepsilon x_{v,j}. \)
They are strictly positive, since
\( y_{v,j}\ge\frac1D-\varepsilon=\frac1{2D}>0. \)
Their total mass is \(1-\varepsilon\), and their aggregate population, together with the new coalition, is exactly
\( \sum_{v,j}y_{v,j}p^{v,j}+\varepsilon q =\mu-\varepsilon q+\varepsilon q =\mu. \)
Thus these \(N+1\) coalitions form an admissible finite outcome. Its welfare is
\( W=(1-\varepsilon)c+\varepsilon\left(1-\frac1{k+1}\right) =c+\frac{\varepsilon}{k(k+1)}. \)
Since \(k+1\le2k\),
\( W\ge c+\frac{\varepsilon}{2k^2}=b. \)
Therefore the constructed welfare instance is a yes-instance.
We have \(k<2(t-1)\), hence \(n'=O(n)\) and \(N=O(n^2)\). The affinity matrix has \(N^2=O(n^4)\) binary entries.
Every population mass has denominator dividing \(kD\), and the threshold has denominator dividing \(4Dk^2\). Because \(D<2N\), all these values require \(O(\log n)\) bits each. The complete construction therefore takes polynomial time and produces an input of polynomial length.
We have proved
\( \omega(G)\ge t \quad\Longleftrightarrow\quad \text{the constructed society admits an outcome with }W\ge b. \)
This settles the target question: the exact continuous problem is \(\mathrm{NP}\)-hard. An algorithm polynomial in \(\tau\) and \(L\) would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem. It establishes \(\mathrm{NP}\)-hardness under polynomial-time many-one reductions, including the claimed restrictions to zero diagonal affinities and dyadic input values. I found no major or minor mathematical issues requiring repair.
The argument addresses the continuous problem directly: its no-instance bound covers every admissible finite outcome, and its yes-instance construction preserves the prescribed population exactly while keeping every coalition mass strictly positive.
The support-compression argument is valid.
For nonadjacent supported vertices \(u,v\), the assumptions \(A_{uu}=A_{vv}=A_{uv}=0\) eliminate all quadratic terms involving their coordinates alone. With their total mass fixed, the objective therefore has precisely the stated affine dependence on \(x\).
Choosing the endpoint with the larger coefficient preserves nonnegativity, preserves total mass, does not decrease welfare, and strictly reduces the number of positive coordinates. Consequently, the procedure terminates after finitely many steps at a composition whose support is a clique.
On a clique support of size \(d\), the identity
\[
p^{\mathsf T}A_Hp=1-\sum_i p_i^2
\]
and the Cauchy–Schwarz bound are correct. The inequality involving \(\omega(H)\) has the correct direction because \(d\le\omega(H)\).
The argument also covers an edgeless graph with at least one vertex: its clique number is \(1\), and its quadratic welfare is zero. No external Motzkin–Straus theorem is needed, since the output proves the bound it uses.
The gadget claims are correct for every stipulated \(k\ge2\).
The indexing in the formula for \(x_j\) agrees with the subsequent summation. Substitution gives exactly \(Bx=z\), and summing the coefficients gives
\[
\sum_jx_j=(m-2k)t=t.
\]
For nonnegative \(z\), the bound \(x_j\le t\) is valid. The coefficients need not be nonnegative, and the later construction correctly handles this; it never treats them as coalition masses.
The cited source problem is the standard decision version of \(\mathrm{CLIQUE}\): given a simple graph and an integer threshold, decide whether a clique of at least that size exists. Its polynomial many-one hardness is the result invoked from [Karp’s paper](https://doi.org/10.1007/978-1-4684-2001-2_9).
Restricting to \(3\le t\le n\) is legitimate. The excluded threshold cases are directly decidable, and fixed yes- and no-instances exist within the restricted domain.
The padding parameter \(h=k+1-t\) is nonnegative. Every added vertex is adjacent to every other vertex, so every maximum clique contains all added vertices. Hence
\[
\omega(G')=\omega(G)+h
\]
and the threshold equivalence follow exactly as written.
The gadgets have disjoint vertex sets after each gadget’s distinguished vertex is identified with its own vertex of \(G'\). No distinguished vertex belongs to two gadgets.
A private vertex has no neighbor outside its gadget. Therefore a clique containing such a vertex lies entirely within that gadget. Cliques containing only distinguished vertices are precisely cliques of \(G'\). This verifies
\[
\omega(H)=\max\{k,\omega(G')\}.
\]
The type count \(N=n'(2k+1)\) is correct, and \(A_H\) is symmetric, binary, and has zero diagonal.
The baseline masses sum to one. The replacement mass is at least \(1/D\) because \(D\ge N\). Every prescribed type mass is positive by the stated incidence count, and the resulting population sums to one.
Since \(k\) and \(D\) are powers of two, the population masses and threshold are dyadic. The threshold satisfies \(0<c<b<1\), including the smallest permitted value \(k=2\).
When \(\omega(G)<t\), integrality and the padding identity imply \(\omega(G')\le k\). Thus \(\omega(H)=k\).
The quadratic bound applies to every composition, without any restriction on how its support crosses gadgets. Averaging that bound with positive coalition masses summing to one gives \(W\le c<b\).
This excludes every admissible outcome, regardless of its finite number of coalitions or splitting of types. There is no quantifier gap.
A clique of size at least \(k+1\) contains one of exactly that size, so the chosen uniform composition \(q\) exists and has the stated welfare.
The restrictions \(z^v\) are nonnegative and partition \(q\) across the disjoint gadgets. Applying the proved identity therefore yields both the aggregate population equation and the coefficient-sum equation used in the repair.
The repaired masses are strictly positive:
\[
y_{v,j}=\lambda_{v,j}-\varepsilon x_{v,j}
\ge\frac1D-\varepsilon
=\frac1{2D}>0.
\]
This bound remains valid when a repair coefficient is negative.
The repaired masses sum to \(1-\varepsilon\), and adding the new coalition restores exactly \(\mu\). All compositions remain simplex elements. Consequently, the construction is an admissible outcome with exactly \(N+1\) coalitions.
The welfare calculation is correct:
\[
W=c+\frac{\varepsilon}{k(k+1)}.
\]
The inequality \(k+1\le2k\) gives the claimed comparison \(W\ge b\). Thus the yes direction is established with the exact decision threshold.
The smallest-power-of-two choice gives \(k<2(t-1)\), so \(n'=O(n)\), \(N=O(n^2)\), and the explicitly written affinity matrix has \(O(n^4)\) entries.
The denominator bounds are correct. Since \(D<2N\), both denominators and numerators have \(O(\log n)\) bits. The population is computed from explicitly specified baseline compositions; constructing the input does not require finding a clique.
The reduction is therefore polynomial in the source input length and proves the required many-one equivalence.
No claim of membership in \(\mathrm{NP}\) is made or needed. The implication concerning an algorithm polynomial in \(\tau\) and \(L\) is valid because both parameters are polynomially bounded on the reduction’s outputs.
None required. The proof establishes the claimed hardness with no unresolved mathematical steps.
⟨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.