Strategyproof Mechanisms for Facility Location Games

This direction is merged into another direction: incentive compatibility. Its last version stays readable and citable here.

Version 1 of 133 papers34 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_strategyproof_mechanisms_for_facility_lo_56ead8c6,
  title = {Strategyproof Mechanisms for Facility Location Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strategyproof-mechanisms-for-facility-location-games/rdr_56ead8c66e7b4704a1e311b5d1ed31c4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_strategyproof_mechanisms_for_facility_lo_56ead8c6_v1,
  title = {Strategyproof Mechanisms for Facility Location Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strategyproof-mechanisms-for-facility-location-games/rdr_56ead8c66e7b4704a1e311b5d1ed31c4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}