| paper | d4-conf-aaai-2021-2035 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 3.3 is a computational result, but its dynamics depends on individual agents changing coalition sizes. In an atomless population those moves leave the mass profile unchanged; the proposed positive-mass transfers instead permit collective moves and can skip consent-blocked intermediate states. That is a different dynamics, not a continuous analogue of the anchored result.
fails bit b-changes — the continuum limit changes the question
The proposed model aimed to mirror Theorem 3.3’s AHG path and convergence hardness results; it did not address the paper’s other results, and its changed move rule prevents that coverage from counting as a mirror.
The strongest mirror is the anonymous hedonic game result, Theorem 3.3. Proved in this paper, with separate reductions in Appendix Lemmas A.1 and A.2, it says that deciding whether some sequence of individually stable deviations reaches an individually stable partition is NP-hard, and deciding whether every such sequence reaches one is co-NP-hard, even with strict preferences. The reductions are from (3,B2)-SAT. The hardness is about the dynamics and its starting partition, not merely about finding a stable partition. ([Theorem 3.3 in the paper](https://pub.dss.in.tum.de/brandt-research/individual.pdf))
Here is a continuous version I would be willing to defend. The population has a finite set \(T\) of preference types, with \(|T|=\tau\). Type \(t\) is a complete, strict ranking \(\succ_t\) of rational coalition shares in \((0,1]\); it describes everything relevant about an agent’s preferences. The input gives rational masses \(\mu_t\geq 0\), summing to \(1\), and an initial partition into finitely many coalitions. Coalition \(a\) is represented by a vector \(x^a\in\mathbb Q_{\geq 0}^{\tau}\), where \(x^a_t\) is the mass of type \(t\) in it, and \(\sum_a x^a_t=\mu_t\). A finite comparison program for each type specifies its ranking on rational shares.
A move chooses a source coalition \(a\), a destination \(b\) (or a new coalition), a type \(t\), and a rational mass \(\delta>0\) to transfer, with \(\delta\leq x^a_t\). The movers must prefer the destination’s resulting share, \(\lVert x^b\rVert_1+\delta\), to their source share, \(\lVert x^a\rVert_1\). Every type \(u\) already in \(b\) must weakly prefer its new share to its old one: \(\lVert x^b\rVert_1+\delta\succeq_u\lVert x^b\rVert_1\). For a new coalition that consent condition is vacuous; if the source empties, it disappears. A terminal state has no such move.
This gives two concrete questions, one for each clause of Theorem 3.3:
A plausible regime is a large membership organization whose members form communities: millions of people, but relatively few preference types, each with a shared ranking over community size as a fraction of the population. For instance, members may share a preference for smaller or larger groups. The initial partition records how much of each type belongs to each community. Thus \(n\), the number of people, can be much larger than \(\tau\). The paper’s anonymous model is a good fit for this story because agents already care only about coalition size, not its members’ identities.
I would initially expect Mass-IS-Path to be Class B, with hardness transferring. In the AHG reduction, the formula’s logical structure appears in the clause-, variable-, and literal-linked preference types; the large dummy populations create separated coalition-size landmarks. The number of types grows with the formula, while the many identical dummies supply multiplicity. Those landmarks can be represented as exact rational shares. A guarded-grid construction—preserving the ranking at those shares and preventing off-grid moves from helping—looks like a plausible route to a reduction. It is not already proved: fractional transfers could split a type cohort and create paths unavailable in the integer model.
For Mass-IS-Convergence, I would expect Class C unless a guarded-grid argument rules out a new source of nontermination. The discrete paper’s convergence question can be analyzed through cycles because its state space is finite. Here, rational mass transfers create infinitely many possible states, so an infinite trajectory need not repeat a state or form a cycle. The paper’s co-NP-hardness anchor is still the right starting point, but it does not settle this richer termination question.
The soft spot is that a mass transfer can move a whole cohort in one step. In the paper, one agent moves; a cohort transfer may fail to be implementable as a sequence of individual moves because intermediate coalition sizes could be rejected. That is a real change to the dynamics. I find the path question the more credible mirror: in a high-multiplicity setting, a mass transfer can represent many identical agents making the same locally beneficial move, while all incumbents still have a veto. The mirror covers only Theorem 3.3’s AHG path and convergence results. It keeps time discrete and continuizes the population; coalition shares are the normalization that makes population mass meaningful, not a separate outcome-space continuity goal.
The AHG result is the strongest anchor, and it exposes the central problem with both proposed mirrors: the paper studies one agent moving, while a nonatomic population has no positive-mass individual.
If one agent has mass zero, her move leaves every coalition’s mass—and therefore every anonymous coalition-size payoff—unchanged. The state recorded by the proposed mass vector does not change. A non-stable state cannot reach a stable mass profile through such moves; if individual identities are tracked to make the moves visible, the model is no longer the anonymous mass-state model. This is not just a technical issue with strict preferences or ties. It removes the state change on which the paper’s dynamics runs.
The proposed Mass-IS-Path restores state changes by letting a positive mass \(\delta\) move at once. But that is a group deviation, not the paper’s unilateral deviation. It can also skip the intermediate coalition sizes at which the paper checks whether each new member consents. With non-monotone preferences, a destination’s incumbents may accept the endpoint after a mass transfer while rejecting an intermediate one-agent arrival. So the proposed path question changes which routes are possible. The paper’s NP-hardness theorem does not establish hardness for this block-move process.
A guarded grid could try to force \(\delta=1/n\), preserving the one-agent steps. That is the strongest repair for the path anchor, but it restores a minimum indivisible agent mass. It gives a high-multiplicity discrete dynamics, which may be a worthwhile question in its own right; it does not vindicate the proposed continuously divisible moves. Alternatively, preferences could be designed to block off-grid transfers. Then the grid is imposed by the constructed instance, not supplied by the paper’s discrete rankings: those rankings say how agents compare integer coalition sizes, but do not determine their comparisons at intermediate shares. The reduction would need to prove that its particular extension has the desired behavior.
The convergence anchor faces the same choice, with an added mismatch. Under positive-mass transfers, there are infinitely many rational mass profiles and transfer sizes. An infinite execution need not revisit a state, as every cycle in the paper does. One would have to specify what counts as an execution, how small transfers may be, and whether a limiting profile counts as termination. Those choices define a new termination problem. On an agent-sized grid, the finite-state cycle reasoning returns—but so does the discrete action granularity the continuum was meant to remove.
Moving from AHGs to HDGs, FHGs, or DHGs does not fix this: their dynamics also depends on individual agents changing coalition composition, and FHGs add identity-specific interactions that are harder to aggregate.
I would not green the proposed Mass-IS-Path or Mass-IS-Convergence as mirrors of Theorem 3.3. The case against is strongest on fidelity, not on whether coalition mass dynamics could ever be useful. A population of members making coordinated bulk moves might motivate such a model, but the paper’s authors would need to recognize that collective dynamics as their problem. I cannot honestly rule out that scenario; it is the main weakness in the universal negative case.
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.