Proof of Theorem 4.16, pp. 32–33 — the choice probabilities are regular
ProvedRevenueOrdered.Stackelberg.choiceProb_isRegulardiscrete-choicematroidsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stackelberg-pricing
Let be a Stackelberg Matroid instance, and the auxiliary matroid on . Let be a linear ordering of that is non-decreasing in cost ( for , for ) and puts elements of before red elements of equal cost. Define, for and ,
Then is a regular discrete choice model: it satisfies axioms (i), (ii), (iii) and (iv), including axiom (iv) for the no-purchase option.
This is the first step of the proof of Theorem 4.16; it shows that the Stackelberg Matroid problem is an assortment problem under a regular model, to which the bounds of §3 apply.
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
/-- Regularity of the choice model of the proof of Theorem 4.16 (Berbeglia–Joret,
arXiv:1606.01371v3, pp. 32–33): for every ordering `L` of `R ∪ 𝒞` that is non-decreasing in cost
with `𝒞` before `R` on ties, `𝒫((e, q), S) = 1/|B|·[(e, q) ∈ greedy_{M′}(R ∪ S, L)]` satisfies
axioms (i)–(iv). -/
theorem choiceProb_isRegular {α : Type*} (I : Instance α) (L : List (α ⊕ (α × ℝ)))
(hL : IsAuxOrder I L) :
RevenueOrdered.Ratio.IsRegular (choiceProb I 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. 32–33, proof of Theorem 4.16 ("Let us prove that P is a regular discrete choice model")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.