In spatial social choice, a central planner must decide where to place a public resource—like a library, a hospital, or a landfill—based on the reported locations of the people who will use (or avoid) it. The fundamental challenge is that these participants are strategic: they may misreport their private locations to "pull" a desirable facility closer or "push" an undesirable one away.
As surveyed by Hau Chan, Aris Filos-Ratsikas, and colleagues in Mechanism Design for Facility Location Problems: A Survey, this research area seeks to design strategyproof mechanisms—algorithms where no agent can benefit from lying—while still achieving social goals like efficiency or fairness.
The Intuition of the Median
To understand why strategyproofness is difficult, consider placing a single library on a one-dimensional street. If the planner chooses the average of all reported locations, a single agent living at the far left could report a location miles further left to pull the average toward their actual home. The average is highly manipulable.
The "hero" of 1D facility location is the Median Mechanism. If you place the facility at the median of the reported locations, it becomes strategyproof. Why? If you are to the left of the median, reporting a location even further left doesn't change the median. Reporting a location to the right might move the median to the right, which is further from you. Truth-telling becomes the dominant strategy.
However, as Dimitris Fotakis and Christos Tzamos demonstrate in On the Power of Deterministic Mechanisms for Facility Location Games, this simplicity vanishes when we move to two or more facilities. They prove that for multiple facilities, deterministic strategyproof mechanisms are surprisingly limited, often forcing the planner into "dictatorial" outcomes or extreme approximations to prevent cheating.
When Facilities are Obnoxious
Not every facility is a library. For "obnoxious" facilities like landfills or power plants, agents want to be as far away as possible. In Obnoxious Facility Location Problems: Strategyproof Mechanisms Optimizing Lp-Aggregated Utilities and Costs, Hau Chan, Jianan Lin, and Chenhao Wang explore this inversion.
In this setting, agents have an incentive to report locations closer to the proposed site than they actually are, hoping the planner will move the site further away to protect them. The authors show that while deterministic rules face harsh bounds, randomized mechanisms can significantly improve social welfare by injecting uncertainty that discourages strategic "pushing."
Constraints of Capacity and Scarcity
The problem becomes even more complex when facilities have limited resources. In The capacity constrained facility location problem, Hau Chan and Barton E. Lee highlight a shift from simple spatial preference to strategic interdependence.
When a facility has a maximum capacity, an agent’s utility depends not just on the facility's location, but on whether they are among the closest $k$ people served. This creates a "competition for proximity." The authors identify Generalized Median Mechanisms (GMMs) as the only class of strategyproof rules that can handle these constraints while maintaining a degree of efficiency. Similarly, Jie Zhang and Gennaro Auricchio use Optimal Transport theory in Designing Optimal Mechanisms to Locate Facilities with Insufficient Capacity for Bayesian Agents to find "percentile mechanisms" that maximize welfare when the distribution of agents is known.
Balancing Efficiency and Fairness
A recurring theme across this literature is the tension between minimizing total cost (efficiency) and ensuring no group is left behind (fairness). Alexander Lam suggests in Nash Welfare in the Facility Location Problem that the product of utilities (Nash welfare) can bridge this gap, though it remains difficult to optimize without inviting manipulation.
To address demographic disparities, Houyu Zhou, Minming Li, and Hau Chan developed mechanisms for Group-Fair Facility Location. In Strategyproof Mechanisms For Group-Fair Facility Location Problems, they prove that while perfect fairness is often mathematically impossible to achieve efficiently, randomized placement strategies can provide guaranteed fairness levels that are robust against individual lies.
Expanding the Action Space
Recent work has pushed these boundaries into more realistic, high-dimensional, or data-rich environments:
- Complex Preferences: Richard Cole and Pranav Jangir introduce "doubly-peaked" costs in Facility Location with Public Locations and Private Doubly-Peaked Costs, where agents want to be near a facility but not directly adjacent to it (e.g., wanting to live near a train station but not on the tracks).
- Machine Learning Integration: Eric Balkanski and colleagues explore Randomized Strategic Facility Location with Predictions, showing how noisy predictions about agent locations can be used to improve mechanism performance without sacrificing strategyproofness.
- Multi-Agent Coordination: Paul Friedrich and others extend these concepts to pathfinding in Scalable Mechanism Design for Multi-Agent Path Finding, ensuring that agents like delivery drones cannot gain priority by lying about their spatial constraints.
By treating facility location as a game of information, this field provides the mathematical tools to build public infrastructure that is both socially optimal and resistant to the self-interest of its users.