Mechanism Design for Heterogeneous and Distributed Facility Location Problems

As a field of study that integrates game theory and algorithm design, algorithmic game theory aims to design efficient algorithms in environments with strategic agents. In this thesis, we investigate one of algorithmic game theory's main classes of problems, namely facility location problems. In the most classical setting, the goal is to locate one facility on a line given the reported positions of strategic agents, who aim to be as close to the facility as possible so that the agents do not benefit from reporting false information and some social objective function is (approximately) optimized. Many researchers have recently proposed extensions to this original facility location problem. We investigate some variants of the single-facility location problem, particularly the discrete heterogeneous two-facility location problem and the distribution facility location problem. For both of them, we devise deterministic (strategyproof) mechanisms with nearly tight performance guarantees.