Single-Agent Dynamics in Additively Separable Hedonic Games (aaai22-20415)

Given a finite type set \(\mathcal T\), rational masses \(\mu\) with \(\sum_a\mu_a=1\), rational AEG utilities \(v_{ab}\in\{-M,1\}\), and a support bound \(Q\), decide whether there exists a finite-support partition \(\lambda=\sum_{\ell=1}^{q}\rho_\ell\delta_{z^\ell}\), with \(q\le Q\) and \(\sum_{\ell}\rho_\ell z^\ell=\mu\), such that no occupied coalition \(z\) admits a type-\(a\) move to an occupied coalition \(y\) satisfying \(z_a>0\), \(U_a(y)>U_a(z)\), and \(\operatorname{in}_a(y)\ge\operatorname{out}_a(y)\), where \(U_a(z)=\sum_bv_{ab}z_b\), \(\operatorname{in}_a(y)=\sum_{b:v_{ba}>0}y_b\), and \(\operatorname{out}_a(y)=\sum_{b:v_{ba}<0}y_b\).

A society is given by its support: a list \(\mathcal T\) of \(\tau\ge1\) types with positive binary rational masses \(\mu_a\), where \(\sum_a\mu_a=1\); \(\tau\) counts listed types, not possible types. Input also includes a rational \(M\ge1\), directed valuations \(v_{ab}\in\{-M,1\}\), and a binary integer \(Q\ge1\).
A coalition is a real vector \(z\) with \(0\le z_a\le\mu_a\) and \(z\ne0\). A partition is a finite positive measure \(\lambda=\sum_{\ell=1}^{q}\rho_\ell\delta_{z^\ell}\), with distinct coalition vectors, real weights \(\rho_\ell>0\), \(1\le q\le Q\), and \(\sum_\ell\rho_\ell z^\ell=\mu\); the weights need not sum to one.
Define \(U_a(z)=\sum_bv_{ab}z_b\), \(\operatorname{in}_a(y)=\sum_{b:v_{ba}>0}y_b\), and \(\operatorname{out}_a(y)=\sum_{b:v_{ba}<0}y_b\). Diagonal valuations describe interactions between distinct members of the same type; an individual's own mass is zero.
A partition is majority-in stable if no occupied \(z\), type \(a\) with \(z_a>0\), and destination \(y\) satisfy both \(U_a(y)>U_a(z)\) and \(\operatorname{in}_a(y)\ge\operatorname{out}_a(y)\). Destinations are other occupied coalitions and \(y=0\), representing singleton formation; hence stability also requires \(U_a(z)\ge0\) whenever \(z_a>0\). Moves are infinitesimal, require no consent from the abandoned coalition, and are tested regardless of the support bound after the move.
Is deciding whether such a majority-in stable partition exists solvable in polynomial time, or is it NP-hard? Measure running time in \(\tau\) and total binary input length \(L\), including the encodings of \(M\) and \(Q\); there is no separate candidate parameter \(m\).
For finite societies of \(n\) agents with off-diagonal valuations \(\{-n,1\}\), existence of a majority-in stable partition is NP-complete. No result settling this exact continuous problem was identified in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-hard, even when \(Q=3\), all masses are equal, valuations are symmetric, every diagonal valuation is \(1\), and \(M=3\tau\).

We prove this by a polynomial-time reduction from graph 3-colorability, a classical \(\mathrm{NP}\)-complete problem. See [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975%2876%2990059-1).

1. Construction

Let \(G=(V,E)\) be a simple undirected graph with \(n\ge1\) vertices. Construct one type per vertex and set

\(\tau=n,\qquad \mu_a=1/n,\qquad Q=3,\qquad M=3n.\)

Define the valuations by

\(v_{ab}=-3n\) if \(\{a,b\}\in E\), and \(v_{ab}=1\) otherwise.

In particular, \(v_{aa}=1\). These diagonal valuations are permitted by the stated model.

We will prove that \(G\) is 3-colorable if and only if the constructed society admits a majority-in stable partition with at most three occupied coalition vectors.

2. A stable partition yields a 3-coloring

Suppose such a partition exists:

\(\lambda=\sum_{\ell=1}^{q}\rho_\ell\delta_{z^\ell},\qquad 1\le q\le3.\)

Define the contributed mass vectors \(x^\ell=\rho_\ell z^\ell\). Population conservation gives

\(\sum_{\ell=1}^{q}x^\ell_a=1/n\quad\text{for every }a.\)

All their coordinates are nonnegative. Consequently, writing \(s_\ell=\sum_bx^\ell_b\), we have

\(\sum_{\ell=1}^{q}s_\ell=1,\qquad s_\ell\le1.\)

Singleton formation is always accepted because \(\operatorname{in}_a(0)=\operatorname{out}_a(0)=0\). Stability therefore requires \(U_a(z^\ell)\ge0\) whenever \(z^\ell_a>0\). Since \(\rho_\ell>0\) and utilities are linear,

\(x^\ell_a>0\quad\Longrightarrow\quad U_a(x^\ell)=\rho_\ell U_a(z^\ell)\ge0.\)

For each vertex \(a\), choose an index \(c(a)\) maximizing \(x^\ell_a\), breaking ties arbitrarily. Then

\(x^{c(a)}_a\ge1/(nq)\ge1/(3n).\)

We claim that \(c\) is a proper coloring. Suppose instead that an edge \(\{a,b\}\in E\) has \(c(a)=c(b)=\ell\). Both \(x^\ell_a\) and \(x^\ell_b\) are positive. By the valuation construction,

\(U_a(x^\ell)=s_\ell-(3n+1)\sum_{d:\{a,d\}\in E}x^\ell_d.\)

Because \(b\) is a neighbor of \(a\),

\(U_a(x^\ell)\le1-(3n+1)x^\ell_b\le1-(3n+1)/(3n)=-1/(3n)<0.\)

This contradicts the required nonnegative utility for type \(a\). Thus \(c\) is a proper coloring using at most three colors.

This argument allows arbitrary real weights and arbitrary splitting of every type.

3. A 3-coloring yields a stable partition

Suppose \(G\) is 3-colorable. Among its proper colorings with three labeled colors, choose one maximizing

\(\Phi=|C_1|^2+|C_2|^2+|C_3|^2,\)

where empty color classes are allowed. Such a maximum exists because there are finitely many colorings.

For each nonempty color class \(C_i\), define \(z^i_a=1/n\) when \(a\in C_i\), and \(z^i_a=0\) otherwise. Give each coalition weight \(1\).

These vectors are nonzero, distinct, satisfy \(0\le z^i_a\le\mu_a\), and sum to \(\mu\). Hence they define a valid partition with at most three occupied vectors.

Fix \(a\in C_i\), and write \(s=|C_i|\). Since \(C_i\) is independent, every valuation from \(a\) toward a type in \(C_i\) equals \(1\). Therefore

\(U_a(z^i)=s/n>0.\)

Singleton formation cannot improve this utility.

Consider another occupied coalition \(z^j\), and write \(t=|C_j|\). There are two cases.

The destination contains a neighbor of \(a\). Let \(r\ge1\) be the number of these neighbors. Then

\(U_a(z^j)=\bigl(t-(3n+1)r\bigr)/n\le\bigl(n-(3n+1)\bigr)/n<0.\)

Thus this destination cannot improve utility.

The destination contains no neighbor of \(a\). Then \(U_a(z^j)=t/n\). A strict improvement would require \(t>s\).

However, moving vertex \(a\) from \(C_i\) to \(C_j\) preserves proper coloring: the destination contains no neighbor of \(a\), and removing a vertex preserves independence of the source. The change in the coloring potential would be

\((s-1)^2+(t+1)^2-s^2-t^2=2(t-s+1)>0.\)

This contradicts maximality of \(\Phi\). Hence this destination also cannot strictly improve utility.

We have exhausted all destinations. The constructed partition admits no strictly profitable infinitesimal move, even before checking majority acceptance, so it is majority-in stable. The whole-vertex recoloring above is only an argument for selecting the coloring; it does not change the model’s move semantics.

4. Complexity conclusion

The construction has \(\tau=n\) types, \(n^2\) valuation entries, rational masses \(1/n\), integer \(M=3n\), and constant \(Q=3\). Its total binary encoding length is polynomial in the graph input size; a direct encoding uses \(O(n^2\log n)\) bits.

Both directions of the reduction are proved. Therefore the requested decision problem is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(\tau\) and \(L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the task: the continuous decision problem is \(\mathrm{NP}\)-hard under the stated restrictions. I found no major or minor mathematical gaps.

• Source problem and reduction target.

The invoked theorem is that deciding whether a finite simple undirected graph admits a proper coloring with at most three colors is \(\mathrm{NP}\)-complete. This is the standard graph 3-colorability problem treated in the [cited paper by Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1). The reduction uses precisely this problem. Restricting to nonempty graphs does not affect its hardness.

The claimed target is \(\mathrm{NP}\)-hardness, not membership in \(\mathrm{NP}\). Consequently, the proof does not need to establish bounded rational certificates for arbitrary feasible continuous partitions.

• Validity of the constructed input.

For every graph with \(n\ge1\), the construction satisfies all input requirements:

• There are exactly \(\tau=n\) listed types.
• Each mass \(1/n\) is a positive binary-encoded rational, and the masses sum to one.
• \(M=3n\ge1\) and \(Q=3\) are valid binary-encoded integers.
• Every valuation belongs to \(\{-M,1\}\).
• Valuations are symmetric because the graph is undirected.
• Every diagonal valuation is \(1\) because the graph is simple.

The diagonal contribution used later agrees with the task’s utility definition: interactions with other members of the same type contribute, while an individual’s own mass is zero.

• Population conservation with arbitrary real weights.

Defining \(x^\ell=\rho_\ell z^\ell\) is legitimate because every \(\rho_\ell>0\). The partition constraint gives
\[ \sum_{\ell=1}^{q}x^\ell_a=\frac1n. \]
Every coordinate is nonnegative. Therefore, with \(s_\ell=\sum_bx^\ell_b\), the statements
\[ \sum_{\ell=1}^{q}s_\ell=1,\qquad s_\ell\le1 \]
follow directly.

The proof does not treat the vectors \(x^\ell\) as permissible destination coalitions. It uses them only for conservation and linear utility calculations. Thus scaling by possibly large real weights introduces no domain error.

• Necessary nonnegative utilities.

The zero destination satisfies majority acceptance because both incoming and outgoing mass equal zero. Since \(U_a(0)=0\), stability implies \(U_a(z^\ell)\ge0\) whenever \(z^\ell_a>0\).

Positivity of \(\rho_\ell\) preserves the occupied coordinates and utility signs. Hence the claimed implication
\[ x^\ell_a>0\ \Longrightarrow\ U_a(x^\ell)\ge0 \]
is valid.

• Extraction of a proper coloring.

For each vertex, a maximizing index exists because \(1\le q\le3\). Conservation implies
\[ x^{c(a)}_a\ge\frac1{nq}\ge\frac1{3n}. \]
This bound remains valid under arbitrary splitting and arbitrary tie-breaking.

If adjacent vertices \(a,b\) receive the same index \(\ell\), both corresponding coordinates are positive. The displayed utility identity correctly starts from valuation \(1\) for every coordinate and subtracts \(3n+1\) for each neighbor:
\[ U_a(x^\ell)=s_\ell-(3n+1)\sum_{d:\{a,d\}\in E}x^\ell_d. \]
Using \(s_\ell\le1\) and the lower bound on \(x^\ell_b\) yields
\[ U_a(x^\ell)\le1-\frac{3n+1}{3n}=-\frac1{3n}<0. \]
This contradicts Step 4. The extracted coloring is therefore proper.

• Existence and validity of the partition from a coloring.

The potential maximizer exists because the set of proper colorings with three labeled colors is finite and nonempty. Allowing empty classes is consistent with coloring using at most three colors.

Each nonempty class produces a nonzero coalition within the coordinate bounds. Different nonempty classes yield distinct vectors, and assigning weight one gives exact population conservation. There is at least one occupied vector and at most three.

Selecting a potential-maximizing coloring is used only to prove existence of a stable partition. The reduction itself constructs the society directly from the graph; it does not require computing that coloring.

• Verification of every destination.

For an occupied type in a class of size \(s\), independence gives current utility \(s/n>0\). Singleton formation therefore cannot improve utility.

For another occupied class of size \(t\) containing \(r\ge1\) neighbors, the utility calculation is correct:
\[ U_a(z^j)=\frac{t-(3n+1)r}{n}<0, \]
using \(t\le n\). Such a destination cannot improve the positive current utility.

If the destination contains no neighbor, its utility is \(t/n\), so strict improvement requires \(t>s\). The proposed recoloring preserves properness, including when the source class becomes empty. The potential difference is correctly computed as
\[ (s-1)^2+(t+1)^2-s^2-t^2=2(t-s+1), \]
which is positive under \(t>s\). Maximality excludes this case.

These cases exhaust all destinations specified in the task. Since none offers a strict utility improvement, majority acceptance cannot produce a blocking move. The recoloring argument is solely a comparison between colorings and does not substitute a whole-vertex move for the model’s infinitesimal move.

• Encoding and complexity conclusion.

The construction writes \(n^2\) valuations and rational masses whose encodings have logarithmic length in \(n\). Its stated asymptotic encoding bound is polynomial in the standard explicit graph input length, and the construction is polynomial-time.

Both implications are established for the exact continuous model, including arbitrary real weights and type splitting. Thus the restricted instances already establish \(\mathrm{NP}\)-hardness in the requested input parameters \(\tau\) and \(L\).

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩