Mechanism Design in Facility Location Games

Algorithmic game theory is a research field integrating game theory and algorithm design. The major target is to design good algorithms in strategic environments. In this thesis, I intend to study a well-established problem in algorithmic game theory called facility location games. In the most classic setting, the government plans to build a facility on a street where some strategic agents with private information live. Agents want to be as close as possible to the facility. The objective of the government is to collect the agents' information and use a mechanism to decide where to build the facility so that agents will not gain by reporting false information and certain objective values are approximately optimized. In recent years, many extensions to the original facility location games are proposed and studied by the researchers. This thesis studies three different kinds of facility location games, and designs truthful mechanisms with good performances, which will offer new insight on extending the classic facility location games.