Proof of Theorem 1, pp. 37–38 — the value loss is at most the optimal value of the linear program (14)
ProvedProviderGuarantee.Bound.lp_boundThroughout, is a finite set of jobs with real values and ; there are providers ; and ; is a set of allocations satisfying Assumption 1, and satisfies Assumption 2. The optimal sets are and . Assume also .
Let denote the optimal value of the linear program (14) (p. 38):
Then
This is the bound the page obtains by solving the fractional program (13) and rescaling it, using that its constraints are homogeneous, into the linear program (14). From here on, the proof of Theorem 1 studies only the linear program, as a function of .
Formalization Note is lpValue γ, the supremum of the objective over the feasible set of (14); the milestone lp_well_posed states that, for , this set is non-empty and the objective is bounded by on it. No hypothesis is needed here: with no provider the loss is and Lean's supremum of the empty set is , so the inequality holds trivially.
Differences from the source:
- reading: the bound is stated on pp. 37–38 'for any F and F_G, given γ' → F satisfies Assumption 1, F_G ⊆ F satisfies Assumption 2, and γ ∈ [γmin, γmax]^n with 0 < γmin ≤ γmax; reason: these are the standing assumptions of §2 (pp. 7–12) under which the appendix works; the proof on pp. 35–36 uses Assumption 1-(ii), (iii), (iv), Assumption 2 and γ_j > 0, and the bound is false without them
- encoding: L_γ(F, F_G) is the ratio (1), which is 0/0 when max_F Σγ_i v(A_i) = 0 → valueLoss uses Lean's division, so the loss is 0 in that case; reason: only the instances where the page's ratio is undefined are affected; no hypothesis 0 < max_F is added
- reading: a set of jobs D (never said to be finite; v(S) is a finite sum and maxima over F are taken) → D a finite type; reason: the page writes v(S) = Σ_{d∈S} v(d) and max over F, which presuppose finitely many jobs; the paper calls D a discrete set of jobs
- encoding: providers N = {1, …, n} → indices i : Fin n (0, …, n−1); reason: Lean convention; a relabelling, same instances
import Mathlib import Definitions.Def_ProviderGuarantee_Bound_Model
namespace ProviderGuarantee.Bound
theorem lp_bound {D : Type*} [Fintype D] [DecidableEq D] {n : ℕ} (v : D → ℝ)
(γmin γmax : ℝ) (hγmin : 0 < γmin) (hγ : γmin ≤ γmax)
(γ : Fin n → ℝ) (hγmem : ∀ i, γ i ∈ Set.Icc γmin γmax)
(F FG : Set (Fin n → Finset D)) (h1 : Assumption1 F) (h2 : Assumption2 v F FG)
(hFG : FG.Nonempty) :
valueLoss γ v F FG ≤ lpValue γ := by sorry
end ProviderGuarantee.Bound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.