Facility Location Games: Previous Results to Recent Development


Event Details
Thursday, December 2, 2021
Talk:
7 p.m., Zoom

Reception:
N/A, N/A

Minming Li, Ph.D.

Professor, City University of Hong Kong

Abstract

Mechanism design, one of the most important areas in algorithmic game theory, can be classified into two categories: with money and without money. One of the first and well-studied settings in mechanism design without money is that of facility location games, which will be the main focus of this talk. Procaccia and Tennenholtz proposed and studied the facility location games in 2009, where there are n agents on a line and the social planner aims to build a facility in a certain location given the agents reported information on their positions. Since every agent wants the facility to be closer to themselves, the social planner wants to make sure truth-telling is the best strategy for every agent while optimizing some social objective when locating the facility to serve the agents. Since then, theoretical bounds on the approximation ratios of the truthful mechanisms have been improved and new variations of the games have been proposed. In this talk, I will briefly describe the classic facility location games and discuss the recent development of these fascinating games on new variations proposed by us and other research groups.

Speaker Bio

Minming Li is currently a professor in the Department of Computer Science, City University of Hong Kong. He received his Ph. D. and B.E. degree in the Department of Computer Science and Technology at Tsinghua University in 2006 and 2002 respectively. His research interests include algorithmic game theory, combinatorial optimization and algorithm design and analysis for scheduling problems.