| paper | d4-conf-aaai-2018-0949 |
| 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}\)-complete, already for \(\tau=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite goods set \(G\), a catalogue \(T\) of multi-output tools, and a finite support of cell types \(r=(U_{\rm in}^r,U_{\rm out}^r)\) with rational masses \(\mu_r>0\) summing to \(1\), where all specified bundles are single-unit, decide whether there are legal sequences \(\Sigma\) for each type and fractions \(\lambda_{r,\Sigma}\ge 0\) such that \(\sum_{\Sigma}\lambda_{r,\Sigma}=1\) for every \(r\), and \(\sum_r\mu_r\sum_{\Sigma}\lambda_{r,\Sigma}|\Sigma|\le K\). Each cell executes its own sequence under the paper’s goods-update rules; the question is whether the population’s average action load is at most \(K\).
A distribution over independent production-cell types, each specified by its initial and target bundles and using the same multi-output tool catalogue. The decision variables allocate each type’s mass among locally legal sequences, and the objective is average action load.
The mirror covers Theorem 4 for multi-output WINDET; it leaves the tabac-tool and nonconsumable-tool results unaddressed.
The strongest mirror I believe is a batch-production version of the paper’s multi-output WINDET problem. A factory has many production cells, each starting with a bundle of goods and tools and needing to make a specified output bundle. The cells use the same catalogue of transformations, and applying any transformation costs one unit of work. A type records a cell’s complete relevant specification: its initial bundle and its target bundle. A large facility might have \(N\) cells but only \(\tau\) distinct types, with \(N\gg\tau\); the society is the distribution \(\mu\) of cell types.
Here is the continuous problem. The instance gives a finite goods set \(G\), a catalogue \(T\) consisting only of multi-output tools, a finite set of cell types \(r=(U_{\rm in}^r,U_{\rm out}^r)\), rational masses \(\mu_r>0\) summing to \(1\), and an action budget \(K\). Use the paper’s exact legality and goods-update rules within each cell. Restrict all specified bundles, including tool outputs, to be single-unit bundles. For each type \(r\), let \(\mathcal S_r\) be its legal sequences that achieve \(U_{\rm out}^r\). A solution assigns fractions \(\lambda_{r,\Sigma}\ge 0\) of type \(r\)’s mass to those sequences, with \(\sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}=1\). Its action load is
\[
\sum_r \mu_r\sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}|\Sigma|.
\]
The question is whether there is such a plan with load at most \(K\). The fractions describe how much of each type follows each plan; each cell still executes a legal sequence with its own integral bundle state. Only the population shares and aggregate action load are fractional.
My anchor is Theorem 4, proved in this paper: when all transformations are multi-output tools, WINDET is NP-complete, even under the single-unit restriction. WINDET asks whether an auction instance has a legal sequence of at most \(K\) actions that achieves its desired output. The theorem’s hardness follows from the single-output special case, and the paper establishes NP membership by bounding the needed sequence length. So the result concerns the underlying production-sequence problem, not an encoding of it.
For the continuous problem above, the same hardness holds already when \(\tau=1\) and \(\mu_1=1\): its minimum action load is the length of the shortest successful sequence, so the budget question is exactly WINDET. This remains a high-multiplicity scenario: \(\mu_1=1\) can represent any \(N\) identical cells. The continuous problem is also in NP under this restriction: with no shared capacity constraints between cells, assigning a type’s mass among several plans cannot beat its shortest plan, so a certificate can give one successful sequence per type. Each can be chosen with length at most \(|G|\), since any action adding no new good can be omitted. Thus this mirror is NP-complete, and I expect Class B: hardness transfers. The reduction’s combinatorics live in choosing and sequencing transformations over goods, not in the number of production cells.
I think the authors could recognize this as a continuous analogue of their problem: every cell retains the paper’s exact local auction and sequence rules, while the population represents many repeated production orders or lines. The paper itself is motivated by assembly lines and supply chains, where large cohorts of standardized production units are plausible.
The weakness is that the paper studies one auctioneer’s evolving inventory, whereas this mirror gives each cell its own initial bundle and process. It is a batch of tool-auction instances, not one auctioneer coordinating a shared stock across the whole population. That makes the continuous problem separable by type; the continuum does not itself remove the hardness. The positive case depends on accepting high-volume standardized production cells as a sensible regime for the authors’ underlying sequence problem.
This mirror covers Theorem 4’s multi-output WINDET result, not the paper’s tabac-tool or nonconsumable-tool results. It raises a natural next question: if production cells share a pooled stock or limited tool capacity, can a type-mass optimization model preserve the sequence constraints while exposing useful continuous-optimization structure?
Theorem 4 is a genuine computational anchor: multi-output WINDET is NP-complete. The difficulty is that the paper’s instance has one planner, one inventory, and one sequence of actions. Its goods and transformations describe a production process; they are not agents in a population.
The proposed cell model instead gives each cell its own auction instance and sequence. If \(d_r\) is the shortest successful sequence for type \(r\), its minimum action load is \(\sum_r \mu_r d_r\). The masses weight separate planning problems; they do not couple the cells’ states or decisions. With one type, the decision is exactly the paper’s WINDET problem. That preserves the hardness, but it makes the proposed “population” a batch of repeated planning instances, rather than a continuous version of the paper’s single-auction problem. Duplicating \(N\) identical cells only repeats the same plan \(N\) times; expressing the budget per cell removes \(N\) again.
A stronger supply-chain mirror could give many order types a shared stock of tools and goods. But that creates a choice the paper does not settle. If stock and targets are pooled and goods are fungible, the order labels disappear and the instance reduces to one auctioneer’s aggregate inventory problem. If orders keep separate targets while drawing on shared stock, the model needs joint allocation and scheduling rules across orders. That could be worth studying, but it is a new resource-constrained planning model; Theorem 4 does not establish it as the continuous mirror. A common action budget has the same split: without shared capacity the cells remain separable, while adding capacity or scheduling constraints adds structure absent from the paper.
This is a case against treating Theorem 4 as a strong ChoCo anchor, not a proof that no useful model can be made. The negative case is weak against the production-cell scenario itself: repeated standardized cells are plausible, and the paper explicitly motivates its model with industrial production. If such cells count as the relevant population, the proposed model is well-posed and its hardness at \(\tau=1\) is a legitimate Class B result. The objection then rests on whether a batch of independent production plans is the kind of continuous-population question this programme means to pursue.
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.