In this thesis, we study the problem of designing mechanisms for placing public facilities in a city. We focus on scenarios where the locations of individuals are private information, and the objective is to minimize either the total or the maximum distance of all individuals to the chosen facility location. Traditional approaches that rely on monetary transfers are often inappropriate in such settings, so we seek mechanisms that prevent individuals from misreporting their true location in order to gain an advantage-i.e., to be closer to the facility. Since optimal truthful mechanisms often do not exist, we turn our attention to approximation mechanisms that guarantee a solution not too far from the optimal in terms of social cost. We begin by considering the case where the city is modeled as the real line and a single facility is to be located. We then extend the problem to the case of two facilities and, finally, to the case where the city is represented as a graph.
|
