Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation (d4-journals-jair-2018-0028)

Given rational type masses \mu with \sum_t \mu_t=1, a symmetric nonnegative rational compatibility matrix \(W\), and a threshold \(B\), decide whether there are finitely many positive-mass coalitions \(x^1,…,x^K\in\mathbb{R}_{\ge0}^{\tau}\), with \sum_k x_t^k=\mu_t, such that, for \(q_k=\sum_t x_t^k\), every type used in coalition \(k\) weakly prefers \(k\) to every occupied coalition \ell\), meaning \sum_r w_{tr}x_r^k/q_k \ge \sum_r w_{tr}x_r^\ell/q_\ell, and \sum_{k,t,r}w_{tr}x_t^kx_r^k/q_k\ge B\).

Input consists of rational masses \(\mu_t\ge 0\) for \(t\in[\tau]\), with \(\sum_t\mu_t=1\), a symmetric nonnegative rational matrix \(W=(w_{tr})\), and a rational threshold \(B\). A feasible outcome is any finite collection \(x^1,\ldots,x^K\in\mathbb R_{\ge0}^{\tau}\) with \(q_k=\sum_t x_t^k>0\) and \(\sum_k x_t^k=\mu_t\) for every type.
Type \(t\)'s utility in coalition \(k\) is \(u_t(k)=\sum_r w_{tr}x_r^k/q_k\). The outcome is stable if \(x_t^k>0\) implies \(u_t(k)\ge u_t(\ell)\) for every occupied coalition \(\ell\). Its welfare is \(\sum_{k,t,r}w_{tr}x_t^kx_r^k/q_k\).
Is deciding whether a stable outcome with welfare at least \(B\) exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite agents, maximizing welfare over Nash-stable partitions is NP-hard even with symmetric \(0/1\) weights ([Bilò et al.](https://www.jair.org/index.php/jair/article/download/11211/26422/20780)). That result does not address divisible type masses; the search found no result for the exact mass formulation above.

Result. The decision problem is \(\mathrm{NP}\)-hard, even when all masses are strictly positive and \(W\) is a symmetric \(\{0,1\}\)-matrix with zero diagonal.

The proof below is a polynomial-time reduction from \(\mathrm{3SAT}\). It allows arbitrary real-valued splittings and any finite number of coalitions.

1. A quadratic bound and its equality case

For a finite simple graph \(H\), let \(A\) be its adjacency matrix and let \(\omega(H)\) denote its maximum clique size. A probability vector means a vector \(p\geq 0\) with \(\sum_v p_v=1\).

We need the following version of the [Motzkin–Straus bound](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maxima-for-graphs-and-a-new-proof-of-a-theorem-of-turan/AC3CC45896B053B75C856F25829CA95C), including an equality property. We prove both directly.

Lemma. Suppose \(\omega(H)\leq h\). Every probability vector satisfies
\(p^{\mathsf T}Ap\leq 1-\frac1h\).
Moreover, if equality holds and \(p_z>0\), then \(H\) contains an \(h\)-vertex clique containing \(z\).

Proof. Suppose two nonadjacent vertices \(a,b\) both have positive coordinates. Keep all other coordinates fixed and redistribute their combined mass between \(a\) and \(b\). The quadratic form is affine in this redistribution parameter: its potentially quadratic terms vanish because \(A_{aa}=A_{bb}=A_{ab}=0\).

Consequently, transferring all their combined mass to one endpoint can be done without decreasing the quadratic form. This reduces the support size. Repeating produces a probability vector \(r\) supported on a clique \(C\), with
\(p^{\mathsf T}Ap\leq r^{\mathsf T}Ar\).
Writing \(s=|C|\), we have
\(r^{\mathsf T}Ar=1-\sum_{v\in C}r_v^2\leq 1-\frac1s\leq 1-\frac1h\).
Here \(\sum_{v\in C}r_v^2\geq 1/s\) follows from Cauchy–Schwarz.

Now suppose \(p^{\mathsf T}Ap=1-1/h\) and \(p_z>0\). The bound just proved makes \(p\) a global maximizer. For any two nonadjacent vertices in its support, the current redistribution parameter lies strictly inside its feasible interval. An affine function attaining its global maximum at an interior point is constant. Thus either endpoint transfer preserves the objective.

Perform the transfers while preserving \(z\): whenever a pair contains \(z\), transfer its combined mass to \(z\). Every intermediate vector remains a global maximizer. Eventually the support is a clique \(C\) containing \(z\). If \(|C|<h\), the preceding bound gives an objective strictly smaller than \(1-1/h\), a contradiction. Therefore \(|C|=h\). \(\square\)

2. Uniform maximum-clique coalitions are stable

Suppose \(\omega(H)\leq h\), and consider any feasible outcome whose coalition compositions are uniform on \(h\)-vertex cliques.

A type belonging to such a coalition has utility \((h-1)/h\). Its utility in any other coalition is at most \((h-1)/h\):

• If the type belongs to that coalition’s clique, it has exactly \(h-1\) neighbors there.
• Otherwise, it cannot be adjacent to all \(h\) clique vertices, since that would create an \((h+1)\)-vertex clique.

Thus the outcome is stable. Every coalition composition \(p\) satisfies \(p^{\mathsf T}Ap=(h-1)/h\), so its total welfare is also \((h-1)/h\), because total mass is one.

We will construct masses that can be allocated to such coalitions precisely when the input formula is satisfiable.

3. A gadget for allocating the remaining masses

Fix an integer \(h\geq 2\). Let \(F_h\) be the complement of the cycle on \(2h+1\) vertices, labeled \(0,1,\ldots,2h\), with indices interpreted modulo \(2h+1\).

Its clique number is \(h\). Indeed, a clique in \(F_h\) is an independent set in the cycle. Mapping every vertex in an independent set to its successor gives an injection into the complement of that set, so its size is at most \(\lfloor(2h+1)/2\rfloor=h\).

For each index \(j\), define
\(S_j=\{j,j+2,\ldots,j+2(h-1)\}\).
These sets contain no consecutive cycle vertices, so each is an \(h\)-vertex clique in \(F_h\).

Each vertex belongs to exactly \(h\) of the sets \(S_j\): for each choice of \(a\in\{0,\ldots,h-1\}\), there is exactly one index \(j\) satisfying \(v=j+2a\) modulo \(2h+1\).

Also,
\(S_1=\{1,3,\ldots,2h-1\}\)
and
\(S_2=\{2,4,\ldots,2h\}\).
Thus \(S_1,S_2\) partition all vertices other than \(0\).

For a vertex set \(S\), write \(\mathbf 1_S\) for its indicator vector, and write \(e_0\) for the unit vector at vertex \(0\). The preceding facts give two identities:
\(\sum_{j=0}^{2h}\frac{2}{h}\mathbf 1_{S_j}=2\mathbf 1\),
and
\(\sum_{j=0}^{2h}\frac{1}{h}\mathbf 1_{S_j}+\mathbf 1_{S_1}+\mathbf 1_{S_2}=2\mathbf 1-e_0\).

Their allocation meaning is exact. A term \(c\mathbf 1_S\) specifies a coalition receiving mass \(c\) from each vertex in \(S\). Its composition is uniform on \(S\). Therefore the gadget permits either of these allocations using only uniform \(h\)-clique coalitions:

• Mass two at every vertex.
• Mass one at vertex \(0\), and mass two at every other vertex.

4. Construction from a Boolean formula

Take an instance \(\varphi\) of \(\mathrm{3SAT}\) with \(m\geq 2\) clauses. Restricting to this case preserves hardness: clauses can be duplicated without changing satisfiability.

Construct a graph \(G\) with one vertex for each literal occurrence. Two vertices are adjacent exactly when they occur in different clauses and their literals are not complementary. Let \(n=|V(G)|\).

A clique contains at most one vertex from each clause, so \(\omega(G)\leq m\). Furthermore,
\(\varphi\) is satisfiable if and only if \(G\) has an \(m\)-vertex clique.

For completeness, a satisfying assignment supplies one true literal occurrence per clause; these form a clique. Conversely, an \(m\)-vertex clique selects one occurrence per clause and contains no complementary pair. Set all selected literals true and extend the assignment arbitrarily to the remaining variables. Every clause is satisfied.

Set \(h=m+1\). Construct \(H\) as follows:

• Retain \(G\), add a new vertex \(z\), and join \(z\) to every vertex of \(G\).
• For every vertex \(v\in V(G)\), attach a separate copy of \(F_h\), identifying its vertex \(0\) with \(v\). All its other vertices are new.
• Add no further edges.

The attached gadget copies have disjoint vertex sets: their identified vertices are distinct vertices of \(G\).

Any clique containing a private gadget vertex lies entirely in that gadget, because that vertex has no neighbors outside its gadget. Any clique containing no private gadget vertex lies in \(G\cup\{z\}\). Hence
\(\omega(H)\leq h\).
Each gadget contains an \(h\)-vertex clique, so in fact \(\omega(H)=h\).

The neighbors of \(z\) are exactly the original vertices of \(G\). Consequently,
\(z\) belongs to an \(h\)-vertex clique in \(H\) if and only if \(\varphi\) is satisfiable.

There are \(n(2h+1)\) vertices other than \(z\). Define
\(D=2n(2h+1)+1\).
The output instance has one type per vertex of \(H\), with
\(\mu_z=1/D\),
\(\mu_v=2/D\) for every \(v\neq z\),
\(W=A_H\),
and threshold
\(B=(h-1)/h\).

All masses are positive and sum to one. The graph has \(n(2h+1)+1\) vertices, and the rational numbers have polynomial encoding length. Thus this construction is computable in polynomial time.

5. Satisfiable formulas yield stable outcomes at the threshold

Suppose \(\varphi\) is satisfiable. Choose an \(m\)-vertex clique \(C\) in \(G\). Then \(C\cup\{z\}\) is an \(h\)-vertex clique.

First work with unnormalized masses: one at \(z\) and two at every other vertex.

Create a coalition receiving mass one from each vertex in \(C\cup\{z\}\). This exhausts \(z\). Each original vertex in \(C\) now has remaining mass one; every other vertex has remaining mass two.

Allocate the remaining masses within each attached gadget:

• If its identified vertex belongs to \(C\), use the second gadget identity from Section 3.
• Otherwise, use the first identity.

These identities allocate exactly the remaining masses. Every coalition is uniform on an \(h\)-vertex clique, and the collection is finite.

Finally, divide every allocated mass by \(D\). This gives precisely the specified masses \(\mu\), without changing coalition compositions. Section 2 proves that the outcome is stable and has welfare \(B\).

6. Unsatisfiable formulas admit no outcome at the threshold

Suppose some feasible outcome has welfare at least \(B\). Stability is not needed for this direction.

For each occupied coalition \(k\), define its composition \(p^k=x^k/q_k\). Each \(p^k\) is a probability vector, and feasibility gives \(\sum_k q_k=1\). Welfare is
\(\sum_k q_k(p^k)^{\mathsf T}A_Hp^k\).

Since \(\omega(H)=h\), Section 1 gives
\((p^k)^{\mathsf T}A_Hp^k\leq B\)
for every coalition. Therefore total welfare is at most \(B\). If it is at least \(B\), equality must hold in every occupied coalition: all coefficients \(q_k\) are strictly positive.

Because \(\mu_z>0\), at least one coalition satisfies \(p_z^k>0\). That coalition attains equality in the quadratic bound. Its equality property implies that \(z\) belongs to an \(h\)-vertex clique.

By the construction, this implies that \(\varphi\) is satisfiable. Thus, for an unsatisfiable formula, no feasible outcome—stable or otherwise—reaches \(B\). This argument covers arbitrary real coalition masses.

7. Complexity conclusion

The construction proves the equivalence:
\(\varphi\) is satisfiable if and only if the output instance has a stable outcome with welfare at least \(B\).

This is a polynomial-time many-one reduction from \(\mathrm{3SAT}\), establishing \(\mathrm{NP}\)-hardness under the restrictions stated at the beginning. Membership in \(\mathrm{NP}\) is not needed for this conclusion and is not asserted.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct. The reduction establishes \(\mathrm{NP}\)-hardness for the exact divisible-mass formulation, including arbitrary real splittings and any finite number of coalitions. No major or minor issues were found.

1. Quadratic bound and equality property

The support-reduction argument is valid.

• For nonadjacent supported vertices \(a,b\), the diagonal entries and the entry \(A_{ab}\) vanish. With their combined mass fixed, the objective is therefore affine in the redistributed mass.
• An endpoint with objective at least the current value exists. Moving to that endpoint removes one supported vertex, so the procedure terminates.
• The resulting support is a nonempty clique. For its size \(s\), the calculation \(r^{\mathsf T}Ar=1-\sum_{v\in C}r_v^2\) is correct. Cauchy–Schwarz and \(s\leq h\) give the stated bound.

The equality argument also holds. A vector attaining the upper bound is a global maximizer. When both coordinates are positive, the current redistribution parameter is interior to its feasible interval. An affine function cannot have an interior maximum unless it is constant, so either endpoint preserves equality.

The prescribed choice of endpoint preserves positive mass at \(z\). Every transfer reduces the support, and the final clique contains \(z\). Its size cannot be smaller than \(h\), because that would give a strictly smaller objective; it cannot exceed \(h\) by hypothesis. Thus the equality property is established as stated for the positive integer parameter used in the reduction.

The proof is self-contained; it does not rely on an unverified equality characterization from the cited theorem.

2. Stability and welfare of uniform clique coalitions

Both assertions are correct.

For a uniform composition on an \(h\)-vertex clique, a participating type has utility \((h-1)/h\). Against any other such coalition:

• If its type vertex lies in the clique, exactly \(h-1\) clique vertices are neighbors.
• If its type vertex lies outside the clique, adjacency to every clique vertex would contradict \(\omega(H)\leq h\).

Thus every participating type weakly prefers its own coalition to every occupied coalition. This verifies the precise stability definition, including types split among multiple coalitions.

Each composition has quadratic value \((h-1)/h\). Coalition welfare is its total mass multiplied by that value, so total welfare equals \((h-1)/h\) when total mass is one.

3. Remaining-mass gadget

The gadget claims and coefficients check out.

The successor map sends an independent set of the cycle injectively into its complement, establishing the upper bound \(h\). Each \(S_j\) has \(h\) distinct vertices and contains no consecutive cycle vertices, including across the modular boundary. Therefore the exhibited sets establish that the clique number is exactly \(h\).

Each vertex occurs in exactly \(h\) indexed sets \(S_j\). Consequently, the first identity assigns mass \(h(2/h)=2\) to each vertex.

In the second identity, the sum with coefficient \(1/h\) assigns mass one to every vertex. The sets \(S_1,S_2\) are disjoint and cover precisely the vertices other than \(0\). Their additional contributions therefore produce mass one at \(0\) and mass two elsewhere.

All coalition coefficients are positive. A term \(c\mathbf 1_S\) has total mass \(hc>0\) and uniform composition on its clique. Both identities consequently describe valid finite allocations. Possible repetition of a clique among the terms is harmless: the model permits distinct coalitions with identical compositions.

4. Formula encoding and graph construction

The standard literal-occurrence construction is correctly justified within the output.

An \(m\)-vertex clique chooses exactly one occurrence from each clause and cannot contain complementary literals. The selected literals can therefore all be made true simultaneously. Conversely, selecting a true literal from each clause under a satisfying assignment produces the required clique.

The restriction \(m\geq2\) does not affect hardness, and yields \(h=m+1\geq3\), within the gadget’s stated range.

The clique analysis of \(H\) is correct:

• Every private gadget vertex has no neighbors outside its own gadget, so any clique containing it lies within that gadget.
• Every clique without private vertices lies in \(G\cup\{z\}\), whose clique number is at most \(m+1=h\).
• A gadget supplies an \(h\)-vertex clique, establishing \(\omega(H)=h\).
• Since \(z\) has exactly the original vertices as neighbors, an \(h\)-vertex clique containing \(z\) is equivalent to an \(m\)-vertex clique in \(G\).

The vertex count is correct: each of the \(n\) original vertices accounts for itself and \(2h\) private vertices, giving \(n(2h+1)+1\) vertices including \(z\).

The masses sum to
\[ \frac{1+2n(2h+1)}{D}=1. \]
They are strictly positive rationals. The adjacency matrix is symmetric, binary, and has zero diagonal. Both its explicit size and the encoding lengths of all numerical parameters are polynomial in the formula size.

5. Satisfiable-instance allocation

The forward implication is fully established.

The initial coalition consumes one unit at \(z\) and one unit at each selected original vertex. Every selected original vertex consequently has one unit remaining; every other non-\(z\) vertex has two.

The attached gadgets have disjoint vertex sets, so applying their identities independently neither double-counts masses nor leaves any type unallocated. The chosen identity matches the remaining mass at each identified vertex exactly.

Dividing all allocations by \(D\) gives the specified feasible masses. Every coalition remains nonempty and uniform on an \(h\)-vertex clique. The verified stability argument therefore applies, and welfare is exactly \(B\).

6. Converse for arbitrary feasible outcomes

The converse correctly handles all outcomes permitted by the task.

For every occupied coalition, \(q_k>0\), so \(p^k=x^k/q_k\) is well-defined. Feasibility gives \(\sum_k q_k=1\), and the welfare expression is correctly rewritten as
\[ \sum_k q_k(p^k)^{\mathsf T}A_Hp^k. \]

Each quadratic value is at most \(B\). A finite weighted average with strictly positive weights can reach \(B\) only when every value equals \(B\). Thus the equality property applies to every occupied coalition in an outcome meeting the threshold.

Positive total mass at \(z\) guarantees an occupied coalition with positive \(z\)-coordinate. Its equality case forces an \(h\)-vertex clique containing \(z\), which forces satisfiability.

This argument does not assume rational coalition masses, a predetermined number of coalitions, clique-supported compositions, or stability. The stronger impossibility claim for unsatisfiable instances is justified.

7. Complexity conclusion and feedback

The construction is a polynomial-time many-one reduction with both directions proved. It establishes the requested \(\mathrm{NP}\)-hardness under the additional restrictions claimed by the prover.

Membership in \(\mathrm{NP}\) is neither needed nor asserted. No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩