静5青年讲座 | Benchmark-Tight Approximation Ratio…

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

报告人

Dr. Yaonan Jin

Huawei

时  间

2023年12月18日 星期一 10:00am

地  点

静园五院204

Host

姜少峰 助理教授

 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.

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.

往 期 讲 座

• 静5前沿讲座回顾 | 周俊杰教授谈多层网络上的协作博弈

• 静5前沿讲座回顾 | 区文浩教授谈密码学前沿进展及在区块链中的应用

• 静5前沿讲座回顾 | 黄志毅教授谈数据驱动的拍卖机制设计问题

• 静5杰出讲座回顾｜叶荫宇教授谈随机Fisher市场中的在线均衡标价问题

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”查看海报