Proof of Theorem 1, p.23 —
ProvedMultiStageAlloc.regPoly_ge_selfbatchingcompetitive-analysisconvex-programmingonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dual
For all and ,
The proof of Theorem 1 uses this for inequality (1) at the last stage.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_MultiStageAlloc_Regularizers
Formal statement
namespace MultiStageAlloc
/-- **`f_s(x) ≥ x`.** Feng & Niazadeh, arXiv:2211.16581v1, proof of Theorem 1, p.23: "`f_s(x) ≥ x` for
all `x ∈ [0, 1]` and `s ∈ [K - 1]`". -/
theorem regPoly_ge_self (K s : ℕ) (hs1 : 1 ≤ s) (hsK : s < K) (x : ℝ)
(hx : x ∈ Set.Icc (0 : ℝ) 1) : x ≤ regPoly K s x := by sorry
end MultiStageAlloc
Source
Feng & Niazadeh, Batching and Optimal Multi-stage Bipartite Allocations, arXiv:2211.16581v1, proof of Theorem 1, p.23, "the fact that fs(x) ≥ x for all x ∈ [0, 1] and s ∈ [K − 1]"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.