Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2 (corrected: a node runs out when its capacity is no longer positive) — Picard iteration for fulfillment converges in at most |Q_T| + 1 iterations

Proved
PicardFO.Fulfill.theorem_3_2

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

convergencefulfillmentp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1picard-iterationpolicy-simulation

Consider the fulfillment optimization problem with III products, JJJ nodes, real initial inventories x1∈RI×Jx_1 \in \mathbb R^{I \times J}x1​∈RI×J and capacities c1∈RJc_1 \in \mathbb R^{J}c1​∈RJ, a sequence of orders ω1,ω2,…\omega_1, \omega_2, \dotsω1​,ω2​,… for products i(ωt)i(\omega_t)i(ωt​), and a feasible policy π\piπ satisfying Inventory Independence, Consistency and Monotonicity (Assumptions 1–3). Run Algorithm 1 (the Picard iteration) with the time steps partitioned by products: each product is owned by one process, and order ttt is handled by the owner of i(ωt)i(\omega_t)i(ωt​). Let atseqa^{\mathrm{seq}}_tatseq​ be the actions of the sequential run and αtk\alpha^k_tαtk​ the cache after iteration kkk. Fix a horizon TTT and let

QT={ j∈[J]:c1,j>0 and ct,jseq≤0 for some t∈[T] }Q_T = \{\, j \in [J] : c_{1,j} > 0 \text{ and } c^{\mathrm{seq}}_{t,j} \le 0 \text{ for some } t \in [T] \,\}QT​={j∈[J]:c1,j​>0 and ct,jseq​≤0 for some t∈[T]}

be the set of nodes that run out of capacity in the sequential run. Then:

  1. for every iteration k≥∣QT∣+1k \ge |Q_T| + 1k≥∣QT​∣+1,
αtk=atseqfor all t∈[T];\alpha^k_t = a^{\mathrm{seq}}_t \qquad \text{for all } t \in [T];αtk​=atseq​for all t∈[T];
  1. whenever the convergence test of Algorithm 1 succeeds at an iteration k≥1k \ge 1k≥1, that is αtk=αtk−1\alpha^k_t = \alpha^{k-1}_tαtk​=αtk−1​ for all t∈[T]t \in [T]t∈[T], the returned cache is the sequential action sequence: αtk=atseq\alpha^k_t = a^{\mathrm{seq}}_tαtk​=atseq​ for all t∈[T]t \in [T]t∈[T].

The number of Picard iterations needed is thus bounded by one more than the number of nodes that run out of capacity, independently of the horizon TTT and of the number of products and processes. Since each iteration evaluates the policy on max⁡m∣Tm∣\max_m |T_m|maxm​∣Tm​∣ orders per process in parallel, this bound is what turns the Picard iteration into a speed-up of policy simulation for fulfillment.

Formalization Note Actions are Option (Fin J) (none is the paper's action 0=aϕ0 = a_\phi0=aϕ​); orders are 0-based (Lean order t < T is the paper's order t+1∈[T]t + 1 \in [T]t+1∈[T]); Q … T is the paper's QTQ_TQT​ computed over the sequential states s1,…,sTs_1, \dots, s_Ts1​,…,sT​ (the state after the last order is not included); cache … k is αk\alpha^kαk; processes are an arbitrary type ι with ownership map own. Runs are defined for all orders, and the horizon enters only through Q … T and t < T; no step of Algorithm 1 at order ttt depends on later orders.

Differences from the source:

  • correction: 𝒬_T = |{j : τ_j ≤ T}| with τ_j = min{t : c^{seq}{t,j} = 0} → |{j : c{1,j} > 0, c^{seq}_{t,j} ≤ 0 for some t ∈ [T]}|; reason: as printed the theorem is false over the paper's real capacities. Counterexample satisfying every assumption: J = 1, products A, B owned by two processes, x₁ = 3 for both at node 1, c₁ = 3/2, orders A, B, A, π = "node 1 if feasible, else 0": sequential capacities 3/2, 1/2, −1/2 are never 0, so 𝒬_T = 0, but a^{seq} = (1, 1, 0) and α¹ = (1, 1, 1). On integer data the corrected Q_T is contained in the printed one, so the corrected statement implies the printed one there.
  • reading: Assumption 2 with j′ arbitrary → j′ ≠ π((x, c), ω); reason: read literally only the never-fulfilling policy satisfies it (a policy choosing j would have to keep choosing j after c_j is set to 0), which makes the theorem vacuous; the chosen reading is the weaker hypothesis.
  • reading: Assumption 3's first clause for every decision j → for decisions j ∈ [J]; second clause for every decision including 0; reason: e_{i,0} is undefined.
  • reading: "converges in at most 𝒬_T + 1 iterations" → the cache equals a^{seq} on [T] in every iteration k ≥ |Q_T| + 1, and the cache returned by the convergence test is a^{seq}; reason: the sense used in the paper (proof of Proposition 2.1, p. 12, "setting k = T"); the test of line 10 needs one more iteration to observe convergence.
  • generalization: M processes and a partition of [I] → any type of processes and any ownership map (processes may own no product); reason: specializes to ι = Fin M and a partition.
  • encoding: action set {0} ∪ [J], 1-based orders, finite disturbance sequence {ω_t : t ∈ [T]} → Option (Fin J), 0-based orders, ω : ℕ → Ω with t < T; reason: Lean convention, same instances (later orders never influence earlier steps).
Preamble
import Mathlib
import Definitions.Def_PicardFO_Fulfill_Model
Formal statement
namespace PicardFO.Fulfill

/-- Theorem 3.2 (p. 6), corrected (a node runs out when its capacity is no longer positive):
for a feasible policy satisfying Assumptions 1–3, the cache of Algorithm 1 (partition by
products) equals the sequential actions on the first `T` orders in every iteration
`k ≥ |Q_T| + 1`; and whenever the convergence test of line 10 succeeds at an iteration
`k ≥ 1`, the returned cache is the sequential one. -/
theorem theorem_3_2 {I J : ℕ} {Ω ι : Type*} (prod : Ω → Fin I)
    (π : State I J → Ω → Option (Fin J)) (s₁ : State I J) (ω : ℕ → Ω) (own : Fin I → ι)
    (hfeas : PolicyFeasible prod π) (h1 : InvIndep prod π) (h2 : Consistent prod π)
    (h3 : MonotonePolicy prod π) (T : ℕ) :
    (∀ k : ℕ, (Q prod π s₁ ω T).card + 1 ≤ k →
        ∀ t < T, cache prod π s₁ ω own k t = seqAct prod π s₁ ω t) ∧
    (∀ k : ℕ, 1 ≤ k →
        (∀ t < T, cache prod π s₁ ω own k t = cache prod π s₁ ω own (k - 1) t) →
        ∀ t < T, cache prod π s₁ ω own k t = seqAct prod π s₁ ω t) := by sorry

end PicardFO.Fulfill
Source
Farias et al., Speeding up Policy Simulation in Supply Chain RL, arXiv:2406.01939v2, p. 6, Theorem 3.2 (with §3.1, p. 5, for τ_j and Q_t; proof in App. A.2, pp. 12–13)
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 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