| paper | d4-conf-aaai-2017-0696 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable, in \(\mathrm{P}\). A blocking coalition exists exactly when the type graph is not complete multipartite. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 28
statement extracted from the paper’s text layer
Given a finite set of types \(T=\{1,\ldots,\tau\}\), positive rational masses \(\mu_i\) summing to \(1\), and a symmetric binary tie matrix \(A\), decide whether there is a vector \(x\) with \(0\leq x_i\leq\mu_i\) and \(\sum_i x_i>0\) such that every type with \(x_i>0\) strictly gains: \(\frac{\sum_j A_{ij}x_j}{\sum_j x_j}>\sum_j A_{ij}\mu_j\). Equivalently, decide whether the grand coalition is core stable in this type-mass popularity game.
A population is a distribution \(\mu\) over finitely many complete tie-profile types; \(A_{ij}\) records whether members of types \(i\) and \(j\) are tied, including within-type ties when \(A_{ii}=1\). A blocking coalition chooses mass \(x_i\) from each type, and its members' popularity is their tie mass within the coalition divided by total coalition mass.
Because popularity is scale-invariant, any feasible mixture of types can be scaled down to fit their available masses; the mass values therefore affect only which types are present, making this an infinitesimal-invasion question rather than a test of how much of the population can block.
fatal: False
The mirror covers Theorem 28's decision problem for social cohesion. It leaves the graph-class characterizations, the structural-cohesion connection, and the heuristics and their experiments aside.
My lead is Type-Mass Social Cohesion. The anchor is Theorem 28, proved in this paper: deciding whether a given unweighted network is socially cohesive—whether its grand coalition is core stable in the popularity game—is CoNP-complete. The theorem also proves CoNP-hardness when the network is connected, has diameter at most two, and is not diametrically uniform. The hardness proof reduces from MaxClique, whose NP-hardness the paper cites as [14].
Here is a continuous version of that underlying decision problem. An instance has a finite set of distinct social types \(T=\{1,\ldots,\tau\}\), positive rational masses \(\mu_i\) summing to \(1\), and a symmetric matrix \(A\in\{0,1\}^{\tau\times\tau}\). \(A_{ij}=1\) means that members of types \(i\) and \(j\) are tied; \(A_{ii}\) specifies whether members of type \(i\) are tied to one another. A coalition is any selection of mass \(x_i\in[0,\mu_i]\) from each type, with total mass \(X=\sum_i x_i>0\). In that coalition, a member of type \(i\) has popularity
\[
p_x(i)=\frac{\sum_j A_{ij}x_j}{X},
\]
while their popularity in the grand coalition is
\[
p_\mu(i)=\sum_j A_{ij}\mu_j.
\]
The problem, Type-Mass COH, asks whether the grand coalition is stable: is there *no* such \(x\) for which every participating type strictly gains, meaning \(p_x(i)>p_\mu(i)\) for every \(i\) with \(x_i>0\)? A solution is yes or no; a no answer can be witnessed by a blocking mass vector \(x\).
This keeps the paper’s question recognizable. It still asks whether a group can disrupt the grand coalition because every member would become more popular together. It changes the population unit from individual nodes to fractions of society and uses type-level tie profiles to calculate per-capita popularity. The agents are many members of a large organization or online community, grouped into a small number of role or cohort types; \(\tau\) is small relative to the total population \(N\). Ties follow a stable block pattern: members in the same pair of types have the same tie relation. This is a stylized but plausible high-multiplicity regime, and the popularity definition is the limit of degree divided by group size. Crucially, coalition formation remains divisible: any fraction of a type can join a deviation.
I expect this problem to remain hard, with hardness transfer the natural first target. The paper’s reduction puts its combinatorics in the graph structure—ultimately a clique question—not in the number of people. In the mirror, that structure can live in the type interaction graph, while each type represents a large cohort. But Theorem 28 does not prove hardness for Type-Mass COH: continuous selection lets a blocker take different fractions of different types, so a transfer proof must show that this extra freedom does not invalidate the reduction. The first follow-up questions are whether the theorem’s NDU2 hardness survives that freedom, and how the answer depends on the number \(\tau\) of types and the bit length of the masses.
The scope is deliberately one result: Theorem 28’s decision problem. I am not claiming a mirror of the structural-cohesion results or the heuristics. The weakest point is the block-structured scenario: it narrows the networks represented, and fractional blockers make the complexity connection a conjectured direction rather than a consequence of the theorem. Still, the underlying stability question and popularity payoff carry over directly, which makes this a credible mirror to investigate.
Theorem 28 is the one serious anchor, and I cannot honestly make the negative case airtight against it. It proves CoNP-completeness for a clear computational problem. My concern is that the natural continuous versions either lose the network the theorem studies or narrow it to a special block model whose population dimension does little explanatory work.
A type in this paper has to preserve everything that affects a player’s payoff: their ties to everyone else. In a general social network, that makes most vertices distinct types. Exact aggregation is plausible for twins or role-based cohorts, but the resulting network is a blow-up of a small quotient graph: each pair of types is either fully tied or untied. That is a reasonable stylization for some dense organizations. It is a poor fit for the sparse, locally varied networks that motivate the paper’s examples. Theorem 28’s reduction can be inflated by cloning vertices, but its source graph still supplies a separate type for each vertex whose adjacency matters. The resulting instance has many people and essentially the same number of structurally distinct types.
The best repair is a type-level affinity model, perhaps a kernel \(W(s,t)\), with popularity in coalition \(S\) given by
\[
\frac{\int_S W(s,t)\,d\mu(t)}{\mu(S)}.
\]
That gives a coherent continuum game and can represent more than all-or-nothing blocks. But an arbitrary kernel has no finite input description on which to state a computational complexity result. Restricting to a finite rational step kernel restores a finite input, and brings us back to the type-interaction matrix. Using probabilities or expected tie densities for sparse networks changes the deterministic game: in the usual sparse limit, the paper’s degree-over-population payoffs tend to zero, while the small blocking sets that matter in finite graphs have zero limiting mass. A rescaling or sparse-network limit may be possible, but it needs a new payoff and a new representation of local structure.
There is also a mismatch in what the proposed mass model measures. If \(x_i=\varepsilon q_i\), then any composition \(q\) over positive-mass types is feasible for sufficiently small \(\varepsilon>0\). The upper bounds \(x_i\leq\mu_i\) therefore do not constrain the coalition’s composition. The question becomes whether some type mixture can strictly improve each participating type’s payoff. That is a sensible invasion question, but it is a more specific object than the paper’s question about which subsets of a realized network can block. Requiring a minimum blocking mass would restore scale as a constraint, but a fixed threshold has no counterpart in the finite definition, where a blocker may be a single person.
So the strongest objection is about fit: the anchor concerns identity-rich, often sparse networks, while the defensible continuous model needs dense, exchangeable blocks or a separately specified kernel class. That leaves a real and potentially worthwhile research question for block networks. The weakness in my case is that such networks are plausible, and Theorem 28’s reduction could be adapted to a mass model. I would present this as a substantial limitation on the mirror’s reach, not as proof that no worthwhile mirror exists.
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.