| paper | d4-conf-ijcai-2020-0051 |
| 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: Blocker existence is \(\mathrm{NP}\)-hard; continuous core-stability verification is \(\mathrm{coNP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite symmetric type graph \(H=(T,a)\), with \(a_{ts}\in\{0,1\}\) specifying friendship between types, including within-type relations; positive rational masses \(\mu_t\) summing to \(1\); and a proposed partition \(\Pi=(p^1,\ldots,p^r)\) with \(\sum_j p_t^j=\mu_t\), decide whether \(\Pi\) is core stable. For a coalition profile \(q\), define \(f_t(q)=\sum_s a_{ts}q_s\) and \(e_t(q)=\sum_s(1-a_{ts})q_s\). Extend selfish-first preferences by lexicographically comparing \((f_t(q),-e_t(q),\sum_s a_{ts}\sum_jp_s^j f_s(p^j),-\sum_s a_{ts}\sum_jp_s^j e_s(p^j))\). A blocker is a real selection \(z_t^j\in[0,p_t^j]\) of positive total mass; it forms \(y_t=\sum_jz_t^j\), leaving residual coalitions \(p^j-z^j\). Decide whether there is no such selection for which every selected unit strictly prefers the resulting partition to \(\Pi\).
An atomless population with rational masses of interchangeable types, a symmetric block-structured friendship relation, and a proposed partition into coalition mass profiles. The decision variable is a real mass selection from each type in each coalition; the question is whether any unanimous improving coalition can form under the per-capita selfish-first utility extension.
The mirror covers Theorem 5’s selfish-first core-verification result for block-structured type populations. It leaves strict-core verification, the equal- and altruistic-treatment results, and the paper’s other stability notions untouched.
The strongest case I see is for a high multiplicity version of core stability verification. I would anchor it on the hardness claim in Theorem 5, proved in this paper (the proof is omitted for space). The theorem says that core stability verification is in coNP for all three altruism treatments, and is coNP-complete under the selfish-first treatment. It also says strict-core stability verification is in coNP for all three treatments. I would mirror the coNP-complete selfish-first core-verification problem.
Call the mirror SF-Mass-Core Verification. Its input is a finite set of types \(T\), an undirected friendship graph \(H=(T,E)\), rational type masses \(\mu_t>0\) summing to \(1\), and a proposed coalition structure \(\Pi=(p^1,\ldots,p^r)\). Each \(p^j\in\mathbb{Q}_{\ge 0}^{T}\) gives the mass of each type in coalition \(j\), and \(\sum_j p^j_t=\mu_t\). The population is atomless. Every member of type \(t\) is friends with every member of each adjacent type \(s\), and enemies with members of all other types, including their own type. Thus agents of a type are interchangeable in the full interaction pattern.
For a coalition profile \(p\), let
\[
f_t(p)=\sum_{s:\{s,t\}\in E}p_s,\qquad
e_t(p)=\sum_{s:\{s,t\}\notin E}p_s,
\]
where the second sum includes \(s=t\). Under the continuous selfish-first interpretation, an agent compares utilities lexicographically: first their own friend mass in their coalition, then the negative of their enemy mass there, then the aggregate friend mass and negative enemy mass of all their friends across the society. For example, the first aggregate friend component for type \(t\) in \(\Pi\) is
\[
\sum_{s:\{s,t\}\in E}\sum_{j=1}^{r}p^j_s f_s(p^j).
\]
This lexicographic scaling carries the paper’s selfish-first priority into a mass model: an agent’s own friend-oriented valuation takes priority, with friends’ valuations breaking ties.
The question is whether \(\Pi\) is core stable. A possible blocking coalition chooses amounts \(z^j_t\in[0,p^j_t]\) from each existing coalition and type, with positive total mass. It forms a new coalition of profile \(y_t=\sum_j z^j_t\); each old coalition becomes \(p^j-z^j\). The deviation blocks if every selected mass \(z^j_t>0\) strictly prefers the resulting partition to \(\Pi\), using the utilities above. A “yes” solution means no such mass selection exists; a “no” solution is a blocking mass vector \(z\). This makes the question finite-dimensional for the given input partition, while allowing a type’s population to split across coalitions and across deviations.
The regime is a large organization or civic network whose members form teams, with friendship understood as a reciprocal, role-level relation—for example, all members of one role are socially aligned with all members of certain other roles. There may be thousands of members but only a moderate number \(\tau=|T|\) of roles. The scenario is fairly structured, but the type is complete: members of a type have the same preferences and the same friends. It also preserves the paper’s distinctive feature that agents care about friends in other coalitions, not just about their own group.
My tentative prediction is Class C: the atomless model might still be hard because its input retains an arbitrary friendship graph over types, and altruistic friend-welfare terms depend quadratically on coalition masses. I would not claim Theorem 5’s coNP-hardness transfers automatically. Divisibility lets a type split, so a discrete blocking coalition need not have a direct continuous counterpart. The main follow-up questions are whether blocking can be characterized by a tractable optimization problem, whether rational or algebraic blocking masses always have suitably short representations, and which graph restrictions on \(H\) change the answer.
The weakest point is the block-structured friendship assumption. It is a plausible high multiplicity regime, but a named-agent friendship network is more general, and the mirror does not cover that full model. The other gap is exactly where the continuous question becomes interesting: the paper’s hardness result does not by itself settle the complexity after agents become divisible. This case covers Theorem 5’s selfish-first core-verification result, not the paper’s other stability notions.
The strongest case against this mirror is about fit. The coNP-completeness result in Theorem 5 concerns core verification on an arbitrary friendship graph. In the reduction, the \(\beta\)- and \(\zeta\)-agents encode the incidences of an exact-cover instance; most of those agents have distinct neighborhoods. The reduction therefore relies on many structurally distinct agents, not on a large population of interchangeable agents. In ordinary friendship networks, exact repeats of a person’s relationships are also uncommon. Grouping people into a small number of role types and declaring every member of one role friends with every member of an adjacent role replaces that individual network with a dense, block-structured one. That is a narrow regime, and the paper gives little reason to think it captures the settings driving its hardness result.
The proponent’s formal model also needs repair before it is a faithful mirror. The paper’s simple graph excludes an agent’s relation to themself; it does not imply that distinct members of the same type are enemies. A type-level model needs to specify whether distinct members of each type are friends or enemies. It also needs a consistent normalization of friend and enemy counts and of the sum of friends’ valuations. These are repairable choices, though: a finite type graph with a within-type friendship flag and a lexicographic per-capita utility can express them.
That repaired model is the strongest version of the case against my position. Consider a large organization with repeated roles and a stable, role-level friendship pattern. Give each type a rational mass, each type pair a friendship relation, and a proposed partition into finitely many coalitions. A blocking coalition can select positive amounts of each type, and its members’ preferences depend on the resulting coalition masses and the welfare of their friends. This is a coherent continuous core-verification problem. Core stability compares whether agents benefit from a deviation; it does not require remembering their names. The atomless limit does not by itself make the question vacuous, and the paper contains no continuous treatment that already answers it.
So the negative case is a case for low priority, not rejection. The role-based regime is much narrower than the paper’s general graph model, and this mirror is not obviously an LP: altruistic terms involve aggregate friend welfare, which can make blocking conditions nonlinear. But nonlinear or hard is not the same as unworthy; it could still map out where continuization stops helping. I cannot honestly defeat the anchor: a reasonable high-multiplicity core-verification question survives Theorem 5, even though its fit to the paper’s broadest model is limited.
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.