Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems
Authors: Jiaqian Li, Minming Li, Hau Chan
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Jiaqian Li1, Minming Li1*, Hau Chan2 1Department of Computer Science, City University of Hong Kong, HKSAR China 2School of Computing, University of Nebraska-Lincoln, USA jiaqian.li@my.cityu.edu.hk, minming.li@cityu.edu.hk, hchan3@unl.edu |
| Pseudocode | No | The paper describes mechanisms (e.g., Mechanism 1, Mechanism 2) in narrative text rather than in structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement about releasing source code or a link to a code repository. |
| Open Datasets | No | This is a theoretical paper that defines mechanisms and proves approximation ratios and lower bounds. It does not involve empirical experiments with datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with validation datasets. |
| Hardware Specification | No | As a theoretical paper, it does not describe any specific hardware used for experiments. |
| Software Dependencies | No | As a theoretical paper, it does not list any specific software dependencies with version numbers for experimental setup. |
| Experiment Setup | No | As a theoretical paper, it does not detail any experimental setup with hyperparameters or training configurations. |