| paper | d4-conf-atal-2002-0039 |
| 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→P discrete result → its continuous mirror
Answer: Feasibility and exact minimum-cost winner determination are polynomial-time solvable in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2.5
statement extracted from the paper’s text layer
Given \(m\) items and \(\tau\) supplier types, where type \(t\) has integer ask vector \(q_t\), rational price \(p_t\), and population mass \(\mu_t\) with \(\sum_t \mu_t=1\), along with per-supplier demand \(d\in\mathbb{Q}_{\ge 0}^m\), determine whether there are accepted masses \(x_t\in[0,\mu_t]\) satisfying \(\sum_t q_{ti}x_t=d_i\) for every item \(i\); if feasible, find a minimum-cost choice minimizing \(\sum_t p_t x_t\).
A continuum of suppliers grouped by complete ask type, with mass \(\mu_t\) available for each type. Choose accepted mass \(x_t\) at price \(p_t\), subject to exact aggregate supply \(d_i\) for each item; the resulting linear program has \(\tau\) variables and \(m\) item constraints.
The paper already uses LP relaxations inside CPLEX, so solving the mass formulation as an LP may add little optimization insight.
fatal: False
The mirror covers the multi-unit reverse-auction case of Theorem 2.5 without free disposal. It leaves the other auction and exchange variants, the free-disposal results, the approximation result, and the experimental findings unaddressed.
My lead is a continuous mirror of the multi-unit combinatorial reverse auction without free disposal.
The anchor is Theorem 2.5, proved in this paper. It says that for combinatorial auctions, reverse auctions, and exchanges, in both the single-unit and multi-unit cases without free disposal, even finding a feasible winner set is NP-complete, including with integer prices and units. I would mirror its multi-unit reverse-auction case: the buyer needs an exact quantity of each item, and accepted asks must supply exactly those quantities. The paper proves the hardness by reduction from Exact Cover by 3-Sets.
A plausible high-multiplicity regime is procurement from a very large pool of small providers choosing among standardized offers. Each provider, for the purposes of the market, is described by their complete ask: a vector of quantities and a price. Many providers may have the same ask, while the number of distinct asks stays small compared with the provider population. If reliability or other attributes affect the market, those belong in the type too.
Here is the continuous problem. There are \(m\) items and \(\tau\) supplier types. Type \(t\) has ask vector \(q_t\in\mathbb{Z}_{\ge 0}^{m}\), price \(p_t\in\mathbb{Q}_{\ge 0}\), and population mass \(\mu_t\in\mathbb{Q}_{\ge 0}\), with \(\sum_t\mu_t=1\). The buyer’s demand \(d\in\mathbb{Q}_{\ge 0}^{m}\) is expressed per supplier in the population. Choose accepted mass \(x_t\in[0,\mu_t]\) for each type to minimize \(\sum_t p_t x_t\), subject to \(\sum_t q_{ti}x_t=d_i\) for every item \(i\). A solution is the vector \(x\); if the constraints cannot be met, the instance is infeasible. With \(N\) suppliers and absolute demand \(U_i\), use \(d_i=U_i/N\); multiplying the objective by \(N\) gives total procurement cost.
This preserves the market question: which offers should be accepted, at what cost, to procure the required goods? Each provider still supplies their whole ask or none of it. The variable \(x_t\) is the mass of providers of that type accepted, so aggregate supply can be fractional. That fits the no-disposal condition: the buyer receives exactly the required quantity, and no accepted supplier is asked to retain part of their offer. The resulting problem is a linear program with \(\tau\) variables and \(m\) item constraints, solvable in time polynomial in \(m\), \(\tau\), and the input bit length. This is a strong case for Class A: the discrete feasibility hardness disappears in the continuous population model.
The weakest point is the change in granularity. In the finite problem, a type with \(n_t\) providers permits only multiples of \(1/N\) as accepted mass; the continuous problem permits any real \(x_t\) in the interval. Thus the mirror can be infeasible as a proxy for a market where each quote must remain an individually indivisible decision. I think the authors could still recognize it as their winner-determination problem in the high-multiplicity procurement regime: participants remain all-or-nothing, but a large cohort of indistinguishable providers can be selected by mass.
This mirror covers the no-free-disposal multi-unit reverse-auction result, not all the paper’s auction and exchange variants. It raises natural follow-up questions: how does continuous cost or feasibility relate to finite instances with large multiplicities; when can a continuous solution be rounded while controlling supply error and cost; and can the same mass formulation yield useful dual prices for procurement?
The only anchor the proponent raises is Theorem 2.5, for multi-unit reverse auctions without free disposal. I do not think the case against it is strong: a large procurement pool with repeated, standardized asks is a plausible high-multiplicity regime, and mass acceptance gives a sensible limit question. The paper has an explicit computational result to mirror, so the decisive “no result to mirror” objection does not apply.
The best objection is that this particular mirror appears to be the paper’s own LP relaxation in population notation. If type \(t\) has \(n_t\) suppliers among \(N\), with ask vector \(q_t\) and price \(p_t\), write \(y_t=Nx_t\) for the number of type-\(t\) suppliers accepted. The proposed constraints become
\[
\sum_t q_{ti}y_t=U_i,\qquad 0\le y_t\le n_t,
\]
with \(y_t\) allowed to be fractional. Those are the winner-determination constraints with integrality relaxed. The paper already uses LP relaxations inside CPLEX to bound its search. Thus the continuous formulation exposes no new optimization machinery or hidden pricing problem; it repackages a relaxation already central to the paper’s method.
That makes the proposed mirror look thin as a ChoCo project. Its headline result would be that this explicit LP is solvable in polynomial time. Studying when its solutions predict feasibility or cost in the finite market could be more substantial, but that work would turn on rounding, divisibility, and exact integer feasibility. It would answer how well the relaxation represents the original procurement problem, rather than opening a new continuous winner-determination problem.
This objection has a limit. The paper’s LP relaxation is not itself a continuous-population treatment, so this is not a strict novelty collision under the programme’s definition. Also, rational feasible masses can be scaled to integer supplier counts for a suitable replicated instance. The mirror therefore has a coherent asymptotic interpretation, even if it does little beyond making the existing relaxation the object of study. I can make a case that this anchor is low-yield; I cannot honestly argue that no worthwhile mirror exists in any scenario.
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.