| paper | d4-conf-atal-2014-0412 |
| 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}\)-hard even for \(m=\tau=1\) and \(\varepsilon=1/4\). The explicit-list requirement also rules out the requested polynomial running time unconditionally. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), and a rational piecewise-linear coalition-value function \(\phi\) on \([0,\mu]\), compute a finite list of nonzero vectors \(x^1,\ldots,x^k\) with \(\sum_j x^j=\mu\) whose total value \(\sum_j\phi(x^j)\) is within \(\varepsilon\) of the supremum over such lists. Determine the complexity in \(|T|\), the number of linear pieces, input bit length, and \(\log(1/\varepsilon)\), including whether dynamic programming over type-mass splits admits useful pruning.
A population of sensor types with masses \(\mu_t\); each coalition is represented by its type-mass vector \(x\) and has value \(\phi(x)\). A solution partitions \(\mu\) into finitely many such vectors and maximizes their total value.
Theorem 4’s split rule is based on finite coalition cardinalities, and the cases do not show that it yields useful pruning for arbitrary type-mass vectors.
fatal: False
The mirror covers typed coalition structure optimization and the algorithmic question of handling mass-vector splits. It leaves aside IDPG’s hardware synchronization bound, subset indexing, memory-access optimizations, empirical speedups, and coalition values that depend on individual identities.
The strongest continuous analogue I can make is \(\varepsilon\)-Mass Coalition Structure Generation. Imagine a large fleet of sensors drawn from a small number \(\tau\) of types, where a type fixes every feature relevant to coalition value, such as location, capability, and energy profile. The fleet size \(N\) is large while \(\tau\) stays modest. A coalition is described by its type-mass vector \(x\), and its value is \(\phi(x)\).
An instance gives rational population masses \(\mu\), with \(\sum_t\mu_t=1\), and a rational piecewise-linear function \(\phi\) on \([0,\mu]\). Assume \(\phi(0)=0\) and \(|\phi(x)|\le B\|x\|_1\), so the objective is bounded. A feasible coalition structure is a finite list of nonzero vectors \(x^1,\ldots,x^k\) with \(\sum_j x^j=\mu\). The problem is to return a list whose value \(\sum_j\phi(x^j)\) is within \(\varepsilon\) of the supremum over all such lists. The list is the solution; its vectors specify the mass of each type assigned to each coalition.
This has a direct high-multiplicity interpretation. For \(N\) with \(N\mu_t\) integral, give a discrete coalition containing \(k_t\) agents of type \(t\) value \(N\phi(k/N)\). Its total value divided by \(N\) is exactly the mass objective. As \(N\) grows, the grid of possible coalition compositions becomes finer, so any fixed finite mass partition can be approximated by discrete coalition structures. The paper itself motivates coalitions with applications such as sensor fleets, and this model gives that story a credible many-agents/few-types regime.
My provisional expectation is that the unrestricted-\(\tau\) problem is hard, probably because the combinatorics can persist in the type-composition space. For fixed \(\tau\), piecewise-linear geometry may make it tractable. The useful questions are whether there is an efficient \(\varepsilon\)-algorithm in \(\tau\), the number of linear pieces, the input bit length, and \(\log(1/\varepsilon)\); whether fixed-\(\tau\) tractability holds; and whether optimal or near-optimal solutions need many coalitions.
There is a serious anchor problem: the paper has no named result asserting a complexity classification for Coalition Structure Generation. Theorem 2, proved here, says that every parallelization of IDP requires at least \(\lfloor n/2\rfloor-1\) synchronization points; the paper’s stage scheme meets that bound. The other numbered theorems concern IDPG’s stage dependencies, subset enumeration, and which splits IDP evaluates. These are real algorithmic results, but they do not establish that the underlying optimization problem is in P, hard, or otherwise classified. The reported GPU speedup is empirical. So \(\varepsilon\)-Mass CSG is a plausible mirror of the paper’s underlying problem, but it cannot honestly serve as an anchor-based positive case under your rule.
The weakest point is also the model’s main assumption: the paper allows coalition values to depend on the exact members. The mirror needs values to depend only on type composition. That is a natural high-multiplicity regime for homogeneous sensor fleets, but the paper neither specifies it nor studies its complexity.
The strongest negative case is that this is a GPU algorithm paper, not a paper that classifies the complexity of a coalition problem. The \(O(3^n)\) bound for IDP is attributed to earlier work; this paper’s results concern IDPG’s parallelization, subset enumeration, and memory access. The only plausible result to anchor a mirror on is Theorem 2, but it lower-bounds synchronization points in IDP’s finite, subset-indexed dependency graph. That is an implementation constraint, not a complexity result about coalition structure generation.
A more careful continuous version of that theorem still has no scale-independent object to measure. Fixing the population at unit mass makes \(n\) disappear. Discretizing it into \(N\) increments gives a synchronization lower bound that grows with \(N\), so it diverges as the mesh is refined. A mass-based dynamic program would have a dense set of possible splits, not IDP’s finite stages; another continuous optimizer might have no synchronization stages at all. Any resulting bound would describe a chosen algorithm and discretization, not the continuous coalition problem.
The better underlying mirror is the proponent’s typed sensor-fleet model: coalition value depends on a vector of type masses, and the task is to partition the population to maximize total value. That is coherent and fits the paper’s application story. But it replaces the paper’s general characteristic function over agent identities with a new, succinct input model \(\phi\). It may be a worthwhile ChoCo problem, but it does not mirror a result established here. The proposed finite-list formulation also needs a careful bridge from discrete instances: discrete partitions can contain \(O(N)\) small coalitions, and the limit may not be captured by a fixed finite list. A countable or measure-based formulation might repair that, but it would further define a new problem rather than recover IDPG’s theorem.
So the negative case is strong against a result-based mirror of this paper, and Theorem 2 does not rescue one. It is weak against the broader claim that no worthwhile continuous mirror exists: a typed, high-multiplicity coalition problem remains plausible and may be worth studying on its own. I would not defend the universal claim more strongly than that.
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.