picking_turn_alloc_subset
One turn never un-allocates a good: the set of goods already allocated before a picking turn is contained in the set of allocated goods after it.
Statement
theorem picking_turn_alloc_subset {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (i : N) (st : (N → Finset G) × Finset G) : st.2 ⊆ (picking_turn l i st).2
- Source
- step towards picking_prefix_state_alloc_mono
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
- Used by 2
- foldl_picking_turn_alloc_subset_of_prefixFolding the picking turn over a prefix of a list of bidders only allocates fewer goods: if L1 is a prefix of L2, the allocated set after…
- picking_prefix_state_alloc_monoThe set of allocated goods is monotone in the number of turns: if s <= t then the goods allocated after s turns are allocated after t turns.
The proof, explained
The proof proceeds by unfolding the definition of `picking_turn` and performing case analysis on whether an unallocated good is found in the list `l`. If an available good is found, it is added to the allocated set, which trivially preserves containment by `Finset.subset_insert`. If no available good is found, the state is left unchanged, and containment holds by reflexivity (`subset_refl`).
The claim reduces to two cases depending on whether an unallocated good is found.
Unfolding the definition of `picking_turn`, the function inspects the list `l` to find the first good not already in `st.2`. Splitting on this search yields two cases: either some available good is found, or no such good exists.
unfold picking_turn split
If an unallocated good is found, the old allocated set is a subset of the updated allocated set.
When an unallocated good g is found, the updated allocated set is `insert g st.2`. Any finite set is a subset of the result of inserting an element into it, by `Finset.subset_insert`.
uses
Finset.subset_insert· exact Finset.subset_insert _ _If no unallocated good is found, the old allocated set is contained in itself.
When no item in `l` is available, the state is returned unchanged, so the goal is `st.2 ⊆ st.2`, which holds by reflexivity (`subset_refl`).
uses
subset_refl· exact subset_refl _
Finset.subset_insert- A finite set is a subset of the set obtained by inserting an element into it: s ⊆ insert a s.
subset_refl- Subset inclusion is reflexive: every set is a subset of itself (a ⊆ a).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A single picking turn only inserts a good into the allocated set (or does nothing), so the old allocated set stays contained in the new one. -/theorem picking_turn_alloc_subset {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (i : N) (st : (N → Finset G) × Finset G) : st.2 ⊆ (picking_turn l i st).2 := by unfold picking_turn split · exact Finset.subset_insert _ _ · exact subset_refl _