Truthfulness of Decision-Theoretic Calibration Measures

Calibration measures quantify how much a forecaster’s predictions violates calibration, which requires that forecasts are unbiased conditioning on the forecasted probabilities. Two important desiderata for a calibration measure are its decision-theoretic implications (i.e., downstream decision-makers that best-respond to the forecasts are always no-regret) and its truthfulness (i.e., a forecaster approximately minimizes error by always reporting the true probabilities). Existing measures satisfy at most one of the properties, but not both. We introduce a new calibration measure termed subsampled step calibration, ${\mathsf{S}\mathsf{t}\mathsf{e}\mathsf{p}\mathsf{C}\mathsf{E}}^{\mathsf{\text{sub}}}$, that is both decision-theoretic and truthful. In particular, on any product distribution, ${\mathsf{S}\mathsf{t}\mathsf{e}\mathsf{p}\mathsf{C}\mathsf{E}}^{\mathsf{\text{sub}}}$ is truthful up to an $O(1)$ factor whereas prior decision-theoretic calibration measures suffer from an $e^{-\mathrm{\Omega }(T)}$-$\mathrm{\Omega }(\sqrt{T})$ truthfulness gap. Moreover, in any smoothed setting where the conditional probability of each event is perturbed by a noise of magnitude $c>0$, ${\mathsf{S}\mathsf{t}\mathsf{e}\mathsf{p}\mathsf{C}\mathsf{E}}^{\mathsf{\text{sub}}}$ is truthful up to an $O(\sqrt{\log (1\mathrm{/}c)})$ factor, while prior decision-theoretic measures have an $e^{-\mathrm{\Omega }(T)}$-$\mathrm{\Omega }(T^{1\mathrm{/}3})$ truthfulness gap. We also prove a general impossibility result for truthful decision-theoretic forecasting: any complete and decision-theoretic calibration measure must be discontinuous and non-truthful in the non-smoothed setting.