Proof of Theorem 1, p. 38 — the linear program (14) is feasible, its objective is at most 1, and its value lies in [0, 1]
ProvedProviderGuarantee.Bound.lp_well_posedlinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1provider-guarantees
Let and let have positive entries. Consider the linear program (14) of p. 38 in the variables and : maximize subject to , for all , and . Then:
- the program has a feasible point;
- every feasible point has objective value at most :
- its optimal value satisfies .
The page states that (14) is a linear program with an objective bounded above by , and uses this to invoke strong duality; feasibility and the range make the optimal value a well-defined number (the page's , p. 38).
Formalization Note is lpValue γ, a real supremum; items 1 and 2 show it is the supremum of a non-empty bounded set rather than a default value.
Differences from the source:
- generalization: γ ∈ [γmin, γmax]^n with 0 < γmin → any γ with γ_i > 0 for every i; reason: every γ in the box has positive entries, so the Lean statement specializes to the page's
- reading: N = {1, …, n}, a set of n service providers → 0 < n; reason: with no provider the program (14) is infeasible (its normalization reads 0 = 1), so its value is not defined; the page's LP statements presuppose n ≥ 1
- reading: '(14) is a linear program … with an objective function bounded above by 1' → (14) has a feasible point, its objective is ≤ 1 on the feasible set, and 0 ≤ value ≤ 1; reason: the page's appeal to strong duality and its f(γ) : [γmin, γmax]^n → [0, 1] (p. 38) presuppose a feasible program with value in [0, 1]; stating them keeps the real supremum from being a default value
Preamble
import Mathlib import Definitions.Def_ProviderGuarantee_Bound_Model
Formal statement
namespace ProviderGuarantee.Bound
theorem lp_well_posed {n : ℕ} (hn : 0 < n) (γ : Fin n → ℝ) (hγ : ∀ i, 0 < γ i) :
(∃ x y : Fin n → ℝ, ∃ w : Fin n → Fin n → ℝ, PrimalFeasible γ x y w) ∧
(∀ (x y : Fin n → ℝ) (w : Fin n → Fin n → ℝ), PrimalFeasible γ x y w →
primalObj γ x y w ≤ 1) ∧
0 ≤ lpValue γ ∧ lpValue γ ≤ 1 := by sorry
end ProviderGuarantee.Bound
Source
Gur, Iancu & Warnes, Value Loss in Allocation Systems with Provider Guarantees, SSRN 3351509 (version of March 24, 2020), p. 38, proof of Theorem 1, (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.