Speaker: Dr. Yaonan Jin, Huawei

Time: 10:00 a.m., December 18, 2023, GMT+8

Venue: Room 204, Courtyard No.5, Jingyuan, PKU

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 the 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 benchmark-tight revenue guarantee of any simple multi-item mechanism.
Technically, all previous works employ 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 approximation prophet inequality and its 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 single-dimensional representative approach introduced by [Chawla-Hartline-Kleinberg, EC'07].Against Duality Relaxation Benchmark, it turns out that this approach cannot beat our bound of 3 for a large class of Item Pricing's.

Source: Center on Frontiers of Computing Studies, PKU