New pricing algorithm achieves tight 3x revenue guarantee for unit-demand buyers

The paper tackles the classic problem of maximizing revenue from a unit-demand buyer (who wants at most one item) using simple item pricing. The authors present Uniform-Ironed-Virtual-Value Item Pricing, which guarantees a tight 3-approximation to the Duality Relaxation Benchmark—a widely used upper bound on optimal revenue. This improves on the prior best known ratio of 4, which had stood since foundational works by Chawla, Hartline, Malec, and Sivan (STOC 2010).

The key innovation is a clever avoidance of the Myerson Auction as an intermediate step. Earlier approaches first compared item pricing to Myerson's optimal single-item auction (tight 2-approximation), then compared Myerson to the Duality Benchmark (another tight 2-approximation), yielding a combined 4-approximation. By directly linking item pricing to the Duality Benchmark, the authors achieve a 3-approximation. Central to this is a new "benchmark-based" 3-competitive prophet inequality, with a fully constructive proof that could generalize to multi-item mechanism design.

Moreover, the authors prove an impossibility result: within the widely used "single-dimensional representative" framework, no item pricing strategy can beat a 3-approximation against the Duality Relaxation Benchmark. This establishes that their algorithm is optimal under that approach. The result has significant implications for algorithmic game theory and the design of simple, practical pricing mechanisms for digital goods and online marketplaces.