Truncation-loss conjecture for quasi-regular distributions

From papers

Let F={Fi}i[n]\boldsymbol{F}=\{F_i\}_{i\in[n]} be n1n\geq1 asymmetric quasi-regular valuation distributions, let ε(0,1)\varepsilon\in(0,1), and define truncated distributions F~={F~i}i[n]\widetilde{\boldsymbol{F}}=\{\widetilde F_i\}_{i\in[n]} by truncating each distribution to [0,t][0,t], where

t=1εBOM(F).t=\frac{1}{\varepsilon}\,\operatorname{BOM}(\boldsymbol{F}).

Here BOM(F)\operatorname{BOM}(\boldsymbol{F}) is the expected revenue of the Bayesian Optimal Mechanism. Quasi-regular truncation conjecture. The truncated distributions satisfy

BOM(F~)(1O(ε))BOM(F).\operatorname{BOM}(\widetilde{\boldsymbol{F}})\geq(1-O(\varepsilon))\operatorname{BOM}(\boldsymbol{F}).

This would show that truncating quasi-regular distributions incurs the same-order revenue loss as truncating regular distributions, yielding the corresponding sample-complexity bound. The conjecture is proved for single-buyer instances, n=1n=1, but remains open for multiple buyers.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yiding Feng and Yaonan Jin, “Beyond Regularity: Simple versus Optimal Mechanisms, Revisited”, arXiv:2411.03583 (2024).

Solutions 0

No solutions have been posted yet.