| paper | Single-Agent Dynamics in Additively Separable Hedonic Games |
| authors | Felix Brandt, Martin Bullinger, Leo Tappe |
| venue | AAAI 2022 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 6
statement extracted from the paper’s text layer
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\).
An atomless typed ASHG with rational mass vector \(\mu\); decision variables are coalition templates \(z^\ell\) and their densities \(\rho_\ell\), constrained to realize \(\mu\), and the objective is existence of a stable partition under the paper's infinitesimal unilateral deviations and majority-consent rule.
The model has no proved finite/high-multiplicity equivalence: within-type utilities, the marginal vote convention, and the support bound \(Q\) are additional choices, and fractional splitting may invalidate the paper's gadgets.
fatal: False
The mirror covers the existence questions in Theorem 6 for MIS and MOS in AEGs and Theorem 8 for SMS and JMS in ASHGs, but leaves the convergence results of Theorems \(3\)–\(5\) and \(7\), Corollary \(1\), Propositions \(1\)–\(3\), and other existence results untouched.
The strongest mirror is a typed, atomless version of the paper’s majority-consent stability problem. My lead anchor is Theorem 6.
Take a finite set of complete agent types \(\mathcal T=[\tau]\), with rational masses \(\mu_a\ge 0\) summing to \(1\). A type contains everything relevant to coalition formation: its additive utility row and how every other type evaluates its presence. Thus \(v_{ab}\) is the utility contribution of one unit of type \(b\) to an agent of type \(a\), and two agents share a type only when they are indistinguishable in every utility and consent calculation.
A coalition is represented by a nonzero mass vector \(z\in[0,\mu]^\tau\). Its utility to a type-\(a\) agent is \(U_a(z)=\sum_b v_{ab}z_b\). A typed population partition is a finite-support measure \(\lambda=\sum_{\ell=1}^q\rho_\ell\delta_{z^\ell}\), where \(\rho_\ell\) is the mass or density of coalitions of template \(z^\ell\), satisfying \(\sum_\ell\rho_\ell z^\ell=\mu\). For a computational version, \(q\le Q\) is supplied as part of the instance and all masses may be required to be rational.
The deviation remains a single-agent deviation, not a positive-mass coalition deviation. A tagged infinitesimal type-\(a\) agent in a coalition \(z\) may move to an occupied coalition \(y\) if \(z_a>0\) and \(U_a(y)>U_a(z)\). The move does not change \(z\) or \(y\) in the atomless limit, but the affected coalition members’ votes are well defined by mass. Put \(\operatorname{in}_a(z)=\sum_{b:v_{ba}>0}z_b\) and \(\operatorname{out}_a(z)=\sum_{b:v_{ba}<0}z_b\). These are exactly the continuum limits of the paper’s favor-in and favor-out sets; zero valuations count for neither side.
The lead problem is:
\[ \mathrm{CMIS}_\infty^{\mathrm{AEG}} \]
Given \((\mathcal T,\mu,v,Q)\), with every \(v_{ab}\in\{-M,1\}\) for an explicit population scale \(M\), does there exist a finite-support typed partition \(\lambda\) with at most \(Q\) templates and no admissible majority-in deviation? Formally, no occupied \(z,y\) and type \(a\) may satisfy \(z_a>0\), \(U_a(y)>U_a(z)\), and \(\operatorname{in}_a(y)\ge\operatorname{out}_a(y)\).
This is a direct population analogue of the MIS part of Theorem 6: “It is NP-complete to decide if there exists an MIS partition in AEGs.” Theorem 6 is proved in this paper, not cited from elsewhere. The corresponding MOS version is obtained by replacing the last inequality with \(\operatorname{out}_a(z)\ge\operatorname{in}_a(z)\).
The natural regime is a large workforce repeatedly forming project teams: for example, a national emergency-response or engineering organisation with many agents in each recurring skill, affiliation, and compatibility profile. The population may have \(M\) members but only \(\tau\) role-types, with \(\tau\ll M\). AEG utilities are plausible here as a coarse model in which a hard incompatibility outweighs every possible soft benefit. The coalition templates describe recurring team compositions, and majority-in consent says that a prospective team must not be opposed by more than half of its current mass.
I expect \(\mathrm{CMIS}_\infty^{\mathrm{AEG}}\) to retain hardness when \(\tau\) is part of the input: a Class B candidate. The combinatorial object in Theorem 6 is the directed friend/enemy compatibility structure and the majority inequalities, not the names of the individual agents. Replacing each repeated role by a mass should therefore preserve the core obstruction. A plausible lifting theorem would replace each reduction vertex by a large homogeneous cohort and clear denominators; the \(-M\) enemy value ensures that the relevant preference comparisons survive this scaling. For fixed \(\tau\), however, I would expect a substantially easier problem, perhaps fixed-parameter tractable through a finite arrangement of coalition-profile regions. That boundary is itself a useful continuization question.
The second anchor is Theorem 8, also proved in this paper: “Deciding whether an ASHG contains an SMS (respectively, JMS) partition is NP-complete.” Its continuous counterpart is:
\[ \mathrm{CJMS}_\infty \]
Given a rational typed population \((\mathcal T,\mu,v,Q)\) with arbitrary rational additive utility matrix \(v\), does there exist a finite-support typed partition \(\lambda\) with no joint-majority deviation? A move \(z\to y\) by type \(a\) is forbidden precisely when \(z_a>0\), \(U_a(y)>U_a(z)\), and \(\operatorname{out}_a(z)+\operatorname{in}_a(y)\ge \operatorname{in}_a(z)+\operatorname{out}_a(y)\). The SMS version requires both \(\operatorname{in}_a(y)\ge\operatorname{out}_a(y)\) and \(\operatorname{out}_a(z)\ge\operatorname{in}_a(z)\).
This is recognisably the same problem: additive coalition utilities, unilateral moves, and the paper’s exact consent rule are retained. Only the population representation changes from named agents to rational masses. I would again expect hardness in the variable-\(\tau\) typed model, because the hard part can live in the compatibility and utility matrix rather than in population multiplicity. The continuous version may nevertheless become tractable for fixed \(\tau\), since agents of one type can be split among several coalition templates. If hardness survives even after that fractional splitting, it would be an especially interesting Class C result; my prior is that the variable-type problem is Class B, with a possible Class A boundary at bounded type complexity.
The finite/high-multiplicity dictionary is concrete. If \(\mu_a=n_a/M\), a finite partition can be converted into a typed partition by replacing a coalition containing \(k_a\) members of type \(a\) with \(z_a=k_a/M\). Conversely, rational profiles can have denominators cleared to obtain a large finite cloned population. Multiplying the continuous utility \(U_a(z)\) by \(M\) recovers the original additive utility comparison, including AEG values \(\{-M,1\}\). Majority counts become majority masses. Ties should retain the paper’s weak inequalities, since boundary cases are part of the source problem.
The mirror covers the existence problems in Theorems 6 and 8. It does not claim to continuize the paper’s dynamics directly. A single infinitesimal move does not change the population state, so the paper’s finite-round convergence results, such as Corollary 1, would require a separate mass-flow or positive-packet dynamics. Nor does it cover arbitrary identity-sensitive ASHGs: if every agent has a unique utility row, then \(\tau\) is essentially \(M\), and the population compression has disappeared.
That is also the weakest point. The paper’s reductions do not themselves establish that the hard instances are block-homogeneous with \(\tau\ll M\). They may rely on finely differentiated named agents, and fractional splitting among identical types may destroy the gadgets. The tagged-infinitesimal semantics and finite-support coalition measure are therefore a carefully controlled extension, not a theorem already implied by Theorems 6 or 8.
Nevertheless, the extension is minimal and author-recognisable: it preserves the paper’s additive utilities, coalition profiles, unilateral deviations, and exact majority rules. It asks the central ChoCo question directly—whether NP-completeness caused by individual population structure survives when society consists of large masses of indistinguishable agent-types. The key follow-ups are whether hardness can be lifted with \(\tau\ll M\), whether bounded-\(\tau\) instances admit an LP or configuration algorithm, how ties and approximate stability should be rounded back to finite populations, and whether a nontrivial aggregate dynamics can inherit any part of the paper’s Deviation Lemma.
The strongest negative case is that the proposed mirrors have not yet identified a genuine continuum limit of the paper’s problem. They have identified a plausible new typed coalition-formation model, but that is weaker.
Theorem 6 is the better anchor, yet its MIS and MOS results do not transfer merely by replacing counts with masses. In the finite game, a deviation by \(i\) changes both coalitions by one agent, and for every incumbent \(j\),
\[ v_j(C\cup\{i\})-v_j(C\setminus\{i\})=v_j(i). \]
In the proposed atomless model, moving one tagged agent changes a coalition from \(z\) to \(z+\varepsilon e_a\), so the aggregate utility change is \(\varepsilon v_{ba}\), which vanishes as \(\varepsilon\to0\). The proposed majority rule nevertheless retains the sign of \(v_{ba}\) as a non-vanishing vote. That may be a sensible marginal-preference convention, but it is an additional modelling choice, not the limit of the displayed aggregate utility function.
The finite/high-multiplicity dictionary does not resolve this. To clone an agent, one must decide how clones value one another. Giving them value \(0\) imitates the original agent’s self-value but leaves the AEG class, whose off-diagonal values are restricted to \(\{-n,1\}\). Giving same-type clones value \(1\) or \(-n\) changes every clone’s baseline utility and can destroy the gadget. Theorem 6’s four-agent constructions therefore do not automatically survive cloning. Nor does denominator clearing establish equivalence: a typed continuum permits a type to be split among several coalition templates, creating fractional arrangements unavailable in the original instance.
The bound \(Q\) exposes the same problem from another direction. If \(Q\) is fixed, the model excludes finite high-multiplicity partitions containing many small coalitions, including natural singleton-like configurations. If \(Q\) grows with the population, the supposed continuum retains the discrete number of coalitions. If arbitrary finite support is allowed, the input and certificate-size conventions become part of the new problem. None of these choices is supplied by the paper.
Theorem 8 is even less secure. Its hardness concerns arbitrary, generally identity-specific utility matrices. A one-type-per-agent blow-up preserves that structure only by taking \(\tau\) proportional to the number of original agents. That is cloning a finite graph, not a demonstrated regime with a small collection of recurring population types. If one requires \(\tau\ll M\), as the proposed workforce interpretation suggests, the paper gives no reduction at all. Fractionally distributing each repeated type across coalition templates may also eliminate the obstruction behind the NP-completeness proof. The same objections apply to both JMS and SMS.
One could repair these defects: define clone-neutral within-type utilities, formulate marginal consent separately from aggregate utility, prove a finite-support theorem, and then establish hardness or tractability for the resulting model. But those repairs produce new coalition-flow problems rather than continuous versions already anchored by Theorems 6 and 8. The proposed questions may be worthwhile, but their value would come from inventing and analysing this new model, not from continuizing a computational result of the paper.
That is the strongest honest negative case. It is enough to reject the proponent’s claim that the two anchors already support a continuous mirror. It is not enough to prove the requested universal conclusion. A typed repeated-team scenario with explicitly defined clone-neutral utilities remains a plausible author-recognisable mirror, so claiming that no worthwhile mirror exists in any scenario would overreach.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.