| paper | d4-conf-ijcai-2020-0047 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in the binary input length. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational type masses \(N\mu_t\), and an explicit value \(w(q)\) for each feasible integral team composition \(q\in\mathbb{Z}_{\ge 0}^{T}\setminus\{0\}\), find a maximum-welfare allocation \(x_q\ge 0\) satisfying \(\sum_q q_t x_q=N\mu_t\) for every \(t\in T\).
A continuous-type configuration LP: each type \(t\) represents interchangeable agents, each \(q\) is an integral team composition, and \(x_q\) is the fractional number of teams of composition \(q\). Maximize \(\sum_q w(q)x_q\) subject to exhausting the mass of every type.
The mirror covers the maximum-welfare CSG objective and its exact-search goal. It does not transfer CSG-UCT’s UCB1 search policy or establish that compact responder utilities have tractable pricing.
My case is deliberately narrow. The Introduction says CSG is NP-complete, citing Sandholm et al. (1999), but that is an unnumbered result from elsewhere, so it cannot be my anchor. The strongest named result proved in this paper is Theorem 1: CSG-UCT is complete given sufficient time. In full, the theorem says that with enough time the algorithm eventually adds every coalition structure in \(\Pi_A\) to its search tree and can return an optimal one. This is an exact-search guarantee, not a polynomial-time result or a complexity classification. I use it to anchor the underlying optimization problem: finding a maximum-welfare coalition structure.
A plausible high-multiplicity regime is disaster response with hundreds or thousands of responders drawn from a modest number of standard capability profiles. A type could be a responder’s complete role-capability profile—medic, firefighter, soldier, transporter, and any other attributes that affect coalition value. The mass \(\mu_t\) is the fraction of responders of type \(t\). This is a different, plausible operational regime from the paper’s experiments, where random agent-specific capabilities may leave almost everyone with a distinct profile.
Here is the continuous problem I would put to a prover: Continuous-Type Coalition Structure Generation. An instance gives a finite type set \(T\), rational proportions \(\mu_t\geq 0\) summing to \(1\), a rational population scale \(N\geq1\), and a rational worth \(w(q)\geq0\) for each feasible coalition composition \(q\in\mathbb Z_{\geq0}^{T}\setminus\{0\}\) with \(\sum_t q_t\leq\lfloor N\rfloor\). A composition \(q\) describes one team with exactly \(q_t\) members of type \(t\); for the full CSG problem, include every such composition. The question is to find a maximum-welfare allocation of coalition mass:
\[ \max_{x_q\geq0}\ \sum_q w(q)x_q \qquad\text{subject to}\qquad \sum_q q_t x_q=N\mu_t\quad\text{for each }t\in T. \]
The solution is an optimal rational vector \(x\). Its coordinate \(x_q\) is the continuous number of teams with composition \(q\); each team still has an integral composition, while the population may contain a fractional mass of teams of each kind. When \(N\mu_t\) are integer counts, a discrete coalition structure is an integer solution to the same constraints. Relaxing those integer team counts to real values gives this continuous problem.
The authors should recognize this as their CSG objective: teams partition the population, and their values add to total social welfare. The model groups agents only when their preferences, capabilities, and other relevant attributes make them interchangeable, as required for high multiplicity. Coalition value can still depend on team composition and complementarity among skills, so the optimization question is not reduced to maximizing additive individual scores.
For the stated explicit-value-table input, this is a linear program and is Class A: tractable, in time polynomial in the table size, \(|T|\), and the rational bit length. That bound matters: the number of compositions can grow quickly with \(N\) and \(|T|\). If the value function is supplied compactly instead, tractability turns on the pricing problem—whether one can efficiently find a composition maximizing \(w(q)-\pi\cdot q\) for a proposed dual vector \(\pi\). Further questions include whether that pricing problem is tractable for natural responder utilities, and whether the continuous optimum can be rounded to a good discrete structure when the population is large and the number of types is modest.
The weakest point is that Theorem 1 proves only eventual completeness; it does not imply efficient search. The LP’s tractability comes from the continuous formulation and explicit coalition-composition values, not from a polynomial-time result in the paper. Also, if values depend on random, coalition-specific details that cannot be captured by a type composition, this mirror does not cover those instances. That limits the scope to the underlying CSG problem in a credible repeated-type regime, rather than the paper’s entire benchmark suite or its MCTS algorithm.
The strongest objection is that the proponent’s anchor shifts away from what Theorem 1 proves. The theorem says CSG-UCT eventually visits every node in a finite search space, so it can find an optimum. It gives no complexity bound. The proposed LP does not mirror that completeness argument or the algorithm’s MCTS guarantees; it reformulates the underlying CSG objective as a fractional configuration problem.
That reformulation also narrows the paper’s model. Its characteristic function can assign values to individual coalitions, and several benchmark utilities use coalition-specific random values or agent-specific parameters. In those cases, coalition composition alone does not determine value. A type would need to encode the relevant individual interactions, potentially leaving almost every agent in a different type. The paper gives no basis for expecting the resulting type count to stay small.
The proposed tractability claim is correspondingly limited. With an explicit table of values for every composition, the LP is polynomial in a table that can itself be enormous. With compact values, the central question becomes pricing over compositions, and the paper provides no structure that makes that search easy. So the proponent has not shown that Theorem 1’s contribution, or the paper’s benchmark results, yields an algorithmic gain in this continuous model.
That is the strongest negative case, but it does not rule out a worthwhile mirror. A disaster-response setting with a small number of repeated responder profiles and a value function determined by team composition is plausible; a continuous allocation of mass among those teams is a recognizable high-multiplicity CSG problem. The authors could reasonably recognize it as their problem, and pricing for natural role-coverage utilities is a concrete computational question. I can argue that the paper itself does not establish tractability for that regime, but I cannot honestly argue that no such scenario produces a worthwhile mirror.
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.