Source-linked AI summary
Truthful Calibration Measures for Sequential Prediction
Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu
TL;DR
Sequential calibration asks whether truthful probabilistic reporting can coexist with completeness and soundness, a question left open for exact truthfulness. The paper proves impossibility even for independent outcomes, then constructs additive and multiplicative approximately truthful measures through reductions, including a sound and complete multiplicative guarantee for every 0 < ε < 1.
Problem
Exact truthfulness remained open in sequential prediction because calibration measures must both incentivize truthful reports and distinguish calibrated from miscalibrated data.
Method
The paper uses a hybrid argument for impossibility and two reductions from a uniformly complete sound and complete base measure for approximate truthfulness.
Results
Exact truthfulness is incompatible with completeness and soundness even for product distributions, while the multiplicative reduction yields a sound and complete approximately truthful measure.
Takeaways & Limitations
The impossibility is specific to exact truthfulness: relaxing truthfulness permits calibration measures that retain soundness and completeness.
Takeaways & Limitations
The impossibility theorem is deliberately finite-sample and does not require an asymptotic notion of soundness; the reduction additionally assumes uniform completeness.
Abstract
from arXiv · showhide
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).
1 Introduction
The paper studies whether sequential calibration measures can incentivize truthful probabilistic reporting while remaining statistically complete and sound. It proves exact truthfulness is impossible, but approximate truthfulness can coexist with both requirements.
- Motivation: Calibration requires reports to be conditionally unbiased so they can be interpreted as probabilities.For report value p, the event should occur with frequency approximately p conditional on reporting p.
- Existing measures: ECE averages absolute conditional report bias, weighted by the frequency of each reported value.For report p, the bias is the distance between its empirical outcome frequency and p.
- Motivation: ECE can reward strategic misreporting: a truthful predictor incurs sampling error, while a strategic predictor can achieve ECE= 0.The strategic predictor uses later deterministic blocks to correct sampling fluctuations from an earlier fair-coin block.
- Contributions: Exact truthfulness is incompatible with completeness and soundness for sequential binary prediction, even under independent outcomes.The impossibility follows because the requirements separate calibrated from miscalibrated product distributions, creating profitable deviations on rare histories.
- Contributions: Approximate truthfulness remains possible through additive and multiplicative reductions from a uniformly complete sound and complete base measure.Both reductions preserve completeness and soundness; the multiplicative version adds a vanishing squared-loss term.
- Contributions: For every 0 < ε < 1, the multiplicative reduction constructs a sound and complete calibration measure with a stated exponentially small multiplicative-truthfulness gap.The paper reports the guarantee as (1+exp(-T^(1-ε)/2}/2))-multiplicatively truthful in the supplied passage.
2 Technical Overview
The technical overview explains impossibility through rare histories where truthful reports look miscalibrated, then uses hybrids to locate a profitable local deviation. It also sketches reductions that recover additive and multiplicative approximate truthfulness.
- Impossibility intuition: Exact truthfulness fails because truthful reporting is required even on rare histories where the accumulated transcript looks badly miscalibrated.A strategic report can repair the apparent imbalance and receive lower calibration error.
- Impossibility intuition: In the symmetric example, an all-zero first block occurs with probability 2^-n and makes continued reporting of 1/2 look perfectly calibrated.The strategic predictor differs from truthful reporting only on this rare history.
- Hybrid argument: The general proof compares calibrated and miscalibrated one-sample distributions and changes the transcript one coordinate at a time through hybrids.A positive endpoint gap implies an adjacent hybrid pair with a local preference for misreporting on some prefix.
- Hybrid argument: The useful deviation occurs on a fixed rare prefix where reporting 1/2 instead of the truthful value 1 lowers expected calibration error.The prefix is generated by i.i.d. draws from the miscalibrated distribution, while later rounds use a calibrated Bernoulli(1/2) tail.
- Quantitative bound: The online advantage is exponentially smaller than the offline distinguishing gap because the strategy must reach the selected prefix.The quantitative bound loses factors from averaging over hybrid steps and from the probability of reaching the deviation history.
- Approximate construction: Approximate truthfulness is obtained from a uniformly complete sound and complete base measure by first subtracting a sampling-error threshold.Nonnegativity then yields additive approximate truthfulness.
- Approximate construction: A small normalized squared-loss term strengthens the additive guarantee to (1 + o(1))-multiplicative truthfulness.The squared-loss term is proper round by round and supplies a universal lower bound on expected error.
3 Preliminaries
The paper formalizes binary sequential prediction, calibration measures, truthfulness, completeness, and soundness. Reports depend on past outcomes and the known data-generating distribution, while calibration requirements distinguish calibrated from miscalibrated data.
- Sequential prediction: Binary sequential prediction uses a fixed horizon T, with outcomes Y=(Y1,...,YT) in {0,1}^T.At each time, the predictor reports after observing the past outcomes.
- Sequential prediction: A prediction strategy maps each outcome history to a probability report without using future realized outcomes.The strategy may depend on the known ground-truth distribution.
- Data-generating distributions: Under product distributions, outcomes are independent Bernoulli variables with potentially time-varying means; under correlated distributions, the ground truth is an arbitrary joint distribution.The truthful report is the conditional mean under the relevant ground-truth distribution.
- Calibration measures: A calibration measure assigns non-negative error to a report-outcome transcript, with smaller values representing better calibration.The measure is evaluated directly on sequences of prediction-outcome pairs.
- Calibration criteria: A one-sample distribution is calibrated when E[Y | R] = R almost surely.Completeness and soundness use this notion to distinguish calibrated and miscalibrated data.
- Calibration criteria: Completeness requires expected error to vanish for calibrated data as sample size grows, whereas soundness requires positive limiting error for fixed miscalibrated data.Together, they imply eventual expected-error separation between calibrated and miscalibrated one-sample distributions.
- Truthfulness: Truthfulness requires the truthful strategy to minimize expected calibration error for every joint data-generating distribution.Approximate versions relax this requirement using additive or multiplicative inequalities.
- Truthfulness: Multiplicative truthfulness is defined by the corresponding multiplicative inequality for every product distribution and prediction strategy that may depend on it.The arbitrary-joint-distribution version requires the same inequality for every joint distribution.
4 Product-Distribution Impossibility
Exact truthfulness is incompatible with completeness and soundness for sequential calibration measures, even under independent outcomes. The hybrid argument shows that distinguishing calibrated from miscalibrated product distributions creates a profitable online deviation.
- Hybrid impossibility: The constructed deviation changes the report only at one time and on a positive-probability history, while otherwise reporting truthfully.Conditioned on the deviation event, the outcome at the changed time is 1 almost surely and later outcomes remain independent Bernoulli(q).
- Hybrid impossibility: A positive offline gap between calibrated and miscalibrated product distributions implies a strategic predictor can obtain strictly lower expected calibration error than truthful reporting.The hybrid argument localizes the gap to a history where reporting q instead of the truthful value 1 is preferred.
- Consequences: Completeness and soundness therefore rule out calibration measures that satisfy no-deviation truthfulness for every product distribution and strategy.The calibrated distribution Dq and miscalibrated distribution D′q provide the finite-sample separation needed by the hybrid theorem.
- Consequences: The impossibility is finite-sample: at any fixed horizon, separating the calibrated and miscalibrated product distributions already permits a strategic improvement over truthful reporting.No asymptotic notion of soundness is required for this conclusion.
5 Quantitative Lower Bounds from Impossibility
The quantitative hybrid argument bounds strategic gains below using the offline distinguishing gap, with an exponentially small loss caused by averaging over hybrid steps and reaching a rare deviation history. Under completeness and soundness, this yields exponential lower bounds against exact and additive truthfulness.
- Quantitative hybrid bound: The hybrid reduction converts an offline distinguishing gap into a strategic advantage of order (1−q)T−1qT∆T(q).The loss is exponentially small in the horizon because it includes the probability of reaching the prefix where deviation is useful.
- Quantitative hybrid bound: The product-distribution strategic advantage is the largest expected gain available to a predictor from deviating from truthful reporting.Advprod_T(Cal)=0 means no product-distribution strategy improves on truthfulness, while Advprod_T(Cal)≤βT defines additive βT-truthfulness.
- Proof strategy: Theorem 5.1 establishes the lower bound by telescoping across hybrid distributions and embedding a favorable prefix into a product prediction problem.A prefix exists whose conditional gain is at least ∆T(q), and multiplying by its event probability yields the overall strategic advantage.
- Consequences: For complete and sound calibration measures, the distinguishing gap for each fixed q is eventually bounded below by a positive constant, producing an exponential lower bound on strategic advantage.Choosing q as a function of the target exponential rate gives Corollary 5.2.
- Consequences: Additive βT-truthfulness requires ∆T(q)≤qT(1−q)T−1βT for every q∈(0,1).Thus, additive truthfulness constrains how strongly the measure can distinguish the calibrated and miscalibrated product distributions.
6 Approximately Truthful Reductions
The paper reduces approximate truthfulness to uniform completeness of a sound and complete base calibration measure. Thresholding yields additive truthfulness, while adding squared loss yields multiplicative truthfulness while preserving soundness and completeness.
- Motivation: Exact truthfulness fails because rare prefix realizations can make truthful reports appear miscalibrated, incentivizing future strategic correction.Approximate truthfulness relaxes the requirement on every historical prefix realization.
- Base requirement: Uniform completeness bounds truthful calibration error using a sampling-error threshold and a variance-scale tail term.The witnesses τT and ηT are independent of the outcome distribution.
- Additive reduction: Subtracting the sampling-error threshold and truncating at zero produces an additively approximately truthful measure.The reduction provides additive slack ηT/4 for arbitrary joint distributions.
- Multiplicative reduction: Adding a normalized squared-loss term supplies the relative error needed for multiplicative truthfulness when calibration error is near zero.Every strategy incurs a squared-loss contribution tied to the intrinsic variance.
- Multiplicative reduction: The multiplicative construction is (1 + ηT/λT)-multiplicatively truthful for arbitrary joint distributions.Setting λT=0 gives the additive construction, whereas λT>0 gives the multiplicative construction.
- Guarantee preservation: Both reductions preserve soundness and completeness when the threshold and squared-loss weights vanish appropriately.If the base measure is complete, the constructed measure is complete; if it is sound, the constructed measure is sound.
AI Disclosure
The authors disclose using ChatGPT 5.4 to assist with developing and editing two proof components, while independently verifying the content.
- AI Disclosure: ChatGPT 5.4 assisted with developing and editing the peeling and comparison lemma proofs.The assistance concerned Section A.
- AI Disclosure: The authors independently verified the correctness and originality of the paper’s content and references.
A Truthfulness and Weak Soundness
The impossibility proof targets weak constant-predictor soundness and completeness. Its key strategy is to decompose the first round into a proper binary loss while retaining a truthful non-negative tail measure.
- Setup: The proof uses weak constant-predictor requirements: matching the Bernoulli mean should yield small error, while separated reports should yield noticeably larger error.
- Proof strategy: A first-round decomposition identifies the initial contribution with a proper binary loss and leaves a non-negative truthful calibration measure on the tail.
- Contradiction: The comparison lemma transfers the small expected error of a truthful constant predictor to a separated constant misreport.This transfer contradicts the lower error bound required by soundness.
- Tail strategies: Tail strategies map past outcome histories to reports, and σ[w] denotes the realized report vector along tail sequence w.
Then there is a non-negative proper binary loss
The appendix formalizes how truthfulness constrains constant reports through a first-round proper-loss decomposition. Induction on the truthful tail measure yields the comparison inequality needed for impossibility.
- Proper-loss decomposition: For fixed tail distributions, the first-round report induces a proper binary loss, with the remaining objective represented by tail-dependent constants and a residual term.
- Tail truthfulness: The residual tail objective is non-negative and remains truthful on the remaining rounds.This property allows the induction hypothesis to apply to the tail.
- Branchwise constraint: Truthfulness prevents a strategy from improving reports on any positive-probability deterministic branch.Otherwise, changing the tail reports on that branch would strictly reduce unconditional expected calibration error.
- Comparison lemma: The comparison lemma bounds the expected error of a lower constant report by a factor K times the error of the truthful higher report.For 0<q<p<1, the inequality compares constant q and p reports under Ber(p)^⊗T.
- Inductive proof: Induction applies the comparison inequality first to the truthful tail residual and then to the one-step proper binary loss.The resulting bound combines the tail and first-round contributions.
- Impossibility: The resulting comparison transfers completeness’s upper bound for truthful reports to separated misreports, contradicting weak soundness.
A.2 Constant-Predictor Consequence
The comparison lemma shows that truthful calibration cannot maintain a horizon-independent separation between truthful and fixed misreports for constant predictors. Consequently, vanishing truthful error is incompatible with a constant lower error bound for separated misreports.
- Constant-predictor comparison: A horizon-independent comparison factor forces every fixed constant misreport below a low-error truthful report to have comparably low expected error.The factor does not depend on T.
- Impossibility consequence: A truthful calibration measure cannot have c1(T) = o(1) while assigning constant positive error to every fixed-separated constant misreport.The separation is from the true Bernoulli mean by a fixed amount.
A.3 Weak Constant-Predictor Soundness
Weak constant-predictor completeness and soundness already conflict with truthfulness. The impossibility extends from independent Bernoulli outcomes to correlated outcome distributions because the correlated condition includes the i.i.d. product case.
- Weak constant-predictor conditions: Weak constant-predictor completeness requires truthful constant reports to have expected error at most c1 under Ber(p)^⊗T outcomes.The definition quantifies over every p ∈ [0, 1].
- Impossibility theorem: For every 0 < c2 ≤ 1, no truthful calibration measure satisfies (1/4, c2/4, c2)-weak constant-predictor completeness and soundness.The contradiction follows by applying the comparison lemma to the weak requirement.
- Impossibility theorem: The contradiction arises because a truthful constant report at p = 3/4 must also receive low expected error for the constant report p = 1/2, despite their separation being 1/4.Soundness requires the latter expectation to be at least c2.
- Correlated extension: The correlated formulation strengthens the product condition by requiring the bounds for every joint distribution with common marginal mean p, including i.i.d. Bernoulli sequences.Restricting the correlated condition to Ber(p)^⊗T recovers the ruled-out product condition.
B Concentration for Smooth Calibration Error
This section establishes concentration for smooth calibration error under truthful sequential reporting using a martingale exponential-moment argument. The resulting tail bound decays polynomially and exponentially in the horizon, yielding vanishing error thresholds.
- Tail bound: Lemma B.1 bounds the probability that normalized smooth calibration error exceeds a threshold under truthful reporting.The intermediate bound is Pr[L ≥ s] ≤ 2aλe^(aλTμ) cosh(λs/2) − 1.
- Proof strategy: The proof uses bounded martingale differences because truthful reporting makes Y_t − p*_t a bounded martingale difference.Smooth calibration error is the supremum over predictable Lipschitz test functions applied to these differences.
- Proof strategy: The tail analysis applies the exponential-moment method to predictable processes and bounds large-error events with Markov's and Jensen's inequalities.The argument splits the event into a large aggregate term or a large integrated deviation term.
- Tail bound: Pr[L ≥ T^(1−α)] ≤ C T^d exp(−T d/16) μ for sufficiently large T, with d = 1 − 2α > 0.The bound follows after choosing λ = T^(−α/2).
- Extension to sequential outcomes: The concentration result extends to arbitrary joint outcome distributions by conditioning each binary outcome on its past and applying the truthful tail lemma.Finite horizons below T0 are controlled separately, producing sequences τ_T and η_T that converge to zero.