Facility Location Mechanism Design: Breaking The Deterministic Barrier

1.1.1 Our results.

• In R^2, universally strategyproof linear-time RR-CWM achieves expected approximation ratio 4/π ≈ 1.273, below the deterministic strategyproof barrier √2 ≈ 1.414.RR-CWM randomly rotates the points, applies CWM, and rotates the result back.Source: §1.1.1 · p. 4
• In R^d, the mechanism has polynomial runtime O(d^3 + nd^2), while the cited text does not expose the expected-approximation-ratio endpoints needed to state its ratio accurately.Source: §1.1.1 · p. 4
• In the output-prediction model [Agr+22], RR-CMP improves CMP’s consistency-robustness trade-off and degrades smoothly with prediction error.The paper reports strict improvements for specified ranges of trust parameter c and prediction error η.Source: §1.1.1 · p. 4
• For MAC input predictions [BGT24], replacing CWM with RR-CWM in the “predictions-only or CWM” template improves its worst-case arm.This is the paper’s stated improvement for the input-predictions model.Source: §1.1.1 · p. 4
• Any GRD mechanism has expected approximation ratio at least 4/π in R^2 and √2 - O(1/d) in R^d; RR-CWM is weakly better than GRD in R^2.GRD mechanisms return a location reported by an agent.Source: §1.1.1 · pp. 4–5

1.1.2 Our techniques.

• RR-CWM samples a report-independent random rotation before applying CWM, preserving universal strategyproofness; in R^2, its analysis uses Eθ[||Rθv||1] = 4/π ||v||2.The planar lower-bound construction uses two large nearby clusters and a far outlier that pulls RR-CWM across rotated coordinates.Source: §1.1.2 · p. 5

1.2 Further Related Work

• Unlike fixed-rotation improvements on certain distributions, uniform random rotation achieves ≈1.27 on all instances and closes the open question posed by Meir [Mei19] and Goel and Hann-Caruthers.The exact expected approximation guarantee applies to any n-agent instance.Source: §1.2 · pp. 6–7

2 Conclusion and Future directions

• The authors present randomized rotation as surpassing the deterministic barrier in classical and learning-augmented utilitarian facility location, and conclude that peaks-only GRD mechanisms are not the right tool.They suggest randomized rotation may also improve other facility-location problems.Source: §2 · pp. 7–8
• Future work could pin down the exact random-mechanism approximation ratio in R2 with a new lower bound or a mechanism beating RR-CWM’s 4/π result; the GRD lower bound requires new ideas for an upper bound.Source: §2 · p. 7
• Proving Theorem 11 could show that Algorithm 1 has expected approximation ratio at most 2 for every d in N.Source: §2 · p. 7
• For the egalitarian objective of minimizing maximum agent cost, whose deterministic barrier is 2, the authors ask whether randomization can break that barrier.Source: §2 · p. 8

The Utilitarian facility location mechanism design problem

• The mechanism receives n strategic locations in R^d, returns a facility, and seeks to minimize the worst-case ratio of expected social cost to optimal social cost.Each agent’s cost is its Euclidean distance to the facility; strategyproofness is required for every realization of the mechanism’s random choices, also called universal truthfulness.Source: §3 · p. 8

Generalizations of the median to Rd

• The coordinate-wise median (CWM) takes the median in each coordinate and is strategyproof and an SC1 minimizer [Mei19].The geometric median, by contrast, minimizes social cost over facility locations.Source: §3 · p. 9

Rotations in Euclidean space

• Rotated-CWM rotates the dataset, computes its CWM, and rotates the result back.The preliminaries define rotation matrices as orthogonal matrices with determinant 1; in R^2, rotations are parameterized by an angle.Source: §3 · p. 9

Learning augmented settings

• Output predictions provide a predicted optimal facility location, with error normalized by average optimal social cost; consistency and robustness bound approximation when prediction error is zero and arbitrary, respectively [Agr+22].The text notes a general consistency–robustness trade-off: greater consistency typically entails diminished robustness.Source: §3 · p. 10
• MAC input predictions assume at least a 1 − δ fraction of predicted agent locations are correct up to negligible additive error ε [BGT24].Here δ lies in (0, 0.5).Source: §3 · p. 10

4.1 R2 approximation analysis

• 4/pi ≈1.27 is RR-CWM’s exact approximation ratio in R2, improving on the deterministic lower bound of sqrt(2) ≈1.41.The exact ratio follows from matching upper and lower bounds.Source: §4 · p. 10, §4.1 · pp. 12, 14

4.2 Rd approximation ratio analysis

• In Rd, RR-CWM’s approximation ratio lies in [1.41, 1.55].The theorem states a bound for arbitrarily large dimension d.Source: §4 · p. 10, §4.2 · p. 16

4 Breaking The Deterministic Barrier Via Random Rotations

• RR-CWM samples a uniform random rotation and runs coordinate-wise median in the rotated coordinates, preserving strategyproofness universally.Theorem 1 gives running time O(d^3 + nd^2).Source: §4 · pp. 10–12

4.2 Rd approximation ratio analysis

• RR-CWM’s expected cost is upper bounded by the worst-case cost of CWM, since RR-CWM applies random rotations to CWM.Source: §4.2 · p. 16
• The two-cluster-and-outlier construction targets E[ALG] ≈ 2k and shows expected distance ≈1 from each cluster point.The instance has k copies each of e1 and e2, plus one outlier at −M(e1 + e2).Source: §4.2 · pp. 16–17
• For each fixed coordinate, the rotated-column pair is O(1/d)-close in total variation to an i.i.d. Gaussian pair, by the Diaconis–Freedman theorem [DF87].Source: §4.2 · p. 17
• Conjecture 11 states that RR-CWM’s lower bound is tight.Source: §4.2 · p. 18

Output prediction setting

• RR-CMP replaces CWM with RR-CWM in the output-prediction CMP mechanism, retaining strategyproofness and strictly improving the expected consistency-robustness trade-off over CMP for stated parameter ranges.The improvement is described as retaining CMP’s consistency with improved robustness through random rotations, with smooth degradation as prediction error η increases; the authors frame this as breaking the deterministic barrier established for CMP by Agrawal et al. [Agr+22].Source: §5 · pp. 18–19
• For a c-fraction insertion corruption in a general metric space, the section gives a robustness bound for the 1-Median, covering CWM and Geometric-Median as specializations.The reported bound is an approximation ratio of at most (1+c)/(1-c) for the corrupted dataset.Source: §5 · pp. 19–21

MAC input predictions settings

• In the MAC input-predictions model, replacing CWM with RR-CWM in the mechanism of Barak, Gupta, and Talgam-Cohen [BGT24] yields a better approximation result by direct corollary of Theorem 4.The original mechanism chooses the better of a prediction-based option and CWM; the RR-CWM replacement improves that result.Source: §5 · p. 21

Definition

• A GRD mechanism may return only a point reported by an agent, and this definition covers truthful and non-truthful mechanisms.Source: §6 · p. 21

R^2 lower bound

• Theorem 14 states that any GRD mechanism for the utilitarian facility location problem in R2 has an approximation ratio of at least 4.The argument uses that the preceding statement holds for any p_k, then takes n →∞ to obtain the desired result.Source: §6 · pp. 21–22

Higher-dimensional lower bound

• For d > 2, Theorem 16 states that any GRD mechanism for utilitarian facility location in R^d has an approximation ratio of at least a value omitted from the supplied excerpt.The proof samples i.i.d. points from the unit sphere and uses the probabilistic method to show a fixed multiset achieves the same bounds.Source: §6 · p. 22

A Missing analysis from Section 4

• Appendix A supplies missing proofs from Section 4.Source: Organization of Appendices · p. 24

Organization of Appendices

• Appendix B supplies missing proofs from Section 5.Source: Organization of Appendices · p. 24
• Appendix C supplies missing proofs from Section 6.Source: Organization of Appendices · p. 24
• Appendix D explains the connection between the approximation ratios of RR-CWM and Projection-Median.Source: Organization of Appendices · p. 24

A.1 Proof of Theorem 10

• RR-CWM’s expected cost is at most the worst-case cost of CWM because RR-CWM applies random rotations to CWM.The passage also says Gravin and Jia bound CWM’s approximation ratio, but the numerical bound is incomplete in the supplied text.Source: §A.1 · p. 24
• The proof bounds rotated cluster-point distances from the coordinate-wise median using Gaussian approximation and concentration of measure.It uses the Diaconis–Freedman result on rotated coordinates and concentration to control distance variance.Source: §A.1 · p. 24
• E[ALG] ≥ 2k − O(1) and OPT ≤ 2k + O(1) for the constructed instance, yielding the stated bound.The proof uses k copies each of e1 and e2 and one outlier at −M(e1 + e2).Source: §A.1 · pp. 24, 28

A.2 Proof of Theorem 19

• The event that the outlier coordinate cj lies between aj and bj is equivalent to (2M + 1)|s| ≤ |d|, where s = aj + bj and d = aj − bj.This criterion follows by rewriting (aj − cj)(bj − cj) ≤ 0.Source: §A.2 · p. 29

A.3 Proof of Theorem 20

• When y is outside [x, z], the coordinate median mj is x or z, so (x − mj)^2 + (z − mj)^2 = (x − z)^2.Here x = aj, z = bj, and y = cj.Source: §A.3 · p. 29
• Theorem 20’s calculation treats the event Dj, where y lies in [x, z], as a separate case from the outside-interval case.For this case, the proof sets s = x − z and proceeds with a separate calculation.Source: §A.3 · p. 29

A.4 Proof of Theorem 22

• The proof couples (U1, V1) with (G1, G2) so their probability of differing equals their total variation distance.It uses this coupling to compare the truncated function g_L=min{g,L}.Source: §A.4 · pp. 29–30
• The proof controls the truncation tail using g(u, v)≤v^2 and second-moment bounds for the Haar and Gaussian variables.The passage identifies the Gaussian second moment as 3 but omits the resulting O-term’s value.Source: §A.4 · p. 30
• Theorem 22’s proof concludes that E[g(U1, V1)] is at least E[g(G1, G2)] minus an O-term.The supplied passage does not include the order or quantity inside the O-term.Source: §A.4 · p. 30

A.5 Proof of Theorem 24

• Theorem 24’s proof bounds changes in the rotated mechanism by decomposing them into changes in direction vectors and the median output.It applies the triangle inequality and Frobenius-norm bounds to the direction-vector terms.Source: §A.5 · p. 31
• Claim 26 shows that the median is 1-Lipschitz under the infinity norm: |med(x)-med(y)|≤∥x-y∥∞.The proof bounds at least half of the coordinates of y above and below the corresponding median bounds from x.Source: §A.5 · p. 31
• For c=-M(a+b), the proof bounds ∥c-c′∥ using the changes in a and b, then combines the component bounds to conclude the claim.The passage relates the squared changes in a and b to the first two basis-vector terms of the rotation difference.Source: §A.5 · p. 32

B.1 Proof of Theorem 13

• Lemma 28 is introduced to bound how far the 1-Median can move after insertion corruption, for multisets in a metric space with |P̂| = c|P| and c ∈ (0, 1).The supplied passage omits the lemma’s conclusion.Source: §B.1 · p. 32
• Theorem 13’s proof defines m as the 1-Median of P and m′ as the 1-Median of P ∪ P̂.The proof passage says its final inequality follows from Theorem 28, but the displayed bound is absent.Source: §B.1 · p. 33

C.1 Proof of Theorem 15

• Theorem 15’s proof multiplies by sin, applies a product-to-sum identity, uses a telescoping sum, and divides by sin before concluding.The supplied passages do not show the expressions being transformed.Source: §C.1 · pp. 33–34

C.2 Proof of Theorem 17

• The generalized binomial theorem is recalled for real α and |t| ≤ 1 as the basis for the expansion.Source: §C.2 · p. 34
• Taking expectations in Eq. (37) and substituting Eq. (38) yields an expansion involving even moments of X_1.The displayed terms include E[X_1^2], E[X_1^4], and E[X_1^6].Source: §C.2 · p. 34
• Odd moments vanish because reflection by R = diag(−1, 1, . . . , 1) preserves dS.The proof uses invariance under orthogonal isometries to obtain the zero integral.Source: §C.2 · p. 35

D RR-CWM and Projection-Median connection

• Projection-Median averages the one-dimensional medians of projections onto all directions and is equivalently the average case of Rotated-CWM over rotations.Source: D RR-CWM and Projection-Median… · p. 35
• For the example in Theorem 29, Projection-Median’s approximation ratio is strictly smaller than RR-CWM’s by a multiplicative factor greater than 1.Source: D RR-CWM and Projection-Median… · p. 35
• Projection-Median’s social-cost approximation ratio is at most RR-CWM’s, so its lower bounds also apply to RR-CWM and RR-CWM’s upper bounds also apply to Projection-Median.The comparison follows from the equivalence to average Rotated-CWM and convexity of social cost.Source: D RR-CWM and Projection-Median… · pp. 35–36
• In R^2, Projection-Median is deterministic and anonymous with approximation ratio strictly below sqrt(2), so it is not strategyproof under the lower bound of.Source: D RR-CWM and Projection-Median… · p. 36
• The connection and Theorem 10 yield a Projection-Median approximation-ratio upper bound of approximately 1.547, narrowing the prior bound of Basu, Bhattacharya, and Talukdar.Source: D RR-CWM and Projection-Median… · p. 36
• Closing Projection-Median’s approximation gap remains open; further improvement via RR-CWM analysis is ruled out, and strictly separating the mechanisms’ ratios remains future work.Source: D RR-CWM and Projection-Median… · p. 36

• The proof concludes that RR-CWM’s expected approximation ratio is bigger, showing that the two can differ.Source: §D.1 · p. 36
• For the profile p1 = (1, 0), p2 = (0, 1), and p3 = (−1, 0), the proof rotates the points and derives the resulting CWM locations across angle ranges.Source: §D.1 · p. 37
• The proof computes the Projection-Median from an integral over rotated points and gives a resulting value of approximately 2.736.Source: §D.1 · p. 37
• To evaluate RR-CWM’s expected cost, the proof calculates social cost across rotation angles, splitting the calculation at π/4 and averaging over uniform θ by symmetry.Source: §D.1 · pp. 37–38