Research map / Multi-agent systems and games / Games and equilibria
Facility Location Games with Optional Preferences: A Revisit
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.
Designs deterministic strategyproof mechanisms for k-facility location games with optional preferences on the line (Min and Max variants) for k≥3 and k=3, with approximation ratios and matching-style lower bounds for minimizing maximum and social cost.
Problem
Strategyproof facility location on a line where agents have public locations and private optional (acceptable) facility sets, aiming to minimize maximum or social cost with k facilities, under Min (closest acceptable facility) and Max (farthest acceptable facility) cost variants.
Approach
Extends optional-preference facility location from k≤2 to k≥3 facilities by using optimal k-center/k-median style dynamic programs on agent locations as candidate positions, then iteratively deleting candidates so each agent is served by a preferred facility at its closest candidate, which yields strategyproofness; for Max variant, placing each facility at the midpoint or median of agents preferri
Key results
- Min variant, k≥3, well-separated agents: deterministic strategyproof mechanism with approximation ratio 3 for maximum cost and 2n+1 for social cost, with lower bounds 3/2 and n/4.
- Min variant with exactly three facilities: approximation ratio 2 for maximum cost and n+2 for social cost.
- Max variant: optimal strategyproof mechanism for maximum cost (midpoint placement) and k-approximation for social cost (median placement, tight by example).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Mechanism 1 to choose facility locations | Min variant with k ≥ 3 · Maximum cost for well-separated agents | approximation ratio: 3 | Helped |
| Use Mechanism 2 to choose facility locations | Min variant with k ≥ 3 · Social cost for well-separated agents | approximation ratio: 2n + 1 | Helped |
| Specialize the mechanism to exactly three facilities | Min variant maximum-cost mechanism · Maximum cost, k = 3 | approximation ratio: 3 -> 2 | Helped |
| Specialize the mechanism to exactly three facilities | Min variant social-cost mechanism · Social cost, k = 3 | approximation ratio: 2n + 1 -> n+2 | Helped |
| Place each facility at the midpoint of agents who accept it | Max variant maximum-cost mechanism · Maximum cost | approximation ratio | Helped |
| Place each facility at the median of agents who accept it | Max variant social-cost mechanism · Social cost | approximation ratio: k | Helped |
Surprising findings
- For the Min variant with social cost, the best achievable approximation ratio by any deterministic strategyproof mechanism grows linearly in n once k reaches three, unlike the constant ratio for k=2.
Limitations
- Min variant approximation bounds for k≥3 are not matched (gap between upper and lower bounds).
- Results for the social cost in the Min variant are restricted to well-separated agents.
- Analysis is deterministic only; randomized mechanisms are not explored.
Experimental setup
Metrics: approximation ratio for maximum cost approximation ratio for social cost
Baselines: EqualCost mechanism (Fotakis and Tzamos 2013) Chen et al. 2020 mechanisms
Builds on: optional preference facility location (Chen et al. 2020) Li et al. 2020 two-facility mechanism Love 1976 dynamic programming approximate mechanism design without money (Procaccia and Tennenholtz 2013)
Closest papers by meaning
- Facility Location Games With Fractional Preferences (AAAI 2018 · similarity 0.93)
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.89)
- Randomized Strategic Facility Location with Predictions (NeurIPS 2024 · similarity 0.88)
- Altruism in Facility Location Problems (AAAI 2024 · similarity 0.86)
- MAC Advice for facility location mechanism design (NeurIPS 2024 · similarity 0.86)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · 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.