| paper | d4-journals-jair-2025-0023 |
| 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: Both the unpointed and pointed defensive-coalition existence problems are \(\mathrm{NP}\)-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given finitely many types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and a symmetric relation \(\sigma_{tu}\in\{+,-,0\}\) shared by every pair of distinct members of types \(t,u\), does there exist a nonzero coalition mass vector \(x\) with \(0\le x_t\le\mu_t\) such that, for each \(t\) with \(x_t>0\), \(P_t(x)\ge N_t^{\mathrm{in}}(x)\) and \(P_t(x)\ge N_t^{\mathrm{out}}(x)\), where \(P_t(x)=\sum_{u:\sigma_{tu}=+}x_u\), \(N_t^{\mathrm{in}}(x)=\sum_{u:\sigma_{tu}=-}x_u\), and \(N_t^{\mathrm{out}}(x)=\sum_{u:\sigma_{tu}=-}(\mu_u-x_u)\)? In the pointed version, given \(t^\star\in T\), require also \(x_{t^\star}>0\).
A population is a distribution \(\mu\) over signed-interaction types; all pairs of members of types \(t,u\) share relation \(\sigma_{tu}\). Choose coalition masses \(x_t\in[0,\mu_t]\). A positive-mass type must have positive coalition mass at least as large as both its internal and external negative mass. The finite self-defence term becomes negligible after normalizing by population size.
The mirror applies to exact block-structured networks, and the proposed bloc scenario gives limited support for why real populations would share uniform signed ties; this bounds its applicability.
fatal: False
The mirror covers Theorem 11’s DEFALL and DEFPALL existence results; it leaves the minimum-alliance, alliance-building, and parameterized results unaddressed.
The strongest anchor is Theorem 11, proved in this paper by a reduction from NAE-3SAT. It states that both DEFPALL—whether a signed graph has a defensive alliance containing a specified vertex—and DEFALL—whether it has any defensive alliance—are NP-complete. I would mirror the unpointed and pointed questions directly.
Call the mirror Continuous Defensive Alliability. An instance consists of a finite set \(T\) of signed-interaction types, a positive rational mass \(\mu_t\) for each type with \(\sum_{t\in T}\mu_t=1\), and a symmetric relation matrix \(\sigma_{tu}\in\{+,-,0\}\). Here \(\sigma_{tu}\) describes the relation between members of types \(t\) and \(u\); \(\sigma_{tt}\) describes relations between distinct members of the same type. Members of a type share the same relation pattern to every type.
Choose a coalition mass \(x_t\in[0,\mu_t]\) for each type. Define the positive mass and the internal and external negative mass seen by type \(t\) as
\[ P_t(x)=\sum_{\sigma_{tu}=+}x_u,\qquad N_t^{\mathrm{in}}(x)=\sum_{\sigma_{tu}=-}x_u,\qquad N_t^{\mathrm{out}}(x)=\sum_{\sigma_{tu}=-}(\mu_u-x_u). \]
The question is whether there is a vector \(x\) with \(\sum_t x_t>0\) such that, for every type with \(x_t>0\),
\[ P_t(x)\ge N_t^{\mathrm{in}}(x) \quad\text{and}\quad P_t(x)\ge N_t^{\mathrm{out}}(x). \]
A solution is such a coalition-mass vector. The pointed version takes a designated type \(t^\star\) and also requires \(x_{t^\star}>0\). That asks whether the alliance includes a positive mass of the specified kind of member, rather than whether it contains one named person.
This is the atomless, per-capita version of the paper’s two defensive conditions. In a finite population of \(N\) people, dividing the conditions by \(N\) turns the self-defence term \(+1\) into \(+1/N\), which vanishes in the continuum limit. Selecting a fraction of a type is the corresponding high-multiplicity relaxation of selecting some of its members.
A plausible regime is a very large online movement or federation organized into a modest number of durable blocs. Many members share a bloc affiliation and the same bloc-level pattern of trust, hostility, and neutrality. For example, a network with millions of members and dozens or hundreds of such types could ask whether a substantial group is internally stable and has enough positive support against its external enemies. This is a real population question: the decision is about coalition mass in a large society, not about fractional outcomes or a probability distribution over finite networks.
I would expect hardness to transfer for unrestricted numbers of types. Theorem 11’s reduction encodes NAE-3SAT in the signed interaction pattern among vertices—the variable and clause gadgets—not in large voter counts or a numeric population size. One can make the population large by replacing each gadget vertex with a large cohort of identical agents, leaving the number of types to carry the combinatorics. That makes this a plausible Class B case. For a fixed set of active types, the conditions are linear; enumerating the active type sets gives an \(2^{|T|}\operatorname{poly}(|T|,L)\)-time procedure. So the mirror also raises a natural parameterized question: can the active-type search be improved, and what is the exact complexity as the number of types grows?
The weakest point is that the proposed limit changes two things that matter. It drops the \(+1\) self-defence term and permits fractional selection within a type. Theorem 11’s proof does not establish that its gadgets still force the intended choices under those changes; fractional masses could create an alliance where the discrete instance has none. Nor is a large, nearly uniform signed network a good model of every social graph: individualized ties can make the number of types approach the population size. Those are reasons to treat hardness transfer as a conjecture, not a consequence of the theorem. They do not make the question unrecognizable: it retains the paper’s signed relationships, its two stability conditions, and its computational question of whether a defensible alliance exists. This mirror covers Theorem 11’s alliability results; it does not claim to continuize the paper’s minimum-alliance or alliance-building results.
Theorem 11 is a genuine computational anchor: it proves NP-completeness for both DEFALL and DEFPALL. The strongest case against mirroring it is about what a type would have to preserve. In this paper, a vertex’s signed neighborhood is part of the problem: each alliance member must satisfy two conditions involving its own friends and enemies. Two people who share a broad affiliation but have different ties are not interchangeable for that test.
In a realistic sparse social network, exact types would therefore need to encode very detailed neighborhood information, and their number could grow with the population. Grouping people into a few blocs changes the network: it treats each relation between blocs as applying uniformly across their members, effectively replacing local ties with block-wide interactions. That is hard to square with the paper’s account of edges as relationships that determine who can help or attack whom. It also weakens the proponent’s online-movement example: shared bloc membership alone does not make every member’s signed neighborhood the same.
The best repair is a deliberately block-structured society, or a network model with type-level interaction rates. Such a model could be worth studying, but it needs careful semantics. An average interaction rate does not ensure that every member is defended; preserving the paper’s “for each member” condition requires information about the distribution of local neighborhoods. A block model with uniform interactions avoids that problem, though it describes a narrower institutional setting. The pointed version has a coherent mass interpretation—positive mass of a designated type—and the disappearing \(+1\) term is an expected change in the limit. Neither point defeats the mirror on its own.
So the negative case is a serious limitation on scope, not a successful refutation of the anchor. There are plausible block-structured populations in which the continuous question would remain recognizable, and the paper’s existing grouping by signed neighborhood diversity makes that possibility harder to dismiss. I cannot honestly defend the universal claim that no worthwhile mirror exists. The proponent has a viable question; their hardness-transfer story remains conjectural, and the proposed applications need a more convincing account of why ties are shared across whole blocs.
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.