Research map / Learning theory and algorithms / Fairness
Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies strategyproof mechanisms for group-fair facility location on a line, showing some group-fair objectives are unboundable, proposing group-based mechanisms (MGDM, NRM) for max total/average group cost and a k-LDM for intergroup-intragroup fairness objectives with tight ratios.
Problem
Strategyproof facility location on the real line for agents partitioned into groups, where the facility should approximately optimize group-fair cost objectives (max total group cost, max average group cost, and intergroup/intragroup fairness) while agents report locations privately.
Approach
Shows many natural group-fair objectives (group-cost differences/ratios) admit no finite approximation for deterministic SP mechanisms; proposes group-aware mechanisms (MGDM placing facility at median of largest group, NRM narrowing the randomized interval to medians of groups) and new IIF objectives combining intergroup average cost with intragroup max-min spread, with k-LDM achieving tight ratio
Key results
- MGDM achieves approximation ratio 3 for max total group cost (mtgc) with matching example, and lower bound 2 for deterministic SP mechanisms.
- NRM achieves approximation ratio 2 for max average group cost (magc), with randomized lower bound 3/2.
- k-LDM achieves tight approximation ratio 4 for both IIF1 and IIF2, matching the deterministic lower bound of 4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MGDM, which places the facility at the median of the largest group, instead of group-independent mechanisms | Strategyproof facility-location mechanisms · mtgc | approximation ratio: 3; MDM: Ω(m); LDM: Ω(n) | Helped |
| use NRM, which randomizes over the extreme group medians and their midpoint, instead of RM's extreme agent locations and midpoint | Strategyproof randomized facility-location mechanisms · magc | approximation ratio: Ω(n) -> 2 | Helped |
| use NRM instead of RM | Strategyproof randomized facility-location mechanisms · mtgc | approximation ratio: Ω(n) -> Ω(n) | No clear effect |
| use k-LDM, placing the facility at the kth agent's location | Strategyproof facility-location mechanisms · IIF₁ and IIF₂ | approximation ratio: 4 | Helped |
Surprising findings
- Any deterministic strategyproof mechanism has unbounded approximation ratio for many natural group-fair objectives (group cost differences and ratios).
- MDM achieves ratio 3 for magc despite being group-agnostic, while it is unbounded (Omega(m)) for mtgc.
Limitations
- Gaps remain between lower and upper bounds for mtgc (2 vs 3) and magc (3/2 vs 2 for randomized).
- Analysis restricted to one-dimensional real line with agents' locations as the only private information.
Experimental setup
Metrics: approximation ratio
Baselines: MDM LDM RM MGDM NRM k-LDM
Builds on: approximate mechanism design without money randomized mechanism for maximum cost (1.5 ratio)
Closest papers by meaning
- Minimizing Inequity in Facility Location Games (AAAI 2026 · similarity 0.94)
- Heterogeneous Facility Location with Limited Resources (AAAI 2022 · similarity 0.90)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.89)
- Altruism in Facility Location Problems (AAAI 2024 · similarity 0.89)
- Randomized Strategic Facility Location with Predictions (NeurIPS 2024 · similarity 0.88)
- MAC Advice for facility location mechanism design (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.