Lemma 4.15 — the Stackelberg revenue does not depend on the customer's compatible ordering
ProvedRevenueOrdered.Stackelberg.stackRevenue_order_independentgreedy-algorithmmatroidsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stackelberg-pricing
Consider a Stackelberg Matroid instance: a matroid , a bipartition into red and blue elements, red costs , and a red base of . Let be a price assignment, and let , be two linear orderings of compatible with the costs and prices (non-decreasing in weight, blue before red on ties; (15a)–(15b)). Then for every ,
and in particular the revenue is the same for and .
This makes the optimum revenue of the Stackelberg Matroid problem well defined, although the customer's ordering is not unique.
Preamble
import Mathlib import Definitions.Def_RevenueOrdered_Stackelberg_Greedy import Definitions.Def_RevenueOrdered_Stackelberg_Instance open Classical
Formal statement
namespace RevenueOrdered.Stackelberg
/-- Lemma 4.15 (Berbeglia–Joret, arXiv:1606.01371v3, p. 23). In a Stackelberg Matroid instance,
for a price assignment `p : B → ℝ_{>0}` and any two orderings `L`, `L'` of `R ∪ B` compatible
with the costs and prices (non-decreasing, blue before red on ties), the number of bought blue
elements of each price `γ` is the same; in particular the RevenueOrdered.Ratio.revenue is the same. -/
theorem stackRevenue_order_independent {α : Type*} (I : Instance α) (p : α → ℝ)
(hp : ∀ e ∈ I.B, 0 < p e) (L L' : List α) (hL : I.IsCustomerOrder p L)
(hL' : I.IsCustomerOrder p L') :
(∀ γ : ℝ, ((I.B ∩ greedyM I.M L (I.R ∪ I.B)).filter (fun e => p e = γ)).card =
((I.B ∩ greedyM I.M L' (I.R ∪ I.B)).filter (fun e => p e = γ)).card) ∧
I.stackRevenue 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, p. 23, Lemma 4.15 (proof pp. 31–32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.