On Voting and Facility Location

1 Introduction

• The paper frames candidate selection as voters possibly misrepresenting preferences over fixed candidates, including policies and other nonphysical choices.The motivation includes settings where money is restricted, despite VCG achieving optimal social cost when payments are allowed.Source: §1 · pp. 1–2

1.1 Our Contributions

• On the line, deterministic truthful mechanisms have a tight approximation factor of 3, while randomized mechanisms have a tight factor of 2.The deterministic bound is matched by the median mechanism; the randomized bound is achieved by the spike mechanism.Source: §1 · p. 2, §1.1 · pp. 3–4

1 Introduction

• Voting, ranking, and location mechanisms differ in how much information agents submit, trading input simplicity against accuracy and potential privacy or cognitive costs.Voting elicits a favorite candidate, ranking elicits ordinal preferences, and location elicits an exact position.Source: §1 · pp. 2–3

1.1 Our Contributions

• A reduction framework compares the three mechanism classes, establishing containment relationships and equivalence between TIE location and voting mechanisms when there are two candidates.The contribution presents these results as a step toward characterizing truthful mechanisms.Source: §1.1 · p. 3
• On the line, the universally truthful spike mechanism selects votes using a probability distribution designed to handle misreports and achieves ratio 2, matching the randomized lower bound.The lower bound applies even to location mechanisms, and the resulting tight ratio also holds for TIE voting, ranking, and location mechanisms.Source: §1.1 · p. 3
• For general metric spaces, random dictator has an upper bound of 3; the paper also gives lower bounds for voting mechanisms in ℜd and ranking mechanisms in ℜ2 and higher dimensions.The cited voting lower-bound expression is incomplete in the supplied passage; the ranking lower bound is 7/3.Source: §1.1 · p. 3

1.2 Related Work

• Prior distortion work attributes imperfection to limited information, while this paper’s approximation ratio also reflects incentive constraints and can quantify both costs.Related work covers social-choice mechanisms and facility-location models, but the paper says no formal framework had assessed relationships among the three mechanism types.Source: §1.2 · pp. 5–6

2 Model

• Each agent and candidate occupies a point in a metric space, and on the line their locations are numbered in ascending order.The candidate set is fixed and publicly known.Source: §2 · p. 7
• Voting mechanisms accept a favorite-candidate vote, ranking mechanisms accept ordinal preferences, and location mechanisms accept reported locations.On the line, voting zones are separated by midpoint borders; ranking zones distinguish full candidate orderings.Source: §2 · pp. 7, 9
• A truthful report conveys an agent’s real preferences, and truthfulness requires that truthful reporting cannot leave an agent worse off regardless of others’ actions.For voting, truthful reports are the candidate or candidates closest to the agent’s location.Source: §2 · p. 8
• Social cost sums agents’ costs, while a mechanism’s approximation ratio compares its worst truthful-profile cost with the optimal candidate’s cost.When multiple candidates are optimal, the leftmost is designated Copt.Source: §2 · p. 8
• A weighted percentile voting mechanism chooses the i’th percentile vote with a predetermined probability that does not depend on the action profile.On the line, votes have an inherent order that makes percentiles available.Source: §2 · p. 9

3 Classes of Mechanisms

• The reduction framework shows that every deterministic truthful ranking mechanism can be reproduced by a deterministic truthful voting mechanism, despite ranking normally offering richer input.The theorem also states that truthfulness prevents mechanisms from using location information beyond rankings; strict-containment examples illustrate the expressiveness of additional information.Source: §3 · pp. 9–10
• Deterministic truthful ranking mechanisms strictly contain voting mechanisms, while deterministic truthful location and ranking mechanisms are equivalent.The hierarchy is defined through whether mechanisms can be reduced to mechanisms in another class.Source: §3 · p. 10
• For truthful-in-expectation mechanisms, ranking strictly contains voting, location strictly contains ranking, and voting strictly contains universally truthful voting.These relations distinguish general truthful-in-expectation randomization from universal truthfulness.Source: §3 · p. 10
• With two candidates, truthful-in-expectation location and voting mechanisms are equivalent.This is a special-case equivalence within the randomized hierarchy.Source: §3 · p. 10

4 Spike Mechanism

• Unlike the median’s bad central-agent case and random dictator’s bad extreme-agent case, spike is designed to resist bad instances for any agent.The section focuses on voting mechanisms on the real line.Source: §4 · pp. 10–11
• The spike distribution is symmetric, and its outcome depends on vote counts and candidate order rather than distances between candidates.The mechanism’s cumulative count tracks votes for candidates no farther right than a given candidate.Source: §4 · p. 11
• A tight profile moves non-border agents as close as possible to Copt within their voting zones; left-compression shifts agents on the leftmost border rightward when the neighboring border remains left of Copt.Right-compression is defined symmetrically, and the proof uses these transformations to bound the ratio.Source: §4 · pp. 11–12
• Spike is a weighted percentile voting mechanism, which makes it universally truthful.Weighted percentile voting assigns predetermined probabilities to percentile votes.Source: §4 · pp. 11–12
• 2 is the spike mechanism’s approximation ratio on the line, and the mechanism is universally truthful.The proof reduces arbitrary profiles to tight and compressed profiles, ending with at most three active candidates.Source: §4 · pp. 13–14
• The proof uses backwards induction: tighten a profile, compress it on both sides until at most three candidates are active, then apply the ratio-2 base case.The lemmas preserve the upper bound when reversing the compression steps.Source: §4 · pp. 13–14

5.1 Lower Bounds

• 2 is the tight approximation ratio on the line for truthful-in-expectation mechanisms, and spike is optimal within that class.The lower bound holds even for location mechanisms; it therefore applies to truthful-in-expectation ranking and voting mechanisms as well.Source: §5.1 · pp. 15–16
• At a border between ranking zones, a voter’s expected cost is unchanged between the two corresponding truthful reports; the same property holds for voting mechanisms.The lower-bound arguments use this invariance when changing reports.Source: §5.1 · p. 15
• 3 − 2/(d+1) is a lower bound for truthful-in-expectation voting mechanisms in d-dimensional real space.The bound uses d + 1 candidates on a regular simplex.Source: §5.1 · p. 15
• 7/3 is a lower bound for truthful-in-expectation ranking mechanisms in ℜ2, and the same bound holds in ℜd for d > 2.The proof’s final instance yields a ratio of at least 7/3.Source: §5.1 · pp. 15, 17
• 2 is a lower bound for randomized ranking mechanisms on the line even without truthfulness requirements.Source: §5.1 · pp. 15, 18

5.2 Upper Bound

• Random dictator achieves an approximation ratio of exactly 3 on any metric space, but is not group-strategyproof in the candidate model.In the continuous model, random dictator achieves an approximation ratio of 2.Source: §5.2 · p. 18

6.2 Upper Bound

• The candidate-constrained median result differs from the continuous line model, where choosing the median agent’s location is truthful and optimal.Source: §6.1 · p. 18, §6.2 · p. 19

6.1 Lower Bound

• No deterministic truthful location, ranking, or voting mechanism can achieve an approximation ratio below 3, even on the line.The lower bound follows from profiles with the same votes whose mechanism outcome must therefore be identical, while one profile yields a ratio tending to 3.Source: §6.1 · pp. 18–19

6.2 Upper Bound

• The median voting mechanism is truthful and achieves a 3-approximation of optimal social cost on the line.It chooses the median vote.Source: §6.2 · p. 19

• Some bounds remain open, and future directions include electing several candidates, obnoxious facility location, and group-strategyproofness bounds.The authors note that this setting has been barely investigated.Source: §7 · p. 19

A.1 Missing Proofs from Section 3

• A consistent reduction preserves the candidate-outcome distribution while translating action profiles; mechanisms with finer-grained inputs can simulate mechanisms with coarser inputs.For example, a ranking mechanism can simulate a voting mechanism by using only each ranking’s top candidate.Source: §A.1 · p. 22
• Truthful mechanisms transfer from a coarser input type to a finer one, and the same reduction result holds for truthfulness in expectation.The finer-type mechanism can ignore information beyond the coarser report; any outcome-changing report that could defeat truthfulness would also contradict truthfulness of the original mechanism.Source: §A.1 · p. 23
• Deterministic ranking mechanisms strictly contain deterministic voting mechanisms: every truthful voting mechanism reduces to a ranking mechanism, but some truthful ranking mechanism does not reduce to voting.The witness behaves differently on ranking profiles that any consistent mapping sends to the same vote profile.Source: §A.1 · pp. 23–24
• Deterministic location mechanisms and deterministic ranking mechanisms are equivalent under reduction.The proof constructs border-free and then within-zone location profiles preserving the chosen candidate, enabling a ranking mechanism to simulate the location mechanism.Source: §A.1 · pp. 24–26
• Truthful-in-expectation ranking mechanisms strictly contain truthful-in-expectation voting mechanisms.The proof carries over the deterministic ranking witness and uses the truthful-in-expectation reduction result for the reverse inclusion.Source: §A.1 · p. 26
• Truthful-in-expectation randomized location mechanisms strictly contain truthful-in-expectation randomized ranking mechanisms.A three-candidate location mechanism is given that treats two points with the same ranking differently, preventing reduction to a ranking mechanism.Source: §A.1 · p. 26
• Truthful-in-expectation randomized voting mechanisms strictly contain universally truthful randomized voting mechanisms.The witness selects an agent uniformly and chooses that agent’s reported candidate with probability 0.9 and the other candidate with probability 0.1.Source: §A.1 · pp. 27–28
• With two candidates, truthful-in-expectation randomized location and voting mechanisms are equivalent under reduction.The proof establishes the reverse direction by reducing any such location mechanism to a truthful-in-expectation voting mechanism.Source: §A.1 · p. 28
• Moving each non-border agent to their favorite candidate location preserves the mechanism’s outcome, as a hybrid argument would otherwise give an agent an incentive to misreport.The proof compares profiles differing in one agent’s location and uses truthfulness to rule out a change in the probability of selecting C1.Source: §A.1 · p. 28
• Mapping each vote for Ci to location yi defines a consistent reduction that simulates the location mechanism; away from borders, the inverse location-to-vote mapping is unique.For agents on borders, the proof requires a consistent map that breaks ties in the same manner as the mechanism.Source: §A.1 · p. 28
• For profiles with n1 agents at y1, n2 on the border, and n3 at y2, the C1-selection probabilities satisfy p3 ≤ p1 ≤ p2 when border agents move to either candidate location.The proof uses truthfulness to show that moving border agents one by one to y1 cannot decrease the probability of C1, and symmetrically moving them to y2 cannot increase it.Source: §A.1 · p. 29
• Choosing a consistent border tie-breaking map with probability q of assigning border agents to C1 yields p2 · q + p3 · (1 − q) = p1, preserving the mechanism’s outcome.The proof selects q between 0 and 1 to match p1.Source: §A.1 · p. 29

A.2 Missing Proofs from Section 4

• Moving agents toward Copt preserves the optimal candidate and the outcome probabilities, allowing the proof to assess the ratio on the modified profile.The proof also identifies bounding the mechanism-cost increase by twice the optimal-cost decrease as sufficient for its comparison.Source: §A.2 · pp. 30–31
• The spike mechanism’s approximation ratio is at most 2 when the median agent is at the center, and the proof separately establishes the bound for the other case.The other case places the median agent at bL; the case with the median at bC is identical by symmetry.Source: §A.2 · pp. 33–34
• For a WPV mechanism, a border agent’s vote for the nearer of two adjacent candidates has social cost no greater than a vote for the farther one.The stated lemma assumes the two candidates lie on the same side of the optimal candidate.Source: §A.2 · p. 35

A.3 Missing Proofs from Section 5

• In the contradiction proof, an agent in ranking zone Rj at distance ε < δ from xl has an incentive to misreport.The argument uses the stated inequalities to reach a contradiction.Source: §A.3 · p. 35
• With two agents and two candidates, any mechanism decision incurs an approximation ratio of at least 2 on one of two truthful voting profiles.The profiles are x = (−1, ε) and x′ = (−ε, 1).Source: §A.3 · p. 36
• The constructed profile has SC(C1, x) = 1+ε = SC(OPT, x), while SC(C2, x) = 2(n−1)+(1−ε).The passages then set up an approximation-ratio calculation for this profile.Source: §A.3 · p. 36
• The analyzed mechanism's social cost is bounded above by 3 · SC(OPT, x), with the proof invoking the triangle inequality.The final inequality also uses that no candidate is closer to an agent than y(ai) is.Source: §A.3 · p. 37
• Random dictator is universally truthful as a WPV mechanism, but it is not group-strategyproof in the candidate model.In the example, truthful reports give each agent expected cost 1, whereas jointly reporting C2 makes C2 certain and gives each cost 0.51.Source: §A.3 · pp. 36–37

A.4 Missing Proofs from Section 6

• The median mechanism is truthful because misreporting either leaves the selected location unchanged or moves it farther from the agent.An agent at the median location also cannot benefit: the possible change is selection of a different location.Source: §A.4 · p. 38
• The median mechanism chooses the candidate corresponding to the middle-ranked favorite vote after ordering votes by candidate location.The proof orders the favorite candidates by their locations before selecting the median vote.Source: §A.4 · p. 38
• The approximation analysis bounds α by γ and β by α + γ + δ, using distance comparisons and the triangle inequality.The proof also justifies one inequality by summing at least as many non-negative terms.Source: §A.4 · p. 38