The Exact Approximation Ratio of Uniformly Rotated Coordinate-wise Median in the Euclidean Plane

Uniformly rotated coordinate-wise median chooses a random orthonormal coordinate system, takes a median in each coordinate, and maps the resulting point back to the Euclidean plane. We determine its exact worst-case expected approximation ratio when social cost is the $L_p$ norm of the agents’ Euclidean distances and $1<p<2$. The ratio is $\frac{2^{2-1\mathrm{/}p}}{\pi }{\int }_0^{\pi \mathrm{/}2}({\cos }^p\theta +{\sin }^p\theta {)}^{1\mathrm{/}p}\text{dd}\theta$. This expression was previously established as a lower bound by Chan, Lin, and Wang; our contribution is the matching upper bound. The proof establishes a strengthened coordinate-wise median inequality relative to an arbitrary reference point. Its right-hand side is linear in a sum of direction-dependent norms, which permits direct averaging over rotations without the loss incurred by passing through a $p$th-moment bound. We give all auxiliary inequalities and a self-contained proof of tightness using the established two-cluster-and-outlier construction. The upper bound holds for every finite profile and every measurable choice within the coordinate median intervals, while odd-size profiles suffice for the matching lower bound. The result characterizes this fixed mechanism, rather than the optimal approximation ratio among all randomized strategyproof mechanisms.