Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.16 — Stackelberg Matroid pricing is an assortment problem under a regular choice model, and uniform pricing is revenue-ordered assortments

Proved
RevenueOrdered.Stackelberg.stackelberg_matroid_is_assortment

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

assortment-optimizationdiscrete-choicematroidsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stackelberg-pricing

Let M=(E,X)M=(E,\mathcal X)M=(E,X) be a matroid with a bipartition E=R⊔BE=R\sqcup BE=R⊔B into red and blue elements (B≠∅B\neq\emptysetB=∅), red costs c:R→R>0c:R\to\mathbb R_{>0}c:R→R>0​ with distinct values c1<⋯<ckc_1<\dots<c_kc1​<⋯<ck​, and a base of MMM contained in RRR. Build the assortment instance of the proof: products C=B×{c1,…,ck}\mathcal C=B\times\{c_1,\dots,c_k\}C=B×{c1​,…,ck​}, revenues r((e,q))=∣B∣ qr((e,q))=|B|\,qr((e,q))=∣B∣q, and, for a linear ordering LLL of R∪CR\cup\mathcal CR∪C that is non-decreasing in cost with C\mathcal CC before RRR on ties,

P((e,q),S)={1/∣B∣if (e,q)∈greedyM′(R∪S,L),0otherwise,\mathcal P((e,q),S)=\begin{cases}1/|B|&\text{if }(e,q)\in\mathrm{greedy}_{M'}(R\cup S,L),\\0&\text{otherwise,}\end{cases}P((e,q),S)={1/∣B∣0​if (e,q)∈greedyM′​(R∪S,L),otherwise,​

where M′M'M′ is the auxiliary matroid on R∪CR\cup\mathcal CR∪C. Write revStack(p,L∗)=∑e∈B∩greedyM(R∪B,L∗)p(e)\mathrm{rev}_{\mathrm{Stack}}(p,L^*)=\sum_{e\in B\cap\mathrm{greedy}_M(R\cup B,L^*)}p(e)revStack​(p,L∗)=∑e∈B∩greedyM​(R∪B,L∗)​p(e) for the leader's revenue under prices ppp when the customer uses a compatible ordering L∗L^*L∗. Then:

  1. P\mathcal PP is a regular discrete choice model and r>0r>0r>0;
  2. the assortment optimum is the optimal Stackelberg revenue:
max⁡S⊆C∑y∈SP(y,S) r(y)=max⁡{revStack(p,L∗):p:B→R>0, L∗ compatible with (c,p)};\max_{S\subseteq\mathcal C}\sum_{y\in S}\mathcal P(y,S)\,r(y)=\max\bigl\{\mathrm{rev}_{\mathrm{Stack}}(p,L^*): p:B\to\mathbb R_{>0},\ L^*\text{ compatible with }(c,p)\bigr\};S⊆Cmax​y∈S∑​P(y,S)r(y)=max{revStack​(p,L∗):p:B→R>0​, L∗ compatible with (c,p)};
  1. for each red cost level cic_ici​ there is y∈Cy\in\mathcal Cy∈C such that the revenue-ordered assortment {y′∈C:r(y′)≥r(y)}\{y'\in\mathcal C:r(y')\ge r(y)\}{y′∈C:r(y′)≥r(y)} earns the revenue of the uniform price cic_ici​ on every blue element;
  2. for each y∈Cy\in\mathcal Cy∈C there is a red cost level cic_ici​ such that {y′∈C:r(y′)≥r(y)}\{y'\in\mathcal C:r(y')\ge r(y)\}{y′∈C:r(y′)≥r(y)} earns the revenue of the uniform price cic_ici​.

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 LLL), 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 cic_ici​ 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. B≠∅B\neq\emptysetB=∅ is needed only for item 3 (otherwise C\mathcal CC is empty and no yyy exists).

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

/-- 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
Source
Berbeglia & Joret, Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments, arXiv:1606.01371v3, p. 24, Theorem 4.16 (proof pp. 32–35)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me