高瓴人工智能学院学术前沿讲座总第69期 2023年第23期

报告题目：Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer

讲座时间：2023年12月20日（周三） 15:30-17:00

地点：立德楼403

邀请人：祁琦 人大高瓴人工智能学院长聘副教授

报告摘要

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]. This is the first benchmark-tight revenue guarantee of any simple multi-item mechanism.

Technically, all previous works employ Myerson Auction as an intermediary. 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.

主讲嘉宾

金耀楠 华为理论计算机实验室研究员

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.