Proof of Theorem 4.16, p. 32 — the auxiliary system on is a matroid
ProvedRevenueOrdered.Stackelberg.auxIndep_isMatroidLet be a Stackelberg Matroid instance with distinct red costs , and . Call independent if
- for each , contains at most one pair with , and
- is independent in .
Then there is a matroid with ground set whose independent sets are exactly these sets.
The paper leaves this check to the reader. replaces each blue element by parallel copies, one per red cost level; in the graphical case it is the graphical matroid of the graph with each blue edge replaced by parallel edges. The matroid property is what allows Lemma 4.14 to be applied to .
Formalization Note Elements of are terms of α ⊕ (α × ℝ); the statement characterises the independent finite sets, which determine a matroid on a finite ground set. The paper's typos in conditions (1) and (2) are corrected as described in the module Assortment.
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
/-- The auxiliary system `M′` is a matroid (Berbeglia–Joret, arXiv:1606.01371v3, proof of
Theorem 4.16, p. 32; the paper leaves the check to the reader): there is a matroid on the ground
set `R ∪ 𝒞` whose independent finite sets are exactly the sets satisfying conditions (1) and (2). -/
theorem auxIndep_isMatroid {α : Type*} (I : Instance α) :
∃ M' : Matroid (α ⊕ (α × ℝ)), M'.E = (auxGround I : Set (α ⊕ (α × ℝ))) ∧
∀ X : Finset (α ⊕ (α × ℝ)), M'.Indep (X : Set (α ⊕ (α × ℝ))) ↔ auxIndep I X := by sorry
end RevenueOrdered.Stackelberg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.