| paper | d4-conf-atal-2010-0251 |
| 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: \(\mathrm{NP}\text{-hard}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational population masses \(\mu_t\), and rational formulas assigning each coalition block’s per-capita value from its mass, type mix, and specified aggregate moments of the full partition, find a finite mass partition with total value within \(\varepsilon\) of the supremum. Require the formulas to allow mixed externalities and satisfy the paper’s typed competition and complementation conditions.
An anonymous partition-function game with finitely many complete agent types: blocks are nonzero type-mass vectors \(x^j\) summing to \(\mu\), and the objective sums each block’s mass times its per-capita value under the full mass partition.
The paper allows coalition values to depend on agent identities even within a type, and Theorem 3’s finite set relations do not automatically yield valid bounds for mass blocks; the proposed mirror therefore needs an explicit exchangeable-type regime and new continuous bounding definitions.
fatal: False
The mirror covers optimal coalition structure generation and a possible mass analogue of Theorem 3’s pruning criterion; it leaves Theorem 2’s initial bound, the empirical pruning results, and identity-dependent instances without a continuous formulation.
The strongest honest case is a high-multiplicity mirror of their optimal coalition structure generation problem. I would anchor it on Theorem 3, proved in this paper. It is an algorithmic pruning theorem, not a claim that CSG is in P or is hard; the paper gives no named complexity-class result. Theorem 3 says: for a coalition \(C\) and a partition \(P\) of \(C\), a search branch containing \(P\) can be pruned if there is another partition \(P'\) of \(C\) whose lower-bound value is at least \(P\)’s upper-bound value, and every block \(p'\in P'\) satisfies at least one of these conditions: (1) \(p'\) is already a block of \(P\); (2) \(p'\subset p\) for some \(p\in P\), and \(T_p\supseteq T_{\bar C}\); or (3) \(T_{p'}\cap T_{\bar C}=\varnothing\), and there is an \(S\subseteq P\) with \(p'\subseteq\alpha(S)\), such that each \(p\in S\) with \(T_p\cap T_{\bar C}=\varnothing\) is contained in \(p'\), while each \(p\in S\) with \(T_p\cap T_{\bar C}\ne\varnothing\) has \(T_p\supseteq T_{\bar C}\). Here \(T_{\bar C}\) is the set of types outside \(C\). The proof uses the paper’s competition and complementation assumptions to show that replacing \(P\) by \(P'\) cannot lower the value of the rest of the structure.
A natural regime is a large marketplace, grid, or task-allocation system with many participants but relatively few complete behavioral types. A type records every feature relevant to coalition values and externalities; \(\mu_t\) is the fraction of the population of type \(t\). The paper itself builds its framework around repeated types, from one type shared by everyone to all-distinct types, so the high-multiplicity regime is already part of its model. For example, a large service market might have millions of participants distributed across a few supplier or customer types, with complementarities between some types and competition between others.
Here is a concrete continuous problem I would hand to a prover: \(\varepsilon\)-Mixed-Externality Mass CSG. An instance gives a finite type set \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), and rational formulas for coalition values. A coalition is a nonzero mass vector \(x\in\mathbb R_{\ge0}^{T}\), and a continuous coalition structure is a finite list \(\Pi=(x^1,\ldots,x^K)\) with \(\sum_j x^j=\mu\); \(K\) is allowed to vary. Write \(r_j=\sum_t x_t^j\) and \(q^j=x^j/r_j\). The value formula gives each block’s per-capita worth from its mass \(r_j\), its type mix \(q^j\), and a finite vector \(z(\Pi)\) of rationally specified aggregate moments of the coalition-mass distribution. The total worth is \(W(\Pi)=\sum_j r_j u(r_j,q^j;z(\Pi))\). The formulas permit mixed externalities and obey the paper’s typed sign assumptions: splitting a competing block weakly benefits the focal coalition, and joining complementary blocks weakly benefits it. Given a rational \(\varepsilon>0\), the task is to return a finite list of rational mass vectors whose total worth is within \(\varepsilon\) of the supremum over feasible mass partitions.
The mass version of Theorem 3 would compare partitions of a subpopulation mass vector: set inclusion becomes componentwise containment of mass vectors, type sets become positive supports, and the same upper-bound/lower-bound comparison can justify pruning. The underlying question remains optimal coalition structure generation, rather than the pruning rule itself.
My provisional expectation for this general moment-polynomial version is Class C, continuum-specific hardness: the objective retains global, nonlinear coupling through mixed externalities, so allowing fractional masses does not by itself turn the search into an LP. That is a conjecture about the proposed problem, not a result of this paper. If values have stronger affine or convex structure, Class A becomes plausible; Class B would need a reduction that survives fractional splitting. Useful follow-up questions are whether fixed support size permits efficient approximation under restricted value formulas, and whether a continuous pruning rule can recover the paper’s discrete bounds.
The weakest point is the input model. The paper allows broad partition-dependent values but does not give a succinct continuous value representation or complexity theorem. The moment-polynomial specification makes the mirror computable and explicit, but it is an additional modeling choice. The authors should recognize the population, type masses, and mixed-externality optimization as their problem; whether they would accept this particular continuous value language is the point most open to challenge.
The strongest objection is to the proponent’s anchor, Theorem 3, as a mirror of the paper’s model. The paper’s types do not make agents interchangeable in all respects relevant to coalition values. They classify whether coalitions compete or complement one another; the value function \(v(C,CS)\) can still depend on the identities of agents and coalitions. The experimental construction makes this explicit with coalition-specific values \(v_C\) and externality weights \(e_C\). If those details are part of an agent’s complete type, many instances have nearly one type per agent, so the repeated-type regime the mirror needs is absent.
The proposed mass formulation supplies the missing symmetry itself: values depend on type mixes, block masses, and aggregate moments. That may define a coherent model, but it adds assumptions the paper does not impose. Nor does Theorem 3 immediately transfer by replacing set inclusion with componentwise containment. Its proof uses finite blocks of agents and exact set relations; a mass version needs new definitions for splitting mass, representing feasible coalition structures, and bounding values near zero-mass types. The paper’s sign assumptions alone do not provide that bridge.
A stronger, anonymous version is plausible: a large marketplace with a few genuinely exchangeable supplier and customer types, where coalition returns depend on how the rest of the population is grouped. I cannot honestly rule that out as a worthwhile continuous CSG problem. The best case against is therefore narrower: the proponent has not shown that this paper’s Theorem 3 gives a faithful mirror, and the paper’s actual formalism leaves the key anonymity assumption open. That weakens this anchor substantially; it does not establish the requested universal claim that no worthwhile mirror exists in any scenario.
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.