学术讲座

时间：2024年1月23日（周二） 10:00-11:30

腾讯会议：280-777-376

邀请人：王子贺 高瓴人工智能学院准聘副教授

主讲人：王康宁 美国斯坦福大学 博士后研究员

报告题目：Better Distortion for Metric Voting

嘉宾简介：

Kangning is a Motwani Postdoctoral Fellow at Stanford University, hosted by Moses Charikar and Aviad Rubinstein. He earned his Ph.D. in Computer Science from Duke University, advised by Kamesh Munagala. He was a J.P. Morgan Research Fellow of the program 'Data-Driven Decision Processes' at the Simons Institute, UC Berkeley. He interned twice at Google Research, hosted by Jieming Mao, Renato Paes Leme, and Aranyak Mehta.

He conducts research at the intersection of Computer Science, Economics, and Operations Research, with a focus on Mechanism Design, Social Choice, Information Design, Market Design, and Algorithmic Fairness. His work has been recognized by an ACM SIGecom Doctoral Dissertation Award Honorable Mention, a Duke CS Best Dissertation Award, and with coauthors, Best Paper Awards at SODA 2024 and WINE 2018.

报告摘要：

In this talk, we consider the distortion of metric voting, a topic that has gained quite significant attention among the EconCS community in recent years. Here, we have an election with voters and candidates in a shared metric space, and our goal is to design a voting rule that chooses a candidate whose social cost — sum of distances to the voters — is small. However, instead of having direct access to the distances in the metric space, each voter gives us a ranked list of candidates in order of their distances. Can we design a voting rule that, regardless of the election instance and underlying metric space, chooses a candidate whose social cost differs from the true optimum by only a small factor (known as the distortion)? During the past years, researchers have proposed many different voting rules, deterministic and randomized, with distortion 3. We will discuss these along with our new ideas that allowed us to design a (randomized) voting rule with distortion 2.753, finally breaking the barrier of 3.