Proof of Theorem 4.16, p. 34 — rounding blue prices up to the red cost levels keeps valid and does not decrease revenue
ProvedRevenueOrdered.Stackelberg.roundUp_revenue_lep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stackelberg-pricing
Let be a Stackelberg Matroid instance with distinct red costs , let be a price assignment and an ordering of the customer may use under . Define the rounded prices
Then is still an ordering the customer may use under , and the revenue does not decrease:
This justifies restricting attention to prices in when bounding the Stackelberg optimum from above. The paper asserts it, noting that a blue element priced above is never bought because contains a base.
Formalization Note The price is abovePrice . The paper modifies one element at a time; here all prices are rounded at once.
Preamble
import Mathlib import Definitions.Def_RevenueOrdered_Stackelberg_Model import Definitions.Def_RevenueOrdered_Stackelberg_Greedy import Definitions.Def_RevenueOrdered_Stackelberg_Instance import Definitions.Def_RevenueOrdered_Stackelberg_Assortment open Classical
Formal statement
namespace RevenueOrdered.Stackelberg
/-- Proof of Theorem 4.16, p. 34 (Berbeglia–Joret, arXiv:1606.01371v3): rounding every blue
price up to the next red cost level `c_i` (or to `+∞` if it exceeds `c_k`) keeps the
customer's ordering valid and does not decrease the RevenueOrdered.Ratio.revenue. -/
theorem roundUp_revenue_le {α : Type*} (I : Instance α) (p : α → ℝ)
(hp : ∀ e ∈ I.B, 0 < p e) (L' : List α) (hL' : I.IsCustomerOrder p L') :
I.IsCustomerOrder (roundUp I p) L' ∧
I.stackRevenue p L' ≤ I.stackRevenue (roundUp I p) L' := by sorry
end RevenueOrdered.Stackelberg
Source
Berbeglia & Joret, Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments, arXiv:1606.01371v3, p. 34, proof of Theorem 4.16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.