Yao averaging: a competitive mixed strategy contains a good deterministic algorithm

Let $\widetilde{\mathcal{A}}$ be a randomized online $k$-server algorithm (a mixed strategy: a probability measure over deterministic algorithms) that is $\rho$-competitive from the configuration $C_0$ against oblivious adversaries, with $\rho \ge 0$. Then there is a constant $a \ge 0$ such that for every finitely supported probability distribution $(p_1, \sigma_1), \dots, (p_m, \sigma_m)$ over request sequences and every $\varepsilon > 0$, some deterministic algorithm $\mathcal{A}$ in the support of $\widetilde{\mathcal{A}}$ starts at $C_0$ and satisfies

Role

This is the easy (averaging) direction of Yao's minimax principle, in the form needed for randomized lower bounds: to show that every $\rho$-competitive randomized algorithm has $\rho \ge L$, it suffices to exhibit request distributions against which every deterministic algorithm pays at least $L$ times the expected offline cost plus an arbitrarily large constant. It is the first pillar of the Bubeck–Coester–Rabani refutation of the randomized $k$-server conjecture (STOC 2023), which constructs such distributions on $(k+1)$-point spaces forcing $L = \Omega(\log^2 k)$.

The proof is an exercise in the linearity and monotonicity of the lower Lebesgue integral: the expected average cost of the randomized algorithm is the average of its expected costs (Fubini for finite sums, using the measurability field of the mixed strategy), each bounded by $\rho\, c_{\mathrm{OPT}}(\sigma_j) + a$; if every outcome exceeded the average bound by $\varepsilon$, integrating the pointwise bound over the probability measure would contradict it.

Formalization note

Expected costs are lower Lebesgue integrals valued in ENNReal; the constant is normalized to $\max(a,0)$ so that the comparison of ENNReal.ofReals can be reflected back to the reals, and the $\varepsilon$ of slack absorbs the fact that a lower integral bound only yields pointwise bounds up to any positive margin.