Research map / Multi-agent systems and games / Games and equilibria
Altruism in 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 mechanism design for facility location with altruistic agents in overlapping groups, introducing Pareto strategyproofness and giving approximation upper and lower bounds for four objectives under two altruistic cost models.
Problem
Facility location on a line where agents belong to multiple overlapping groups and act altruistically (caring about group members' costs), so standard strategyproofness does not apply and the planner must elicit true locations while approximately optimizing social cost, maximum cost, or group-fair o
Approach
Model altruistic agents with altruistic total or maximum group costs, define ex-post Pareto strategyproofness for incomparable multi-group costs, use a profile preprocessing step to avoid group-median manipulation, and design mechanisms (Majority-Med, Weighted-Med, Union-Med, UnionTrunc-Med, Weighted-Mid, Majority-Mid) with matching-style bounds.
Key results
- UnionTrunc-Med is Pareto strategyproof with approximation ratio m(4m-5)/(3m-4) (about 4m/3) for social cost, with matching lower bound of m for deterministic PSP mechanisms.
- Majority-Med and Majority-Mid achieve approximation ratio 3 for mtgc/magc under altruistic total cost, with tight lower bound of 3.
- Weighted-Mid is Pareto strategyproof with approximation ratio n/2 for social cost under altruistic maximum cost, with matching lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use UnionTrunc-Med instead of Majority-Med or Union-Med for social cost | Altruistic total cost facility location · Social cost | approximation ratio: 2m − 1 -> m(4m−5)/(3m−4) | Helped |
| use Weighted-Mid for the social cost objective | Altruistic maximum cost facility location · Social cost | approximation ratio: n/2 | Helped |
| use Weighted-Mid for the maximum cost objective | Altruistic maximum cost facility location · Maximum cost | approximation ratio: 2 | Helped |
| use Majority-Mid rather than Weighted-Mid for group-fair objectives | Altruistic maximum cost facility location · Maximum total group cost | approximation ratio: |Gmax| -> |Gmax|/2 + 1 | Helped |
| use Majority-Mid rather than Weighted-Mid for group-fair objectives | Altruistic maximum cost facility location · Maximum average group cost | approximation ratio: |Gmax| -> |Gmax|/2 + 1 | Helped |
Surprising findings
- No ex-ante Pareto strategyproof mechanism has a bounded approximation ratio for both altruistic cost types, even with one group, motivating the weaker ex-post notion.
- Existing classical mechanisms (median, leftmost, and Majority-Med-type group median) are not Pareto strategyproof under altruistic costs.
Limitations
- Most proofs are omitted in the paper body due to space limits.
- Results are for deterministic mechanisms on the real line; upper and lower bounds are not always tight (e.g., social cost gap between m(4m-5)/(3m-4) and m).
- Only Pareto strategyproofness with ex-post implementation is considered; ex-ante notion admits no bounded mechanism.
Experimental setup
Metrics: approximation ratio
Baselines: Median mechanism Leftmost mechanism Majority-Med Weighted-Med
Builds on: Procaccia and Tennenholtz 2009 approximate mechanism design without money Zhou, Li, and Chan 2022 group-fair facility location
Closest papers by meaning
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.89)
- Minimizing Inequity in Facility Location Games (AAAI 2026 · similarity 0.88)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.86)
- Randomized Strategic Facility Location with Predictions (NeurIPS 2024 · similarity 0.85)
- MAC Advice for facility location mechanism design (NeurIPS 2024 · similarity 0.82)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.82)
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.