Truthful Calibration Measures for Sequential Prediction
2026-08-21 • Data Structures and Algorithms
Data Structures and AlgorithmsComputer Science and Game TheoryMachine Learning
AI summaryⓘ
The authors studied how to measure if predictions about yes/no events are accurate and fair. They showed it’s impossible to have a perfect system that is exactly truthful while also being complete and sound, even when events are independent. However, they found ways to create systems that are almost perfectly truthful, improving on earlier work by Haghtalab and colleagues. These new systems maintain accuracy while being nearly truthful in how they report errors over time.
calibrationprobabilistic forecaststruthfulnesscompletenesssoundnessbinary predictiononline predictionapproximate truthfulnesserror measurementindependent outcomes
Authors
Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu
Abstract
Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. We resolve this question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. We then show that this impossibility is specific to exact truthfulness. We give two general reductions from a base calibration measure, producing additively and multiplicatively approximately truthful calibration measures, respectively. Applying the multiplicative reduction, for every $0 < \varepsilon < 1$ we construct a sound and complete calibration measure that is $(1+\exp(-T^{(1-\varepsilon)/2}/2))$-multiplicatively truthful. This improves the approximate-truthfulness guarantee of Haghtalab et al. (2024).