Strategyproof Mechanisms For Group-Fair Facility Location Problems

Ensuring group fairness among groups of individuals in our society is desirable and crucial for many application domains. A social planner's typical medium of achieving group fair outcomes is through solving an optimization problem under a given objective for a particular domain. When the input is provided by strategic agents, the planner is facing a difficult situation of achieving fair outcomes while ensuring agent truthfulness without using incentive payment. To address this challenge, we consider the approximate mechanism design without money paradigm with group-fair objectives. We first consider the group-fair facility location problems where agents are divided into groups. The agents are located on a real line, modeling agents' private ideal preferences/points for the facility's location. Our aim is 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 consider various group-fair objectives and show that many objectives have an unbounded approximation ratio. We then consider the objectives of minimizing the maximum total group cost and 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.