| paper | d4-journals-jair-2025-0101 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: The problem is $\mathrm{NP}$-complete, already for $h=1$, $\tau=1$, and universal eligibility. Hardness also holds for $\tau=2$ with distinct types and fixed masses $\mu_1=\mu_2=1/2$. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 16
statement extracted from the paper’s text layer
Given a finite task set \(Q\), type masses \(\mu_t\) with \(\sum_t\mu_t=1\), per-unit resource vectors \(b_{tk}\), eligibility sets \(I_t\), per-capita task demands \(d_{qk}\), and rewards \(r_q\), choose \(y_q\in\{0,1\}\) and resource allocations \(x_{tqk}\ge 0\) to maximize \(\sum_{q\in Q}r_qy_q\), subject to \(x_{tqk}=0\) when \(q\notin I_t\), \(\sum_qx_{tqk}\le\mu_tb_{tk}\), \(\sum_tx_{tqk}=d_{qk}y_q\), and \(x_{tqk}\le\mu_t\min\{b_{tk},d_{qk}\}y_q\). Tasks remain indivisible; allocations may split type mass across tasks. Determine the complexity of deciding whether a feasible allocation has reward at least \(K\).
A distribution over complete agent types, with each type’s mass supplying its per-unit resources across eligible tasks. Binary task decisions determine completed tasks; real-valued type-level allocations enforce resource demands and shared supply limits.
The paper’s random experiments do not establish that their instances contain repeated complete types; this limits evidence about those experiments, though the standardized-unit regime is independently plausible.
fatal: False
The mirror covers the task-based OCSGP optimization question anchored by Proposition 16. It leaves the EAF’s empirical performance and the separate feasibility-checking results unexamined.
My lead is the continuous task-based OCS generation problem for large pools of standardized response units. Imagine a disaster-response system with many units that share the same resource inventory and the same set of locations they can serve. A type \(t\) records that complete description: its per-unit resource vector \(b_t\) and its eligible task set \(I_t\). The type has population fraction \(\mu_t\), with only \(\tau\) types represented even if the pool contains many thousands of units. Tasks are service locations or orders; each has a resource demand and a reward for completion.
Here is the mirror I would hand to a prover. Let \(Q\) be the finite task set, and let \(N\) be the population scale. Task demands \(D_{qk}\) are aggregate demands; in a growing population family, hold \(D_{qk}/N\) fixed. Choose \(y_q\in\{0,1\}\) for each task and allocate resource mass \(x_{tqk}\ge0\) from type \(t\) to task \(q\), maximizing \(\sum_{q\in Q} r_qy_q\). Require \(x_{tqk}=0\) when \(q\notin I_t\), \(\sum_q x_{tqk}\le N\mu_t b_{tk}\), and \(\sum_t x_{tqk}=D_{qk}y_q\) for every task and resource. Also require \(x_{tqk}\le N\mu_t\min\{b_{tk},D_{qk}\}y_q\), reflecting the paper’s bound on each unit’s contribution. The allocation to a task defines its serving coalition; the same type’s mass can contribute to several coalitions, subject to its total resource limit. Fractional type-level allocations represent distributions over integral bundles received by individual units. Thus the model keeps tasks all-or-nothing and keeps the paper’s resource and interest constraints, while replacing the named finite agents with mass over complete types.
The anchor is Proposition 16, “The OCSGP is NP-complete.” It is proved in this paper, in Appendix B: the proof establishes membership in NP and reduces from the optimal OCS problem in threshold task games, citing Chalkiadakis et al. (2010) and Zhan et al. (2012) for that problem’s NP-completeness. In the paper’s special case, there is one resource type and every agent is interested in every task. The continuous problem above has a direct knapsack subcase too: use one type, one resource, and tasks with demands \(a_q\) per unit of population and rewards \(r_q\). A task subset is feasible exactly when its total demand is at most the type’s capacity. The decision version is therefore 0–1 knapsack. This remains hard even with \(\tau=1\): the combinatorics are in which indivisible tasks to complete, not in how many distinct agent types there are. I expect this mirror to be hardness-transferring, not tractable or continuum-specifically hard.
This is a plausible mirror of the authors’ problem because their objective and constraints already depend on agents through their task interests and finite resource supplies. In a regime with many interchangeable response units and a much smaller number of inventory-and-eligibility profiles, aggregation preserves those features. Per-task coalitions make the overlap explicit: a type’s mass may serve multiple tasks, but its resources cannot be spent twice. This covers the paper’s exact optimization question and its Proposition 16 complexity result; it does not claim to mirror the evolutionary algorithm’s empirical performance.
My weakest point is that this regime needs genuine repetition of complete agent types. If geography, inventory, or eligibility makes nearly every unit unique, then \(\tau\) approaches the population size and the high-multiplicity representation buys little. Task demands must also scale with population for a nontrivial large-population family. Those are real limits on where the mirror applies, but the paper’s task-based resource model gives a credible setting in which repeated types can arise.
The mirror also poses useful follow-up questions: how does complexity change when the number of resource dimensions or types is fixed; what approximation guarantees are possible; and how much of the hardness disappears if tasks may be completed fractionally?
The strongest case against is that the useful type compression may be rare in the paper’s motivating applications. A complete type must include both a resource bundle and the set of tasks an agent can serve. For location-specific disaster response, sensing, or transport, eligibility can vary from site to site; then \(\tau\) may be close to the number of agents, and aggregation buys little. The paper’s experiments do not establish that its tested instances have repeated complete types.
That concern does not defeat the stronger mirror, though. A large fleet of standardized computing units, with the same resources and access to the same batch of tasks, is a plausible high-multiplicity regime. The task demands can scale with the fleet, while tasks remain all-or-nothing. The proposed mass allocation then represents shared resource use across overlapping task coalitions, with each type’s supply capped by its population and per-unit resources. The fact that the resulting optimization retains binary task choices is compatible with continuizing the population.
Proposition 16 is a named computational result, and its continuous counterpart is well posed. Its knapsack subcase is a real limitation on hopes for tractability, but the programme explicitly treats hardness that survives continuization as a worthwhile boundary result. I see no existing continuous treatment in the paper that makes this a novelty collision.
So I cannot make the requested universal negative case honestly. The mirror looks worthwhile in a credible standardized-unit regime; the negative case is that its relevance may be narrow, and the paper itself does not show that its experiments occupy that regime.
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.