Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer

Abstract. We study revenue maximization in the unit-demand single-buyer setting. Our main result is that Uniform-Ironed-Virtual-Value Item Pricing guarantees a tight 3-approximation to Duality Relaxation Benchmark (Chawla, Malec, and Sivan, EC’10 and GEB’15; Cai, Devanur, and Weinberg, STOC’16 and [ SIAM J. Comput., 50 (2021), pp. STOC16-160–STOC16-200]), breaking the barrier of 4 since Chawla et al. [ Proceedings of STOC’10, 2010, pp. 311–320] and Chawla, Malec, and Sivan (EC’10 and GEB’15). To our knowledge, this is the first benchmark-tight revenue guarantee of any simple multi-item mechanism. Technically, all previous work employs Myerson Auction as an intermediary. The barrier of 4 follows as Uniform-Ironed-Virtual-Value Item Pricing achieves a tight 2-approximation to Myerson Auction , which then achieves a tight 2-approximation to Duality Relaxation Benchmark . Instead, our new approach avoids Myerson Auction , thus enabling the improvement. Central to our work are a benchmark-based 3-competitive prophet inequality and its fully constructive proof. Such prophet inequality variants will likely find applications in, e.g., multi-item mechanism design, when the optimal revenue objective is relaxed to various more accessible benchmarks. We complement our benchmark-tight ratio with an impossibility result. All previous works, including ours, follow the single-dimensional representative approach introduced by Chawla, Hartline, and Kleinberg [ Proceedings of EC’07, 2007, pp. 243–251]. Against Duality Relaxation Benchmark , it turns out that this approach cannot beat our bound of 3 for a large class of Item Pricing .