| paper | d4-conf-atal-2014-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Both exact decision and additive value approximation are \(\mathrm{NP}\)-hard for every fixed rational \(\gamma\ge2\), including approximation when \(1/\varepsilon\) is polynomially bounded in \(L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), a type compatibility graph \(H=(T,E_H)\), rational interaction weights \(w_{tu}\), \(\alpha>0\), and fixed \(\gamma\ge 2\), maximize the sum of coalition payoffs over finite mass partitions \(x^1,\ldots,x^k\in\mathbb{R}_{\ge0}^{T}\), where \(\sum_j x_t^j=\mu_t\), each \(\operatorname{supp}(x^j)\) is connected in \(H\), and each payoff is \(F(x^j)=\frac12\sum_t w_{tt}(x_t^j)^2+\sum_{\{t,u\}\in E_H}w_{tu}x_t^jx_u^j-\alpha(\sum_t x_t^j)^\gamma\). Determine the exact optimum or return an additive-\(\varepsilon\) approximation.
A society with finitely many complete agent types carrying masses \(\mu\), and a type compatibility graph whose edges represent block-structured synergies. The decision is a finite partition of each type's mass into connected coalition compositions \(x^j\); the objective sums normalized pairwise synergy and coordination payoffs across coalitions.
The type-pair payoff models dense block interactions and cannot preserve the sparse, agent-level neighborhoods central to many of the paper's examples; the mirror therefore applies only when repeated types also have block-structured synergies.
fatal: False
The mirror covers the connected-coalition optimization and the bounding idea in Proposition 4 for a type-level mass model. It does not transfer the finite edge-contraction search, CFSS running times, parallel speedups, or empirical approximation ratios; Proposition 6 supplies the objective structure but is not itself a computational anchor.
There is no numbered NP-hardness or polynomial-time classification in this paper. Its numbered results are structural and algorithmic ingredients. The strongest computational anchor is Proposition 4, proved here: on a lattice whose search tree proceeds by coarsening and whose subtree supremum can be computed efficiently, if the objective splits into a monotone part \(f^+\) and an antimonotone part \(f^-\), then the value of \(f^-\) at a node plus the value of \(f^+\) at the coarsest partition reachable below it is an admissible upper bound on every solution in that subtree. That is a result about bounding the underlying coalition structure generation problem, not a claim that the full optimization problem is in P.
My lead mirror is Continuous Edge-Sum Synergy CSG, grounded in Proposition 6, also proved here. That proposition says the paper’s edge-sum-with-coordination-cost objective is an \(m+a\) function: its positive internal edge weights form a monotone component under coalition merging; its negative internal edge weights and coordination penalties form an antimonotone component. This is the concrete objective class for which the paper uses the bounding method.
Here is the continuous problem. The input is a finite set \(T\) of complete agent types, a rational mass vector \(\mu\) with \(\sum_{t\in T}\mu_t=1\), and a type compatibility graph \(H=(T,E_H)\). A type records everything relevant to the problem: for example, a household’s load profile, network role, and interaction costs. Assume agents of a type are interchangeable, agents within a type can form a coalition, and an edge of \(H\) means every agent of one endpoint type can connect to every agent of the other. A coalition is feasible when its positive-mass type support is connected in \(H\).
For a coalition containing mass vector \(x\), use the payoff
\[
F(x)=\frac12\sum_{t\in T} w_{tt}x_t^2+
\sum_{\{t,u\}\in E_H}w_{tu}x_tx_u
-\alpha\left(\sum_{t\in T}x_t\right)^\gamma,
\]
where the weights and \(\alpha>0\) are rational and \(\gamma\ge2\) is fixed. The quadratic terms are the normalized limit of edge sums in a dense, repeated-type network; the last term is the coordination cost. The decision is to partition the population mass into feasible coalitions to maximize the sum of their payoffs. A solution is a finite list \(x^1,\ldots,x^k\) of rational mass vectors with \(\sum_j x^j=\mu\), each with connected support, together with its objective value; for an additive-\(\varepsilon\) version, return a feasible list within \(\varepsilon\) of the supremum. Because the population is atomless, each type’s mass can be split among coalitions while each individual unit of mass still belongs to one coalition.
This is a credible regime for large energy cooperatives: many households, far more households than standardized load and network-role types, and recurring compatibility relations between those roles. I would not claim that the paper’s 2,732 measured households already have small type support. The mirror is for settings where profiles and roles recur at scale. I scale pair interactions and coordination costs to obtain finite per-capita values; that co-modification is explicit, and it is part of the mirror.
For this model, the positive and negative parts of the edge objective retain the monotonicity that Proposition 6 uses. Proposition 4’s bound therefore has a natural analogue: at a partial partition, evaluate the antimonotone part there and bound the monotone part by its value at the coarsest reachable feasible partition.
A second, more general mirror for Proposition 4 is Continuous \(m+a\) Synergy CSG. Its input is the same typed society and compatibility graph, plus succinct rational functions \(F^+\) and \(F^-\) specifying coalition payoffs, with the promise that their sums over a partition are respectively monotone and antimonotone under feasible coarsening. The question and solution format are the same: find a finite feasible mass partition maximizing \(\sum_j(F^+(x^j)+F^-(x^j))\), or an additive-\(\varepsilon\) approximation. The edge-sum problem is a specific instance; the general problem asks how far the bounding idea extends beyond it.
My expectation for the general version is Class C in full generality: arbitrary succinct nonlinear payoff functions can make mass allocation hard even before the graph is considered. For the edge-sum version, my tentative expectation is Class B when the number of types varies, because the signed interaction and connectivity choices in \(H\) preserve combinatorics in the type graph. That prediction needs a reduction showing that splitting a type’s mass does not defeat the discrete choices. Further questions are whether there is a polynomial pricing algorithm for a coalition composition \(x\), how runtime depends on \(\tau=|T|\) and \(\varepsilon\), and whether discrete instances on repeated-type graph blow-ups converge to this optimum.
The mirror covers the paper’s edge-sum objective and its \(m+a\) bounding argument. It does not turn the reported speedups, parallel performance, or 2,700-agent approximation ratios into theorems for the continuous model.
The weakest point is substantial: Proposition 4’s efficient bound does not give a polynomial-time algorithm here. The finite edge-contraction search tree in the paper does not carry over directly when type mass can split continuously. Also, the block-structured type graph is a modeling assumption, not a feature of every social network. Those gaps limit claims about transferred algorithms, but they do not make the mirror artificial: the population is the continuous object, while the problem remains the authors’ connected-coalition optimization with synergy-based values.
The strongest case against is that the proposed mirror loses the feature that makes this paper about *synergy graphs*: its sparse, agent-level pattern of relationships. A type distribution records how much population has each kind of agent. It does not, by itself, record which particular agents are connected or the weights on their particular edges.
That matters directly for Proposition 6. The proposed \(F(x)\) treats a coalition’s pairwise payoff as a function of its type masses, such as \(w_{tu}x_tx_u\). This is a dense block-graph model: a positive type-pair weight stands for interaction across essentially all pairs in those two groups. In a sparse graph, most such pairs have no edge. If the edge sum is normalized by \(N^2\), its contribution vanishes; if normalized by \(N\), the type-pair masses alone do not determine it. For example, a path with \(N\) agents of one type has only \(N-1\) edges. Its total internal edge value is not the quadratic-in-mass value of a clique of that type. Encoding the actual neighborhoods in the types can preserve the answer, but in a generic sparse graph that makes nearly every agent a different type, so the proposed high-multiplicity reduction disappears.
The energy-purchasing example does not remove this problem. Repeated load profiles could make a sensible type system for the purchasing calculation, but the paper’s feasible-coalition relation comes from a separate social or trust graph. If everyone of two compatible types is treated as mutually connected, the mirror has replaced that sparse graph with a dense block graph. If the graph is retained at individual resolution, the load-profile distribution is not enough to determine feasible coalitions. A more elaborate continuous graph limit might preserve the relationships, but then the input includes that graph structure and coalition feasibility depends on it; it is no longer the proposed finite type-mass problem.
Proposition 4 is a real algorithmic anchor, but its useful bound is tied to the paper’s finite search tree. Its states record indivisible edge-contraction decisions, and its subtree supremum is computed from the remaining edges. With divisible masses, there are continuously many possible splits and no corresponding finite contraction tree. One can formulate a configuration LP over coalition compositions, but then the central computational question is its pricing problem over compositions with connected support. The \(m+a\) condition alone does not make that pricing problem easy; for arbitrary succinct payoff functions its difficulty depends on the encoding, while for the specific quadratic model it still carries the type-graph structure. The proposed analogue therefore either supplies a general inequality without the paper’s efficient search procedure or asks a new pricing question whose computational content must be established separately.
I would not claim that a continuous coalition model is impossible. A dense population with repeated roles and block-structured synergies is conceivable, and the proposed quadratic formulation could be worth studying for that setting. The negative case is that this is a different network regime from the paper’s sparse relational problem. The gap is especially clear for Proposition 6; for Proposition 4, the monotonicity insight survives formally, but the finite combinatorial machinery that makes it an algorithmic result does not.
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.