Hedonic Games with Graph-restricted Communication

The strongest positive case is a high-multiplicity, atomless version of the paper’s star games. My lead anchor is Theorem 18, proved in this paper (with the PLS-hardness of LOCAL MAX-CUT used as the external starting point):

Given a symmetric additively separable hedonic graph game whose underlying graph is a star, finding an in-neighbor stable feasible partition is PLS-complete.

The paper proves membership in PLS using the symmetric welfare potential. Its hardness reduction maps a weighted LOCAL MAX-CUT instance \(G=(V,E,w)\) to a star with centre \(s\), setting \(U(u,s)=\sum_{v\in V}w(u,v)\) and \(U(u,v)=-2w(u,v)\). Every feasible partition places each \(u\in V\) either with \(s\) or alone, and an in-neighbor stable partition induces a locally optimal cut.

My continuous mirror is Typed Continuum In-Neighbor Stability on a Star. An instance consists of:

• finitely many types \(T=\{s\}\cup V\);
• rational masses \(\mu_t\ge 0\), with \(\sum_t\mu_t=1\);
• a star communication graph \(H\) on the types;
• a symmetric rational utility matrix \(U:T\times T\to\mathbb Q\).

There is a continuum of agents, with mass \(\mu_t\) of type \(t\). Agents of the same type have identical utilities and communication links. The star is therefore the type-level blow-up of the paper’s graph: with \(M\) copies of every role, the population has \(M|T|\) agents but only \(|T|\) types.

A feasible outcome is a finite measurable partition represented by mass vectors \(b^1,\ldots,b^q\), where \(b^k_t\) is the mass of type \(t\) in coalition \(k\), \(\sum_k b^k_t=\mu_t\), and each support \(\{t:b^k_t>0\}\) is connected in \(H\). An agent of type \(t\) in coalition \(b^k\) receives utility \(u_t(b^k)=\sum_r U(t,r)b^k_r\).

A small positive mass \(\delta\) of type \(t\) may move from \(b^k\) to \(b^\ell\) when the resulting support remains connected, its utility strictly increases, and every destination type \(r\) adjacent to \(t\) accepts the incoming mass. For additive utilities, the latter condition is exactly \(U(r,t)\ge 0\). The question is:

Find a feasible mass partition with no profitable accepted infinitesimal mass transfer.

This is not fractional coalition membership for an individual: every individual belongs to one integral coalition. Only the population measure is continuous. It is the limit of duplicating every original player into a large homogeneous cohort and letting one-player moves become arbitrarily small mass moves.

The mirror is especially credible because symmetric additively separable games have the continuum potential
\[ \Phi(\mathcal B)=\frac12\sum_k\sum_{t,r}U(t,r)b^k_tb^k_r. \]
The derivative of \(\Phi\) under a type-mass transfer is precisely the moving type’s utility difference. Thus the continuous question is the atomless analogue of the paper’s local-search problem, not a different welfare objective.

I would expect the fully splittable star version to be tractable, or at least to lie on the Class A/Class C boundary rather than inherit Theorem 18’s PLS-hardness. In the paper’s own LOCAL MAX-CUT construction, take equal masses \(\mu_s=\mu_v\) and place all centre mass in one coalition, together with \(x_v=\mu_v/2\) of every leaf type. Then each leaf type’s utility in the centre coalition is
\[ \mu_s\sum_u w(v,u)-2\sum_u w(v,u)x_u=0, \]
equal to its singleton utility. The centre accepts every leaf because \(U(s,v)\ge0\). Hence the fractional half-mass profile is already stable, even though the corresponding discrete problem is PLS-hard. The discrete local-search combinatorics have been removed by divisibility.

This generates useful follow-up questions: whether the general star problem reduces to a polynomial-size complementarity or convex-optimization formulation; whether hardness returns when a type may not split across coalitions; and whether trees with many connected type supports produce genuinely continuum-specific hardness.

The weakest point is the interpretation of in-neighbor approval. For a literally atomless individual, adding one agent has zero effect on the destination members, so approval would collapse. The mirror therefore uses marginal approval by a small positive mass, which is the natural high-multiplicity limit but is not a word-for-word copy of an individual deviation. If that co-modification is rejected, the safer conclusion is that this particular stability notion has no faithful atomless analogue. The population blow-up, type regime, utilities, feasible coalitions, and mass-transfer objective otherwise remain recognisably the authors’ problem.