Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (5) (corrected Q_{t_c}: capacity no longer positive) — a process's own decision is sequential, or goes to a node of Q_{t_c}, or to a node where it holds more inventory

Proved
PicardFO.Fulfill.eq_5

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

fulfillmentmonotonicityp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1picard-iteration

Let π\piπ be a feasible FO policy satisfying Inventory Independence, Consistency and Monotonicity, and run Algorithm 1 with partition by products. Fix an iteration k≥1k \ge 1k≥1 and an order ttt for product i=i(ωt)i = i(\omega_t)i=i(ωt​), and let mmm be the process owning iii. Let (xtk,m,ctk,m)(x^{k,m}_t, c^{k,m}_t)(xtk,m​,ctk,m​) be the state of process mmm just before order ttt and (xtseq,ctseq)(x^{\mathrm{seq}}_t, c^{\mathrm{seq}}_t)(xtseq​,ctseq​) the sequential state just before order ttt. Then the decision atk,m=π((xtk,m,ctk,m),ωt)a^{k,m}_t = \pi\bigl((x^{k,m}_t, c^{k,m}_t), \omega_t\bigr)atk,m​=π((xtk,m​,ctk,m​),ωt​) satisfies

atk,m∈{atseq} ∪ Qt ∪ { j∉Qt:xt,i,jk,m>xt,i,jseq },a^{k,m}_t \in \{a^{\mathrm{seq}}_t\} \,\cup\, Q_t \,\cup\, \{\, j \notin Q_t : x^{k,m}_{t,i,j} > x^{\mathrm{seq}}_{t,i,j} \,\},atk,m​∈{atseq​}∪Qt​∪{j∈/Qt​:xt,i,jk,m​>xt,i,jseq​},

where QtQ_tQt​ is the set of nodes with positive initial capacity whose sequential capacity is no longer positive in one of the states s1,…,sts_1, \dots, s_ts1​,…,st​ (up to and including the state before order ttt).

So even a wrong decision either goes to a node that has run out sequentially, or uses a unit of inventory that the process holds in excess of the sequential run; in both cases the inventory dominance of Lemma A.1 survives the update.

Formalization Note Lean order t is the paper's order tc=t+1t_c = t + 1tc​=t+1; seqState … t and procState … (cache … k) m t are the states before that order (the appendix's xtc−1x_{t_c - 1}xtc​−1​), and the paper's QtcQ_{t_c}Qtc​​ is Q … (t + 1). cache … k is αk\alpha^kαk, so the process states are those of the paper's iteration k+1k + 1k+1; Lean's k ranges over all of ℕ. The statement is unconditional: no induction hypothesis is assumed.

Differences from the source:

  • correction: Q_{t_c} = {j | τ_j ≤ t_c} with τ_j = min{t : c^{seq}{t,j} = 0} → Q{t_c} = {j : c_{1,j} > 0, c^{seq}_{t,j} ≤ 0 for some t ≤ t_c}; reason: over ℝ a capacity can jump from positive to negative without being 0. 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": in iteration 1 process A chooses node 1 at the third order (its capacity is 1/2), while a^{seq} = 0, the printed Q is empty, and its inventory of A at node 1 (2) equals the sequential one (2).
  • generalization: the claim inside the induction at k = k_c, t = t_c → every iteration and every order, without the induction hypothesis; reason: the statement holds unconditionally and specializes to the induction step.
  • generalization: processes m ∈ [M] with a partition of [I] → any type of processes and any ownership map; reason: specializes to ι = Fin M and a partition.
  • encoding: 1-based orders, state x_{t_c−1} before order t_c → 0-based order t = t_c − 1 with the state before it, Q … (t + 1) for Q_{t_c}; reason: Lean convention, same instances.
  • reading: Assumption 2 with j′ arbitrary → j′ ≠ π((x, c), ω); reason: read literally only the never-fulfilling policy satisfies it, which makes the statement 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.
Preamble
import Mathlib
import Definitions.Def_PicardFO_Fulfill_Model
Formal statement
namespace PicardFO.Fulfill

/-- Eq. (5) (p. 13): when the process `m` owning the product of order `t` evaluates `π` at
order `t` (in any iteration, with cache `cache … k`), its decision is the sequential one, or a
node of `Q_{t+1}` (exhausted in the sequential run by the state before order `t`), or a node
outside `Q_{t+1}` where the process holds strictly more inventory of that product than the
sequential run before order `t`. -/
theorem eq_5 {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 π)
    (k t : ℕ) (m : ι) (hm : own (prod (ω t)) = m) (s : State I J)
    (hs : s = procState prod π s₁ ω own (cache prod π s₁ ω own k) m t) :
    π s (ω t) = seqAct prod π s₁ ω t ∨
      ∃ j, π s (ω t) = some j ∧
        (j ∈ Q prod π s₁ ω (t + 1) ∨
          (j ∉ Q prod π s₁ ω (t + 1) ∧
            (seqState prod π s₁ ω t).x (prod (ω t)) j < s.x (prod (ω t)) j)) := by sorry

end PicardFO.Fulfill
Source
Farias et al., Speeding up Policy Simulation in Supply Chain RL, arXiv:2406.01939v2, p. 13, eq. (5), proof of Lemma A.1
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