The Price of Near-Perfect Consistency in Online Metric Matching with Predictions

Abstract

We study online metric matching with per-request action predictions. On the real line, every deterministic $(1+\varepsilon)$-consistent algorithm has robustness at least $1+\sum_{j=1}^{k-1}2^{j+1}/\varepsilon^j$, and we give a deterministic algorithm for arbitrary metrics with the same leading term. Thus, for every fixed $k$, $\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k^{\mathbb{R}}(1+\varepsilon)=\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k(1+\varepsilon)=2^k$. The comparison is uniform up to an absolute constant for $0<\varepsilon\le 1/(k-1)$. We determine the two-server trade-off in both settings and the real-line three-server value $1+4/\varepsilon+8/\varepsilon^2$ for $0<\varepsilon\le\sqrt{13}-3$. When the predicted labels are distinct, the algorithm pays at most $(1+\varepsilon)$ times the cost of the predicted matching. For randomised algorithms, the fixed-$k$ dependence remains $\Theta_k(1/\varepsilon^{k-1})$. Uniformly in $k$, robustness is at most $M_0(\varepsilon)\rho_k^0$, where $\rho_k^0$ is the optimal strict prediction-free randomised ratio on the real line and $M_0(\varepsilon)=(2e+o(1))e^{2/\varepsilon}$. For every $\eta>0$, a lower bound $\exp((2-\eta)/\varepsilon)$ holds once $k\ge C_\eta/\varepsilon$. The randomised upper bound follows from a comparison theorem for two online algorithms whose states can be coupled at a cost bounded by their cumulative costs. For every fixed $c>1$, the least comparison factor $M^*(c,\varepsilon)$ under these assumptions satisfies $\lim_{\varepsilon\downarrow 0}\varepsilon\log M^*(c,\varepsilon)=2$. The guarantee is strictly multiplicative and has no diameter-dependent additive term. Irrevocable metric matching and metrical task systems satisfy the assumptions, and the exponent $2$ is optimal under them.