  A sequence of predictions is calibrated if and only if it induces no swap
regret to all down-stream decision tasks. We study the Maximum Swap Regret
(MSR) of predictions for binary events: the swap regret maximized over all
downstream tasks with bounded payoffs. Previously, the best online prediction
algorithm for minimizing MSR is obtained by minimizing the K1 calibration
error, which upper bounds MSR up to a constant factor. However, recent work
(Qiao and Valiant, 2021) gives an ${\Omega}(T^{0.528})$ lower bound for the
worst-case expected $K_1$ calibration error incurred by any randomized
algorithm in T rounds, presenting a barrier to achieving better rates for MSR.
Several relaxations of MSR have been considered to overcome this barrier, via
external regret (Kleinberg et al., 2023) and regret bounds depending
polynomially on the number of actions in downstream tasks (Noarov et al., 2023;
Roth and Shi, 2024). We show that the barrier can be surpassed without any
relaxations: we give an efficient randomized prediction algorithm that
guarantees $O(\sqrt{T}logT)$ expected MSR. We also discuss the economic utility
of calibration by viewing MSR as a decision-theoretic calibration error metric
and study its relationship to existing metrics.
