AFTD Auto-Formalizing Theoretical Domains

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

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)) _
See it in the graphDiscuss this resultChallenge it