New strategyproof algorithm for facility location handles mixed agent types
Researchers prove deterministic mechanisms achieve 3-approximation even with private locations and types
In a new arXiv preprint, researchers Gruszecki and Anshelevich tackle the strategic facility location problem, where n agents with private locations and cost types influence the placement of k facilities. Agents can be max-type (want the farthest facility as close as possible) or sum-type (want the average distance minimized). The challenge: design mechanisms that are strategyproof (agents cannot benefit from lying) while still approximating the optimal social cost.
For settings where agent locations are public but their types are private, the authors provide a deterministic mechanism achieving an approximation ratio of 3 - 2/k for any metric space. If the overall fraction of each type is known but not individual types, they improve the ratio to (2/(1 - k + sqrt(k² - k + 1)) - 1). When locations are private (on a line metric), a simple generalization of the median mechanism yields a 3-approximation for any k and any type mix. The results highlight the trade-off between collecting type information vs. location information, showing that good outcomes are possible without full knowledge.
- Deterministic strategyproof mechanism achieves (3 - 2/k) approximation for known locations, unknown types in any metric space
- With known type fractions, approximation improves to (2/(1 - k + sqrt(k² - k + 1)) - 1) for arbitrary k
- On a line metric with private locations, a median generalization gives 3-approximation for any mix of max and sum agents
Why It Matters
Practical insights for fair resource allocation (e.g., hospitals, polling stations) when users have diverse fairness preferences.