讲座题目：Favorite-Candidate Voting for Eliminating the Least Popular Candidate in a Metric Space 主讲人：陈旭瑾 研究员 主持人🏊♂️：袁龙图 开始时间：2020-08-06 14:00:00 结束时间💲：2020-08-06 15:00:00 讲座地址💂🏻♂️：腾讯会议 ID：751 890 211 主办单位：数学科学学院
报告人简介： 陈旭瑾研究员👨🏻🚀，2004年获香港大学博士学位，现为中国科学院数学与系统科学研究院研究员👨🦳。主要研究兴趣和方向是组合优化的理论和应用，包括算法博弈论🤦🏻👨🏼🔬、网络优化👩🎓、多面体组合等。2010年获“中国运筹学会青年科技奖”一等奖，2013年获首届国家优秀青年基金。
报告内容： We study single-candidate voting embedded in a metric space, where both voters and candidates are points in the space, and the distances between voters and candidates specify the voters’ preferences over candidates. In the voting, each voter is asked to submit her favorite candidate. Given the collection of favorite candidates, a mechanism for eliminating the least popular candidate finds a committee containing all candidates but the one to be eliminated. Each committee is associated with a social value that is the sum of the costs (utilities) it imposes (provides) to the voters. We design mechanisms for finding a committee to optimize the social value. We measure the quality of a mechanism by its distortion, defined as the worst-case ratio between the social value of the committee found by the mechanism and the optimal one. We establish new upper and lower bounds on the distortion of mechanisms in this single-candidate voting, for both general metrics and well-motivated special cases. (Joint work with Minming Li and Chenhao Wang.) |
