publications

2025

1. STOC 25

   Approximation Guarantees of Median Mechanism in ℝᵈ

   Nikolai Gravin, and Jianhao Jia

   In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Prague, Czechia, 2025

   Abs PDF

   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 L2(ℝd) is √d via a simple argument of embedding L1(ℝd) into L2(ℝd) metric space, that only appeared in appendix of [Meir 2019]. This upper bound is known to be tight in dimension d=2 from [Goel and Hann-Caruthers 2023], but there are no known super constant lower bounds. A few recent papers on mechanism design with predictions (e.g., [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 Lq(ℝd) spaces for any Lq 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 L2 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 used in [Agrawal, Balkanski, Gkatzelis, Ou, Tan 2022] for L2(ℝ2) space to arbitrary dimensions d with similar results for both robustness and consistency approximation guarantees.

2023

1. WWW 23

   Online resource allocation in Markov Chains

   Jianhao Jia, Hao Li, Kai Liu, Ziqi Liu, Jun Zhou, Nikolai Gravin, and Zhihao Gavin Tang

   In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023, 2023

   Abs PDF

   A large body of work in Computer Science and Operations Research study online algorithms for stochastic resource allocation problems. The most common assumption is that the online requests have randomly generated i.i.d. types. This assumption is well justified for static markets and/or relatively short time periods. We consider dynamic markets, whose states evolve as a random walk in a market-specific Markov Chain. This is a new model that generalizes previous i.i.d. settings. We identify important parameters of the Markov chain that is crucial for obtaining good approximation guarantees to the expected value of the optimal offline algorithm which knows realizations of all requests in advance. We focus on a stylized single-resource setting and: (i) generalize the well-known Prophet Inequality from the optimal stopping theory (single-unit setting) to Markov Chain setting; (ii) in multi-unit setting, design a simple algorithm that is asymptotically optimal under mild assumptions on the underlying Markov chain.