Paper Overview
Field: Machine Learning Authors: Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu Posted: 2026-08-21 arXiv: 2608.21348
Summary
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.
This paper resolves that question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. The authors then show that this impossibility is specific to exact truthfulness. They 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 < ε < 1, they construct a reliable and complete calibration measure that is (1 + exp(-T^(1-ε)/2/2))-multiplicatively truthful, improving the approximate truthfulness guarantee of Haghtalab et al. (2024).
Key Contributions
- Impossibility result: Exact truthfulness cannot be combined with completeness and soundness in sequential binary prediction, even with independent outcomes.
- Two general reductions: From any base calibration measure, they derive additively and multiplicatively approximately truthful calibration measures.
- Improved guarantee: A construction achieving (1 + exp(-T^(1-ε)/2/2))-multiplicative truthfulness while remaining reliable and complete, for any 0 < ε < 1.