| paper | d4-conf-sigecom-2000-0017 |
| 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: Exactly solvable in deterministic time polynomial in \(m,\tau,L\); therefore the requested \(m^{1/2-\varepsilon}\)-approximation exists for every fixed \(0<\varepsilon<\tfrac12\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(n\) commodities, bid types \(t=1,\ldots,\tau\) with rational masses \(\mu_t\) summing to \(1\), bundle vectors \(q(t)\), prices \(p_t\), and rational per-capita supplies \(\kappa_j\), choose accepted masses \(x_t\) satisfying \(0\le x_t\le\mu_t\) and \(\sum_t q_j(t)x_t\le\kappa_j\) for each commodity \(j\), to maximize \(\sum_t p_t x_t\).
A society of standardized bid types carrying mass \(\mu_t\), with supply \(\kappa_j\) per bidder; the decision variable \(x_t\) is accepted mass, each unit of which receives its type's full bundle \(q(t)\), and the objective is total accepted value \(\sum_t p_t x_t\).
The same LP is already computed as a branch-and-bound upper bound, so the mirror adds no new optimization machinery; this limits its novelty but leaves the continuous-population question intact.
fatal: False
The mirror covers Theorem 1's WMSP winner-determination problem. It does not cover the branch-and-bound search, its bid-ordering heuristic, the other bounds, or the experimental results.
The strongest mirror is the paper’s Theorem 1, for the weighted multi-set packing problem (WMSP). Imagine a large procurement or allocation market with \(N\) bidders and a relatively small support of \(\tau\) bid types. A type \(t\) specifies a complete bid: a bundle \(q(t)\in\mathbb{Z}_{\ge 0}^n\) and an offered price \(p_t\ge 0\). The mass \(\mu_t\) is the fraction of bidders with that bid. This is plausible for a platform with standardized bundles and price tiers; as the market grows, the number of bidders can grow much faster than the number of templates. Let the supply of commodity \(j\) be \(N\kappa_j\), so \(\kappa_j\) is supply per bidder.
Call the mirror Continuous Multi-Unit Auction Allocation. Its input is \(n\), the explicitly listed types \(t=1,\dots,\tau\), their rational masses \(\mu_t\) summing to \(1\), bundle vectors \(q(t)\), rational prices \(p_t\), and rational per-capita supplies \(\kappa_j\). It asks for an acceptance mass \(x_t\) for each type, with
\[
0\le x_t\le\mu_t,\qquad
\sum_{t=1}^{\tau}q_j(t)x_t\le\kappa_j\quad(j=1,\dots,n),
\]
that maximizes \(\sum_t p_t x_t\). A solution is an optimal vector \(x\) and its value. Each accepted bidder still receives their entire requested bundle; only the accepted *mass* of a type is fractional. This is a rational LP with \(\tau\) variables and \(n+\tau\) constraints, so it is solvable in polynomial time in \(n,\tau\), and the input bit length.
Theorem 1 is my lead anchor. As printed, it says that for every \(\varepsilon>0\), unless \(\mathrm{NP}=\mathrm{ZPP}\), WMSP cannot be approximated in polynomial time within \(n^{1/2-\varepsilon}\), where \(n\) is the number of commodities. The theorem and its reduction are proved in this paper; the proof uses the cited hardness of approximating independent set. In the continuous mirror, the corresponding allocation problem is exactly solvable by LP. So the expected class is tractable: the discrete inapproximability does not carry over to this mass-allocation version.
The authors have a strong reason to recognize this as their problem’s continuous analogue. Section 3.1 already relaxes one variable per finite bid from \(\{0,1\}\) to \([0,1]\), explicitly interpreting fractional values as fractional allocation. The mirror gives that move a population interpretation: \(x_t\) is the mass of otherwise identical bidders accepted, and supplies scale with population. It therefore covers Theorem 1’s WMSP winner-determination problem, not the paper’s branch-and-bound search procedure, its ordering heuristic, or its experimental claims.
This also suggests a finite-population bridge. If a realization has \(N\mu_t\) bidders of each type and capacities \(N\kappa_j\) are integral, accepting \(\lfloor Nx_t\rfloor\) whole bids per type is feasible. Its per-capita value is within \(\sum_t p_t/N\) of the continuous optimum. Questions beyond the LP include sharp rounding bounds and when this additive guarantee yields a useful relative guarantee.
The weakest point is that Theorem 1’s hardness is parameterized by the number of commodities, and its proof uses combinatorial conflicts among bids; it is not a hardness result shown to arise solely from population multiplicity. The mirror removes the all-or-nothing choice among atomic bids, so its tractability is a meaningful relaxation of winner determination, but it does not establish that the theorem’s hardness disappears merely because a market has many buyers. The paper’s own fractional-allocation formulation and its stated interest in markets with many buyers make the mirror credible despite that limitation.
Theorem 1 is a valid computational anchor, and standardized bid types in a large procurement market give it a credible population interpretation. The strongest case against the proposed mirror is that its optimization problem is already in the paper.
Section 3.1 relaxes each bid’s acceptance variable to \([0,1]\), explicitly interpreting this as fractional allocation. Group identical bids into types \(t\), with \(B_t\) copies of each. The paper’s LP then has aggregate variables \(y_t\) satisfying
\[
0\le y_t\le B_t,\qquad
\sum_t q_j(t)y_t\le k_j,
\]
and maximizes \(\sum_t p_t y_t\). Set \(B_t=N\mu_t\), \(k_j=N\kappa_j\), and \(y_t=Nx_t\). Dividing by \(N\) gives exactly the proposed continuous-population LP. The paper already presents and uses that LP as an upper bound. Interpreting its fractional acceptance as accepted mass therefore supplies a population story for a computation the paper already formulates and carries out.
The finite-population rounding argument does not rescue a new continuous-complexity question: rounding each type’s accepted count down loses at most \(\sum_t p_t/N\) in per-capita value. Sharper finite-\(N\) guarantees could be worthwhile, but they concern the integer packing problem’s rounding and integrality gap; the continuous optimization problem remains the paper’s LP.
This is a narrow objection, and it supports “already treated here” more than “no sensible continuous society exists.” I cannot honestly defend the universal claim: the repeated-bid population is sensible, and Theorem 1 is a genuine computational result. The negative case is that this particular mirror appears to restate the paper’s own LP relaxation rather than open a new continuous-complexity problem.
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.