Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems
DOI:
https://doi.org/10.1609/aaai.v38i9.28843Keywords:
GTEP: Social Choice / Voting, MAS: Mechanism DesignAbstract
We study the group-fair obnoxious facility location problems from the mechanism design perspective where agents belong to different groups and have private location preferences on the undesirable locations of the facility. Our main goal is to design strategyproof mechanisms that elicit the true location preferences from the agents and determine a facility location that approximately optimizes several group-fair objectives. We first consider the maximum total and average group cost (group-fair) objectives. For these objectives, we propose deterministic mechanisms that achieve 3-approximation ratios and provide matching lower bounds. We then provide the characterization of 2-candidate strategyproof randomized mechanisms. Leveraging the characterization, we design randomized mechanisms with improved approximation ratios of 2 for both objectives. We also provide randomized lower bounds of 5/4 for both objectives. Moreover, we investigate intergroup and intragroup fairness (IIF) objectives, addressing fairness between groups and within each group. We present a mechanism that achieves a 4-approximation for the IIF objectives and provide tight lower bounds.Downloads
Published
2024-03-24
How to Cite
Li, J., Li, M., & Chan, H. (2024). Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 38(9), 9832-9839. https://doi.org/10.1609/aaai.v38i9.28843
Issue
Section
AAAI Technical Track on Game Theory and Economic Paradigms