报告题目：Single-Candidate Reverse Voting in a Metric Space

主 讲 人：陈旭瑾 研究员（中国科学院数学与系统科学研究院）

报告时间：12月3日 16:00-17:00

报告地点：腾讯会议ID：248 361 454、数学楼305

主办单位：数学科学学院

报告摘要：In this talk, we discuss a variant of single-candidate voting embedded in a metric space. Both voters and candidates are points in the space. The distances between voters and candidates specify the voters' preferences over candidates. Each voter submits her favorite candidate to a mechanism that does not know voters' locations. The mechanism outputs the least popular candidate, i.e., finds a committee containing the other candidates.

Each committee is associated with a social value -- the sum of the costs (utilities) it imposes (provides) to the voters. We design algorithmic mechanisms for finding a committee to optimize the social value. We measure the quality of a mechanism by its distortion, i.e., the worst-case ratio between the social value of the committee found by the mechanism and the optimal one. We establish upper and lower bounds on mechanism distortion for this single-candidate reverse voting in general metrics and well-motivated special cases. (Joint work with Minming Li and Chenhao Wang.)

主讲人简介：陈旭瑾，2004年获香港大学博士学位，现为中国科学院数学与系统科学研究院研究员。主要研究兴趣是组合优化的理论和算法，包括算法博弈论、网络优化、多面体组合等。曾获中国青年科技奖、中国运筹学会青年科技奖、国家优秀青年基金。