Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM seminar] - Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer

     We study revenue maximization in the unit-demand single-buyer setting. Our main result is that {\sf Uniform-Ironed-Virtual-Value Item Pricing} guarantees a {\em tight} $3$-approximation to the {\sf Duality Relaxation Benchmark} [Chawla-Malec-Sivan, EC'10/GEB'15; Cai-Devanur-Weinberg, STOC'16/ SICOMP'21], breaking the barrier of $4$ since [Chawla-Hartline-Malec-Sivan, STOC'10; Chawla-Malec-Sivan, EC'10/GEB'15]. To our knowledge, this is the first {\em benchmark-tight} revenue guarantee of any simple multi-item mechanism.

     Technically, all previous works employ {\sf Myerson Auction} as an intermediary. The barrier of $4$ follows as {\sf Uniform-Ironed-Virtual-Value Item Pricing} achieves a {\em tight} $2$-approximation to {\sf Myerson Auction}, which then achieves a {\em tight} $2$-approximation to {\sf Duality Relaxation Benchmark}. Instead, our new approach avoids {\sf Myerson Auction}, thus enabling the improvement. Central to our work are a {\em benchmark-based} $3$-competitive prophet inequality and its {\em fully constructive} proof. Such variant prophet inequalities shall find future applications, e.g., to Multi-Item Mechanism Design where optimal revenues are relaxed to various more accessible benchmarks.

     We complement our benchmark-tight ratio with an impossibility result. All previous works and ours follow the {\em single-dimensional representative} approach introduced by [Chawla-Hartline-Kleinberg, EC'07]. Against {\sf Duality Relaxation Benchmark}, it turns out that this approach cannot beat our bound of $3$ for a large class of {\sf Item Pricing}'s.