| paper | d4-conf-ijcai-2017-0031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: A polynomial-time algorithm computes rational static prices and caps guaranteeing welfare at least \(\mathrm{OPT}_{\mu}/2\), and therefore at least \(\mathrm{OPT}_{\mu}/4\), for every measurable arrival order and every measurable utility-maximizing tie resolution. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 3.3
statement extracted from the paper’s text layer
Given \(M\) goods, \(\tau\) buyer types with rational masses \(\mu_t\) summing to one, XoS demand and valuation oracles, and rational piecewise-linear convex per-capita cost curves \(C_i\), can a polynomial-time algorithm in \(M,\tau,L\) compute item prices \(p_i\) and mass supply caps \(q_i\in[0,1]\) such that an on-the-fly posted-price mechanism achieves at least \(\mathrm{OPT}_{\mu}/4\) for every measurable arrival order with type frequencies \(\mu\)? Each infinitesimal buyer chooses a utility-maximizing integral bundle from the available goods, and \(\mathrm{OPT}_{\mu}\) maximizes \(\sum_{t,S}x_{t,S}v_t(S)-\sum_i C_i(y_i)\), where \(\sum_S x_{t,S}=\mu_t\) and \(y_i=\sum_{t,S\ni i}x_{t,S}\).
A normalized continuum market with \(M\) goods and \(\tau\) complete buyer valuation types carrying rational mass \(\mu_t\). Type members receive integral bundles, while allocation mass and per-capita supply can be fractional; convex production costs scale with population size, and the mechanism posts one price and one mass cap per good.
The paper’s polynomial running time is in the finite buyer count, so it does not establish an algorithm polynomial in \(M,\tau,L\); the continuum guarantee for every measurable arrival order also needs a new proof.
fatal: False
The mirror covers Corollary 3.3’s on-the-fly result for XoS buyers, supported by Theorem 3.1 and Claim 3.2. It leaves the commitment mechanism, subadditive extension, and unknown-valuation result aside.
My lead is Continuum Anonymous Posted Pricing with Convex Production.
The anchor is Corollary 3.3, proved in this paper using Theorem 3.1 and Claim 3.2. For Bayesian markets with XoS buyers and convex production costs, it says one can compute in polynomial time a single price per good and a supply cap per good so that, for any buyer arrival order, the on-the-fly posted-price mechanism achieves at least one-fourth of optimum expected social welfare. The computation uses the paper’s demand and XoS oracles and its finite-support representation of the product distribution. The paper’s named results here are algorithmic; it offers no comparable hardness result to anchor instead.
Here is the continuous problem. There are \(M\) goods and \(\tau\) buyer types. A type \(t\) is a complete XoS valuation function \(v_t\) over bundles of goods, and the society is a distribution \(\mu\) over those types, with rational masses \(\mu_t\) summing to one. Each buyer still receives an integral bundle; only the mass of a type assigned to each bundle can be fractional. For good \(i\), the seller has a nondecreasing convex per-capita production cost \(C_i(y_i)\), where \(y_i\) is the mass of units sold. These are costs for serving a population normalized to mass one: in a population of size \(n\), capacity and total production cost scale as \(n\).
The benchmark is
\[ \operatorname{OPT}_{\mu} = \max_{x\ge 0} \left[ \sum_{t}\sum_{S\subseteq [M]} x_{t,S}v_t(S) - \sum_{i=1}^{M} C_i(y_i) \right], \qquad \sum_{S\subseteq[M]}x_{t,S}=\mu_t,\quad y_i=\sum_{t}\sum_{S\ni i}x_{t,S}. \]
Call the question Continuum Anonymous Posted Pricing with Convex Production: given \(M,\tau,\mu\), XoS oracles for each \(v_t\), and rational piecewise-linear convex cost curves, can a polynomial-time algorithm compute prices \(p_i\ge 0\) and mass supply caps \(q_i\in[0,1]\) such that the on-the-fly mechanism achieves at least \(\operatorname{OPT}_{\mu}/4\) for every measurable arrival order whose type frequencies are \(\mu\)? Each infinitesimal buyer chooses a utility-maximizing integral bundle from the goods still available, at the same posted item prices. Fix a tie-breaking rule as part of the mechanism. The solution is the price and cap vectors, with the guarantee measured by buyer value minus production cost. The intended complexity bound is polynomial in \(M,\tau,L\), with polynomially many demand and XoS oracle calls.
A plausible regime is a large procurement market for a shared catalog, with many customers but a modest number of recurring valuation profiles. The number of buyers is large relative to \(\tau\); members of a type have the same preferences over all bundles. Customers arrive throughout a selling window, while supply and production costs scale with the customer population. The paper’s Bayesian distribution is over the valuations of a finite set of buyers; here \(\mu\) is the society itself. This is a high-multiplicity limit of the paper’s market, not a claim that its finite buyers already form a continuum.
I expect this problem to be tractable (Class A). The continuum allocation benchmark has finitely many type coordinates and can be represented with type-and-bundle variables; convex costs point toward convex optimization, while demand oracles can support pricing or separation over bundles. The paper’s per-good surplus/profit balancing also looks suited to integration over type mass. In the nonatomic model, an individual buyer cannot affect whether a good sells out, which may take the place of the paper’s leave-one-buyer-out independence argument. The guarantee and its computation still need to be proved in this model.
The authors would likely recognize this as their problem: the mirror retains their central question about anonymous posted prices, convex production, welfare, and arbitrary arrivals. It does not turn the outcome space continuous: every buyer gets a bundle of whole goods. The continuous variables represent population mass and per-capita supply.
The soft spot is the passage from a finite Bayesian product prior to a fixed continuum society. Nonatomicity may simplify the dependence between a buyer and supply exhaustion, but it does not automatically establish the same quarter-of-optimum guarantee for every arrival path. That is a real proof obligation, not a reason to reject the mirror.
This lead covers Corollary 3.3’s on-the-fly XoS result. It does not try to mirror the commitment mechanism, the subadditive extension, or the unknown-distribution result. Natural follow-ups are whether the quarter guarantee survives without randomness, whether the constant can improve, and whether the same continuum model supports a logarithmic guarantee for subadditive buyers with limited per-capita supply.
The strongest case against Corollary 3.3 is that the proposed mirror changes what is being averaged over. The paper’s theorem starts with independent buyer valuations and guarantees welfare in expectation over the valuation profile. A fixed distribution \(\mu\) over realized valuation types instead describes a deterministic full information population. That is a sensible mirror, but it is not the paper’s Bayesian question.
That distinction does not defeat the anchor. The paper also permits deterministic valuation profiles: take the product distribution to be a point mass. Replicating each of \(\tau\) valuation types according to rational proportions then gives finite markets to which the paper’s guarantee applies. The guarantee is for every buyer arrival order, so adversarially ordering those types does not by itself break the bridge. Scaling the production costs with population size also avoids a vanishing-cost objection.
The better mirror would retain Bayesian uncertainty by assigning each population type its own valuation distribution, then ask for anonymous prices and per capita supply in a continuum population. That preserves the paper’s central pricing question. It also exposes the actual technical gap: the finite algorithm runs in time polynomial in the number of buyers, while the continuous input can encode enormous multiplicities in binary. A result polynomial in \(M,\tau,L\) would require genuine high multiplicity compression; it does not follow just by replicating buyers or taking a limit.
That gap is a reason to be careful about the proposed tractability argument: a convex allocation benchmark does not by itself give prices with the sequential welfare guarantee. But it is not a reason to reject the question. The model has repeated valuation types, keeps each buyer’s bundle integral, and makes population mass the continuous object. Arrival order, type level fractional allocations, and per capita costs all have recognizable formulations. I see no fundamental identity, degeneracy, or scope obstruction that survives the stronger version of the mirror.
So I cannot honestly make a strong case that no worthwhile mirror exists here. The negative case is weak: the best objection is that the simplest guarantee may be a limit of the paper’s deterministic finite instances, leaving the real contribution to be a compressed algorithm and a rigorous continuum guarantee. Whether that contribution merits the programme’s time is a judgment about value, not a demonstrated failure of the mirror.
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.