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

We study online metric matching with per-request action predictions. On the real line, every deterministic $(1+\epsilon )$-consistent algorithm has robustness at least $1+{\sum }_{j=1}^{k-1}{2}^{j+1}\mathrm{/}{\epsilon }^j$, and we give a deterministic algorithm for arbitrary metrics with the same leading term. Thus, for every fixed $k$, ${\lim }_{\epsilon \downarrow 0}{\epsilon }^{k-1}{R}_k^{\mathbb{R}}(1+\epsilon )={\lim }_{\epsilon \downarrow 0}{\epsilon }^{k-1}{R}_k(1+\epsilon )=2^k$. The comparison is uniform up to an absolute constant for $0<\epsilon \le 1\mathrm{/}(k-1)$. We determine the two-server trade-off in both settings and the real-line three-server value $1+4\mathrm{/}\epsilon +8\mathrm{/}{\epsilon }^2$ for $0<\epsilon \le \sqrt{13}-3$. When the predicted labels are distinct, the algorithm pays at most $(1+\epsilon )$ times the cost of the predicted matching. For randomised algorithms, the fixed-$k$ dependence remains ${\mathrm{\Theta }}_k(1\mathrm{/}{\epsilon }^{k-1})$. Uniformly in $k$, robustness is at most $M_0(\epsilon ){\rho }_k^0$, where ${\rho }_k^0$ is the optimal strict prediction-free randomised ratio on the real line and $M_0(\epsilon )=(2e+o(1))e^{2\mathrm{/}\epsilon }$. For every $\eta >0$, a lower bound $\exp ((2-\eta )\mathrm{/}\epsilon )$ holds once $k\ge C_{\eta }\mathrm{/}\epsilon$. 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^{\ast }(c,\epsilon )$ under these assumptions satisfies ${\lim }_{\epsilon \downarrow 0}\epsilon \log M^{\ast }(c,\epsilon )=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.