Imagine a city planning committee trying to decide where to place a new public facility—such as a school, a library, or a wireless base station—along a main street. The committee relies on residents to report their locations. However, residents are selfish: each wants the facility as close to their own front door as possible. If the committee decides to place the facility at the average (mean) of all reported locations, a single resident living on the far right could drastically exaggerate their location, dragging the average toward themselves.
When monetary incentives or penalties are unavailable—a framework known as approximate mechanism design without money, surveyed comprehensively by Chan et al.—designers must find alternative ways to prevent such manipulation. The most robust solution to this problem relies on the mathematical properties of the median.
Why the Median Resists Manipulation
To understand why median-based selection works, consider its stability. If a facility is placed at the median of all reported agent positions, no individual agent can unilaterally shift the facility closer to themselves by lying.
If an agent is located to the left of the median, reporting an even further left position does not change the median index or its value. Conversely, if they report a position to the right, they can only shift the median to the right if their report crosses the current median. However, doing so pulls the facility away from their true location, worsening their own outcome. Thus, truth-telling is a dominant strategy. As Jiao et al. demonstrate in spatial crowdsourcing scenarios, this property ensures that infrastructure deployment remains strategyproof even when participants have strong incentives to minimize their own power consumption or travel distance.
The Power of Phantoms: Generalized Medians
While the simple median ensures honesty, it limits the designer's ability to optimize for other social objectives or physical constraints. To introduce flexibility without sacrificing strategyproofness, designers employ generalized median mechanisms.
This approach introduces fixed, auxiliary points—often called "phantom points"—into the calculation. The mechanism computes the median of the combined set of true agent reports and these static phantoms. The phantoms act as structural anchors:
- They allow the designer to bias the location toward a desirable central point or distribute resources more evenly.
- Because the phantoms are fixed and independent of agent reports, the underlying incentive structure is preserved. Agents still cannot manipulate the outcome to their advantage.
The theoretical necessity of this framework is profound. Aziz et al. proved that when capacity constraints limit how many users a facility can serve, generalized median mechanisms are the only deterministic mechanisms that guarantee strategyproofness. Furthermore, Lam et al. showed that when a facility's operational efficiency scales dynamically with its physical position, designers can mathematically derive phantom points directly from the efficiency scaling function to maintain system-wide stability.
Scaling to Order Statistics and Capacity Constraints
As spatial allocation problems grow more complex—such as managing strict capacity limits or covering entire intervals rather than single points—the pure median must be generalized to broader order statistics (selecting the $k$-th ranked position).
In the Truthful Interval Covering (TIC) problem introduced by Deligkas et al., a central authority must place a continuous service window to satisfy agents who have private, demanded intervals. The authors demonstrate that anchoring the start of this service window to a specific order statistic of the reported starting positions prevents manipulation. Because the selection rule depends strictly on the sorted rank rather than the reported lengths of the intervals, small individual shifts fail to alter the chosen rank threshold.
This rank-based logic is vital when facilities have capacity constraints. When a facility can only serve a maximum number of individuals, agents must compete to be among the closest to it. Aziz et al. and Auricchio et al. show that group strategyproofness—where even coalitions of agents cannot successfully collude—can be preserved by linking facility placement to specific capacity-defined indices within the agent distribution. Similarly, Deligkas et al. demonstrate that in distributed environments where agents are pre-grouped into local districts, rank-based rules allow robust, truthful collective decisions to be made locally without requiring global oversight of every individual's exact coordinate.
Hierarchies, Weights, and Strategic Intermediaries
In large-scale systems, a central authority rarely interacts with citizens directly; instead, data is filtered through representatives or districts. Filos-Ratsikas et al. show that median-based strategies scale effectively to these distributed settings, balancing local district efficiency with global strategyproofness.
However, if the intermediaries themselves act strategically to favor their own local populations, simple aggregation fails. To counter this, Tennenholtz et al. introduced weighted median aggregation. By taking the local medians reported by intermediaries and weighting them by the population sizes they represent, the central authority can bound the social cost to a tight factor of 3. This achieves the theoretical limit for any deterministic mechanism operating under strategic intermediaries.
[Strategic Agents] ──> [Local Median] ──> [Weighted Median Aggregation] ──> [Final Placement]
▲
│
[Population Weights]
Weighted medians also prove essential when agents have fractional preferences across multiple related facilities (such as a hospital and a local clinic), as shown by Fong et al., ensuring that physical coordinate misrepresentation remains unprofitable.
Extreme Anchoring and Boundary Constraints
When multiple facilities must be placed, or when resources are highly constrained, median-based selection is sometimes swapped for an alternative strategyproof paradigm: boundary-constrained placement or extreme-agent anchoring.
Instead of looking at the center, these mechanisms anchor resource allocation directly to the outermost agents. Serafino et al. demonstrate that by placing heterogeneous facilities at the extreme edges of the requesting population, any movement by an agent within those bounds fails to shift the facility locations in a way that benefits them. For the 2-facility location game on a line, Fotakis et al. provide a complete characterization proving that any deterministic strategyproof mechanism with a bounded approximation ratio must either be dictatorial or place facilities at these two extremes.
This boundary logic also applies when a facility is already physically fixed, and the mechanism must determine a shuttle service or accessibility range. Chan et al. show that anchoring the service range to the position of the most distant agent prevents group collusion. Any collective report that shifts the range to benefit some members would necessarily disadvantage the anchor agent, thereby maintaining strong group strategyproofness.
Finally, when the mechanism must operate under extreme constraints—such as deciding which single facility type to build with limited resources—Deligkas et al. show that decoupling the placement from individual agent coordinates entirely (e.g., placing it at the geometric center of the available space) can guarantee strategyproofness. When discrete jumps or switching points are required in multi-facility environments, Lu et al. and Xu et al. emphasize that strict, deterministic tie-breaking protocols—such as consistently selecting the leftmost optimal solution—are vital to ensure that strategic agents cannot manipulate the final configuration.
Key Foundational Work
Mechanism Design with Strategic Mediators (2015) — contributed 2 concept elements to this direction.
Truthful Mechanisms without Money for Non-Utilitarian Heterogeneous Facility Location (2015) — contributed 1 concept elements to this direction.
Winner-imposing strategyproof mechanisms for multiple Facility Location games (2013) — contributed 1 concept elements to this direction.