| paper | Individually Stable Dynamics in Coalition Formation over Graphs |
| authors | Angelo Fanelli, Laurent Gourvès, Ayumi Igarashi, Luca Moscardelli |
| venue | AAAI 2025 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | no |
The paper does pass bit (a): its numbered theorems and proposition establish computational termination and deviation-time results, even though the cited PLS result is not original. However, every proposed mirror places mass on complete finite-game configurations; disconnected copies yield an ensemble or direct sum, while player-type marginals cannot preserve adjacency, coalition correlations, or unilateral moves. This changes the population unit, so no qualifying continuous analogue survives under ChoCo.
fails bit b — no continuous question survives
The mass distribution is over whole local game states rather than agents, and replication across disconnected copies leaves each finite dynamics problem unchanged.
fatal: True
The attempted construction targets Theorem 5.2, Theorem 4.1, and Proposition 5.9; no accepted mirror covers the remaining convergence results.
The paper has no named NP-hard, P, or parameterized-complexity theorem of its own; the PLS-completeness result mentioned in the related work is cited from Gairing and Savani (2010). It does, however, contain named computational results about convergence and convergence time. Those are enough for a credible mirror.
The strongest mirror is a high-multiplicity population of repeated local games. Let \(H=(R,E)\) be a fixed tree with \(q\) role types. A role specifies its position in \(H\), all LAS values \(v_{rs}\), and every other parameter relevant to its preference. Construct \(K\) disjoint copies of \(H\), with \(K\gg q\), all having the same role template. This models, for example, many geographically separate but structurally identical teams, wards, or local organizations undergoing coalition formation independently. The paper explicitly notes that disconnected components can be treated separately, so this is not changing the local game.
Let \(\Omega_H\) be the finite set of feasible partitions of one copy of \(H\). A continuous society is a rational distribution \(\nu\) over \(\Omega_H\): \(\nu_\pi\) is the fraction of local games currently in state \(\pi\). Equivalently, after clearing denominators, \(\nu\) describes \(K\) repeated copies with \(\nu_\pi K\) copies in state \(\pi\). No coalition is fractional: each unit of mass is a whole copy of the original graph game. The operational type is therefore a complete local configuration—template, role identities, graph, preferences, and current partition—so agents that are aggregated really are interchangeable.
For every \(\pi\in\Omega_H\), construct the exact IS-transition graph \(D_H\): an edge \(\pi\to\pi'\) exists for every unilateral deviation permitted by Algorithm 1, including the paper’s prescribed reconnection of the departing coalition. A mass action transfers rational mass \(a\) from state \(\pi\) to state \(\pi'\) along such an edge. The natural objective is normalized convergence time: every unit of mass taking one local IS deviation contributes one unit. Thus the total cost is the average number of deviations made by the repeated local games.
The following is the lead problem.
Tree-LAS Mass-IS Time. Given a tree \(H\), rational LAS values, an initial rational distribution \(\nu\) over feasible local partitions, and a binary threshold \(B\), compute the maximum total mass-weighted number of IS deviations before all mass reaches IS states. Return \(+\infty\) if some positive mass can be routed around a directed cycle. A solution is either a reachable cycle or a mass flow \(f\) on \(D_H\) satisfying flow conservation: initial mass plus incoming flow equals outgoing flow plus residual mass, with residual mass permitted only at IS-sink states. The objective is \(\sum_e f_e\).
This is the continuous analogue of running the paper’s exact dynamics independently on a high-multiplicity collection of identical graph games. The strongest anchor is Theorem 5.2, proved in this paper: “in a graph hedonic game with LAS preferences over a tree the IS dynamics always converge.” In the mirror, it predicts that \(D_H\) is acyclic and therefore the mass-time problem is finite. In the explicit configuration representation, the problem is a maximum-cost flow and is therefore Class A. The interesting remaining question is whether the exponential configuration graph admits a compact separation or dynamic-programming representation in \(q\); that part could instead be Class B, since the combinatorics live in the tree and coalition structure, not in population multiplicity.
This mirror is recognisable to the authors: graph feasibility, unilateral improvement, unanimous acceptance, LAS preferences, arbitrary initial states, and the exact reconnection rule are all retained. Only the number of repeated copies has been continuized.
A second, independent anchor is Theorem 4.1, also proved here. It states that on a star, under individually rational preferences, IS dynamics converge in \(O(n^2)\) steps. The corresponding problem is:
Star-IR Mass-IS Time. Given a star template with \(q\) roles, rational individually rational preferences, and a rational distribution over initial feasible partitions of repeated star copies, compute the maximum average number of IS deviations before all copies reach individually stable states.
The solution is the same kind of mass flow, now restricted to the star transition graph. Theorem 4.1 gives the pointwise bound \(O(q^2)\) for every copy, hence the continuous average is also \(O(q^2)\), independently of \(K\). I would expect this to be Class A in the explicit-type regime, with a worthwhile open question being whether the bound and the optimum can be computed directly from a compressed description of the star rather than by expanding its configuration states. This is a particularly clean mirror because the high-multiplicity population gain is obvious: millions of identical local star-games can be summarized by the distribution of their coalition states.
The third useful anchor is the negative boundary, Proposition 5.9, proved here. It states that on trees with LAS preferences, the IS dynamics may require an exponential number of deviations before converging. Its continuous problem is:
Tree-LAS Mass-IS Long-Run Threshold. Given a LAS tree instance, an initial partition \(\pi_0\), and a binary \(B\), decide whether the mass-time value of the point distribution \(\nu_{\pi_0}=1\) is at least \(B\), or whether it is infinite.
The proposition transfers directly: take every repeated copy to start in the paper’s hard initial state. The normalized mass-time is then exactly the number of deviations of that local instance, so it can be exponential in the number \(q\) of distinct roles even though \(K\) has disappeared from the representation. I would classify the succinct version as likely Class B: the difficulty is carried by the tree topology and coalition-state dynamics, not by population individuation. I would not claim an NP-hardness theorem from Proposition 5.9 alone; what it securely provides is an exponential lower bound and a clear warning that continuization does not automatically make the dynamics easy.
This mirror covers the paper’s central convergence results—Theorem 5.2, Theorem 4.1, and Proposition 5.9—rather than its entire table. It also generates natural further questions: whether the mass-flow problem has a compact pricing oracle; whether best-response rather than arbitrary better-response mass dynamics improve the bounds; whether changing the reconnection rule changes the continuous complexity; and whether one can define a genuine single-graph atomless limit with role masses while retaining individual stability.
My weakest point is that this is a cohort-state mirror rather than the naive limit of one enormous connected graph. The population mass is attached to repeated complete local games, and the aggregate state records correlations inside each game. An opponent can therefore say that this is a structured high-multiplicity extension, not a fully atomless graph-hedonic society. I think that criticism is real, but not fatal: it preserves the paper’s exact computational object and has a plausible regime with \(Kq\) agents, \(q\) roles, and \(K\) arbitrarily large. A direct atomless role-mass model would erase individual deviations or require positive-mass deviations, changing the game substantially; I would not pretend otherwise. The repeated-component mirror is the honest positive case because it makes population continuity genuine while preserving topology, identities, unilateral IS semantics, and the paper’s named convergence results.
The proponent’s construction is clever, but it continuizes the number of complete games, not the society of players inside a game. That distinction is fatal under ChoCo’s scope.
The distribution \(\nu\) is not a distribution over player types. It is a distribution over complete partitions of an entire finite graph. If one instead uses the role distribution over the \(q\) players, that distribution does not determine the state: adjacency, coalition membership, and correlations between players are essential to deciding which IS deviations exist. Adding the full partition to the “type” repairs this only by making the type a whole \(q\)-player microgame. The resulting mass flow is a distribution over finite game states—effectively a randomized initial condition or an ensemble of independent experiments—not a continuous society whose agents interact.
The repeated-copy construction therefore does not provide a genuine high-multiplicity version of the paper’s game. The copies are disconnected, and the paper itself says disconnected components can be treated separately. No agent in one copy can join, accept, or affect a coalition in another. The aggregate problem decomposes into the independent problems for each copy; \(K\) is merely a replication index. This is a perfectly sensible ensemble-dynamics problem, but it is not population continuization in the programme’s sense. Indeed, the same construction could turn any finite transition system into a “continuous” mass-flow problem, regardless of whether its states represented agents, games, or computer configurations.
A more ambitious mirror with one large connected graph does not repair matters. A marginal distribution of repeated roles cannot specify the graph relation: the same role counts can produce different trees, different coalition possibilities, and different IS dynamics. One must retain a typed network or a joint measure over graph locations and coalition configurations. That is a graph-limit or network-dynamics model, not the paper’s finite-type society. In an atomless version, a unilateral move has zero mass and leaves the aggregate state unchanged; allowing a positive mass to move turns an individual deviation into a coordinated block deviation. Either way, the paper’s IS semantics disappear.
This defeats Theorem 5.2. In the proposed mirror, acyclicity of \(D_H\) simply says that each finite component has no cyclic execution; the mass-flow problem is a direct sum of those finite executions. A genuine atomless-tree version would need new state variables and new deviation semantics, so Theorem 5.2 would no longer be the result being mirrored.
Theorem 4.1 is no stronger. A large star with many identical leaves is the best direct candidate, but it has one exceptional centre controlling coalitions of a continuum of leaves. Individual leaf moves change zero mass, while a positive-mass move is not unilateral. Moreover, the theorem counts individual deviations, and the continuum supplies no canonical time unit: raw step count diverges, whereas normalized average time is an externally chosen ensemble normalization. Keeping the centre as a special institution may produce an interesting leader–followers model, but it is a new model rather than a continuous mirror of the theorem’s general IR star result.
Proposition 5.9 is the weakest anchor. Taking \(\nu_{\pi_0}=1\) merely embeds the original finite hard trajectory as a point mass. Replicating that point mass across \(K\) copies adds no continuous content; it only repeats the same exponential execution. If a delta distribution over one finite instance counts, then every finite dynamics theorem automatically has a “continuous mirror,” which makes the criterion vacuous.
The absence of an NP-hardness or polynomial-time theorem in the paper is not by itself decisive: its named convergence and runtime theorems are legitimate computational results. The real problem is that all three proposed mirrors obtain continuity by moving from agents to whole game states. There is a plausible application for many independent, structurally identical local teams, and that could support a paper on ensemble dynamics or high-multiplicity transition systems. But it does not make the population of this paper continuous. Under ChoCo’s narrower definition, none of the three anchors survives.
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.