Approximation guarantees of Median Mechanism in ℝd

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 d-dimensional Euclidean space mathbbL2(ℝd) is √d via embedding mathbbL1(ℝd) into mathbbL2(ℝd) 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 Theta(√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 mathbbLq(ℝd) spaces for any mathbbLq norm with q∈[1,∞] and any dimension d. We derive a series of constant upper bounds UB(q) independent of the dimension d. This series UB(q) is growing with parameter q, but never exceeds the constant UB(∞)= 3. Our bound UB(2)=√6√3-8<1.55 for mathbbL2 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)=UB(q)·(1-O(1/d)) for any dimension d with LB(q,d)=UB(q) when d→∞. We also extend our analysis to the generalized median mechanism in [Agrawal, Balkanski, Gkatzelis, Ou, Tan 2022] for mathbbL2(ℝ2) space to arbitrary dimensions d with similar results.