| paper | d4-conf-aaai-2016-0334 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), already for one template with \(\lambda_1=1\); decidable in time \(O(\tau\,8^mL^3)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given finitely many connected graphical hedonic-game templates \(H_j\), each with an HC-net representation and treewidth at most \(2\), and positive rational copy intensities \(\lambda_j\), consider a continuum of copies of each template. Does there exist a measurable assignment of an ordinary integral partition to each copy such that no measurable coalition of positive population mass makes every member strictly prefer that coalition to their assigned coalition? Equivalently, does every positive-mass template admit a core-stable local partition?
A continuum of copies of finite network communities. Let \(Z=\sum_j \lambda_j |V(H_j)|\), so role \((j,v)\) has population mass \(\mu_{(j,v)}=\lambda_j/Z\); preserve each copy’s graph correlations and assign local partitions with masses \(\theta_{j,\pi}\), where \(\sum_\pi\theta_{j,\pi}=1\). Core stability is tested against measurable positive-mass blocking coalitions, using each agent’s original graph-dependent preferences.
The mirror covers Theorems 7 and 8, the NP-hardness results for core-stable and Nash-stable partition existence. It leaves the meta-algorithmic results, faster algorithms, allocation applications, and other hardness claims unaddressed.
The strongest case is a continuum of repeated network communities. A type is a vertex role \(t=(H,v)\) in a finite graphical hedonic-game template \(H\): its graph neighbors and its preferences are exactly those of \(v\) in \(H\). The society contains a continuum of copies of each template. Give template \(H\) a positive rational copy intensity \(\lambda_H\), and let \(Z=\sum_H \lambda_H|V(H)|\). Then each role type has mass \(\mu_{(H,v)}=\lambda_H/Z\), so the agent-type masses sum to \(1\).
Each copy receives an ordinary, integral partition of its vertices. The decision variable \(\theta_{H,\pi}\) is the fraction of copies of \(H\) assigned local partition \(\pi\), with \(\sum_\pi\theta_{H,\pi}=1\). Agents evaluate coalitions by their original preferences in \(H\). As in the paper’s connected-partition argument, cross-copy membership adds no relevant neighbors, so the stability question can be evaluated copy by copy. The copies form a continuum population; the network and each copy’s outcome remain discrete. That coupling is a necessary part of the mirror because the paper’s agents have graph-dependent preferences.
This is a high-multiplicity regime when many communities repeat the same designs: with \(M\) copies, there are \(M\sum_H|V(H)|\) agents but only \(\sum_H|V(H)|\) supported role types. The scenario is plausible for repeated organizations or local communities whose members have standardized roles and interact only within their unit. It also retains the paper’s underlying questions: existence of a core-stable or Nash-stable partition.
Theorem 7 is the strongest anchor. As printed, it says: “CORE-EXISTENCE is NP-hard even for graphical hedonic games of treewidth 2 that are given by an HC-net.” Peters proves this result in the paper, by reduction from 3SAT. The construction uses variable agents as leaves attached to a triangle of agents \(a,b,c\); the preferences encode the formula so that a core-stable partition exists exactly when the formula is satisfiable.
The corresponding question is Continuous Replicated Core Existence. Given finitely many connected template games \(H\), each specified by its graph and HC-net preferences, and positive binary-rational intensities \(\lambda_H\), does there exist an assignment \(\theta_{H,\pi}\) of the continuum of copies to local partitions such that no measurable coalition of positive population mass makes every member strictly better off? A solution is the assignment of local partitions, represented by \(\theta\). Every positive-mass local outcome must be core-stable: if an unstable partition occurs on positive mass of copies, its blocking coalition can be assembled across those copies; conversely, a block assembled across copies must give its members improving local groups within their copies.
I expect hardness transfers (Class B). Set the support to one template, \(\lambda_H=1\), where \(H\) is the input game from Theorem 7. A stable partition of \(H\) can be assigned to every copy, and if \(H\) has no stable partition, the continuum cannot have one. The mirror preserves the core question rather than making it easier by weakening preferences or fractionalizing the communities’ internal partitions.
Theorem 8 supplies a second, worthwhile anchor. It says: “NASH-STABLE-EXISTENCE is NP-hard even for graphical hedonic games of treewidth 1 that are given by an HC-net.” This result is also proved in the paper, by reduction from X3C. Its graph is a star: the leaves represent elements, while a central “stalker” agent’s preferences are designed so that a Nash-stable partition exists exactly when the X3C instance has an exact cover.
Its mirror is Continuous Replicated Nash-Stable Existence: on the same kind of rational distribution over repeated graphical-game templates, does there exist an assignment of copies to local partitions such that almost every agent has no profitable move to another coalition or to the empty coalition? The solution is again \(\theta_{H,\pi}\); the stability test is the paper’s Nash-stability test inside each copy. An unstable local outcome on positive mass makes a positive mass of agents profitable deviators. The single-template construction gives the same equivalence as for the core question, so I also expect hardness transfer. Theorem 8 is a distinct question from Theorem 7, and its treewidth-1 bound shows that the mirror is not relying on the core’s triangle structure.
Both mirrors cover only the paper’s named hardness results for existence of stable outcomes. They do not claim to continuize the whole paper or to obtain an algorithmic gain. The authors should recognize the questions: the same agents’ roles, preferences, graph dependencies, partitions, and stability criteria are retained, while population mass records how many copies of each role occur. This is a Class B use of continuization—the programme’s trichotomy allows hardness to survive when the combinatorics are not merely about counting individuals.
The weak point is that the repeated-community scenario preserves, rather than relaxes, the hard instance. A single template can contain the whole 3SAT or X3C construction; the continuum sits across copies of that template. Thus the number of distinct roles may still grow with the instance, and these hardness anchors use unbounded-degree graphs. With a fixed finite library of small templates, the mirror no longer carries the reductions. That limits its case for a tractability payoff, but it remains a concrete and honest continuous-population version of the paper’s stability problems.
The negative case cannot deny that Theorems 7 and 8 are named computational results. Nor is repeating the hard instances across a continuum automatically invalid: a repeated-community model is plausible, and the authors might recognize it. The stronger objection is that, for these two questions, the continuum adds no population-level decision structure.
For Theorem 7, the natural continuous question is whether a continuum of copies of each template can be assigned local partitions so that almost every community is core-stable. With finitely many templates and no links between copies, this is equivalent to asking whether every template with positive mass has a core-stable partition. A blocking coalition that mixes copies separates into its within-copy parts, because agents’ preferences depend only on neighbors in their own copy; conversely, any local block can be repeated across the positive mass of copies using that partition. Thus the mass variables do not trade off against one another. Setting the template to the paper’s reduction gives the same 3SAT instance in every copy.
Theorem 8 has the same problem even more directly. Nash stability is checked by each agent’s possible moves within their community. The continuous question is equivalent to asking whether every positive-mass template has a Nash-stable local partition. Repeating the star from the X3C reduction preserves its answer, but makes the number of copies irrelevant.
This points to a representational dilemma for both anchors. A distribution over vertex roles alone does not say which roles belong to the same community, so it cannot preserve the graph relationships the stability tests use. The proponent’s variable \(\theta_{H,\pi}\), which assigns mass to whole-community partitions, repairs that loss. But with those correlations retained, the continuous problem is a distribution over discrete local outcomes, and stability is a pointwise constraint: only locally stable partitions can receive positive mass. The input still has to carry the template that encodes the hard instance. In the proposed reduction, the number of role types grows with that instance; the continuum is in the number of copies, not in the structure that the theorem analyzes.
A stronger mirror could use a fixed library of small communities with rational population shares. That makes the repeated-population story cleaner, but the existence question then reduces to a finite table of local core or Nash checks. Adding quotas or other aggregate constraints could make the shares interact and create a genuine optimization problem, but those constraints are not part of Theorems 7 or 8. A model of an expanding sparse network might also preserve neighbor relationships, but it would need a richer network limit than a distribution over agent types, and would be a substantially different problem.
So my best case against is that both proposed anchors yield a replication identity built into the model, rather than a new computational question about a continuous society. That makes them weak contributions to ChoCo’s complexity landscape, even though the mirrors are coherent. The case is not airtight: a useful continuous theory of populations of network communities could emerge from a richer model, and the paper’s results make that direction plausible.
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.