| paper | d4-conf-aaai-2015-0402 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even with \(\mathcal G=\{K_5\}\), equal payoffs, permanently accessible coalitions, \(\tau=1\), and \(m=\Theta(n)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite local coalition-formation game \(I=(V,L,\mathcal{C},w,\mathcal{G})\), an explicit rational initial distribution \(x^0\) over its coalition structures, and a round bound \(B\), can mass be routed in at most \(B\) synchronous rounds along legal local-improvement transitions so that all terminal mass is on locally stable states? Each unit of mass represents identical copies of the game, and each copy takes at most one improvement step per round.
A society consists of a continuum of independent copies of one finite local coalition-formation game. Each copy retains the paper’s agents, permanent links, allowed coalitions, formation graphs, and payoffs; \(x_S\) is the mass of copies in coalition structure \(S\). Round-by-round mass flows move between structures connected by one legal local-improvement step, with terminal support restricted to locally stable structures.
The continuum is over repeated whole communities and retains the correlations among agents inside each finite network, so it does not provide a fractional relaxation within a single network; this limits the mirror to a repeated-community regime.
fatal: False
The mirror covers Theorem 3’s exponential lower bound for non-clique, non-star formation graphs and Theorem 1’s clique convergence guarantee. It leaves Theorem 2, Theorem 4, and the paper’s other stability variants aside.
The strongest mirror I see is for the paper’s local improvement dynamics, not for hedonic games in general. Consider a continuum of independent, repeated communities. Each community is a copy of one finite local coalition formation game from the paper: it has the same permanent-link network, allowed coalitions, formation graph, and payoffs. A role \(v\) in that network defines an agent type: agents in that role have the same preferences and the same visibility pattern, described by role rather than by personal identity.
Let each community contain \(n\) roles and have total population mass \(1\). Each role type then has mass \(1/n\). Let \(x_S\) be the fraction of communities currently in coalition structure \(S\); because all communities are the same size, this is also the fraction of the agent population in those communities. The vector \(x\) records the distribution of local states, including the correlations among roles within a community. Communities do not form coalitions across their boundaries, which is a permitted restriction on the paper’s coalition set.
Here is the continuous problem I would hand to a prover: Mass-Replicated Local Stabilization. The input is the finite local game, an explicit rational initial distribution \(x^0\) over its coalition structures, and a round bound \(B\). In one round, choose amounts of mass in occupied states and move them to successor states obtained by resolving a local blocking coalition under the paper’s rules. Each community can take at most one improvement step per round; different masses of communities can move in parallel. The question is whether a schedule of at most \(B\) rounds can leave mass only on locally stable states. A solution is the sequence of state distributions and mass transfers witnessing that schedule. The agents inside each community still form integral coalitions; it is the population of repeated communities that is continuous.
My lead anchor is Theorem 3, proved in this paper. It says that for every fixed connected formation graph \(G\) of constant size that is neither a clique nor a star, and for every \(n\), there is a local coalition formation game with \(n\) agents, \(m=\Theta(n)\) possible coalitions, formation graph set \(\{G\}\), and an initial state such that every sequence of improvement steps to stability has length \(2^{\Theta(n)}\). This is an exponential lower bound on convergence time, not a proof of NP-hardness.
For the mirror, take that finite game as the local template and put a continuum of identical copies of it into the society, initially all in the theorem’s starting state. The mass problem asks whether the copies’ mass can be stabilized within \(B\) rounds. Theorem 3 predicts an exponential lower bound: each positive mass cohort must follow a legal path through its local states, and every such path in the constructed game is exponentially long. Parallelizing updates across copies does not shorten the number of sequential steps any one copy needs. I expect this mirror to inherit the discrete obstruction, in the Class B sense, rather than to reveal a new continuum-specific one. The result supports a precise claim about stabilization depth; it does not settle the computational complexity of deciding whether an arbitrary schedule of a given length exists.
A second, complementary anchor is Theorem 1, also proved here. It says that when every formation graph is a clique, every local game has a path to stability of length at most \(n\) from any starting state; moreover, random dynamics converge in expected time at most \(O(mn)\). In the same mass-replicated model, the deterministic clause gives a direct algorithmic mirror: for each occupied state, choose a maximum-benefit local blocker and move all its mass along that transition. Applying the paper’s argument to each state cohort in parallel gives a stable distribution within \(n\) rounds. With an explicit coalition list and explicit initial support, the schedule can be constructed by scanning for blockers, so this version is tractable in the input size and round bound. The random-dynamics clause does not transfer as directly: choosing one agent uniformly from an atomless population changes zero mass, so a meaningful continuous random update rule would need its own definition.
The scenario is a large system of repeated local units—say, many similar project groups or networked chapters—with the same role structure and local opportunities for coalition formation. For a finite approximation with \(H\) copies, there are \(Hn\) agents but only \(n\) role types, each with multiplicity \(H\); taking \(H\) large gives the continuum. The paper already permits arbitrary restrictions on possible coalitions, so keeping coalitions within each unit preserves its local problem rather than changing its rules. This seems plausible as a mirror of the authors’ question about how local visibility affects convergence, though it is a narrower regime than one connected network of interacting agents.
The mirror covers the clique convergence guarantee and the exponential lower bound for non-clique, non-star formation graphs. It does not cover the paper’s other stability questions, nor does it claim that continuous optimization solves the local dynamics. A natural next question is whether the star guarantee in Theorem 2 lifts to the same mass-state formulation, and what random-update rule gives the clique theorem’s expected-time result a meaningful atomless analogue.
The weak point is that this continuization aggregates repeated copies of a finite game; it does not fractionally relax the membership of agents inside one coalition. The exponential lower bound still depends on the local template size \(n\), and its role-type support grows with that template. Thus the case shows that high multiplicity of agents can coexist with the paper’s hard dynamics, but it does not show that a fractional, member-level relaxation preserves the lower bound. An author might regard that as too conservative a mirror. I think it is the most defensible one here because the problem being asked remains their local coalition formation process, with continuous mass introduced at the population level.
Theorem 1 and Theorem 3 are legitimate computational anchors: one gives short convergence paths, and the other gives an exponential lower bound on stabilization depth. I would not reject them for lacking algorithmic content. The problem is that the proposed mirror makes the *community* the unit of mass. It describes a continuum of copies of a finite game, rather than a continuous population of agents in a network.
That change carries substantial information in the state variable. Accessibility depends on which particular agents are linked and which particular agents currently share a coalition. Masses for individual roles do not say whether those relations line up inside the same community. If the model retains that information by assigning mass to whole coalition structures, as the proponent does, it preserves each finite game intact and distributes mass over its configurations. That is a coherent ensemble model, but the continuum sits over complete local systems. The number of copies can grow without changing any game’s transitions or its stabilization depth.
This weakens both anchors. For Theorem 1, each occupied community state can follow the paper’s existing short-path argument independently. Applying it to every state in the input support gives a mass schedule; the continuous mass variables do not create a new optimization problem. The theorem’s random-dynamics clause also lacks a direct atomless interpretation: selecting one uniformly random community updates zero mass. A rate-based version could be defined, but its convergence question would need its own model.
For Theorem 3, the proposed construction is exact repetition of the finite hard instance. Starting with all mass on its initial state, every positive-mass part follows a legal path in that instance. The exponential number of sequential steps is inherited unchanged as the template grows; parallel updates across copies cannot shorten one copy’s path. More generally, bounded-time stabilization of independent copies reduces to asking whether each initial state in the support can reach a stable state within the bound. This is a useful property of the repeated-system model, but it does not chart how a continuous population of interacting agents changes the computational landscape.
A stronger agent-level mirror would need to preserve the network’s relational structure while allowing mass to move among agent types. The paper’s local coalitions are finite sets of linked agents, with payoff \(w(C)\) attached to each allowed coalition. In an atomless population, individual agents have zero mass, while type-level masses alone cannot specify which agents form those linked sets or which temporary links appear together. One can restore that information with distributions over complete network configurations; that returns to the community-level ensemble. A spatial or graphon-style model could keep a richer visibility structure, but the positions and overlapping neighborhoods in the paper’s exponential gadget then become part of the type description, and a clear high-multiplicity computational question still has to be supplied.
The honest limitation of this negative case is that repeated networked units are plausible in applications. A population of similar project groups or local chapters could make the proponent’s formulation worth studying. I would argue that this is continuization of communities, while the paper’s central object is coalition formation among individuals in a network. A richer continuum of interacting agents might also yield a worthwhile mirror; the paper alone does not rule it out. The case against is strongest for these two anchors: their proposed lifts preserve the original finite dynamics inside each unit, and the continuous aggregation does no computational work on the population of agents.
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.