Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
- Dr. Yaonan Jin, Huawei
- Time: 2023-12-18 10:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
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$-approximation 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.
Biography
Yaonan Jin is a full-time researcher at the Huawei TCS Lab. His research interests encompass Theoretical Computer Science, with an emphasis on Algorithmic Economics. Before joining Huawei, he obtained his PhD from Columbia University in 2023, advised by Prof. Xi Chen and Prof. Rocco Servedio. Before that, he obtained his MPhil from Hong Kong University of Science and Technology in 2019 and his BEng from Shanghai Jiao Tong University in 2017.