Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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]

Proved
ProviderGuarantee.Bound.lp_well_posed

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

linear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1provider-guarantees

Let n≥1n \ge 1n≥1 and let γ∈Rn\gamma \in \mathbb R^nγ∈Rn have positive entries. Consider the linear program (14) of p. 38 in the variables x,y∈Rnx, y \in \mathbb R^nx,y∈Rn and w∈Rn×nw \in \mathbb R^{n\times n}w∈Rn×n: maximize ∑iγixi−∑iγiyi+∑i∑jwij(γi−γj)\sum_i \gamma_i x_i - \sum_i \gamma_i y_i + \sum_i \sum_j w_{ij}(\gamma_i - \gamma_j)∑i​γi​xi​−∑i​γi​yi​+∑i​∑j​wij​(γi​−γj​) subject to ∑iγixi+∑i∑jwijγi=1\sum_i \gamma_i x_i + \sum_i \sum_j w_{ij}\gamma_i = 1∑i​γi​xi​+∑i​∑j​wij​γi​=1, xi+wij−∑kwkj−yj≤0x_i + w_{ij} - \sum_k w_{kj} - y_j \le 0xi​+wij​−∑k​wkj​−yj​≤0 for all i,ji, ji,j, and x,y,w≥0x, y, w \ge 0x,y,w≥0. Then:

  1. the program has a feasible point;
  2. every feasible point has objective value at most 111:
∑i=1nγixi−∑i=1nγiyi+∑i=1n∑j=1nwij(γi−γj)≤1;\sum_{i=1}^n \gamma_i x_i - \sum_{i=1}^n \gamma_i y_i + \sum_{i=1}^n \sum_{j=1}^n w_{ij}(\gamma_i - \gamma_j) \le 1;i=1∑n​γi​xi​−i=1∑n​γi​yi​+i=1∑n​j=1∑n​wij​(γi​−γj​)≤1;
  1. its optimal value V(γ)V(\gamma)V(γ) satisfies 0≤V(γ)≤10 \le V(\gamma) \le 10≤V(γ)≤1.

The page states that (14) is a linear program with an objective bounded above by 111, and uses this to invoke strong duality; feasibility and the range [0,1][0,1][0,1] make the optimal value a well-defined number (the page's f(γ):[γmin⁡,γmax⁡]n→[0,1]f(\gamma) : [\gamma_{\min}, \gamma_{\max}]^n \to [0, 1]f(γ):[γmin​,γmax​]n→[0,1], p. 38).

Formalization Note V(γ)V(\gamma)V(γ) 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
  • 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