A Randomized $\frac32$-Approximation for Strategic Facility Location on a Circle

1 Introduction

• Randomized mechanisms are studied because deterministic strategyproof and onto mechanisms on circles are dictatorial and can have approximation ratio n −1.Earlier work showed that the equal-probability RD–PCD mixture achieved a 7/4 ratio for odd n ≥3.Source: §1 · p. 2

1.1 Our Results

• The MRP mechanism achieves a 3/2 approximation for every n ≥3, improving the 7/4 guarantee that applied only to odd n.The paper also establishes a computer-assisted lower bound of 1.088187… for randomized strategyproof mechanisms, improving the previous 1.0456 lower bound.Source: §1.1 · pp. 2, 4
• For even n, MRP mixes RD with EPCD, which deletes one agent uniformly at random before applying PCD to the remaining odd-agent profile.For odd n, it mixes RD and PCD with equal probability, the mechanism studied by Rogowski and Dziubiński.Source: §1.1 · p. 2
• The analysis improves the earlier 7/4 bound by charging cut-metric overestimation against distance savings from the PCD component.The even-agent proof controls in expectation how random deletion changes relevant arcs and crossing terms.Source: §1.1 · p. 4

1.2 Other Related Work

• Related work also studies strategyproof-mechanism characterizations and utilitarian facility location across lines, networks, Euclidean spaces, and multiple-facility settings.The introduction also cites applications including public-facility siting, political representation, and coordinating recurring activities,,.Source: §1 · p. 1, §1.2 · pp. 4–5

• The model places agents on a unit circle, measures facility cost by total distance, and compares expected mechanism cost with the profile optimum.Source: §2 · pp. 5–6
• A mechanism maps reported profiles to distributions over locations; strategyproofness requires truthful reporting to minimize each agent’s expected distance.Source: §2 · p. 5
• RD chooses a uniformly random agent’s report, while odd-n PCD selects ordered copies with probability equal to their opposing gaps.Source: §2 · p. 6
• For even n≥4, EPCD deletes one uniformly random agent before running PCD on the survivors and is strategyproof, anonymous, neutral, and peaks-only.Source: §2 · p. 6
• MRP mixes RD equally with PCD for odd n and EPCD for even n; fixed-probability mixing preserves strategyproofness and the listed symmetry properties.Source: §2 · p. 7

3 Upper Bound

• For every n ≥ 3, MRP is strategyproof, anonymous, neutral, and peaks-only, and achieves an approximation ratio at most 3/2.The result applies to both odd and even numbers of agents.Source: §3 · p. 7
• MRP’s approximation analysis is tight: for arbitrarily large odd and even n, instances make its ratio approach 3/2.Contrasting examples show RD can be a 2-approximation while PCD or EPCD is optimal, and vice versa, motivating the equal-probability mixture.Source: §3 · pp. 7–8

3.1 Setup

• The proof normalizes an optimal location to 0, cuts at its antipode, and accounts for the increased cross-side distances as crossing savings.The cut-saving identity tracks this excess for peaks-only randomized mechanisms.Source: §3.1 · pp. 9–10

3.2 Odd Number of Agents

• For odd n, CRD + CPCD ≤ 3OPT, so their equal-probability mixture achieves a 3/2 approximation by offsetting cut excess with PCD’s cut savings.The proof bounds the odd-case cut excess by PCD’s cut saving; RD’s cut saving is nonnegative.Source: §3.2 · pp. 11–12
• For odd n, the cut-excess decomposition Fodd = B − R reduces the bound to covering the bilinear term with a linear budget and crossing savings.The proof allocates parts of R to cells of B and uses crossing savings for any uncovered remainder.Source: §3.2 · p. 14
• 3/2-approximation holds for odd n: the equal-probability RD–PCD mixture has expected cost at most 3/2 OPT.The proof bounds CRD + CPCD by 3OPT, so their equal-weight expected cost is at most 3/2 OPT.Source: §3.2 · p. 16

3.3 Even Number of Agents

• 3/2-approximation follows for even n by showing EPCD crossing savings dominate the cut excess, implying CRD + CEPCD ≤ 3OPT.The even-case proof separates boundary terms, then controls the remaining interior excess with crossing savings.Source: §3.3 · pp. 17, 21
• For even n, averaging adjacent opposing gaps creates wrap-around boundary terms and splits interior contributions across neighboring cells; the proof separates harmless boundary terms before charging the remaining excess to EPCD crossing savings.The boundary reduction states that the terms involving boundary increments are non-positive, leaving only the interior part to control.Source: §3.3 · pp. 17, 21
• Lemma 8 establishes even crossing domination, which bounds the cut excess using EPCD’s cut saving.The proof concludes that F_even is at most Q_int − L_int.Source: §3.3 · pp. 23, 26
• The proof allocates linear budget to cell contributions and charges any remaining error to EPCD’s cut saving.The combined allocations use at most L_int, and the error estimates are compared with EPCD’s cut saving.Source: §3.3 · pp. 23, 25, 26
• The equal mixture of RD and EPCD has social cost at most 3/2 OPT for every normalized even-agent profile with positive OPT.Its cost is 1/2(C_RD + C_EPCD), which is at most 3/2 OPT.Source: §3.3 · p. 26

4 Lower Bound

• 1.088187... is a lower bound on the approximation ratio of every randomized strategyproof mechanism for n = 4.The construction improves the previous 1.0456 lower bound due to Meir.Source: §4 · pp. 26, 28
• Symmetry reduction and piecewise linearity make the certificate verifiable at finitely many points; its rational verification uses 489 representative profiles.The certificate has 108 nonzero social-cost weights and 700 nonzero incentive weights, with minima checked at breakpoints.Source: §4 · pp. 26, 29
• A weighted certificate combines social-cost and incentive constraints over finitely many profiles to certify an approximation lower bound.The certificate uses nonnegative weights on these inequalities and pointwise lower bounds on their weighted sum.Source: §4 · p. 27
• The same 1.088187... lower bound holds for n = 4k, by cloning each agent k times and using strategyproofness to recover a four-agent mechanism.Social cost and its optimum both scale by k, so the induced mechanism's approximation ratio is no larger than the original's.Source: §4 · p. 29

5 Conclusion

• The parity-dependent mechanism achieves an approximation ratio of 3/2 for every n ≥ 3.For odd n it mixes RD and PCD equally; for even n it mixes RD with EPCD, a random-deletion extension of PCD.Source: §5 · p. 29
• The paper establishes a 1.088187... lower bound on the approximation ratio of any randomized strategyproof mechanism.The lower-bound construction uses four agents, and larger-agent instances may yield stronger impossibility results.Source: §5 · pp. 29–30
• Closing the gap between the 1.088187... lower bound and the 3/2 upper bound remains an open question.The paper suggests that improving the upper bound below 3/2 likely requires mechanisms beyond fixed-weight RD–PCD mixtures.Source: §5 · p. 30