Equation (5), p. 1458 — feasible substitution in the relaxation
ProvedCorreaThreshold.Nonadaptive.eq_5bernoulli-selectionmultilinear-relaxationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and put . Substituting these probabilities into (4) gives
This value is at most the optimum of (P). The formula identifies the auxiliary factor that the analytic lemmas bound.
Formalization Note As on the page, is an optimum of the feasible linear problem in (3), with and . All denominators are positive on that box.
Preamble
import Mathlib import Definitions.Def_CorreaThreshold_Nonadaptive_Bernoulli
Formal statement
namespace CorreaThreshold.Nonadaptive
/-- Substitution in (4) yields (5) and a feasible lower bound on (P). -/
theorem eq_5 {n : ℕ} [NeZero n] (q b z : Fin n → ℝ)
(hq : ∀ i, 0 ≤ q i ∧ q i ≤ 1)
(hz : ∀ i, 0 ≤ z i ∧ z i ≤ q i)
(hzsum : (∑ i, z i) ≤ 1)
(hopt : ∀ w : Fin n → ℝ, (∀ i, 0 ≤ w i ∧ w i ≤ q i) →
(∑ i, w i) ≤ 1 → (∑ i, b i * w i) ≤ (∑ i, b i * z i)) :
objFour b (fun i => 2 * z i / (2 + (Real.exp 1 - 2) * z i)) =
∑ i : Fin n, b i * z i * (2 / (2 + (Real.exp 1 - 2) * z i)) *
fM (Finset.univ.erase i) z ∧
(∑ i : Fin n, b i * z i * (2 / (2 + (Real.exp 1 - 2) * z i)) *
fM (Finset.univ.erase i) z) ≤ objP q b := by sorry
end CorreaThreshold.Nonadaptive
Source
Correa, Foncea, Hoeksma, Oosterwijk, Vredeveld, Posted price mechanisms and optimal threshold strategies for random arrivals, Math. Oper. Res. 46 (2021), p. 1458, (5); https://doi.org/10.1287/moor.2020.1105
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.