Theorem 3.3, p. 14 — repeated-play extension with positive comparison cost

Let $G$ be a cost-minimization game with nonnegative joint cost $C$ and finite robust price of anarchy $\rho(G)$. Suppose the outcome sequence $s^1,s^2,\ldots$ gives every player vanishing average external regret. For every comparison outcome $s'$ with $C(s')>0$, there is a function $\eta(T)\to0$ such that, for every horizon $T\geq1$,

This transfers a smoothness bound to repeated joint play without assuming that the outcomes converge to an equilibrium.

Formalization Note The printed theorem omits $C(s')>0$, but its multiplicative bound fails at zero comparison cost: one player may incur cost 1 once, then cost 0 forever, producing vanishing regret and positive average cost at every finite horizon. The preceding paragraph's additive bound has no such restriction. The nonnegative objective is the paper's standing convention. $\rho(G)$ is the extended-real infimum; an admissible smoothness pair makes it finite here (with $C(s')>0$ it is a real number at least 1), which is the page's only non-vacuous case.