| paper | d4-conf-wine-2018-0022 |
| 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: Yes. A nonnegative rational uniform static price guaranteeing \(W\ge\mathrm{OPT}/3\) for every arrival schedule and every adversarial resolution of ties can be computed in time polynomial in \(m,\tau,L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 6.1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to one, per-capita supply \(s\), and explicit normalized, nondecreasing, subadditive valuation tables \(v_t(0),\ldots,v_t(Q)\), define \(\mathrm{OPT}\) as the maximum of \(\sum_{t,q} y_{t,q}v_t(q)\), subject to \(\sum_q y_{t,q}=\mu_t\), \(\sum_{t,q} qy_{t,q}\le s\), and \(y_{t,q}\ge0\). Does there exist a uniform per-item price \(p\), computable from the instance, such that every measurable arrival schedule with type masses \(\mu_t\), and every adversarial resolution of ties, yields welfare at least \(\mathrm{OPT}/3\)? Each infinitesimal buyer chooses an integral bundle size maximizing \(v_t(q)-pq\), subject to available stock; aggregate stock and welfare evolve with arriving mass.
A nonatomic cohort market with complete valuation curves as types, rational type masses \(\mu_t\), supply \(s\) per unit mass, and integral bundle choices for each infinitesimal buyer. The benchmark permits fractions of each type to receive different integral bundles; the decision is a single uniform per-item price whose worst-schedule welfare is compared with that benchmark.
The opponent notes that replacing counts with weighted masses may be a direct proof extension and yield little new complexity structure; the proponent proposes a polynomial-time route but does not establish it.
fatal: False
Covers the full-information, symmetric-subadditive, uniform-price guarantee in Theorem 6.1. It leaves the paper’s other valuation classes, information settings, pricing rules, and bounds untreated.
The strongest mirror is Fluid Uniform-Price Welfare for Subadditive Buyer Cohorts, anchored on Theorem 6.1, proved in this paper. It says that in every full-information market of identical items with symmetric subadditive valuations, some static uniform price guarantees at least \(1/3\) of optimal welfare against the worst-case arrival order. This is a named algorithmic guarantee, rather than a complexity-class result: the paper gives no named NP-hardness, polynomial-time, or parameterized-complexity theorem. The mirror therefore has a weaker connection to the programme’s complexity trichotomy, but it does preserve the paper’s central computational question of how to set a price for a welfare guarantee.
A plausible regime is a large procurement market with many buyers but a small catalogue of demand profiles. For instance, \(N\) buyers may share one of \(\tau\) quantity-value curves, with inventory growing proportionally to \(N\). A type is the buyer’s complete valuation curve and any other attributes the problem uses; buyers of a type are interchangeable. Here \(\tau\) stays small as \(N\) grows, while the type populations and inventory grow with \(N\). Buyers still arrive in an adversarial order, and the seller must choose one uniform per-item price in advance.
Here is the continuous problem I would hand to a prover. An instance consists of a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), supply \(s\) items per unit mass, and explicit valuation tables \(v_t:\{0,\ldots,Q\}\to\mathbb{Q}_{\ge0}\). Each curve is normalized, nondecreasing, and subadditive; \(Q\) bounds an individual buyer’s relevant demand. The benchmark is
\[
\mathrm{OPT}(\mu,s)=
\max \sum_{t\in T}\sum_{q=0}^{Q} y_{t,q}v_t(q)
\quad\text{subject to}\quad
\sum_q y_{t,q}=\mu_t,\qquad
\sum_{t,q} qy_{t,q}\le s,\qquad y_{t,q}\ge0.
\]
The variables \(y_{t,q}\) are masses of type-\(t\) buyers receiving the integral bundle size \(q\); hence type-level averages can be fractional.
The seller must return a price \(p\ge0\). For any measurable arrival schedule \(\sigma:[0,1]\to T\) with type masses \(\mu_t\), each infinitesimal arriving buyer chooses an integral \(q\) maximizing \(v_{\sigma(u)}(q)-pq\), with ties resolved adversarially. The stock falls by \(q\,du\) for mass \(du\), and welfare rises by \(v_{\sigma(u)}(q)\,du\), until the stock is exhausted. The question is to output \(p\) such that every schedule and tie resolution yields welfare at least \(\mathrm{OPT}(\mu,s)/3\). This is the lead mirror: it asks for a uniform posted price for the same full-information, worst-order welfare problem, with the population represented by type masses.
I expect this to be tractable for explicit valuation tables. The paper’s threshold-and-envelope proof for Theorem 6.1 appears adaptable by replacing counts of marginal-value slots with \(\mu_t\)-weighted masses and cutting at the fractional supply threshold. Sorting or thresholding those weighted values should give a price in time polynomial in \(\tau\), \(Q\), and the input bit length. That is a proposed route for the mirror, not a complexity bound established by Theorem 6.1 itself.
The scope is deliberately narrow: it mirrors Theorem 6.1’s full-information uniform-price guarantee for subadditive valuations. The paper’s finite-market tightness example in Proposition 6.7 is not an anchor here; repeating its few agents as large cohorts does not by itself establish a matching continuum lower bound. A useful follow-up is to determine the exact best worst-case ratio in this fluid model, and whether allowing non-uniform prices changes it.
The weakest point is the regime assumption: buyers must genuinely share complete quantity-value curves, and individual relevant demand must remain bounded as the population and supply grow. That is plausible for standardized procurement cohorts, but not for every market. There is also a proof obligation at the fluid limit, especially around inventory exhaustion and adversarial ties. Still, the mirror keeps the paper’s substantive question—choosing prices against arbitrary arrival order—and continues the population, rather than the outcome space or uncertainty model.
The strongest case against Theorem 6.1 is about fit with ChoCo’s research payoff. It gives a welfare guarantee for choosing a posted price; it does not identify a complexity bottleneck such as an exponential pricing problem, nor classify the complexity of finding that price. Its proof organizes buyers’ marginal values around a threshold. For a finite set of valuation types with bounded demand, the proposed fluid version replaces counts of marginal values with weighted masses. That makes this look like a direct weighted extension of the paper’s construction, rather than a new computational landscape opened by continuization.
That is a limited objection, though. It does not defeat the mirror. The paper’s buyers are interchangeable whenever their complete valuation curves agree, and a large market with many buyers per curve and supply growing with population is a sensible regime. The continuous benchmark can retain integral bundle sizes for each buyer while assigning different bundle sizes to fractions of each type. Adversarial arrival order also has a natural fluid counterpart in measurable schedules. Neither identity, integrality, nor the arrival model supplies a fundamental obstruction.
The proposed task could be strengthened to ask for the best worst-case welfare ratio achievable by a uniform price in that fluid model. The paper’s finite-market guarantee does not answer that question, and the model has no continuous computational treatment here that would make it a novelty collision. The paper’s Bayesian results are not such a treatment either: they randomize valuations while retaining a finite buyer set.
So the negative case is mainly that the lead mirror may be a modest extension, with a straightforward route from the existing proof. That is a research-priority concern, not a reason the question is ill-posed or unworthy. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists: Theorem 6.1 survives the strongest objections available in this paper.
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.