Strategyproof Mechanisms For Group-Fair Facility Location Problems

Motivated by the societal need to provide fair accessibility or representation among groups of agents, we study the group-fair facility location problems where agents are divided into groups based on criteria such as race, gender, or age. The agents are located on a real line, modeling agents' private ideal preferences/points for the facility's location (e.g., a public school or representative). Our aim is to design mechanisms to locate a facility to (approximately) minimize the costs of groups of agents to the facility fairly while eliciting the agents' private locations truthfully. We first introduce various well-motivated group-fair cost objectives and show that many natural objectives have an unbounded approximation ratio. We then consider the objectives of minimizing the maximum total group cost and minimizing the average group cost. For the first objective, we show that the approximation ratio of the median mechanism depends on the number of groups and provide a new group-based mechanism with an approximation ratio of 3. For the second objective, the median mechanism obtains a ratio of 3, and we propose a randomized mechanism that obtains a better approximation ratio. We also provide lower bounds for both objectives. We then study the notion of intergroup and intragroup fairness that measures fairness between groups and within each group. We consider various objectives and provide mechanisms with tight approximation ratios.