Truncation-loss conjecture for quasi-regular distributions

About 2 years old · traced to

Let F={Fi}i∈[n]\boldsymbol{F}=\{F_i\}_{i\in[n]} be n≥1n\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~)≥(1−O(ε))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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.