Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — Transient feasibility and steady state

Proved
MatchingWhileLearning.DEEM.lemma_1

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmsoperations-researchp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability

Fix 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 [0,1][0,1][0,1]. Let N>0N>0N>0 and let a WHO policy satisfy the steady-state capacity constraints (14). Starting from the empty system with cohorts of mass ρi/N\rho_i/Nρi​/N, the implied assignment respects every capacity at every time t≥0t\ge0t≥0, with probability one. Its profile equals its steady-state profile at every time t≥N−1t\ge N-1t≥N−1. 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
Preamble
import Definitions.Def_MatchingWhileLearning_DEEM_Stopping

open scoped BigOperators ENNReal
open Filter MeasureTheory ProbabilityTheory
open MatchingWhileLearning.DEEM
Formal statement
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
Source
Johari, Kamble, Kanoria, Matching While Learning, arXiv:1603.04549v7, https://arxiv.org/abs/1603.04549v7, Lemma 1, p. 17 (PDF p. 17)
Read-back

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

Setting.

  • III is a nonempty finite set and JJJ a finite set.
  • MMM is a model: ρi>0\rho_i>0ρi​>0 with ∑ρi=1\sum\rho_i=1∑ρi​=1; κ∈J\kappa\in Jκ∈J; cj>0c_j>0cj​>0 for j≠κj\ne\kappaj=κ; rij∈[0,1]r_{ij}\in[0,1]rij​∈[0,1] with riκ=0r_{i\kappa}=0riκ​=0 and distinct rows.
  • N∈NN\in\mathbb NN∈N with N>0N>0N>0.
  • π\piπ is a policy: a probability distribution π(⋅∣h)\pi(\cdot\mid h)π(⋅∣h) on JJJ for every finite history hhh of observations (j,b)(j,b)(j,b).

Definitions used.

  • ϕi(j,b)=rij\phi_i(j,b)=r_{ij}ϕi​(j,b)=rij​ or 1−rij1-r_{ij}1−rij​ according to bbb.
  • Hk\mathcal H_kHk​ is the set of histories of length kkk, with the head treated as the newest observation.
  • ν(h,i)=ρiN∏s=1kπ(js∣h≤s−1)ϕi(os)\nu(h,i)=\frac{\rho_i}{N}\prod_{s=1}^k\pi(j_s\mid h_{\le s-1})\phi_i(o_s)ν(h,i)=Nρi​​∏s=1k​π(js​∣h≤s−1​)ϕi​(os​), with o1,…,oko_1,\dots,o_ko1​,…,ok​ oldest to newest.
  • The transient τt(h,i)\tau_t(h,i)τt​(h,i) is defined by recursion: τt(∅,i)=ρi/N\tau_t(\varnothing,i)=\rho_i/Nτt​(∅,i)=ρi​/N; τ0(h,i)=0\tau_0(h,i)=0τ0​(h,i)=0 for nonempty hhh; and τt+1(o::h,i)=τt(h,i) π(j∣h) ϕi(o)\tau_{t+1}(o::h,i)=\tau_t(h,i)\,\pi(j\mid h)\,\phi_i(o)τt+1​(o::h,i)=τt​(h,i)π(j∣h)ϕi​(o). Unfolded, τt(h,i)=ν(h,i)\tau_t(h,i)=\nu(h,i)τt​(h,i)=ν(h,i) if hhh has length ≤t\le t≤t and 000 otherwise.
  • Hypothesis (feasibility). For every j≠κj\ne\kappaj=κ,
∑iρiRij≤cj,Rij=1ρi∑k<N∑h∈Hkν(h,i)π(j∣h).\sum_i\rho_i R_{ij}\le c_j,\qquad R_{ij}=\frac1{\rho_i}\sum_{k<N}\sum_{h\in\mathcal H_k}\nu(h,i)\pi(j\mid h).i∑​ρi​Rij​≤cj​,Rij​=ρi​1​k<N∑​h∈Hk​∑​ν(h,i)π(j∣h).

Conclusion 1. For every t∈Nt\in\mathbb Nt∈N (unrestricted) and every j≠κj\ne\kappaj=κ,

∑i∈I∑k=0N−1∑h∈Hkτt(h,i) π(j∣h)≤cj.\sum_{i\in I}\sum_{k=0}^{N-1}\sum_{h\in\mathcal H_k}\tau_t(h,i)\,\pi(j\mid h)\le c_j .i∈I∑​k=0∑N−1​h∈Hk​∑​τt​(h,i)π(j∣h)≤cj​.

Conclusion 2. For every t≥N−1t\ge N-1t≥N−1, every k<Nk<Nk<N, every h∈Hkh\in\mathcal H_kh∈Hk​ and every iii,

τt(h,i)=ν(h,i).\tau_t(h,i)=\nu(h,i).τt​(h,i)=ν(h,i).

Degenerate cases.

  • N=0N=0N=0 is excluded.
  • N−1N-1N−1 is natural-number subtraction, but with N≥1N\ge1N≥1 it is ordinary.
  • At N=1N=1N=1, conclusion 2 concerns all t≥0t\ge0t≥0 and only the empty history.
  • At t=0t=0t=0, conclusion 1 involves only the empty history (all others have τ0=0\tau_0=0τ0​=0).
  • No condition is placed on cκc_\kappacκ​, and j=κj=\kappaj=κ is excluded from conclusion 1.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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