Proof of Theorem 4.16, pp. 33–34 — equals the Stackelberg revenue of
ProvedRevenueOrdered.Stackelberg.revenue_eq_stackRevenue_priceOfAssortmentassortment-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stackelberg-pricing
In the assortment instance built from a Stackelberg Matroid instance (with an admissible ordering of ), let and let be the price assignment
Then for every ordering of that the customer may use under (compatible with the costs and prices, blue first on ties),
Consequently the optimum of the Stackelberg Matroid instance is at least the optimum of the assortment instance.
Formalization Note The price is the real number abovePrice , strictly larger than every red cost; such a blue element is never bought because contains a base.
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, pp. 33–34 (Berbeglia–Joret, arXiv:1606.01371v3): the RevenueOrdered.Ratio.revenue of an
assortment `S ⊆ 𝒞` equals the Stackelberg RevenueOrdered.Ratio.revenue of the price assignment `p_S`
(`p_S(e) = min{q : (e, q) ∈ S}`, or `+∞` if there is no such pair), for every ordering the
customer may use under `p_S`. -/
theorem revenue_eq_stackRevenue_priceOfAssortment {α : Type*} (I : Instance α)
(L : List (α ⊕ (α × ℝ))) (hL : IsAuxOrder I L) (S : Finset (Product I)) (L' : List α)
(hL' : I.IsCustomerOrder (priceOfAssortment I S) L') :
RevenueOrdered.Ratio.revenue (choiceProb I L) (prodRevenue I) S =
I.stackRevenue (priceOfAssortment I S) 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, pp. 33–34, proof of Theorem 4.16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.