Facility Location Games, from Origin to Recent Development

Speaker:  Minming Li – Hong Kong, Hong Kong
Topic(s):  Computational Theory, Algorithms and Mathematics


Mechanism Design, as one of the important areas in algorithmic game theory, can be classified into two categories: with money and without money. Facility location game is one of the mostly studied problem in mechanism design without money. Procaccia and Tennenholtz proposed and studied the problem back in 2009, where there are n agents on a line and the government will 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 her, the government wants to make sure truth-telling is the best strategy for every agent while achieving some optimization objective. Since then, some bounds on the approximation ratios of the truthful mechanisms have been improved and new models are proposed. In this talk, we will briefly explain the story of the classic model and emphasize on the recent development on new models proposed by us and other groups.

About this Lecture

Number of Slides:  50
Duration:  60 minutes
Languages Available:  Chinese (Simplified), English
Last Updated: 

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.