| paper | d4-conf-ijcai-2018-0404 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper has no numbered theorem, lemma, corollary, or proposition asserting a computational result. Its NP-hardness statement is attributed background, its correctness proof is deferred to the journal article, and its own runtime comparisons are unnumbered experiments; the proposed mirror cannot supply the missing anchor.
fails bit a — no named computational result to mirror
The proposed model addresses the underlying coalition partition objective, but does not mirror a numbered result in this paper or its COP correctness claim, GPU solver, and experimental comparisons.
The supplied extended abstract contains no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational complexity result. Its closest claim is the unnumbered statement “GCCF is NP-Hard,” cited to Voice et al. (2012a); the correctness of COP-GCCF is deferred to the journal version. So I cannot honestly give a numbered anchor, or present the paper’s GPU performance results as one. That leaves the positive case without the required anchor.
The strongest candidate mirror I see is a continuous version of the paper’s underlying coalition-structure problem. Let \(T\) be a finite set of agent types, with rational masses \(\mu_t\) summing to \(1\), and let \(H\) be a compatibility graph on types. Agents of the same type share all payoff-relevant attributes; an edge in \(H\) means agents of those types can cooperate. A coalition is described by a mass vector \(q\in\mathbb R_{\ge 0}^{T}\), feasible when its occupied types induce a connected subgraph of \(H\). Give the coalition a worth \(W(q)\), specified by a rational piecewise-linear formula. The decision is to find a finite or countable family of feasible coalition vectors \((q^j)_j\) with \(\sum_j q^j=\mu\) maximizing \(\sum_j W(q^j)\), or to decide whether that value reaches a supplied threshold.
This preserves the paper’s core question—partition agents into disjoint, graph-feasible coalitions to maximize total characteristic value. A plausible high-multiplicity regime is a large energy cooperative drawn from a small number of neighborhood and consumption classes: many households share each type, and a neighborhood compatibility graph captures which groups can cooperate. The continuous worth \(W\) represents normalized value for a coalition of each composition. This mirrors GCCF’s optimization problem, not the COP encoding or the paper’s runtime comparison.
For this proposed problem, I would tentatively expect hardness to persist when the combinatorics are encoded in the type graph and worth function and the number of types grows. That would be hardness transferred through type structure, provided a reduction can preserve many agents per type. With fixed \(T\) and piecewise-linear worths, continuous optimization may instead be tractable. The excerpt proves neither claim. Natural follow-up questions are whether hardness holds with bounded \(|T|\), what finite discrete instances converge to this model, and whether a more general graphon captures sparse individual friendships.
The weakest point is the aggregation itself: replacing an individual friendship graph with a type graph assumes that compatibility is shared across whole classes. And the finite formula for \(W\) imposes a representation choice absent from the paper’s unrestricted characteristic function. Those choices make the mirror precise, but the authors could reasonably ask whether it remains their general GCCF problem. Without an eligible numbered anchor, this is a plausible research direction, not a paper-anchored positive case.
The strongest case against starts with the missing anchor: the proponent identifies no numbered result in this paper that establishes a computational complexity claim. The statement that GCCF is NP-hard is background attributed to prior work; COP-GCCF’s correctness proof is deferred to the journal version; and the paper’s own contribution is a COP formulation plus experimental runtime and memory comparisons. Those comparisons matter, but they do not supply the named complexity result the proposed mirror is meant to extend.
There is also a fidelity problem with the proposed type model. In this paper, compatibility is an edge between particular agents, and a coalition must be connected in the graph induced by its members. Worths are unrestricted functions of the coalition \(S\). A type graph with masses replaces individual edges with compatibility shared across whole classes, while \(W(q)\) makes worth depend only on coalition composition. In a general sparse network, two coalitions with the same type masses can differ in connectivity and worth. To preserve those distinctions, types may need to encode individual neighborhoods and other relevant features, leaving many types with vanishingly small masses. That defeats the proposed aggregation for the instances this paper emphasizes.
The strongest repair would use a repeated-block network, with many interchangeable agents per block, a compatibility graph between blocks, and worths determined by composition; a more general graph-limit model could retain finer network structure. Those can be coherent models, but the first restricts the graph and characteristic function substantially, and the second needs a finite representation of its relation and worth data before it yields a computational problem with a meaningful input size. Neither is supplied by the paper. In particular, a dense graph limit does not automatically preserve the connectivity constraints of sparse friendship networks.
I would not claim that no such model could ever be worthwhile: the repeated-block version is a plausible research direction. But that possibility does not rescue the case for this paper as a continuous mirror. It would require choosing and defending a new network regime and a new worth representation, without a named computational result here to anchor the complexity question. So the negative case is strong against prioritizing this paper as a ChoCo mirror, but it is not airtight as a claim that no useful continuous coalition-formation model 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.