报告题目（Title）： Mechanisms for dual-role-facility location games: Truthfulness and approximability

报告人（Speaker）：陈旭瑾（中国科学院数学与系统科学研究院）

报告时间（Time）： 2022年9月28日下午2:30-4:30

报告地点（Venue）：

报告摘要（Abstract）：In this talk, we discuss the facility location game with payments, where every agent plays a dual role of facility and customer. In this game, each selfish agent is located on a publicly known location in a metric space, and can allow a facility to open at his location. The opening cost is his private information and he may strategically report it. Besides, each agent bears a service cost equal to the distance to the nearest open facility. Given reports from all agents, a mechanisms outputs a set of agents whose facilities could open and a payment to each of these agents. The mechanism is truthful if no agent has an incentive to misreport.

We characterize the normalized truthful mechanisms for this dual-role facility location game. We study truthful mechanism design for optimizing two types of system objective. For minimizing the total opening and service cost, we give an optimal truthful mechanism which runs in exponential time; when restricted to polynomial-time computation, we prove a small gap between the best known approximation ratios of truthful mechanisms and the pure (nonstrategic) optimization counterparts. For minimizing the maximum agent cost, we provide an optimal truthful mechanism which runs in polynomial time. Moreover, when the total payment cannot exceed a given budget, we prove lower and upper bounds on approximation ratios of truthful mechanisms for both system objectives. (Joint work with Minming Li, Changjun Wang, Chenhao Wang and Yingchao Zhao)

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