Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Lemma A.1, skip step (corrected: = → ≥) — a non-owner process holds at least the owner's previous-iteration inventory

Proved
PicardFO.Fulfill.lemma_A_1_skip_step

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

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

Consider the FO problem with an arbitrary policy π\piπ, initial state s1=(x1,c1)s_1 = (x_1, c_1)s1​=(x1​,c1​), a sequence of orders, and Algorithm 1 with partition by products. Let iii be a product owned by process m′m'm′, and let m≠m′m \ne m'm=m′ be any other process. Write xtk,mx^{k,m}_{t}xtk,m​ for the inventory of process mmm after ttt orders in iteration kkk of Algorithm 1. Then:

  1. in iteration 111 (cache α0≡aϕ\alpha^0 \equiv a_\phiα0≡aϕ​), process mmm consumes no inventory of product iii: xt,i,j1,m=x1,i,jx^{1,m}_{t,i,j} = x_{1,i,j}xt,i,j1,m​=x1,i,j​ for all ttt and jjj;
  2. in every iteration k≥2k \ge 2k≥2, process mmm holds at least as much inventory of product iii as its owner held in the previous iteration:
xt,i,jk,m  ≥  xt,i,jk−1,m′for all t and all nodes j.x^{k,m}_{t,i,j} \;\ge\; x^{k-1,m'}_{t,i,j} \qquad \text{for all } t \text{ and all nodes } j.xt,i,jk,m​≥xt,i,jk−1,m′​for all t and all nodes j.

Process mmm never evaluates π\piπ on orders of product iii; it replays the actions that m′m'm′ took on them in the previous iteration, but only when they are feasible in its own state. This is the case of the induction for Lemma A.1 in which the product of the current order belongs to another process.

Formalization Note Lean's procState … (cache … k) m t is process m after t orders in the paper's iteration k+1k + 1k+1; item 2 is stated for all Lean k ≥ 0, i.e. the paper's iterations k≥2k \ge 2k≥2, and item 1 is the paper's iteration 111 (the paper's "iteration 000" with no order fulfilled). No assumption on π\piπ is used. m ranges over all processes other than the owner, including processes that own no product.

Differences from the source:

  • correction: a^{k,m}t = a^{k−1,m′}t for every order of i_c and x^{k,m}{t,i_c,j} = x^{k−1,m′}{t,i_c,j} → x^{k,m}{t,i,j} ≥ x^{k−1,m′}{t,i,j}; reason: Algorithm 1, line 7, replaces an infeasible cached action by a_φ. Counterexample satisfying every assumption: J = 1, c₁ = 1, products A (process 1) and B (process 2) with ample inventory, orders B then A, π = "fulfil at node 1 when feasible". In iteration 2 process 2 has capacity 0 at A's order, so it does not replay α¹ = 1 there: x^{2,2}{2,A,1} = x{1,A,1} > x^{1,1}{2,A,1} = x{1,A,1} − 1.
  • reading: iteration k − 1 = 0 in the paper's induction ("all orders are not fulfilled") → item 1, process states of iteration 1 equal the initial inventory of i; reason: the paper's base case convention.
  • generalization: processes m ∈ [M] with a partition of [I] → any type of processes and any ownership map, m any process other than the owner; reason: specializes to M processes and a partition.
  • encoding: 1-based times and iterations → 0-based times, cache … k for α^k; reason: Lean convention, same instances.
Preamble
import Mathlib
import Definitions.Def_PicardFO_Fulfill_Model
Formal statement
namespace PicardFO.Fulfill

/-- Proof of Lemma A.1, skip step (p. 12), corrected (`=` → `≥`): a process `m` that does
not own product `i` holds, at every time, at least as much inventory of `i` at every node as
the owner of `i` held in the previous iteration; in the first iteration (cache `α⁰ ≡ aϕ`) it
has not consumed any inventory of `i`. No assumption on `π` is needed. -/
theorem lemma_A_1_skip_step {I J : ℕ} {Ω ι : Type*} (prod : Ω → Fin I)
    (π : State I J → Ω → Option (Fin J)) (s₁ : State I J) (ω : ℕ → Ω) (own : Fin I → ι)
    (m : ι) (i : Fin I) (hm : own i ≠ m) :
    (∀ (t : ℕ) (j : Fin J),
        (procState prod π s₁ ω own (cache prod π s₁ ω own 0) m t).x i j = s₁.x i j) ∧
    (∀ (k t : ℕ) (j : Fin J),
        (procState prod π s₁ ω own (cache prod π s₁ ω own k) (own i) t).x i j ≤
          (procState prod π s₁ ω own (cache prod π s₁ ω own (k + 1)) m t).x i j) := by sorry

end PicardFO.Fulfill
Source
Farias et al., Speeding up Policy Simulation in Supply Chain RL, arXiv:2406.01939v2, p. 12, §A.2.1, proof of Lemma A.1 (case i_c handled by a process m′ ≠ m)
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