| paper | d4-conf-atal-2008-0343 |
| 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: The threshold problem is in \(\mathrm P\). Feasibility, the exact supremum, attainment, and an optimal rational allocation with a compact finite schedule are computable in \(\operatorname{poly}(m,\tau,B,n,L)\) time. Explicitly listing an attaining schedule can require \(2^{\Omega(L)}\) steps; construction takes polynomial time in the input plus expanded output length. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorems 3.1 and 3.2
Given a finite goods set \(G\), rational per-capita inventories \(u^{in},u^{out}\), and supplier types \(r\) with rational masses \(\mu_r\) and complete XOR bid menus, maximize \(\sum_{r,b} p_{rb}x_{rb}\) over accepted bid masses \(x_{rb}\ge 0\), subject to \(\sum_b x_{rb}\le\mu_r\). Each bid’s transformations have integral input and output bundles and multiplicities \(a_{rbj}\). Require that their total execution masses \(a_{rbj}x_{rb}\) admit some finite schedule of nonnegative execution masses, with inventory sufficient before every stage and final inventory at least \(u^{out}\). Determine the optimum and a schedule attaining it.
A high-multiplicity MMUCA procurement market with a finite goods set and \(\tau\) supplier types, each type specifying its complete XOR menu, prices, and transformation bundles. The decision variables are accepted bid masses \(x_{rb}\); the objective is total per-capita auction value; execution variables \(z_{k,rbj}\) and inventories \(q_k\) must witness a finite feasible schedule from per-capita inventory \(u^{in}\) to at least \(u^{out}\).
The opponent points out that the model has no uniform bound on the number of execution stages; the proponent defines feasibility by existence of a finite schedule but does not establish a finite encoding or complexity characterization for that condition.
fatal: False
The mirror covers the winner-determination optimization and the correctness question behind CCIP’s restricted ordering, represented by Theorems 3.1 and 3.2. It does not mirror the empirical speedups as a guaranteed result.
The honest positive case is narrow but real: the paper has no numbered theorem asserting that MMUCA winner determination is in P or NP-hard. Its abstract calls the problem NP-hard, but that is not a numbered result, so I would not use it as an anchor under your rule. The usable named result is the paper’s exactness result for its computed solver.
Anchor: Theorems 3.1 and 3.2, treated as the two directions of one solver-correctness result. Theorem 3.1 says that given a partial sequence \(H\) solving the Direct IP solver (DIP), any reordering \(J\) of \(H\) that fulfils the order-enforcing function \(S\) fulfils all the Connected Component IP solver (CCIP) constraints. Theorem 3.2 says that any partial sequence \(J\) solving CCIP fulfils all DIP constraints. Together, they justify restricting the search to the paper’s order template without changing the winner-determination problem. The paper says the proofs are in reference [5], a technical report, so they are stated here but proved elsewhere. This is an algorithmic formulation result, and the paper computes with CCIP; it is not a complexity-class result.
A continuous mirror I believe in is Fluid-MMUCA-WDP\(_\infty\). Consider a large procurement market with a finite goods set \(G\) and supplier types \(r=1,\ldots,\tau\), each with rational mass \(\mu_r\), where \(\sum_r\mu_r=1\). A supplier’s type gives its complete XOR menu: for each bid \(b\), its price \(p_{rb}\) and the multiset \(D_{rb}\) of transformations it offers. Each transformation still has integral input and output bundles \(I_{rbj},O_{rbj}\in\mathbb{N}^G\), and the type includes any other feature the auction uses. Thus mass is the fraction of interchangeable suppliers with that exact menu and price—not a fraction of an individual contract.
The instance also gives per-capita starting and required inventories \(u^{in},u^{out}\in\mathbb{Q}_{\ge 0}^G\). Choose accepted bid masses \(x_{rb}\ge 0\), with \(\sum_{b\in B_r}x_{rb}\le\mu_r\). For each transformation \(j\) in bid \(b\), if its multiplicity is \(a_{rbj}\), the accepted mass requires total execution \(a_{rbj}x_{rb}\). Ask for the maximum per-capita auction value \(\sum_{r,b}p_{rb}x_{rb}\), subject to there being a feasible finite execution schedule: at stage \(k\), let \(z_{k,rbj}\ge0\) be the mass of transformation executed and let \(q_k\) be the inventory after that stage. Require \(\sum_k z_{k,rbj}=a_{rbj}x_{rb}\), \(q_0=u^{in}\), \(q_k=q_{k-1}+\sum_{r,b,j}z_{k,rbj}(O_{rbj}-I_{rbj})\), and \(q_{k-1}\ge\sum_{r,b,j}z_{k,rbj}I_{rbj}\) componentwise at every stage, with \(q_K\ge u^{out}\). A solution gives the accepted masses, the schedule, and the optimum. This retains the paper’s central requirement that the transformations be executable in an order; aggregate input-output balance alone does not count as feasibility.
That model fits a credible regime: a large market for standardized production or service contracts, with many small suppliers drawn from a modest number of exact archetypes. For example, many suppliers might offer one of a small set of identical input-output packages at the same price. As the number of suppliers grows, \(\tau\) can stay moderate. The accepted mass \(x_{rb}\) represents accepting the full bid from that share of suppliers; the continuous model does not split an individual supplier’s bundle. Per-capita inventories are a natural co-modification as the supplier population scales.
My working expectation is Class A, tentatively: the population-based bid-selection choices become continuous, and the XOR constraints become per-type mass bounds. If executability admitted a compact characterization using the transformation dependency graph and its strongly connected components, optimization might reduce to LP or related continuous optimization. The scheduling condition is the real obstacle, though; the paper’s theorems establish correctness of its discrete solver, not tractability of this fluid problem. If fluid execution still requires inherently difficult sequencing, the mirror could instead be continuum-specifically hard. The useful questions are whether feasible schedules have a compact representation or a polynomial-size witness, whether SCC structure yields an exact algorithm, and whether any remaining hardness comes from transformation topology or the agenda rather than population multiplicity. A discrete-to-continuous comparison should also measure rounding loss as a function of \(\tau\), the number of transformations, and input bit length \(L\).
This mirrors the winner-determination computation and its exactness argument, not the paper’s reported empirical speedups as a theorem. The soft spot is the scenario: many supply-chain participants are bespoke, and exact agreement on their full bid menus and prices can be demanding. I find the case strongest for standardized procurement markets; in that regime, identical menus and prices are exactly what makes the suppliers a high-multiplicity population.
The strongest objection to the anchor is that Theorems 3.1 and 3.2 establish correctness of the CCIP encoding: they relate its solutions to those of DIP. They do not classify the complexity of winner determination or give a complexity bound. The paper reports solver speedups empirically, while its NP-hardness claim appears in the abstract. So the proposed anchor is a formulation-correctness result, not a named complexity result of the kind ChoCo is meant to chart.
The better fluid model is harder to dismiss. Treating a supplier’s full XOR menu and prices as its type, then scaling inventories and requirements per capita, gives a coherent high-multiplicity procurement regime. Supplier identity does not defeat it: agents with identical menus are interchangeable for the objective in this paper. The model also preserves the central execution constraint, since accepted transformations still need to be schedulable.
The skeptical case is that this model’s new question is largely whether a fractional version of the bid-selection and execution problem has a useful exact formulation. The paper’s theorems concern ordering transformations according to their dependency graph; they say little about what fractional supplier mass does to that graph. A fluid schedule could turn into a new continuous resource-reachability problem, but that is a substantial modeling and algorithmic question of its own. It is not a direct continuous counterpart of the stated theorems, and the proposed finite-stage formulation needs a bound or a precise treatment of schedules with arbitrarily many stages before its computational question is settled.
That makes the case against this anchor credible, but it does not establish that no worthwhile mirror exists. Standardized supplier archetypes and per-capita requirements are plausible, and a careful continuous execution model could produce a meaningful computational result. I cannot honestly defend the universal claim that every such mirror is unworthy; the negative case is strongest against using these two theorems as the anchor, and weak against the improved Fluid-MMUCA question.
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.