| paper | d4-journals-jair-2012-0043 |
| 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: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a planar role graph \(H=(T,F)\), positive rational masses \(\mu_t\) summing to \(1\), rational interaction densities \(a_{tu}\) on edges, and a rational threshold \(K\), decide whether the population mass can be partitioned into coalitions with total value at least \(K\). A coalition \(q\) has mass vector \(x^q\), where \(x_t^q\ge 0\) and \(\sum_q x_t^q=\mu_t\); its total value is \(\sum_q\sum_{\{t,u\}\in F}a_{tu}x_t^q x_u^q\).
A population is a distribution \(\mu\) over roles \(T\), with a planar role graph specifying which role classes can cooperate and rational pairwise interaction densities on its edges. Decision variables are coalition mass vectors \(x^q\); maximize \(\sum_q\sum_{\{t,u\}\in F}a_{tu}x_t^q x_u^q\) subject to \(\sum_q x_t^q=\mu_t\).
The planar hardness reduction applies to the role graph; its corresponding graph of individual pairwise links can be nonplanar, so this does not extend the paper's result to planar person-to-person networks.
fatal: False
The mirror covers Theorem 2's planar edge-sum hardness result and its stated minor-free consequence. It leaves the general IDM results, treewidth algorithms, and separator-based bounds unmirrored.
The strongest mirror is the paper’s planar edge-sum hardness result. Theorem 2, proved in this paper in §5.1, says that edge-sum graph coalition structure generation is NP-complete even on planar graphs, and that a 3-SAT instance with \(m\) clauses can be represented by such a planar instance with \(O(m^2)\) nodes. Here the value of a coalition is the sum of the weights of graph edges whose endpoints it contains. The paper also notes that the hardness extends to \(K_k\)-minor-free graphs for \(k\ge5\). I would use the threshold decision version of this result as the anchor.
A credible high-multiplicity regime is a large population divided among a relatively small number of interchangeable organizational roles. For example, many agents may work in a planar network of service roles or local partner classes. Members of one role have the same interaction profile; an edge between roles means their members can cooperate, with the same pairwise synergy for every such pair. The population itself is a distribution over the supported roles, with mass \(\mu_t\) at role \(t\). There can be \(N\gg\tau\) agents, where \(\tau\) is the number of supported roles; the type graph can still grow with the instance. This is not an arbitrary story grafted onto the paper: its §6 discusses coalition generation with agent types, and the paper’s motivating examples include pairwise agent weights.
Call the mirror Mass Edge-Sum Coalition Structure Generation. An instance consists of a planar type graph \(H=(T,F)\), positive rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), rational interaction densities \(a_{tu}\) for edges \(\{t,u\}\in F\), and a rational threshold \(K\). A solution partitions the population mass into coalitions, described by a finite or countable family of mass vectors \(x^q\in\mathbb R_{\ge0}^{T}\), with \(\sum_q x_t^q=\mu_t\) for every type \(t\). Its value is \(\sum_q\sum_{\{t,u\}\in F}a_{tu}x_t^q x_u^q\): the integrated pairwise synergy of members placed together. Ask whether a partition of value at least \(K\) exists, or, in the optimization form, return a maximum-value partition. Disconnected coalition supports can be split into their graph components without changing the value, so connected supports may be required.
The key point is that this is a real mass-allocation question: a type’s mass may be split among coalitions. But for this edge-sum objective, splitting cannot improve the optimum. Fix a type \(t\) and hold the allocations of all other types fixed. The terms involving \(t\) are linear in the amounts \(x_t^q\). Thus some coalition \(q\) has per-unit contribution at least the current mass-weighted average; moving all of \(t\)’s mass into that coalition weakly increases the value. Repeating for each of the finitely many types yields a partition in which every type stays together. If any resulting support is disconnected, split it into components. Therefore the continuous optimum equals the discrete type-partition optimum with edge weights \(a_{tu}\mu_t\mu_u\). This is a “turns out” identity: fractional mass allocations are allowed, but an optimal one can be chosen pure.
That identity makes the expected direction hardness transfers (Class B). Given a planar edge-sum instance with \(\tau\) vertices and edge weights \(w_{tu}\), set \(\mu_t=1/\tau\) and \(a_{tu}=\tau^2w_{tu}\). A pure type partition then has exactly the original value, and the purification argument shows fractional partitions cannot raise it. So the paper’s threshold instance is equivalent to the mass problem. Its 3-SAT reduction remains polynomial, and the continuous problem’s threshold version is NP-complete. The hardness is carried by the number and arrangement of types, not by the number of individuals within each type; taking many agents per role does not remove it.
The authors should recognize the underlying question: maximize the value of a partition under graph-constrained pairwise cooperation. The continuous change is that roles carry population mass and pairwise value is integrated over that mass. The paper’s discussion of agent-type representations supports the high-multiplicity interpretation; existing type-based work supports that regime rather than colliding with this mirror.
The mirror covers Theorem 2’s planar edge-sum result only. It does not claim to continuize the paper’s full class of IDM valuations or its bounded-treewidth algorithms. Its weakest point is the type graph: uniform pairwise interaction across two roles amounts to a mean-field interaction between their populations, and the resulting graph is the graph of roles, not necessarily the literal planar graph of individual agents. If the authors require every edge to remain a specific person-to-person link, this co-modification may not be their problem. The case survives for settings where interaction is genuinely organized by role classes and links between classes—precisely where population mass, rather than individual identities, is the useful description.
The planar hardness theorem is a real computational result, so I cannot dismiss this anchor for lack of something to mirror. The strongest objection is that the proposed mass model changes what the paper’s graph describes. In the paper, vertices are individual agents and edges are particular cooperation links. In the proposed model, an edge between two roles gives every member of one role the same interaction with every member of the other. The corresponding individual graph is a complete bipartite blow-up of the role graph. It can be nonplanar even when the role graph is planar: two role classes of size at least three joined by an edge already contain a \(K_{3,3}\). So the reduction in Theorem 2 establishes hardness for a planar graph of roles, not for a planar high-multiplicity instance of the paper’s individual-agent problem.
Requiring the individual graph to remain planar makes the mirror much narrower. Exact types must preserve the agents’ interaction neighborhoods; adjacent type classes then have complete bipartite links, which rules out having three or more agents in both classes. The paper’s planar hardness construction uses its graph structure to encode a SAT instance, while the type classes large enough to represent substantial multiplicity cannot reproduce that structure as a planar graph. If we instead retain sparse, person-to-person links, masses alone do not determine how many links fall inside each coalition. The proposed product \(x_t^q x_u^q\) assumes dense interaction between roles; sparse networks need additional information about links and their placement.
A stronger version of the proponent’s proposal is still available: treat roles as the graph’s vertices and define a continuous problem directly on a planar role graph. That is a coherent population model, and the paper’s discussion of agent types gives it some foothold. But its hardness theorem concerns a quotient graph whose vertices carry masses, rather than a planar network of individual agents. Whether the authors would recognize this as their problem is the uncertain step. Abandoning planarity and using an arbitrary role graph avoids that mismatch, though it no longer mirrors the planar result.
The purification argument does not defeat this revised mirror. It shows that the continuous optimum has a pure type-level solution, but the programme explicitly allows an identity between discrete and continuous optima to be a result. Nor does the paper’s existing agent-type literature count against the mirror; it supports the regime’s plausibility.
So the best negative case is limited: the proposed reduction does not carry the paper’s *planar individual-network* hardness into a high-multiplicity planar network. I cannot honestly extend that objection to rule out the role-graph model. It remains a plausible continuous computational question, and the universal claim that no worthwhile mirror exists is weak.
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.