Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(14) — orderings that agree on a block partition make greedy pick the same number of elements in each block

Proved
RevenueOrdered.Stackelberg.greedy_block_card_eq

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

greedy-algorithmmatroidsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let M=(E,X)M=(E,\mathcal X)M=(E,X) be a matroid with finite ground set EEE, partitioned into blocks E1,E2,…E_1,E_2,\dotsE1​,E2​,…. Let LLL and L′L'L′ be two linear orderings of EEE that agree on this partition: for i<ji<ji<j, every e∈Eie\in E_ie∈Ei​ precedes every f∈Ejf\in E_jf∈Ej​, both in LLL and in L′L'L′. Then for every block index iii,

∣greedyM(E,L)∩Ei∣=∣greedyM(E,L′)∩Ei∣.|\mathrm{greedy}_M(E,L)\cap E_i|=|\mathrm{greedy}_M(E,L')\cap E_i|.∣greedyM​(E,L)∩Ei​∣=∣greedyM​(E,L′)∩Ei​∣.

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 Ei={e∈E:blk(e)=i}E_i=\{e\in E:\mathrm{blk}(e)=i\}Ei​={e∈E:blk(e)=i} of a function blk:E→N\mathrm{blk}:E\to\mathbb Nblk:E→N (empty blocks are allowed), and "eee precedes fff in LLL" is [e, f].Sublist L. The paper states the agreement only for consecutive blocks Ei,Ei+1E_i,E_{i+1}Ei​,Ei+1​ and indexes the blocks to kkk after naming ℓ\ellℓ of them; agreement for all i<ji<ji<j is the intended condition (consecutive agreement does not order two blocks separated by an empty block).

Preamble
import Mathlib
import Definitions.Def_RevenueOrdered_Stackelberg_Greedy

open Classical
Formal statement
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
Source
Berbeglia & Joret, Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments, arXiv:1606.01371v3, p. 31, proof of Lemma 4.15, (14)
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