picking_prefix_state_alloc_mono
theoremverified
The 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.
Statement
theorem picking_prefix_state_alloc_mono {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) {s t : ℕ} (h : s ≤ t) : (picking_prefix_state seq rank s).2 ⊆ (picking_prefix_state seq rank t).2
- Source
- step towards round_robin_two_mul_add_one_deviation_certificate
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- picking_prefix_stateThe state of a picking-sequence run after its first s turns: the bundle map together with the set of already allocated items, obtained by…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- picking_turn_alloc_subsetOne turn never un-allocates a good: the set of goods already allocated before a picking turn is contained in the set of allocated goods…
- 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…
- Used by 4
- picking_prefix_two_named_first_dev_bundleIn a picking sequence with at most as many turns as goods, suppose agent i acts at turns t1 < t2 and nowhere in between, x is unallocated…
- round_robin_two_mul_add_one_deviation_certificateRound-Robin with n agents and 2n+1 goods, any reports, agent i ≠ 0: for some good g of agent 0's bundle B_0 (its first pick a1), either…
- round_robin_two_mul_add_one_outcome_structureRound-Robin with n agents and 2n+1 goods, any reports: there are goods a2, a3 (agent 0's picks at turns n and 2n) and b1, b2 (agent i's…
- round_robin_two_mul_add_one_cover_pairsRound-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and…
Lean source view module on GitHub
-- Use the accepted list-prefix monotonicity lemma; no indexing assumption on the agent type is needed. /-- The allocated set of a picking sequence is monotone in the number of turns. -/ theorem picking_prefix_state_alloc_mono {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) {s t : ℕ} (h : s ≤ t) : (picking_prefix_state seq rank s).2 ⊆ (picking_prefix_state seq rank t).2 := by unfold picking_prefix_state exact foldl_picking_turn_alloc_subset_of_prefix (fun a => List.ofFn ⇑(rank a)) _ _ (List.take_isPrefix_take.mpr (Or.inl h)) _