Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, pp. 38–39 — f(γ), the optimal value of the dual (16), is quasiconvex on [γmin, γmax]^n with values in [0, 1]

Proved
ProviderGuarantee.Bound.dualValue_quasiconvexOn

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

linear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1provider-guaranteesquasiconvexity

Let 0<γmin⁡≤γmax⁡0 < \gamma_{\min} \le \gamma_{\max}0<γmin​≤γmax​ and let f(γ)f(\gamma)f(γ) be the optimal value of the dual problem (15), equivalently (16), of p. 38. Then fff maps the box [γmin⁡,γmax⁡]n[\gamma_{\min}, \gamma_{\max}]^n[γmin​,γmax​]n into [0,1][0, 1][0,1], and fff is quasiconvex on it: for every t∈Rt \in \mathbb Rt∈R the sublevel set

{γ∈[γmin⁡,γmax⁡]n:f(γ)≤t}\{\gamma \in [\gamma_{\min}, \gamma_{\max}]^n : f(\gamma) \le t\}{γ∈[γmin​,γmax​]n:f(γ)≤t}

is convex.

The page argues that each term of the objective of (16) is quasiconvex jointly in (γ,λ)(\gamma, \lambda)(γ,λ), that its feasible region is convex in (γ,λ)(\gamma, \lambda)(γ,λ), and that minimizing over λ\lambdaλ preserves quasiconvexity. Quasiconvexity is what reduces the maximization of fff over the box to its vertices.

Formalization Note fff is dualValue, and quasiconvexity is Mathlib's QuasiconvexOn (convex sublevel sets) on the box Set.Icc (fun _ => γmin) (fun _ => γmax).

Differences from the source:

  • encoding: f(γ) is the optimal value of problem (16) → dualValue γ, the infimum of s over the feasible (s, λ) of (15); reason: (16) is (15) with s eliminated (p. 38: 'Problem (15) in turn can be rewritten as'); dividing the first two families of constraints of (15) by γ_i, γ_k > 0 gives the max in (16), so the values coincide
  • encoding: 'f(γ) : [γmin, γmax]^n → [0, 1]' and 'f(γ) must be quasiconvex in γ' → 0 ≤ dualValue γ ≤ 1 on the box, and QuasiconvexOn ℝ (box) dualValue; reason: Mathlib's quasiconvexity is convexity of every sublevel set, the standard definition
Preamble
import Mathlib
import Definitions.Def_ProviderGuarantee_Bound_Model
Formal statement
namespace ProviderGuarantee.Bound

theorem dualValue_quasiconvexOn {n : ℕ} (γmin γmax : ℝ) (hγmin : 0 < γmin) (hγ : γmin ≤ γmax) :
    QuasiconvexOn ℝ (Set.Icc (fun _ : Fin n => γmin) (fun _ => γmax)) dualValue ∧
    ∀ γ ∈ Set.Icc (fun _ : Fin n => γmin) (fun _ => γmax),
      0 ≤ dualValue γ ∧ dualValue γ ≤ 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), pp. 38–39, proof of Theorem 1, (16)
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