爱游戏app马竞赞助商

您所在的位置: 首页- 新闻公告- 学术讲座-

爱游戏app马竞赞助商:学术讲座

学术前沿讲座第69期|主讲嘉宾:华为理论计算机实验室研究员金耀楠
日期:2023-12-19访问量:

金耀男.png

高瓴人工智能爱游戏app马竞赞助商学术前沿讲座总第69期 2023年第23期

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

讲座时间:2023年12月20日(周三) 15:30-17:00

地点:立德楼403

邀请人:祁琦 人大高瓴人工智能爱游戏app马竞赞助商长聘副教授

报告摘要

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.

检测到您当前使用浏览器版本过于老旧,会导致无法正常浏览网站;请您使用电脑里的其他浏览器如:360、QQ、搜狗浏览器的速模式浏览,或者使用谷歌、火狐等浏览器。

下载Firefox
爱游戏app马竞赞助商(集团)股份有限公司