The inventory-balancing dual certificate is feasible for
ProvedPersonalizedAssortment.IB.dual_certificate_feasibleLet and , let , and let be a penalty function ( increasing, , ). Let be an inventory-balancing selection rule. Consider any inventory path , compared coordinatewise. Define
Then is feasible for :
- for every period and every ;
- for every product .
Every realized path of the inventory process is non-increasing and starts at , so the certificate is dual feasible with probability one. The certificate is what links the algorithm to the benchmark LP.
Formalization Note The paper writes the chain of inequalities only at . Feasibility means every constraint holds, and that is what is stated.
import Mathlib import Definitions.Def_PersonalizedAssortment_IB_ChoiceModel import Definitions.Def_PersonalizedAssortment_IB_PenaltyFunction import Definitions.Def_PersonalizedAssortment_IB_PrimalLP import Definitions.Def_PersonalizedAssortment_IB_InventoryBalancing
namespace PersonalizedAssortment.IB
/-- §A.3, p. 1548: along any inventory path `c = I 0 ≥ I 1 ≥ ⋯ ≥ I T` on which the
inventory-balancing rule is followed, `θ_i = r_i (1 - Ψ(I_i^T/c_i))` and
`λ^t = ∑_{i ∈ S^t} r_i Ψ(I_i^{t-1}/c_i) φ_i^{z_t}(S^t)` form a feasible solution of
`Dual({z_t})`: every constraint, for every period and every `S ∈ 𝒮`, holds. -/
theorem dual_certificate_feasible {n : ℕ} {Z : Type*} (r : Fin n → ℝ) (hr : ∀ i, 0 < r i)
(c : Fin n → ℕ) (hc : ∀ i, 0 < c i) (𝒮 : Finset (Finset (Fin n))) (h𝒮 : ∅ ∈ 𝒮)
(φ : Z → ChoiceModel n) (Ψ : ℝ → ℝ) (hΨ : IsPenaltyFunction Ψ) {T : ℕ} (z : Fin T → Z)
(sel : Fin T → (Fin n → ℕ) → Finset (Fin n)) (hsel : IsIBRule Ψ r c 𝒮 φ z sel)
(I : ℕ → Fin n → ℕ) (hI0 : I 0 = c) (hmono : ∀ t < T, ∀ i, I (t + 1) i ≤ I t i) :
DualFeasible r 𝒮 φ z (fun t => lamIB Ψ r c φ z sel t (I t.val)) (thetaIB Ψ r c (I T)) := by sorry
end PersonalizedAssortment.IB
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data.
- Products are and periods are .
- and (natural) for every .
- is a finite family of subsets of containing .
- assigns to each a choice model (nonnegative , zero for , with ).
- .
Penalty hypothesis. maps into , is nondecreasing on , and has and .
Selection hypothesis. maps each period and each vector to a set . For every and every :
- ;
- maximizes over ;
- every maximizer in has at least as many elements as .
Path hypothesis. is a sequence of vectors in with and for every and every . The path is not required to be generated by , nor to decrease by at most one per step.
Conclusion. Define
The statement asserts:
- for every period and every , ;
- for every .
Degenerate cases.
- If , only is asserted. Here .
- If , the claim is for each .
- The hypothesis makes nonempty, so the selection hypothesis is satisfiable.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.