Proof of Theorem 1, p. 39 — a quasiconvex function on a box is dominated at each point by its value at some vertex
ProvedProviderGuarantee.Bound.quasiconvexOn_box_vertexextreme-pointshypercubep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quasiconvexity
Let and let be quasiconvex on the box . Then for every there is a vertex of the box, i.e. a point with for every , such that
Consequently, to find 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 with and .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.