Mechanism Design without Money for Heterogeneous and Distributed Facility Location Problems

Algorithmic Mechanism Design (AMD) is an interdisciplinary field that bridges economics and computer science and aims to design mechanisms for systems with self-interested agents. This study focuses on motivating truthful information disclosure while optimizing social goals. Traditional payment-based mechanisms cannot be effectively applied to some of these problems, but we can utilize approximate mechanisms to obtain truthfulness without recourse to payments. One of the well-established problems in approximate mechanism design without money is the facility location problem. In this context, agents possess private positions along a line, and the goal is to determine the location of a public facility while motivating truthful disclosures and achieving optimal social outcomes. This thesis presents contributions across three key dimensions of facility location problems: (1) Heterogeneous Two-Facility Location Problem: Addressing a discrete setting where agents occupy nodes on a line graph and possess private preferences for two facilities, the research introduces deterministic strategy-proof mechanisms with improved approximation ratios, surpassing existing approaches. (2) Two-Facility Location with Candidate Positions: Investigating another variant, where agents have private positions and known preferences for two facilities, the study identifies deterministic strategy-proof mechanisms that achieve the best possible approximation ratios for social and maximum costs. (3) Distributed Facility Location Problem: A set of agents with positions on the line of real numbers are partitioned into disjoint districts, we designed deterministic distributed mechanisms that satisfy various criteria of interest and achieve the best possible distortion bounds. The research analyzes two mechanism classes: Unrestricted, where agents directly provide truthful positions, and strategy-proof, designed to incentivize honesty. The study establishes tight bounds for various social objectives, including average social cost, max cost, and other fairness-inspired criteria. In summary, approximate mechanism design without money addresses complex challenges in multi-agent systems, creating mechanisms that promote truthfulness and optimize societal objectives. This thesis introduces innovative mechanisms and provides comprehensive insights into facility location problems from three distinct perspectives.