| paper | d4-journals-geb-2021-0118 |
| 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: Attainable: an exact seller-information-only lottery with at most \(\tau_s\) prices guarantees \((1-1/e)W^*\) for every buyer distribution and can be constructed in \(O(\tau_s\log(\tau_s+1)L^2)\) bit operations. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4.1
Given unit-mass seller and buyer populations with value distributions \(\mu_s\) and \(\mu_b\), paired according to \(\mu_s \otimes \mu_b\), find a price lottery \(\pi\) that depends only on \(\mu_s\) and satisfies \(\mathbb{E}_{p \sim \pi}[W(p;\mu_s,\mu_b)] \geq (1-1/e)W^*(\mu_s,\mu_b)\) for every \(\mu_b\). Here \(W\) is aggregate welfare when a pair trades exactly when \(s \leq p \leq b\), and \(W^*\) is aggregate first-best welfare.
Two unit-mass populations have types given by role and value, with seller mass \(\mu_s\) and buyer mass \(\mu_b\); bilateral stations are paired by the product measure. The decision is a lottery over posted prices, based only on \(\mu_s\), and the objective is a uniform lower bound on aggregate welfare relative to first best.
The paper does not give a finite encoding for value distributions, so exact runtime and bit complexity require an explicit representation for masses and quantiles.
fatal: False
The mirror covers the Random-Quantile guarantee in Theorem 4.1 and its deterministic existence consequence in Corollary 4.3. It leaves aside the GFT bound in Proposition B.1, the restricted-information results, and the black-box reductions for partnership dissolving and divisible-good markets.
The strongest defensible mirror is a high-volume platform running many separate bilateral trades under a shared pricing policy. A type records an agent’s role and value; mass is the fraction of sellers or buyers with that value. Each trading station still has one seller, one buyer, and one indivisible item. Assume stations pair seller and buyer types according to the product of their two population distributions. Then the source paper’s expected welfare is the aggregate welfare per station in a continuum pool. The number of stations can be enormous while the number of valuation cohorts is small.
My lead anchor is Theorem 4.1, proved in this paper. It says that for every seller distribution, there is a random posted-price mechanism, based only on that distribution, whose expected efficiency is at least \(1-1/e\) of optimal efficiency for every buyer distribution. The mechanism is DSIC, individually rational, and budget balanced. Specifically, it samples a seller quantile \(x\in[1/e,1]\) with CDF \(G(x)=\ln(ex)\), then posts the corresponding seller quantile price.
The continuous problem I would hand to a prover is the Seller-Only Quantile Pricing Problem. Its input is a seller mass distribution \(\mu_s\) over values; the buyer distribution \(\mu_b\) is unknown. For \(s,b\) drawn from the product population, trade at price \(p\) occurs exactly when \(s\le p\le b\). Define aggregate welfare by
\[
W(p;\mu_s,\mu_b)=\int \bigl(\mathbf{1}_{s\le p\le b}b+
\mathbf{1}_{s\not\le p\text{ or }p\not\le b}s\bigr)\,d(\mu_s\otimes\mu_b)(s,b),
\]
and first-best welfare by
\[
W^*(\mu_s,\mu_b)=\int \max\{s,b\}\,d(\mu_s\otimes\mu_b)(s,b).
\]
The requested solution is a price lottery, computed from \(\mu_s\) alone, whose expected welfare is at least \((1-1/e)W^*\) for every \(\mu_b\). Theorem 4.1 supplies one explicitly, so I expect this mirror to be tractable. Further questions include the best possible guarantee for seller-only price lotteries and the finite-input runtime and bit complexity of implementing the quantile rule.
A second, narrower anchor is Proposition B.1, proved in the appendix. For \(t>0\), it gives the buyer density \(f_b(x)=\lambda e^{-x}\) and seller density \(f_s(x)=\lambda e^{x-t}\) on \([0,t]\), where \(\lambda=(1-e^{-t})^{-1}\). It proves that every fixed-price mechanism obtains at most \(O(1/t)\) of the optimal gain from trade.
That motivates the Reciprocal-Cohort GFT Pricing Problem: take a continuum pool with those buyer and seller masses, choose one deterministic posted price \(p\), and maximize
\[
G(p)=\int \mathbf{1}_{s\le p\le b}(b-s)\,d(\mu_s\otimes\mu_b)(s,b)
\]
relative to first-best gains from trade
\[
G^*=\int (b-s)_+\,d(\mu_s\otimes\mu_b)(s,b).
\]
A solution is a price maximizing \(G(p)\), or a uniform approximation guarantee for such prices across \(t\). Proposition B.1 says no fixed-price policy can give a constant fraction across this family as \(t\) grows. This is a real boundary for continuization, though it is a mechanism-impossibility result, not NP-hardness: finding the best one-dimensional price may still be easy. If forced into the programme’s trichotomy, it is closest to a Class C-style barrier for approximating GFT under these constraints. A natural next question is how the barrier changes if the platform may use a menu of \(k\) posted prices.
The mirror covers the paper’s posted-price bilateral-trade guarantees, not its broader black-box reductions or every mechanism-design result. The authors should recognize the market-pool version: it preserves their indivisible trades, price decision, welfare objectives, and incentive constraints while replacing uncertain draws for one pair with realized type mass across many pairs.
The weakest point is that the aggregate integrals are mathematically the same as the paper’s expectations. The distinction is the regime: here the masses describe the actual cross-section of a large marketplace, rather than uncertainty about one buyer and one seller. If the authors or referee regard that change as only an interpretation of their existing distributional model, the mirror loses force. Also, this paper gives named approximation and impossibility results, but no standard P/NP or parameterized-complexity classification.
The strongest case against the proposed mirrors is that their population interpretation adds little computational structure. In Theorem 4.1, the seller and buyer distributions are already the inputs to the pricing rule. Treating those distributions as the actual cross-section of a large platform makes aggregate welfare equal to the same expectation; it does not create a new optimization problem. For finite rational supports, the stated quantile lottery is already an explicit policy, and its price probabilities can be computed from the seller’s support and masses. The paper does not specify a finite-input model for arbitrary distributions, so a runtime question needs extra representation choices before it is a complexity question.
That is a serious objection to this anchor, but it cannot rest just on “the answer is already known”: the brief rules that out. Nor is a realized population identical to the paper’s uncertainty model. A best-case seller-only lottery problem could ask for the optimal robust guarantee, not merely reproduce the \(1-1/e\) policy. That is a coherent question, and the paper’s result does not settle it. The negative case is that it would be a new pricing-optimization question whose computational content depends on how distributions and lotteries are represented, rather than a complexity landscape revealed by continuizing this paper’s agents.
Proposition B.1 is a weaker anchor for ChoCo. Its reciprocal-cohort example transfers directly to a large pool, but the proposition establishes a limit on the welfare guarantee of a fixed price, not computational hardness. For the specified distributions, maximizing \(G(p)\) is a one-dimensional optimization problem. Asking about \(k\)-price policies could be interesting, but it adds a richer mechanism class; the proposition itself gives no reason to expect a population-driven complexity question. The fact that the same impossibility holds in a continuum is a boundary on approximation, not evidence that continuization exposed a computational barrier.
The strongest alternative mirror is the paper’s partnership-dissolving result. A large group of co-owners with repeated value and endowment types is a plausible high-multiplicity regime, and the paper already studies \(n\) owners and divisible shares. But that is also where the universal negative case stops being convincing: masses of shareholder types and aggregate endowments make sense, and per-capita shares can scale with population as the programme allows. The paper’s reductions may make such a mirror easy or already structurally close to the source model, but ease and closeness are not grounds for dismissing a well-posed question.
So the two proposed anchors make a limited case against treating this paper as a source of new complexity results: one largely restates an explicit pricing guarantee, and the other is an approximation impossibility rather than a computational classification. I cannot honestly extend that into “no worthwhile continuous mirror in any scenario.” The partnership-dissolving setting supplies a credible counter-scenario, and the objection that its answer may be straightforward is specifically not enough to rule it out.
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.