| paper | d4-conf-atal-2009-0024 |
| 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: Blocking-coalition existence is \(\mathrm{NP}\)-complete, and deciding that \(\Pi\) has no blocking coalition is \(\mathrm{coNP}\)-complete, even at interaction-graph treewidth at most \(2\) with \(k=2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given finitely many types \(T\), rational masses \(\mu_t>0\) summing to \(1\), type-level Boolean hedonic nets, and a proposed partition \(\Pi\) represented by block masses \(z_t^r\), decide whether \(\Pi\) has no blocking coalition. A coalition has support \(S\subseteq T\); type \(t\)’s utility \(u_t(S)\) depends on which types have positive mass in it. Define \(A_t^\Pi(S)=\sum_{r:\,u_t(S)>u_t(S_r)}z_t^r\), where \(S_r=\{t:z_t^r>0\}\). A blocking coalition with support \(S\) exists exactly when \(A_t^\Pi(S)>0\) for every \(t\in S\), since it can recruit positive mass from each eligible block.
An atomless society with finitely many types and masses \(\mu_t\); each type’s utility is a Boolean net evaluated on the support of types present in its coalition. A proposed partition assigns masses \(z_t^r\) of each type to blocks, and a deviation selects positive masses \(x_t\) from types whose members strictly prefer the deviating support. The problem is to decide whether the partition is in the core.
The paper does not select type-level presence over mass-sensitive aggregation, so the mirror is a particular extension of its nets rather than a uniquely determined limit; the proponent acknowledges the saturation semantics but does not establish that it is the natural choice among alternatives.
fatal: False
The mirror covers Theorem 4’s core-membership hardness for hedonic coalition nets. It leaves the paper’s equivalence results, other stability problems, core non-emptiness and containment results, and bounded-treewidth algorithmic result aside.
The strongest anchor is Theorem 4, proved in this paper: deciding whether a specified coalition partition belongs to the core of a hedonic game represented by hedonic coalition nets is coNP-complete even when the agent graph has treewidth at most \(2\). The paper proves this by reducing from PARTITION. This is a strong anchor because it asks whether a proposed organization resists group deviations, and its hardness survives a substantial structural restriction.
A continuous version I would put to a prover is Atomless Core Membership for Type-Level Hedonic Coalition Nets. Its input is a finite set of types \(T\), positive rational masses \(\mu_t\) summing to \(1\), a hedonic coalition net over those types, and a proposed partition of the population. Every member of type \(t\) has the same net and utility. A rule’s Boolean variables now refer to whether a type has positive mass in a coalition. Thus \(u_t(S)\) is type \(t\)’s utility when the coalition contains positive mass from exactly the types in \(S\subseteq T\).
Represent the proposed partition by a finite list of rational vectors \(z^1,\ldots,z^K\), where \(z^r_t\) is the mass of type \(t\) in block \(r\), and \(\sum_r z^r_t=\mu_t\). Let \(S_r=\{t:z^r_t>0\}\). A deviating coalition chooses a nonempty support \(S\subseteq T\) and positive masses \(x_t\) for \(t\in S\). It is a block if each chosen member strictly prefers it to their current block. More precisely, define the available mass
\[
A_t^\Pi(S)=\sum_{r:\,u_t(S)>u_t(S_r)}z^r_t.
\]
A block with support \(S\) exists exactly when \(A_t^\Pi(S)>0\) for every \(t\in S\): atomlessness lets the deviators choose a positive amount from each eligible block. The problem asks whether there is no such support \(S\). A blocking support, together with any positive rational \(x_t\le A_t^\Pi(S)\), is a witness that the proposed partition is not in the core.
The regime is a large organization with many interchangeable members in each contribution or coordination role. A type includes the role, its net preferences, and its contribution parameters, so members of that type are identical for everything the game uses. With \(q\) copies of each role, the reduction below has \(q(n+3)\) agents but only \(n+3\) types. A measurable coalition can recruit a positive mass from a role, just as a finite blocking coalition can recruit one or more people of that role.
The reduction gives a direct hardness argument for the continuous question. Take a PARTITION instance with positive integers \(a_1,\ldots,a_n\) summing to \(2B\). Use item types \(1,\ldots,n\) and three special types \(p,q,r\), each with mass \(1/(n+3)\). Set item type \(i\)’s utility to \(1\) exactly when \(p\) is present. Set
\[
u_p(S)=(B-1)\mathbf 1[r\in S]+\sum_{i=1}^n a_i\mathbf 1[i\in S\land q\in S],
\qquad
u_q(S)=(B+1)\mathbf 1[p\in S]-\sum_{i=1}^n a_i\mathbf 1[i\in S],
\]
and \(u_r(S)=0\). Put each item type in its own block, \(p\) and \(r\) together, and \(q\) alone. This is the paper’s construction with each player replaced by a positive-mass role; its type-dependency graph has the same treewidth bound.
In this partition, \(p\) gets \(B-1\), while \(q\) and every item type get \(0\). Type \(r\) cannot join a blocker because its utility is always \(0\). Any blocker must include \(p\) and \(q\), along with some item types \(I\). For \(p\) to improve, \(\sum_{i\in I}a_i>B-1\); for \(q\) to improve, \(\sum_{i\in I}a_i<B+1\). Since the sum is integral, both conditions hold exactly when it equals \(B\). Every selected item type then improves as well. Thus the proposed continuous partition is core-stable exactly when the PARTITION instance has no solution. The support of a blocking coalition certifies non-stability, so the continuous problem is coNP-complete on this treewidth-\(2\) family. I expect hardness to transfer (Class B): the subset-sum arithmetic and the distinct contribution types carry the hardness through the mass model.
I would scope the mirror to Theorem 4 only. The paper’s other core, equivalence, and bounded-treewidth results raise separate questions; this argument does not claim to continuize them. A natural follow-up is whether quantitative utility rules—where the amount of each type in a coalition matters, rather than just its presence—admit tractable cases under bounded treewidth or restricted values.
The weakest point is that these Boolean nets make mass amounts irrelevant once they are positive. The mirror has a continuous society and a genuine mass-transfer variable, but the reduction’s decisive information is the support of a coalition, and the hardness scales with the number of distinct contribution types. That makes this a boundary result, not evidence that continuous optimization unlocks an algorithm here. Still, type-level presence is a natural extension of the paper’s membership-based rules, and the high-multiplicity setting is plausible when many people share each role. I think the authors could recognize it as their core-stability problem for a typed population, while a referee might reasonably call it an extension rather than a direct translation.
The only anchor is Theorem 4, and it is a real computational result. The strongest objection is about whether the proposed atomless problem is genuinely a population mirror of that result.
The proposed blocking criterion is correct for its support-only utilities, but it exposes the limitation: once a type has positive mass in an eligible block, any smaller positive amount can deviate. The mass values themselves do no work. Replacing “present” with “positive mass” turns the proposed core test into a search over subsets of types—the same combinatorial object as the finite blocking-coalition test. In the reduction, each distinct \(a_i\) must remain a distinct role, so the number of types grows with the PARTITION instance. The construction gives no regime where a society with a small set of types becomes easier to analyze by treating its population as continuous.
There is a deeper modeling choice behind that result. The paper’s net rules refer to named players, and a player’s utility can depend on exactly which other players are in the coalition. In the reduction, the \(a_i\) roles are distinct because \(p\) and \(q\) value them differently. To make many copies of each role interchangeable, the mirror replaces each set of clone variables with a single “some member is present” test. That is a coherent role-based model, but it is a new saturation rule: one member and nearly the whole role cohort have the same effect. The original nets do not specify that aggregation. Preserving per-member contributions instead would make utility depend on the amount of each type in the coalition, and then the reduction’s subset-sum argument no longer supplies the mirror. Such a mass-sensitive model could be worth studying, but it needs its own utility language and its own connection to the paper’s nets.
This is why I would resist treating the proposed coNP-completeness result as a continuization of Theorem 4. It is a valid question for a typed, role-presence variant of hedonic coalition nets; the large-cohort organization story is plausible. But the paper’s result alone does not select that variant over count-sensitive or mass-sensitive alternatives, and the proposed one makes the population’s proportions irrelevant once they are positive. The mirror therefore has a weak high-multiplicity bridge to the paper’s general model.
That is the strongest negative case I can make, and it is not decisive. The authors could recognize role-presence nets as a sensible restriction of their formalism, and the atomless core question is well-defined. I cannot honestly rule out a worthwhile mirror in that scenario; the objection is that the proponent has not established that this particular typed model is the natural continuous version of the paper’s core-membership result.
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.