Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — a randomized forecast calibrated against every learning rule of the opponent

Proved
CalibratedCE.Forecast.exists_calibrated_randomized_forecast

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

calibrationforecastinglearning-in-gamesp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let player 2 have n≥1n\ge 1n≥1 pure strategies. There exists a randomized forecaster FFF for player 1, whose forecasts are always probability vectors over player 2's strategies, such that no matter what learning rule AAA player 2 uses (deterministic or randomized, depending on the whole past, but not on player 1's current forecast), player 1's calibration score

Ct=∑p∑j∣ρ(p,j,t)−pj∣N(p,t)tC_t = \sum_p \sum_{j} \bigl|\rho(p,j,t) - p_j\bigr|\frac{N(p,t)}{t}Ct​=p∑​j∑​​ρ(p,j,t)−pj​​tN(p,t)​

converges to zero in probability: for every ε>0\varepsilon>0ε>0,

lim⁡t→∞PF,A(Ct<ε)=1,\lim_{t\to\infty} \mathbb P_{F,A}\bigl(C_t < \varepsilon\bigr) = 1 ,t→∞lim​PF,A​(Ct​<ε)=1,

where PF,A\mathbb P_{F,A}PF,A​ is the law of the first ttt rounds when forecast and play are drawn independently in each round given the past.

The forecaster is chosen first and works against every opponent; the convergence rate may depend on the opponent. By the impossibility theorem of Oakes (1985), no deterministic forecaster has this property, which is why randomization is needed.

Formalization Note Forecaster and opponent are maps from histories (lists of (forecast, play) pairs) to Mathlib PMFs; the probability of the event {Ct<ε}\{C_t<\varepsilon\}{Ct​<ε} is the outer measure of the history law, a value in [0,∞][0,\infty][0,∞], and the limit is taken there. n≥1n\ge 1n≥1 is required: with no strategies there is no probability vector.

Preamble
import Mathlib
import Definitions.Def_CalibratedCE_Forecast_IsDist
import Definitions.Def_CalibratedCE_Forecast_CalibScoreH
import Definitions.Def_CalibratedCE_Forecast_HistLaw
Formal statement
namespace CalibratedCE.Forecast

theorem exists_calibrated_randomized_forecast (n : ℕ) (hn : 0 < n) :
    ∃ F : List ((Fin n → ℝ) × Fin n) → PMF (Fin n → ℝ),
      (∀ h, ∀ p ∈ (F h).support, IsDist p) ∧
      ∀ A : List ((Fin n → ℝ) × Fin n) → PMF (Fin n),
        ∀ ε : ℝ, 0 < ε →
          Filter.Tendsto
            (fun t : ℕ => (histLaw F A t).toOuterMeasure {h | calibScoreH h < ε})
            Filter.atTop (nhds 1) := by sorry

end CalibratedCE.Forecast
Source
Foster and Vohra, Calibrated learning and correlated equilibrium, Games Econ. Behav. 21 (1997), p. 49, Theorem 3 (Foster and Vohra, 1991), Eq. (1); proof in the Appendix, pp. 52–54
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement is about a fixed positive integer nnn. It uses three definitions from its own bundle, IsDist, calibScoreH and histLaw, whose code is not shown here. Below they are described only by the types their use forces on them. What they compute is not visible, and the claim's content depends entirely on them.

Objects involved.

  • A forecast is a vector p∈Rnp \in \mathbb{R}^np∈Rn, meaning a function {0,…,n−1}→R\{0,\dots,n-1\} \to \mathbb{R}{0,…,n−1}→R. Nothing in the types requires it to be nonnegative or to sum to 111.
  • An outcome is an element j∈{0,…,n−1}j \in \{0,\dots,n-1\}j∈{0,…,n−1}.
  • A history hhh is a finite list of pairs (forecast, outcome), h=((p1,j1),…,(pk,jk))h = \big((p_1,j_1),\dots,(p_k,j_k)\big)h=((p1​,j1​),…,(pk​,jk​)). The empty list is allowed.
  • IsDist(p)\mathrm{IsDist}(p)IsDist(p) is a property of a single vector p∈Rnp \in \mathbb{R}^np∈Rn from the bundle. Its definition is not shown.
  • calibScore(h)\mathrm{calibScore}(h)calibScore(h) is a real number attached to each history hhh by the bundle's calibScoreH. Its formula is not shown.
  • histLaw(F,A,t)\mathrm{histLaw}(F, A, t)histLaw(F,A,t) takes a forecasting rule FFF, an outcome rule AAA and a natural number ttt. It returns a probability distribution on histories. It is used with the "outer measure" of a probability mass function, so it is presumably a discrete probability distribution. How it is built from FFF, AAA and ttt is not shown. In particular, the code does not show whether the histories it produces have length exactly ttt, or how the forecast and outcome at each step are drawn.

The claim. Suppose n≥1n \ge 1n≥1. Then there exists a map FFF with the following properties:

  • FFF sends every history hhh to a discrete probability distribution F(h)F(h)F(h) on Rn\mathbb{R}^nRn. It is a probability mass function, so it puts all its mass on at most countably many vectors.
  • Validity of forecasts: for every history hhh whatever, including histories that can never actually occur, every vector ppp with F(h)(p)>0F(h)(p) > 0F(h)(p)>0 satisfies IsDist(p)\mathrm{IsDist}(p)IsDist(p).
  • Calibration: for every map AAA and every real ε>0\varepsilon > 0ε>0,
lim⁡t→∞ Pr⁡h∼histLaw(F,A,t)[ calibScore(h)<ε ]  =  1.\lim_{t\to\infty} \ \Pr_{h \sim \mathrm{histLaw}(F,A,t)}\big[\ \mathrm{calibScore}(h) < \varepsilon\ \big] \;=\; 1 .t→∞lim​ h∼histLaw(F,A,t)Pr​[ calibScore(h)<ε ]=1.

Here AAA sends every history to a probability distribution A(h)A(h)A(h) on the outcomes {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1}.

The probability above is the total mass the distribution histLaw(F,A,t)\mathrm{histLaw}(F,A,t)histLaw(F,A,t) gives to histories whose score is strictly below ε\varepsilonε. Measurability is not an issue because the distribution is discrete. The limit is taken along the natural numbers ttt.

Order of quantifiers. A single FFF is chosen first, and it must work simultaneously for every AAA and every ε>0\varepsilon > 0ε>0. FFF may not depend on AAA or on ε\varepsilonε.

Each of FFF and AAA sees only a history, meaning the list of past (forecast, outcome) pairs. Nothing else is passed to them. How much they "see" in practice depends on how histLaw\mathrm{histLaw}histLaw chains them together, and that is not shown. For example, the code does not show whether AAA sees the forecast realized at the current step.

The only convergence required is convergence of this probability to 111. Nothing is said about any rate, about almost-sure behaviour along a single infinite play, or about the size of calibScore\mathrm{calibScore}calibScore beyond the strict threshold ε\varepsilonε.

Degenerate cases.

  • n=0n = 0n=0: excluded by the hypothesis 0<n0 < n0<n.
  • n=1n = 1n=1: forecasts are single real numbers, and there is exactly one outcome. The only possible AAA always returns the point mass on that outcome. The statement then reduces to the existence of an FFF whose supported values satisfy IsDist\mathrm{IsDist}IsDist and for which the displayed limit holds for that single AAA.
  • Finitely many ttt: the claim says nothing about any particular finite ttt, including t=0t = 0t=0 and whatever histLaw(F,A,0)\mathrm{histLaw}(F,A,0)histLaw(F,A,0) is (possibly the point mass on the empty history). Only the behaviour as t→∞t \to \inftyt→∞ matters.
  • If calibScore\mathrm{calibScore}calibScore is below every ε>0\varepsilon > 0ε>0 on all histories (for example, if it is always ≤0\le 0≤0, or on every history histLaw\mathrm{histLaw}histLaw can produce), the calibration part holds for any FFF. The statement then reduces to the existence of an FFF whose supported forecasts satisfy IsDist\mathrm{IsDist}IsDist. Whether this happens depends on the unshown definition.
  • If IsDist\mathrm{IsDist}IsDist holds for no vector at all, then no distribution F(h)F(h)F(h) can meet the validity condition. A probability mass function always has at least one supported point, so the statement would be false.
  • Junk values inside the definitions: any division by zero or other default value that calibScore\mathrm{calibScore}calibScore produces on some histories (for example on the empty history, or where a count is zero) enters the event {calibScore(h)<ε}\{\mathrm{calibScore}(h) < \varepsilon\}{calibScore(h)<ε} exactly as computed. The code shown does not reveal whether this happens.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me