(14) — orderings that agree on a block partition make greedy pick the same number of elements in each block
ProvedRevenueOrdered.Stackelberg.greedy_block_card_eqLet be a matroid with finite ground set , partitioned into blocks . Let and be two linear orderings of that agree on this partition: for , every precedes every , both in and in . Then for every block index ,
Inside a block the two orderings may differ arbitrarily; the property says that how ties are broken inside blocks does not affect how many elements of each block greedy selects. The paper derives Lemma 4.15 from it.
Formalization Note The blocks are the fibres of a function (empty blocks are allowed), and " precedes in " is [e, f].Sublist L. The paper states the agreement only for consecutive blocks and indexes the blocks to after naming of them; agreement for all is the intended condition (consecutive agreement does not order two blocks separated by an empty block).
import Mathlib import Definitions.Def_RevenueOrdered_Stackelberg_Greedy open Classical
namespace RevenueOrdered.Stackelberg
/-- Property (14) (Berbeglia–Joret, arXiv:1606.01371v3, proof of Lemma 4.15, p. 31). Let the
finite ground set `E` of a matroid `M` be partitioned into blocks `E_i = {e ∈ E : blk e = i}`,
and let `L`, `L'` be two linear orderings of `E` that agree on the block partition: every element
of a lower-indexed block precedes every element of a higher-indexed block, in both orderings.
Then the greedy algorithm picks the same number of elements in each block under `L` and `L'`. -/
theorem greedy_block_card_eq {α : Type*} (M : Matroid α) (E : Finset α)
(hE : (E : Set α) = M.E) (L L' : List α) (hL : IsLinearOrderOf L E)
(hL' : IsLinearOrderOf L' E) (blk : α → ℕ)
(hagree : ∀ e ∈ E, ∀ f ∈ E, blk e < blk f → [e, f].Sublist L ∧ [e, f].Sublist L') :
∀ i : ℕ, ((greedyM M L E).filter (fun e => blk e = i)).card =
((greedyM M L' E).filter (fun e => blk e = i)).card := by sorry
end RevenueOrdered.Stackelberg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.