| paper | d4-conf-wine-2020-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm P\): every valid instance admits a successful policy, with polynomial-time construction and exact rational evaluation. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1.2
statement extracted from the paper’s text layer
Given \(m\) item categories, three multi-demand types with rational masses \(\mu_t\) summing to one, rational per-capita supplies \(q_j\), and rational values and caps, does there exist a state-based nonnegative pricing policy, computable from residual type masses and supplies, such that every measurable arrival order and every utility-maximizing tie choice by infinitesimal mass yields terminal welfare equal to the configuration-LP optimum? If so, can such a policy be constructed and evaluated in time polynomial in \(m\), \(\tau=3\), and input bit length \(L\)?
An atomless market has three complete multi-demand buyer types with masses \(\mu_t\), per-capita supplies \(q_j\), and integral bundles for each buyer. A pricing policy updates nonnegative item prices from the residual masses and supplies; welfare is measured against the configuration LP over mass assignments to integral bundles.
The mirror covers Theorem 1.2's optimal dynamic pricing result for multi-demand buyers; it leaves Theorem 1.3's maximal-domain nonexistence result and the Walrasian-equilibrium results aside.
The strongest anchor is Theorem 1.2, proved in this paper: every market with at most three buyers, each having a multi-demand valuation, admits optimal dynamic prices, and those prices can be computed in time polynomial in the number of items \(m\), using value queries. Here “optimal” means that every buyer arrival order and every choice among utility-maximizing bundles leads to maximum social welfare. The paper has a named negative result too, Theorem 1.3, but it is a nonexistence result for some markets, not a hardness classification. I would not present it as an NP-hardness anchor; the paper proves no such complexity lower bound.
A plausible high-multiplicity regime is a large marketplace serving three stable customer segments. Buyers within a segment have the same preferences, multi-demand cap, and other relevant parameters; the number of buyers is large while the number of distinct buyer types is three. Stock scales with population: each original item category has a fixed supply per capita. This is the natural co-modification for a population limit. A buyer still receives an integral bundle, while the fraction of a segment receiving each bundle can be fractional.
Call the mirror Three-Type Atomless Optimal Dynamic Pricing. An instance has \(m\) item categories, three types \(t\in\{1,2,3\}\) with rational masses \(\mu_t\) summing to one, and rational per-capita supplies \(q_j\) for each category \(j\). Type \(t\) has cap \(k_t\) and values \(a_{tj}\) for the categories; its value for a bundle \(S\) is the sum of its \(k_t\) highest-valued items in \(S\), or all of them if \(|S|<k_t\). All values and inputs are binary rationals. This is the high-multiplicity version of a finite market with \(N\mu_t\) buyers of each type and \(Nq_j\) copies of each category, for suitable large \(N\).
The atomless welfare benchmark is the configuration LP: choose masses \(x_{t,S}\ge 0\), where \(x_{t,S}\) is the mass of type \(t\) receiving the integral bundle \(S\), subject to \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le q_j\). Maximize \(\sum_{t,S}x_{t,S}v_t(S)\); call its value \(\mathrm{OPT}\).
The question is whether this instance admits an optimal dynamic pricing policy. Such a policy is a state-based rule \(\pi(\nu,q')\) that assigns nonnegative item prices from the residual type masses \(\nu\) and remaining supplies \(q'\). Parameterize an arrival stream by mass \(s\in[0,1]\): the type arriving at \(s\) follows any measurable order with total mass \(\mu_t\) for each type. At each point, the arriving infinitesimal mass chooses any utility-maximizing feasible integral bundle, given the current prices and available categories; tie-breaking is adversarial. The policy qualifies only if every such arrival order and measurable tie-breaking produces terminal welfare \(\mathrm{OPT}\). A positive solution is a policy with a finite algorithmic description; a negative one is a proof that no state-based policy can guarantee the benchmark. The computational questions are whether the policy exists and, when it does, how efficiently it can be constructed and evaluated, measured in \(m\), the support size \(\tau=3\), input bit length \(L\), and value queries.
I would tentatively expect the restricted three-type problem to be Class A, since the anchor is an efficient pricing result and the population and type masses give a finite aggregate state. The configuration LP supplies the welfare benchmark, while the challenge is finding prices that make every continuous arrival path and every tie choice attain it. Natural follow-ups are whether the policy can be computed in \(\mathrm{poly}(m,\tau,L)\), whether it extends to unbounded \(\tau\), and whether it is the limit of policies for finite high-multiplicity markets.
The mirror covers Theorem 1.2’s multi-demand optimal-pricing problem; it does not claim to mirror Theorem 1.3’s maximal-domain result for arbitrary non-gross-substitutes valuations. The weakest point is the lift from three buyers to three types of a continuum of buyers. The theorem’s bound is on the number of buyers, not the number of distinct valuations, so it does not establish this mirror. The continuum also requires a careful definition of sequential arrivals and price updates. Those are substantial extensions, but the question preserves the paper’s central object—dynamic prices robust to arbitrary order and tie-breaking—and asks whether its positive result survives in the high-multiplicity regime.
Theorem 1.2 is the right anchor: it gives a polynomial-time pricing algorithm, but only for markets with at most three buyers. That bound is doing real work. The paper’s pricing argument uses a bounded item-equivalence graph; its three-buyer case has at most twelve relevant classes. Three buyer types do not give three buyers. With many buyers per type, a new aggregation argument is needed before the theorem’s method or guarantee carries over.
That is the best objection to the proposed atomless mirror. Its three-type restriction preserves support size while changing the number of agents without bound. It therefore asks whether the theorem’s result extends beyond its stated population regime, rather than taking a high-multiplicity limit of instances covered by the theorem. The continuum arrival process also needs its own semantics for price updates and adversarial choices along a mass path. None of that makes the question meaningless, but the paper does not establish that this is a continuization of its positive result.
A sharper version can keep buyers and arrivals discrete: give each of three types a large count, scale stock with population, and ask for a succinct pricing policy that succeeds for every arrival order and tie-breaking. This preserves integral bundles and the paper’s dynamic-pricing objective. But it is a new arbitrary-population problem; Theorem 1.2, which assumes at most three buyers, says nothing about its complexity. The natural finite high-multiplicity formulation also makes the mirror’s value clearer: it would study the same pricing problem on succinctly represented markets, not merely translate the theorem’s existing algorithm.
So I can make a strong case that the proposed mirror is not supported by Theorem 1.2 as stated. I cannot honestly make the universal case that no worthwhile mirror exists. The finite high-multiplicity version is a coherent computational question closely tied to the paper’s open problem about broader valuation markets. The negative case is weak exactly there: it can show that the theorem does not transfer, but not that studying the transfer is unworthy.
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.