Mechanism Design for Facility Location Problems: A Survey

1 Introduction

• Strategyproofness protects agents from incentives to misreport, but can require suboptimal solutions, motivating approximation guarantees for the resulting efficiency loss.Here, approximation is driven primarily by strategyproofness rather than computational limits.Source: §1 · p. 2
• The survey covers strategyproof mechanisms across facility-location variants, with extra emphasis on achievements from the last half decade.It aims to provide a reference for the literature and its future challenges.Source: §1 · p. 2

1.1 The Classic Setting

• The classic model places k facilities in a metric space for n agents, usually measuring each agent’s cost to the nearest facility and optimizing social or maximum cost.Randomized mechanisms instead use expected distance as an agent’s cost.Source: §1.1 · p. 3
• The Median-point mechanism is optimal for social cost, while for maximum cost it achieves the best possible deterministic strategyproof approximation of 2.The optimal maximum-cost placement is not strategyproof in the single-facility real-line setting.Source: §1.1 · p. 4
• The LRM mechanism achieves a 3/2 approximation for maximum cost, improving on the deterministic 2-approximation barrier.It selects the leftmost or rightmost peak with probability 1/4 each and their midpoint with probability 1/2.Source: §1.1 · p. 4

2.1 Locating a Single Facility

• The Median-point mechanism is optimal for social cost and best possible at 2-approximation for maximum cost, while randomized LRM is best possible at 3/2.These results settle the single-facility problem on the line.Source: §2.1 · p. 5
• Alon et al. showed that on general graphs a randomized strategyproof mechanism achieves approximation ratio 2 −2/n, while every deterministic social-cost mechanism on circle networks has ratio Ω(n).Source: §2.1 · p. 5

2.2 Locating Two Facilities

• For two facilities on the line, the extremes mechanism is group strategyproof with social-cost ratio n − 2, which is tight; randomized strategyproof mechanisms achieve ratio 4.The extremes mechanism is also best possible at 2-approximation for maximum cost, with improved bounds possible through randomization.Source: §2.2 · p. 5

2.3 Beyond Two Facilities

• For k facilities on the line, Equal Cost achieves ratios n for social cost and 2 for maximum cost, even with concave cost functions; anonymous deterministic strategyproof mechanisms for k ≤ 3 have no bounded social-cost ratio.Other work gives linear upper and constant lower bounds for n − 1 facilities in general metrics and trees, and impossibility results in 2D Euclidean and Manhattan spaces [81].Source: §2.3 · p. 6

3.1 Obnoxious Facility Location

• For obnoxious facilities, agents prefer greater distance from their specified locations; network mechanisms use majority votes between two prespecified locations.Other work studies line metrics and characterizes group-strategyproof mechanisms in some special cases.Source: §3.1 · p. 6

3.2 Heterogeneous Facility Location

• In dual preferences, agents may regard a facility as desirable or undesirable, and unknown preferences and locations admit a best-possible 3-approximate deterministic group-strategyproof mechanism.With known locations, an optimal strategyproof mechanism for social welfare is possible.Source: §3.2 · p. 7
• With optional preferences, agents may be interested in either or both of two facilities; strategyproof mechanisms for a single facility can approximate total utility under three public/private information settings [24].For two facilities, work also establishes deterministic strategyproof approximation bounds under sum, min, and max cost functions.Source: §3.2 · p. 7
• For k facilities, heterogeneous preferences let agents prefer proximity, distance, or indifference separately for each facility, with results focused mainly on egalitarian welfare.The model combines and extends dual- and optional-preference models, with some social-welfare results as well.Source: §3.2 · p. 7
• With fractional preferences summing to 1, strategyproof mechanisms achieve maximum social welfare when locations are known, while deterministic mechanisms achieve a 4-approximation when locations and preferences are private.When preferences are known, a 2-approximation is possible.Source: §3.2 · p. 7

Multiple locations

• In multi-location models, agents may report multiple locations, hide or replicate locations, or report strategically through mediators [9] [84].The models vary in cost definition and in the information agents report about location importance.Source: §4 · p. 8

False-name manipulations

• False-name-proofness requires robustness to both ordinary and fake-identity manipulation; the leftmost-agent mechanism is best possible for single-facility real-line social and maximum cost [8].For two facilities on a line, the two-extreme mechanism is the best deterministic false-name-proof mechanism, while randomization improves approximations.Source: §4 · p. 8

Mechanism design with verification

• Winner-imposing verification can penalize possibly deceitful agents by restricting their interaction with outcomes; an extension of the Proportional Mechanism achieves a 4k-approximation for k facilities on the line.This mechanism is strategyproof.Source: §4 · p. 8

Limited locations

• When feasible locations are limited, a deterministic 3-approximation and randomized 2-approximation for social cost are achievable on the line, with matching lower bounds [30].Related models study maximum cost, two facilities, and feasible subintervals [80].Source: §5 · p. 9

Distance constraints

• Distance-constrained two-facility models include maximum-separation requirements, linear penalties for violations, minimum-separation requirements, and exact-separation requirements [17].The maximum-distance model includes one desired and one undesired facility.Source: §5 · p. 9

Capacitated facilities

• Capacitated facility location has a complete strategyproof-mechanism characterization for one facility on the line, and the two-facility Extended Endpoint Mechanism achieves a tight ratio [6].The two-facility ratio matches a lower bound established in earlier work [6].Source: §5 · p. 9

Other social objectives

• Alternative objectives include Lp-norm costs, squared costs, maximum envy, envy ratio, and happiness-factor optimization.The survey notes that the envy approximations in are additive, unlike most results it covers.Source: §6 · pp. 9–10

Double-peaked preferences

• Double-peaked preferences yield approximation bounds for deterministic and randomized strategyproof mechanisms, plus a characterization of neutral group-strategyproof mechanisms.Each agent has two peaks on the line, with cost increasing away from either peak.Source: §6 · p. 10

Externalities and weighted agents

• Externalities model agents’ positive or negative effects on one another, while private agent weights can be ignored by the best deterministic strategyproof mechanism.Source: §6 · p. 10

Distributed facility location

• Distributed facility location selects a site from district representatives, and the best possible strategyproof mechanism has approximation ratio 3 [35].The mechanism is oblivious to agents’ actual locations.Source: §6 · p. 10

Approximation and variance; additive approximations

• Related work studies reducing randomized-mechanism variance while preserving approximation guarantees and tight additive-approximation bounds for single-facility mechanisms [43].The latter work argues additive approximation is better suited to some situations.Source: §6 · p. 10

Shuttle facility games

• Shuttle facility games represent each agent’s location as a commuting-route interval and admit a group-strategyproof mechanism achieving optimal social welfare.Source: §6 · p. 10

Mechanisms with payments

• Monetary facility location makes facility holders strategic cost reporters; optimal uncapacitated facility-location algorithms admit truthful mechanisms.Further variants add a total-payment budget or give each agent both facility-holder and customer roles.Source: §6 · p. 10

Automated mechanism design

• Automated-mechanism work has used machine-learning and deep-learning approaches.Source: §6 · p. 10

Dynamic facility location

• Dynamic models remain open: most work assumes fixed locations, while exceptions study staged reallocation or changing populations.The authors see room for more dynamic settings in approximate mechanism design.Source: §7 · p. 11

Incomplete information

• Incomplete-information settings include unknown location distributions and interval-valued possible locations with robust mechanisms, but their effects need further study.Source: §7 · p. 11

Incentives beyond strategyproofness

• Relaxing strategyproofness to an ε-approximate form may expand mechanism design options where lower bounds constrain approximation; prior work studies related tradeoffs.Source: §7 · p. 11

Strategic games and manipulation

• Another direction allows strategic play and evaluates Nash equilibria through the Price of Anarchy; group manipulation of mechanisms also warrants study.For Quantile, group manipulation has been formulated as cone programs for single-facility and multidimensional spaces.Source: §7 · p. 11

• Facility location is a fundamental example of approximate mechanism design and a vibrant research area in artificial intelligence, with further challenges ahead.The survey aims to serve as a reference for researchers identifying challenges and questions.Source: §8 · p. 12