Proof of Theorem 4.16, pp. 34–35 — for prices in , equals the Stackelberg revenue of
ProvedRevenueOrdered.Stackelberg.revenue_assortmentOfPrices_eqassortment-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 take every value either in or above every red cost (the paper's ), and let be an ordering of the customer may use under . Put
Then
Together with the rounding step, this shows that the optimum of the assortment instance is at least the optimum of the Stackelberg Matroid instance.
Formalization Note is formalized as the set of products with and . Note that is defined with the fixed ordering of , not with the ordering induced by .
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. 34–35 (Berbeglia–Joret, arXiv:1606.01371v3): for a price
assignment `p` whose blue prices are red cost levels `c_i` or exceed every red cost (the paper's
`+∞`), and an ordering `L*` the customer may use, the assortment
`S_p = {(e, p(e)) : e ∈ greedy_M(R ∪ B, L*)}` earns the Stackelberg RevenueOrdered.Ratio.revenue of `p`. -/
theorem revenue_assortmentOfPrices_eq {α : Type*} (I : Instance α)
(L : List (α ⊕ (α × ℝ))) (hL : IsAuxOrder I L) (p : α → ℝ)
(hp : ∀ e ∈ I.B, 0 < p e) (hlev : ∀ e ∈ I.B, p e ∈ costs I ∨ ∀ f ∈ I.R, I.c f < p e)
(L' : List α) (hL' : I.IsCustomerOrder p L') :
RevenueOrdered.Ratio.revenue (choiceProb I L) (prodRevenue I) (assortmentOfPrices I p L') =
I.stackRevenue 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, pp. 34–35, proof of Theorem 4.16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.