| paper | d4-conf-aaai-2021-1492 |
| 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}\)-hard; \(\mathrm{NP}\)-complete under the stated input promises, already with \(\tau=1\) and three affine pieces per alternative. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite type set \(K\), rational masses \(\mu_r\) summing to \(1\), \(m\) alternatives, rational continuous piecewise-affine functions \(g_j:[0,1]^{|K|}\to\mathbb{Q}\), and a rational threshold \(q\), does there exist an allocation \(x_{rj}\ge 0\) with \(\sum_{j=1}^{m}x_{rj}=\mu_r\) for each \(r\in K\) and \(\sum_{j=1}^{m}g_j(x_{\cdot j})\ge q\)?
A workforce is a nonatomic population of types \(r\in K\), with mass \(\mu_r\) of each type, assigned across discrete alternatives or tasks. Variables \(x_{rj}\) give the mass of type \(r\) assigned to task \(j\); each task’s value is a rational piecewise-affine function \(g_j\) of its type composition, and the objective is to maximize \(\sum_j g_j(x_{\cdot j})\).
The paper does not study repeated worker profiles or composition-based valuations, so it gives no evidence that this restricted regime captures the phenomena in its theorem or benchmarks.
fatal: False
The mirror covers the decision form underlying Theorem 2 for anonymous, composition-based team values; it leaves unrestricted named-coalition valuations, the paper’s reduction, its heuristic algorithms, and its empirical benchmark claims untouched.
The strongest mirror I see is Type-Anonymous Continuous SCSGA. Imagine a large workforce being divided into \(m\) task-specific teams. Workers share a type when they have the same task-relevant profile: the same skills, qualifications, and other attributes that affect team value. There may be millions of workers but only \(\tau\) types. Each worker still joins one team; because the population is nonatomic, the mass of any type can be split among teams.
An instance consists of types \(K\), rational masses \(\mu_r\) summing to \(1\), \(m\) alternatives, and a rational threshold \(q\). For each alternative \(j\), give a rational continuous piecewise-affine function \(g_j:[0,1]^\tau\to\mathbb{Q}\), represented by a finite rational polyhedral subdivision and affine formula on each cell. It gives the value of the team assigned to \(j\) from its type composition. The decision question is whether there is an allocation \(x_{rj}\ge 0\) such that
\[
\sum_{j=1}^{m}x_{rj}=\mu_r \quad\text{for every }r,
\qquad
\sum_{j=1}^{m}g_j(x_{\cdot j})\ge q.
\]
A yes-instance has the allocation matrix \(x\) as its solution. Equivalently, the underlying optimization problem is to maximize that sum of team values. The alternatives remain discrete; the population is what becomes continuous.
The lead anchor is Theorem 2, proved in this paper using a reduction and a cited hardness result. It says SCSGA is NP-complete. In its decision form, given agents \(A\), alternatives \(T=\langle t_1,\ldots,t_m\rangle\), a value function \(v(C,t)\), and a threshold \(k\), ask whether there is an ordered coalition structure \(\langle C_1,\ldots,C_m\rangle\) partitioning \(A\) with \(\sum_i v(C_i,t_i)\ge k\). The paper proves NP-hardness by reducing from CSG, whose NP-hardness it cites from Sandholm et al. (1999); it establishes membership in NP by checking a proposed structure’s value. This is the paper’s exact-complexity result. Its unnumbered heuristic experiments do not provide another eligible anchor.
The mirror preserves the central decision: partition the whole population into alternative-specific coalitions and assess the sum of their values. It makes the high-multiplicity assumption explicit by requiring agents of a type to be interchangeable and team values to depend on type composition. A plausible regime is a large logistics workforce divided among a fixed set of missions, with many workers in a small number of certification and skill profiles. The original paper’s unrestricted \(v(C,t)\) allows individual coalitions to have unrelated values; the mirror narrows that model to anonymous, type-composition-based values. That is a meaningful high-multiplicity version of their allocation problem, though it does not cover every SCSGA instance.
For unrestricted nonconcave piecewise-affine \(g_j\), I would expect the mirror to remain hard, most plausibly Class C: team-value complementarities can make the continuous allocation problem combinatorial even when no decision targets individual workers. This is a forecast, not a consequence of Theorem 2; its reduction from CSG does not by itself establish hardness for the type-anonymous continuous restriction. The key questions are whether hardness holds with fixed \(\tau\) or a restricted number of affine pieces, and where the boundary lies. If every \(g_j\) is concave piecewise-affine, the resulting optimization is an LP, giving a concrete tractable boundary. A fuller bridge would also compare the continuous optimum with finite, repeated populations of the same types.
The soft spot is the value-function extension. The paper permits arbitrary set values, while a continuous instance needs a finite representation of how value varies with mass. Requiring piecewise-affine functions is a defensible way to model composition-dependent team synergies, but it is an added modeling choice, and the paper does not study it. That limits the claim to a plausible mirror of the paper’s central optimization problem, rather than a continuization of its full input model.
Theorem 2 is a legitimate anchor: it gives an NP-completeness result for SCSGA. The strongest objection is that its hardness is tied to a value function \(v(C,t)\) that can assign unrelated values to every coalition. The paper’s reduction from CSG preserves that freedom by setting \(v(C,t)=u(C)\), where \(u\) may depend on exactly which agents are in \(C\). In the general case, agents can share a type only if swapping them leaves every relevant coalition value unchanged. That may force \(\tau=n\), so the theorem itself supplies no low-support, high-multiplicity regime.
The best repair is the proponent’s workforce model: group workers by task-relevant profile and let team value depend on type composition. That is plausible SCSGA. But it is a restricted valuation model, not a continuous version of the theorem’s input class. The discrete problem specifies values at integer composition vectors; it does not say how values should behave at fractional ones. Choosing a piecewise-affine extension supplies a new representation and new geometric structure. Concavity makes the resulting problem an LP by assumption; arbitrary nonconcave pieces raise a different optimization problem. Either could be worth studying, but neither follows from the paper’s NP-completeness result.
That distinction matters here because the paper’s experiments also use values generated independently for individual coalitions. Its main evidence does not show that repeated worker profiles preserve the phenomena it studies. So the strongest case against is that a continuous team-allocation problem would be a new, structured SCSGA model whose connection to this paper’s theorem is thin.
I would vote against treating Theorem 2 as a strong mirror of the paper. I cannot honestly establish the broader claim that no worthwhile scenario exists: a large workforce with repeated skill profiles is a natural setting, and the authors might recognize that restricted model as theirs. The negative case is weakest precisely there.
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.