2018年7月9日-13日，由北京大学前沿计算研究中心承办的“计算理论周”系列讲座在北京大学静园五院举行。“理论周”由中心邓小铁老师发起及组织，邀请计算机理论方面的多位知名专家学者，介绍计算机理论方向的前沿课题，并就相关问题和同学们开展深入讨论。

　　李闽溟老师的报告题目为“Facility Location Games”，他介绍了一类有趣的博弈问题。在一条直线街道上有若干住户，而政府希望建立一个公用设施。每个住户为了使公用设施安排在对自己有利的位置（可能近可能远），可以选择向调研人员撒谎，宣称自己住在另一处地方，从而影响最后的政府决策。因此，政府的选址机制应当能避免住户通过撒谎获得更好的收益，同时使安排的设施能最小化代价（或最大化社会福利）。

　　这个问题本身变化多端，最简单的一种情况是基于单峰偏好的，例如大家都希望自己能住得离写字楼近，或是大家都希望住得离垃圾场远。另外还有双峰偏好的情况（例如，大家希望和医院的位置适中——太近会导致更高的概率交叉感染，太远会导致就医不方便）、偏好关系互补的情况（例如，有的住户希望菜市场越近越好，而有的住户则希望越远越好）、多个公共设施的情况（例如，政府同时安排商场和火车站的位置）、离散选址的情况（选址只能在离散的位置上）以及多层决策的情况（例如，住户与政府之间还有一层中介）。

　　对于每种情况，我们研究了若干不同的机制，详细分析讨论了它能否避免任何人撒谎，以及它与最优解所带来的代价的差距。

报告人简介：

　　Minming Li is an Associate Professor of Department of Computer Science at City University of Hong Kong. Prof. Li's research interestes include Algorithms Design and Analysis, Combinatorial Optimization, Scheduling, Algorithmic Mechanism Design.