On the Power of Deterministic Mechanisms for Facility Location Games

Previous Work

• Earlier work established TWO-EXTREMES with ratio n−2 and a deterministic lower bound of (n−1)/2; prior single-facility characterizations include generalized median voter schemes.Other Social Choice efficiency conditions had no immediate implications for social-cost approximability, limiting their technical use here.Source: §1 · pp. 2, 4

Motivation and Contribution

• The paper targets open questions on the optimal deterministic ratio for two facilities on the line and bounded-ratio existence for K ≥3 or broader metric spaces.It focuses on characterizing nice mechanisms: deterministic, strategyproof mechanisms with bounded approximation, rather than seeking stronger lower bounds from selected instances.Source: §1 · p. 3
• For 2-Facility Location on the line with n ≥5, every nice mechanism either has a unique dictator or always places facilities at the two extremes; the best deterministic approximation ratio is n−2.TWO-EXTREMES is the only anonymous nice mechanism in this setting.Source: §1 · p. 3
• The characterization proceeds through three-agent, three-location, and general instances, using well-separated cases, threshold restrictions, and partial-dictator analysis.For three agents, thresholds reduce to two extremes, yielding either facilities at both extremes or a partial dictator; a partial dictator receives a facility for all but possibly one permutation.Source: §1 · p. 3
• The proof introduces well-separated instances, reductions to a single-facility game between nearby agents, threshold arguments, and coalition moves that preserve outcomes.These tools are presented as offering insights into nice mechanisms for K-Facility Location beyond the main characterization.Source: §1 · p. 4
• For K ≥3, no deterministic anonymous strategyproof mechanism has a bounded approximation ratio on the line, even for well-separated instances with K+1 agents.For 2 facilities in more general metrics, no deterministic strategyproof mechanism has a bounded ratio, even on simple three-agent star instances.Source: §1 · p. 4

2 Notation, Definitions, and Preliminaries

• Unless stated otherwise, K-Facility Location means placing K facilities on the real line; an instance is a profile of n agents’ locations, and a mechanism maps it to ordered facility locations.An anonymous mechanism gives the same outcome after any permutation of agent identities.Source: §2 · p. 5
• A nice mechanism is deterministic, strategyproof, and has a bounded approximation ratio; strategyproofness means no agent benefits by misreporting her location.The social cost sums each agent’s distance to the nearest facility, while the approximation ratio compares that cost with the optimum.Source: §2 · pp. 5–6
• In a well-separated (K+1)-agent instance, one consecutive pair is closer than 1/ρ times every other consecutive gap, so a ρ-approximate mechanism serves that pair together.Nice mechanisms are unanimous on instances with K distinct agent locations, and image-set holes must be bounded.Source: §2 · p. 6

2.1 Useful Properties

• For K+1 distinct locations ordered on the line, the leftmost facility is no farther right than the second location, and the rightmost is no farther left than the Kth.The bounds follow from strategyproofness together with the bounded approximation ratio.Source: §2.1 · p. 6
• In a well-separated instance whose nearby pair is at the right end, the rightmost facility lies between the pair’s locations.If it begins at either nearby agent’s location, pushing the pair outward while preserving separation keeps that facility with the same agent’s location.Source: §2.1 · p. 6

• For n ≥ 5, every nice mechanism either always places facilities at the instance extremes or has a unique dictator whose location receives a facility.The characterization applies to all instances of 2-Facility Location on the line.Source: §3 · p. 7
• For n ≥ 5, TWO-EXTREMES is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio.It places facilities at the leftmost and rightmost locations.Source: §3 · p. 7
• The deterministic strategyproof approximation ratio is at least n −2, and TWO-EXTREMES achieves n −2, making the bound optimal.Source: §3 · p. 7
• With three agents, a nice mechanism either places facilities at the extremes or has a partial dictator, allocated a facility for all but at most one agent ordering.Theorem 3.2 further specifies that at most two permutations sharing a middle agent can retain the median; all other orderings force the extremes.Source: §3 · p. 7
• The three-agent proof extends ideas from and makes novel use of locality and the image sets of nice mechanisms.Source: §3 · p. 7
• For three agents, COMBINED switches between TWO-EXTREMES and DICTATORIAL by comparing two agents’ locations, and achieves approximation ratio 2.It is strategyproof and admits a partial dictator.Source: §3 · p. 8
• The proof extends the three-agent characterization to three-location instances, rules out partial dictatorship there for n ≥ 5, then uses induction to cover general instances.Source: §3 · p. 8

4.1 Outline of the Proof

• The left- and right-side thresholds reduce to the isolated agent’s location or the corresponding infinite endpoint; every nice mechanism either places facilities at both extremes or has a unique partial dictator.The thresholds depend only on the identity of the leftmost or rightmost agent, not their location.Source: §4.1 · p. 9

4.2 Well-Separated Instances

• On well-separated profiles, the isolated agent receives one facility, while a unique threshold and preferred agent determine the other facility through a generalized median voter scheme.For a left-well-separated profile, the other facility is allocated among the two nearby agents; the right-well-separated case is symmetric.Source: §4.2 · pp. 10–12

4.3 General Instances and the Range of the Threshold p

• On general profiles, if the leftmost agent’s threshold rule specifies preferred agent j, then j receives a facility when xj ≥ p; symmetrically, j receives one when xj ≤ p if that agent is rightmost.These conditions extend the partial-dictator behavior beyond well-separated instances.Source: §4.3 · p. 13
• If the leftmost agent’s threshold is p and the other agents lie between that agent and p, the right facility is at the rightmost agent; the symmetric rule places the left facility at the leftmost agent.These rules apply when the relevant extreme agent has the corresponding threshold at the other extreme.Source: §4.3 · pp. 13–14
• When the rightmost agent lies more than ρ(p − xi) beyond p, the preferred agent of a left-side agent is allocated a facility.For χ(i, a) = (j, p), this applies to instances with a = xi < xj < xk and xk − p > ρ(p − xi).Source: §4.3 · p. 14
• For every agent and location, the left threshold is either that location or ↑, and symmetrically the right threshold is either that location or ↓.The proof rules out an interior threshold by constructing well-separated instances whose implied facility placement violates the mechanism’s bounded approximation ratio.Source: §4.3 · p. 14

4.4 On the Existence of a Partial Dictator

• On well-separated instances, a facility at the middle agent identifies that agent as an endpoint’s preferred agent; this identity holds across locations and for the third agent’s opposite-side preference.The proposition links facility placement to preference, while Lemmas 4.7 and 4.8 establish that the preferred identity persists across locations and transfers to the third agent.Source: §4.4 · pp. 15–16
• If an agent is imposed as a partial dictator, that agent’s left threshold is ↑ and right threshold is ↓ at every location.The lemma’s proof also establishes that the agent’s identity as preferred persists across locations for the imposing agent and the third agent.Source: §4.4 · p. 16
• Either every instance places facilities at its two extremes, or a middle agent is served in one ordering, with the other orderings governed by a partial-dictator case or extreme placement.When a middle agent is served for all instances with one ordering, it is also served for all instances with the reverse ordering or the facilities are always at the extremes; remaining instances use the extremes.Source: §4.4 · p. 17

Coalition-transfer argument

• The proof uses partial group strategyproofness to move agents between coalitions while retaining a facility at the middle location.This transfer argument supports the extension of the three-location results across coalition partitions.Source: §5 · pp. 18–19

Corollary 5.1

• For any coalition ordering other than at most two permitted permutations, the mechanism places facilities at the two extreme locations.In each permitted permutation, a facility is placed at the middle coalition’s location.Source: §5 · p. 18

Lemma 5.1

• If a middle coalition of size at most n−3 receives a facility, every coalition containing it is a dictator for 3-location instances.A dictator coalition’s location receives a facility across the relevant partitions.Source: §5 · p. 18

Lemma 5.2

• If the middle coalition receives a facility in an instance from I−₃(N), one unique agent in it receives a facility in every instance from I−₃(N).The proof uses bounded approximation to establish uniqueness.Source: §5 · pp. 19–20

Lemma 5.3

• If all instances in I−₃(N) place facilities at the extremes, a non-extreme outcome in I+₃(N) implies a dictator coalition.When the middle coalition has size n−2, the coalition formed by the right coalition and any one middle agent is a dictator.Source: §5 · pp. 20–21

Theorem 3.3

• For 3-location instances, if x1 < x2 < x3 and x2 ∈ F(x), a unique agent j ∈ N2 has yj ∈ F(y) for every instance y; otherwise F(y) = (min y, max y) for every y.Source: §5 · p. 20

Induction on distinct locations

• The proof extends Theorem 3.3 to general instances by induction on the number of distinct locations, distinguishing whether a 3-location dictator exists.When one exists, the proof shows that agent is a dictator on all instances; otherwise, it extends the extreme-facility outcome to all instances.Source: §6 · p. 21

Dictator case

• If a dictator exists on 3-location instances, the proof shows that the dictator’s location receives a facility in every general instance.It uses a location outside a hole in the agent’s image set, then moves other agents to construct a contradiction with bounded approximation.Source: §6 · pp. 21–22

No-dictator case

• Without a 3-location dictator, an interior facility can be contradicted by moving all non-extreme agents to its location.This creates a 3-location instance that would not place facilities at the two extremes.Source: §6 · p. 22
• For a facility outside the extremes, the proof chooses an instance with the fewest distinct locations and uses a hole to derive a contradiction.Moving the leftmost agents toward the second location or the hole boundary yields a smaller instance or an interior facility.Source: §6 · p. 22

Theorem 7.1

• For every K≥3 and n≥K+1, any deterministic anonymous strategyproof mechanism on the real line has an unbounded approximation ratio.The theorem’s proof focuses on K=3 and n=4 and states that the argument generalizes.Source: §7 · p. 22

Proof strategy

• The proof reduces to K=3 and n=4, then constructs a well-separated instance with a parameter λ greater than the mechanism’s approximation ratio.The construction is x=(0, λ, 3λ^2+λ, 3λ^2+λ+1); the proof considers whether the third facility is at x3 or x4.Source: §7 · p. 22

Case F3(x)=x4

• When the third facility is at x4, a hole-based strategyproofness argument yields an instance whose approximation ratio exceeds λ.The proof uses anonymity and a nearby perturbed instance to force facilities at both l and l+ε.Source: §7 · pp. 22–23

Case F3(x)=x3

• When the third facility is at x3, the symmetric hole argument likewise produces an instance whose approximation ratio exceeds λ.The proof perturbs the fourth agent’s location and uses anonymity and strategyproofness to force facilities at both r−ε and r.Source: §7 · p. 23

8 Inexistence of Nice Mechanisms for 2-Facility Location in More General Metrics

• On instances with agents on at most two branches, the facility serving at least two agents must lie on the path between them.For i-well-separated instances, the same path constraint applies even when the two nearby agents are on different branches.Source: §8 · pp. 24–25
• The proof extends the line characterization to instances on at most two branches by using the path constraint to prevent the mechanism from exploiting the third branch.The argument applies the characterization to three-agent instances and then uses partial group strategyproofness for 3-location instances.Source: §8 · p. 24
• For agents on any two fixed branches, at most two coalition orderings allow a facility at the middle coalition; all other orderings place facilities at the two extremes.The two exceptional orderings, if present, share the same middle coalition.Source: §8 · p. 25
• For three agents in S3, an i-well-separated instance has one agent served alone and the other facility serving the nearby pair.Here, the distance between the nearby agents, multiplied by 2(ρ + 1), must be less than each distance from i to either of them.Source: §8 · p. 25
• The n-agent impossibility reuses the three-agent proof by treating a coalition of n − 2 agents, including the partial dictator, as one agent.The argument invokes partial group strategyproofness to extend the three-agent steps.Source: §8 · p. 26
• For 2-Facility Location on the three-branch star S3, every deterministic strategyproof mechanism has an unbounded approximation ratio for n ≥ 3.The result is stated first for three agents and then extended to all n ≥ 3.Source: §8 · p. 26

9 Discussion and Open Problems

• Whether the techniques proving Theorem 3.2 extend Theorem 7.1’s impossibility result to non-anonymous mechanisms remains open.Source: §9 · p. 27
• For K ≥ 4, the paper asks whether deterministic imposing or randomized mechanisms can achieve bounded approximation across the stated facility-count and agent-count ranges.For 3-Facility Location on the line, it notes deterministic and randomized imposing mechanisms with approximation ratio n − 1.Source: §9 · p. 27
• The paper also raises the approximability of 2-Facility and 3-Facility Location on the line by deterministic imposing mechanisms.It notes a deterministic imposing mechanism for 2-Facility Location on the line with ratio n − 1 that escapes Theorem 3.1’s characterization.Source: §9 · p. 27

A.1 Pushing the Pair of the Rightmost Agents to the Right: The Proof of Proposition 2.3

• The setup calls an instance (i|j, k)-well-separated when xi < xj < xk and ρ(xk − xj) < xj − xi.Source: §A.1 · p. 28
• If a well-separated instance has F2(x) = xj, the appendix describes pushing agents j and k right while the rightmost facility stays at j’s location.The appendix explicitly proves the 2-facility, three-agent case and says the technical arguments generalize to K facilities with K + 1 agents.Source: §A.1 · p. 28
• Repeated applications of Proposition A.3 move agents j and k right in steps while preserving well-separation and keeping the rightmost facility with j.The induction covers successive intervals of width δ = (xk − xj)/2.Source: §A.1 · p. 29

A.2 Pushing the Pair of the Rightmost Agents to the Left: The Proof of Proposition 2.4

• The appendix explicitly proves the 2-facility, three-agent case and states that the arguments generalize to K facilities with K + 1 agents.Source: §A.2 · p. 29
• If F2(x) = xk in a well-separated instance, pushing agents j and k left while preserving well-separation keeps the rightmost facility at k.Source: §A.2 · p. 29
• An inductive application of Proposition A.7 moves the pair left in steps, retaining well-separation as the rightmost facility follows k.The construction uses steps of size δ and applies the proposition across successive intervals.Source: §A.2 · p. 30