Proportional Fairness in Obnoxious Facility Location
This work addresses fairness in facility location for agents who prefer distance, with incremental contributions to mechanism design and game theory.
The paper tackles the obnoxious facility location problem by proposing proportional fairness axioms based on group size and distance, and analyzes mechanisms for deterministic and randomized settings, showing incompatibility with strategyproofness in deterministic cases and identifying strategyproof mechanisms with constant-factor welfare in randomized cases.
We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, we show that our proportional fairness axioms are incompatible with strategyproofness, and prove asymptotically tight $ε$-price of anarchy and stability bounds for proportionally fair welfare-optimal mechanisms. In the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare. Finally, we prove existence results for two extensions to our model.