Approximation Guarantees of Median Mechanism in ℝᵈ

The coordinate-wise median is a classic and most well-studied strategy-proof mechanism in social choice and facility location scenarios. Surprisingly, there is no systematic study of its approximation ratio in d-dimensional spaces. The best known approximation guarantee in

) metric space, that only appeared in appendix of [Meir 2019]. This upper bound is known to be tight in dimension d = 2, but there are no known super constant lower bounds. Still, it seems that the community's belief about coordinate-wise median is on the side of Θ( √ d). E.g., a few recent papers on mechanism design with predictions [Agrawal, Balkanski, Gkatzelis, Ou, Tan 2022], [Christodoulou, Sgouritsa, Vlachos 2024], and [Barak, Gupta, Talgam-Cohen 2024] directly rely on the √ d-approximation result. In this paper, we systematically study approximate efficiency of the coordinate-median in L q (R d ) spaces for any L q norm with q ∈ [1, ∞] and any dimension d. We derive a series of constant upper bounds U B(q) independent of the dimension d. This series U B(q) is growing with parameter q, but never exceeds the constant U B(∞) = 3. Our bound U B(2) = 6 √ 3 -8 < 1.55 for L 2 norm is only slightly worse than the tight approximation guarantee of √ 2 > 1.41 in dimension d = 2. Furthermore, we show that our upper bounds are essentially tight by giving almost matching lower bounds LB(q, d) = U B(q) • (1 -O(1/d)) for any dimension d with LB(q, d) = U B(q) when d → ∞. We also extend our analysis to the generalized median mechanism used in [Agrawal, Balkanski, Gkatzelis, Ou, Tan 2022] for L 2 (R 2 ) space to arbitrary dimensions d with similar results for both robustness and consistency approximation guarantees.