Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, p. 39 — a quasiconvex function on a box is dominated at each point by its value at some vertex

Proved
ProviderGuarantee.Bound.quasiconvexOn_box_vertex

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

extreme-pointshypercubep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quasiconvexity

Let a,b∈Rna, b \in \mathbb R^na,b∈Rn and let f:Rn→Rf : \mathbb R^n \to \mathbb Rf:Rn→R be quasiconvex on the box [a,b]={x:ai≤xi≤bi for all i}[a, b] = \{x : a_i \le x_i \le b_i \text{ for all } i\}[a,b]={x:ai​≤xi​≤bi​ for all i}. Then for every x∈[a,b]x \in [a, b]x∈[a,b] there is a vertex yyy of the box, i.e. a point with yi∈{ai,bi}y_i \in \{a_i, b_i\}yi​∈{ai​,bi​} for every iii, such that

f(x)≤f(y).f(x) \le f(y).f(x)≤f(y).

Consequently, to find max⁡γ∈[γmin⁡,γmax⁡]nf(γ)\max_{\gamma \in [\gamma_{\min}, \gamma_{\max}]^n} f(\gamma)maxγ∈[γmin​,γmax​]n​f(γ) one need only look at the extreme points of the hypercube. The page cites Bertsekas et al. (2003) for this fact and applies it to the dual value fff with a=(γmin⁡,…,γmin⁡)a = (\gamma_{\min}, \dots, \gamma_{\min})a=(γmin​,…,γmin​) and b=(γmax⁡,…,γmax⁡)b = (\gamma_{\max}, \dots, \gamma_{\max})b=(γmax​,…,γmax​).

Differences from the source:

  • generalization: the hypercube [γmin, γmax]^n and the function f → any box [a, b] ⊆ ℝ^n and any function quasiconvex on it; reason: the page invokes a general fact (cited to Bertsekas et al. 2003); taking a = γmin·1, b = γmax·1 and f = dualValue gives the page's use
  • reading: 'we need only to look at the extreme points of the hypercube' → every point of the box is dominated in value by some vertex; reason: this is the precise content of the reduction: the maximum over the box equals the maximum over the vertices
Preamble
import Mathlib
import Definitions.Def_ProviderGuarantee_Bound_Model
Formal statement
namespace ProviderGuarantee.Bound

theorem quasiconvexOn_box_vertex {n : ℕ} (a b : Fin n → ℝ) (f : (Fin n → ℝ) → ℝ)
    (hf : QuasiconvexOn ℝ (Set.Icc a b) f) :
    ∀ x ∈ Set.Icc a b, ∃ y ∈ Set.Icc a b, (∀ i, y i = a i ∨ y i = b i) ∧ f x ≤ f y := 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. 39, proof of Theorem 1 (citing Bertsekas, Nedić and Ozdaglar 2003)
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