Proposition 2 — at a worst case of (5), is constant
ProvedProductFraming.Nest.proposition_2bound-revealing-programp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-framing
Fix and consider the bound-revealing program (5), with objective and optimal value . There is an optimal solution of (5) at which
This is the worst-case structure of ; Proposition 3 uses it to eliminate from (5).
Formalization Note The paper states the proposition for "the" optimal solution without naming it (p. 10). It is formalized in the existential reading: some optimal solution has a constant . This is what the rest of the argument uses. The universal reading can fail when vanishes on part of at the optimum, since the rescaling in the proof is then impossible. Optimality is stated as for every feasible , which also says that the minimum is attained.
Preamble
import Mathlib import Definitions.Def_ProductFraming_Nest_Program
Formal statement
namespace ProductFraming.Nest
open Finset
/-- Proposition 2 (Gallego, Li, Truong, Wang 2020, p. 10), existential reading: problem (5) has an
optimal solution `(U, Λ)` at which `g(x) = (U(x)/x) E[min(X, x)]` is constant on `[m]`, equal
to the optimal value `γ`. -/
theorem proposition_2 (m : ℕ) (hm : 1 ≤ m) :
∃ U Λ : ℕ → ℝ, Feasible5 m U Λ ∧
(∀ U' Λ' : ℕ → ℝ, Feasible5 m U' Λ' → J5 hm U Λ ≤ J5 hm U' Λ') ∧
∀ x ∈ Icc 1 m, U x / (x : ℝ) * EminTail Λ x = J5 hm U Λ := by sorry
end ProductFraming.Nest
Source
Gallego, Li, Truong, Wang, Approximation Algorithms for Product Framing and Pricing, Operations Research (2020), DOI 10.1287/opre.2019.1875, authors' accepted manuscript, p. 10, Proposition 2 (proof pp. 35–36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.