Lemma 4.14 — and for
ProvedRevenueOrdered.Stackelberg.greedy_card_mono_inter_subsetgreedy-algorithmmatroidsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a matroid with finite ground set , and let be a linear ordering of . For write for the independent subset of produced by the greedy algorithm run on in the order induced by . Then for all :
- , and
Enlarging the set on which greedy runs never shrinks its output, and an element of the smaller set that greedy keeps on the larger set is also kept on the smaller set. This is the property behind the regularity axiom (iv) of the choice model of Theorem 4.16.
Preamble
import Mathlib import Definitions.Def_RevenueOrdered_Stackelberg_Greedy open Classical
Formal statement
namespace RevenueOrdered.Stackelberg
/-- Lemma 4.14 (Berbeglia–Joret, arXiv:1606.01371v3, p. 23). For a matroid `M` with finite
ground set `E`, a linear ordering `L` of `E`, and `F ⊆ F' ⊆ E`:
(i) `|greedy_M(F', L)| ≥ |greedy_M(F, L)|`, and (ii) `F ∩ greedy_M(F', L) ⊆ greedy_M(F, L)`. -/
theorem greedy_card_mono_inter_subset {α : Type*} (M : Matroid α) (E : Finset α)
(hE : (E : Set α) = M.E) (L : List α) (hL : IsLinearOrderOf L E)
(F F' : Finset α) (hFF' : F ⊆ F') (hF'E : F' ⊆ E) :
(greedyM M L F).card ≤ (greedyM M L F').card ∧
F ∩ greedyM M L F' ⊆ greedyM M L F := 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.14 (proof p. 31)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.