Strategyproof Spatial Allocation without Monetary Incentives

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

Version 1 of 154 papers97 conceptsfrozen 2026-10-04

In many collective decision-making scenarios, a central authority must place a resource—a library, a bus stop, or a warehouse—to serve a group of agents. Each agent wants the facility as close to their own location as possible. However, if the authority simply asks everyone where they live and picks the average (the mean), a single "Stubborn Joe" can manipulate the outcome. By reporting a location far to the right of their true home, Joe can pull the average toward himself, unfairly benefiting at the expense of the group.

To prevent this, researchers develop strategyproof mechanisms: rules where no agent can ever benefit by lying about their location. In the absence of money to "buy" truthfulness, these mechanisms rely on the geometry of the problem and the robustness of rank-based statistics.

The Robustness of the Median

The fundamental building block of this field is the Median Rule. As noted in the comprehensive survey by Hau Chan, Aris Filos-Ratsikas, and colleagues in Mechanism Design for Facility Location Problems: A Survey, selecting the median of reported positions is the gold standard for placing a single facility on a line.

The intuition for why the median is strategyproof is elegant:

  1. If you are to the left of the median and you report a location even further left, the median does not move.
  2. If you report a location to the right (but stay to the left of the current median), the median still does not move.
  3. If you "jump" across the median to the right, you can only move the median further away from your true location.

Because your report only affects the outcome when it crosses the median threshold, and doing so always hurts you, truth-telling becomes the dominant strategy. This rank-based logic extends to more complex problems, such as Truthful Interval Covering, where Argyrios Deligkas and Alexandros A. Voudouris show that anchoring a service window at the median starting point provides a stable, truthful approximation of the optimal social cost.

Anchoring with Phantoms

While the median is robust, it is also rigid. To introduce fairness or satisfy specific social objectives, researchers use Generalized Median Mechanisms. These mechanisms augment the set of real agent reports with "phantom points"—fixed, imaginary locations chosen by the designer.

As Haris Aziz and Barton E. Lee demonstrate in their work on Strategyproof and Proportionally Fair Facility Location, phantoms act as anchors. By calculating the median of the combined set (agents + phantoms), the designer can ensure the facility doesn't drift too far into extreme territory, even if the agents are clustered at one end. This structure maintains strategyproofness because the underlying rule is still a median; the phantoms simply act as "votes" that no individual agent can change.

Decoupling Preferences from Locations

The problem becomes significantly harder when facilities are heterogeneous—for example, deciding where to put both a library and a gym when agents have different preferences for each.

A breakthrough by Minming Li, Pinyan Lu, and Jialin Zhang in Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio introduced the concept of decoupling. Instead of letting agents' preferences directly dictate the coordinates, the mechanism first generates a set of "candidate" locations based solely on public or aggregate location data. Because the available sites are fixed before preferences are even considered, agents cannot manipulate the where by lying about the what.

Similarly, in Facility Location with Public Locations and Private Doubly-Peaked Costs, Richard Cole and Pranav Jangir use a "Median-Plus" approach. They anchor the facility on the median of public residential addresses and then allow agents to "bid" their preferred distance. By projecting these private bids toward the public anchor, the mechanism ensures that an agent's influence is strictly limited by their physical position, preventing strategic over-reporting.

Pushing to the Boundaries

Not all facilities are desirable. For "obnoxious" facilities like landfills, agents want the resource as far away as possible. In these cases, the median is no longer effective. Instead, mechanisms often shift to boundary-based allocation.

Paolo Serafino and Carmine Ventre show that placing resources at the extreme edges of the agent population can ensure truthfulness. If a facility is already at the furthest possible boundary, an agent cannot move it further away by misreporting their location. Dimitris Fotakis and Christos Tzamos proved that for certain multi-facility games, this "two-extremes" approach is essentially the only way to maintain both anonymity and strategyproofness.

Integrating Predictions and Outliers

Modern research is now looking at how to integrate external data, such as machine-learned predictions of the optimal location, without sacrificing these hard-won guarantees. Eduard Eiben and Argyrios Deligkas explore this in Mechanism Design with Outliers and Predictions.

The strategy here is often a "projection" rule: the mechanism takes the external prediction but "clips" it so it falls within the interval defined by the agents' reported locations. As Hau Chan and Chenhao Wang describe in Strategyproof Mechanisms for Facility Location with Prediction, this creates a safety net. If the prediction is accurate, the mechanism performs exceptionally well; if the prediction is biased or manipulated, the boundary agents act as a physical constraint that prevents the outcome from becoming disastrously inefficient.

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_spatial_allocation_without_0b15f38e,
  title = {Strategyproof Spatial Allocation without Monetary Incentives},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strategyproof-spatial-allocation-without-monetary-incentives/rdr_0b15f38e67b447048d11d03ac2219950},
  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_spatial_allocation_without_0b15f38e_v1,
  title = {Strategyproof Spatial Allocation without Monetary Incentives},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strategyproof-spatial-allocation-without-monetary-incentives/rdr_0b15f38e67b447048d11d03ac2219950/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}