Lemma 1 — Transient feasibility and steady state
ProvedMatchingWhileLearning.DEEM.lemma_1Fix the continuum market of §§3.1–3.5: finite nonempty type sets, positive normalized worker proportions, positive finite real-job capacities, an unlimited empty job, and a known distinct-row reward matrix in . Let and let a WHO policy satisfy the steady-state capacity constraints (14). Starting from the empty system with cohorts of mass , the implied assignment respects every capacity at every time , with probability one. Its profile equals its steady-state profile at every time . The formal statement uses the exact deterministic population profiles supplied by the paper's ELLN representation, so the capacity inequality is exact.
Differences from the source:
- encoding: arbitrary finite type sets with probability vectors and a dummy job of infinite capacity → finite Lean types, published finite probability distributions, and no capacity constraint at the dummy job; reason: the same markets are represented and no expression zero times infinity is introduced
- encoding: chronological histories up to N-1 and continuum masses from the exact law of large numbers → newest-first lists, policies extended to all finite lists, and the exact deterministic history-mass recursion; reason: reversal and arbitrary extension are bijective on the used histories; the recursion is the source population profile, not a finite-worker approximation
- generalization: the standing generalized imbalance assumption in Section 3.1 → no Imbalance hypothesis for this result; reason: the transient profile is a nonnegative truncation of the steady profile, so the full capacity and steady-state conclusions hold without imbalance
import Definitions.Def_MatchingWhileLearning_DEEM_Stopping open scoped BigOperators ENNReal open Filter MeasureTheory ProbabilityTheory open MatchingWhileLearning.DEEM
namespace MatchingWhileLearning.DEEM
theorem lemma_1 {I J : Type} [Fintype I] [Fintype J] [DecidableEq I] [DecidableEq J]
[Nonempty I] (M : MatchingWhileLearning.DEEM.Model I J) (N : ℕ) (hN : 0 < N) (pi : Policy J) (hpi : Feasible M N pi) :
(∀ t j, j ≠ M.kappa →
(∑ i, ∑ k ∈ Finset.range N, ∑ h ∈ histories k,
transient M N pi t h i * (pi h).prob j) ≤ M.capacity j) ∧
(∀ t, N - 1 ≤ t → ∀ k, k < N → ∀ h ∈ histories k, ∀ i,
transient M N pi t h i = nu M N pi h i) := by sorry
end MatchingWhileLearning.DEEM
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is a nonempty finite set and a finite set.
- is a model: with ; ; for ; with and distinct rows.
- with .
- is a policy: a probability distribution on for every finite history of observations .
Definitions used.
- or according to .
- is the set of histories of length , with the head treated as the newest observation.
- , with oldest to newest.
- The transient is defined by recursion: ; for nonempty ; and . Unfolded, if has length and otherwise.
- Hypothesis (feasibility). For every ,
Conclusion 1. For every (unrestricted) and every ,
Conclusion 2. For every , every , every and every ,
Degenerate cases.
- is excluded.
- is natural-number subtraction, but with it is ordinary.
- At , conclusion 2 concerns all and only the empty history.
- At , conclusion 1 involves only the empty history (all others have ).
- No condition is placed on , and is excluded from conclusion 1.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.