Theorem 4.16 — Stackelberg Matroid pricing is an assortment problem under a regular choice model, and uniform pricing is revenue-ordered assortments
ProvedRevenueOrdered.Stackelberg.stackelberg_matroid_is_assortmentLet be a matroid with a bipartition into red and blue elements (), red costs with distinct values , and a base of contained in . Build the assortment instance of the proof: products , revenues , and, for a linear ordering of that is non-decreasing in cost with before on ties,
where is the auxiliary matroid on . Write for the leader's revenue under prices when the customer uses a compatible ordering . Then:
- is a regular discrete choice model and ;
- the assortment optimum is the optimal Stackelberg revenue:
- for each red cost level there is such that the revenue-ordered assortment earns the revenue of the uniform price on every blue element;
- for each there is a red cost level such that earns the revenue of the uniform price .
Through this correspondence the approximation guarantees for revenue-ordered assortments in §3 become guarantees for uniform pricing in Stackelberg Matroid (and Stackelberg Minimum Spanning Tree) pricing, recovering the bounds of Cardinal et al.
Formalization Note The theorem is stated for the explicit instance of the paper's proof (and for every admissible ordering ), not as an existence statement. Item 2 is stated with IsGreatest: the assortment optimum is an upper bound on every achievable Stackelberg revenue and is achieved by some positive real price assignment, so the Stackelberg optimum is a maximum. Cost levels are quantified as elements of the set of red costs rather than by index. Revenues under a uniform price are asserted for every compatible customer ordering. is needed only for item 3 (otherwise is empty and no exists).
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
namespace RevenueOrdered.Stackelberg
/-- Theorem 4.16 (Berbeglia–Joret, arXiv:1606.01371v3, p. 24), for the explicit assortment
instance of its proof (pp. 32–33): products `𝒞 = B × {c₁, …, c_k}`, revenues
`r((e, q)) = |B| q`, and choice probabilities `𝒫((e, q), S) = 1/|B|` iff
`(e, q) ∈ greedy_{M′}(R ∪ S, L)`. Then (a) the model is regular and `r > 0`; (b) its optimum
`OPT` is the greatest RevenueOrdered.Ratio.revenue achievable in the Stackelberg Matroid instance; (c) for each red cost
level `c_i` some RevenueOrdered.Ratio.revenue-ordered assortment `{y' : r(y') ≥ r(y)}` earns the RevenueOrdered.Ratio.revenue of the uniform
price `c_i`; (d) every RevenueOrdered.Ratio.revenue-ordered assortment earns the RevenueOrdered.Ratio.revenue of some uniform price `c_i`. -/
theorem stackelberg_matroid_is_assortment {α : Type*} (I : Instance α) (hB : I.B.Nonempty)
(L : List (α ⊕ (α × ℝ))) (hL : IsAuxOrder I L) :
(RevenueOrdered.Ratio.IsRegular (choiceProb I L) ∧ ∀ y : Product I, 0 < prodRevenue I y) ∧
IsGreatest {v : ℝ | ∃ p : α → ℝ, (∀ e ∈ I.B, 0 < p e) ∧
∃ L' : List α, I.IsCustomerOrder p L' ∧ v = I.stackRevenue p L'}
(RevenueOrdered.Ratio.opt (choiceProb I L) (prodRevenue I)) ∧
(∀ q ∈ costs I, ∃ y : Product I, ∀ L' : List α, I.IsCustomerOrder (fun _ => q) L' →
RevenueOrdered.Ratio.revenue (choiceProb I L) (prodRevenue I) (thresholdSet (prodRevenue I) y) =
I.stackRevenue (fun _ => q) L') ∧
(∀ y : Product I, ∃ q ∈ costs I, ∀ L' : List α, I.IsCustomerOrder (fun _ => q) L' →
RevenueOrdered.Ratio.revenue (choiceProb I L) (prodRevenue I) (thresholdSet (prodRevenue I) y) =
I.stackRevenue (fun _ => q) L') := by sorry
end RevenueOrdered.Stackelberg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.