AFTD Auto-Formalizing Theoretical Domains

foldl_picking_turn_alloc_subset_of_prefix

theoremverified

Folding 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 running the turns of L1 from a state is contained in the allocated set after running the turns of L2 from the same state, for any assignment f of a ranking list to each bidder.

Statement

theorem foldl_picking_turn_alloc_subset_of_prefix {N G : Type*} [DecidableEq N] [DecidableEq G]
    (f : N → List G) (L₁ L₂ : List N) (hL : L₁ <+: L₂) (st : (N → Finset G) × Finset G) :
    (L₁.foldl (fun s a => picking_turn (f a) a s) st).2 ⊆
      (L₂.foldl (fun s a => picking_turn (f a) a s) st).2
Source
step towards picking_prefix_state_alloc_mono
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_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…
Used by 1
  • 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 first establishes an auxiliary lemma (`rt3_fold_alloc_mono`) by list induction: running any sequence of picking turns only expands the set of allocated goods, as each single turn adds goods (`picking_turn_alloc_subset`). For the main theorem, since $L₁$ is a prefix of $L₂$, we decompose $L₂$ into $L₁ ++ \text{tail}$ and split the fold via `List.foldl_append`. The result then follows by applying the auxiliary lemma to the remaining sequence $\text{tail}$ starting from the state reached after $L₁$.

  1. Any sequence of picking turns never removes allocated goods: the initial set of allocated goods is a subset of the allocated set after folding over the sequence.

    We prove this auxiliary lemma (`rt3_fold_alloc_mono`) by induction on the list $L$ of bidders, generalizing over the initial state $st$. In the base case ($L = []$), no turns are taken, so the set of allocated goods is unchanged and the claim follows by reflexivity (`subset_refl`). In the inductive step ($a :: L$), the single turn of bidder $a$ does not remove any allocated goods (`picking_turn_alloc_subset`), and the induction hypothesis on $L$ guarantees that subsequent turns also only add goods; transitivity yields the claim.

    lines 4–7

    uses subset_refl, picking_turn_alloc_subset

      induction L generalizing st with
      | nil => exact subset_refl _
      | cons a L ih =>
        exact (picking_turn_alloc_subset (f a) a st).trans (ih _)
  2. The sequence of picking turns for $L₂$ decomposes into the turns for $L₁$ followed by the remaining turns.

    Since $L₁$ is a prefix of $L₂$ ($hL$), there is a list $\text{tail}$ such that $L₂ = L₁ ++ \text{tail}$. Rewriting the fold across concatenation using `List.foldl_append`, running the turns of $L₂$ from $st$ is equivalent to first running $L₁$ from $st$, and then running $\text{tail}$ starting from the resulting state.

    lines 14–15

    uses List.foldl_append

      obtain ⟨tail,rfl⟩ := hL
      rw [List.foldl_append]
  3. The set of goods allocated after running $L₁$ is a subset of the set of goods allocated after running $L₂$.

    Applying the monotonicity lemma `rt3_fold_alloc_mono` to the remaining sequence $\text{tail}$, starting from the state reached after $L₁$, shows that running $\text{tail}$ only adds goods to the allocated set, completing the proof.

    line 16

    uses rt3_fold_alloc_mono

      exact rt3_fold_alloc_mono f tail _
subset_refl
Set inclusion is reflexive: every set is a subset of itself ($A ⊆ A$).
picking_turn_alloc_subset
A single picking turn never removes allocated goods: the set of allocated goods before the turn is a subset of the set of allocated goods after the turn.
List.foldl_append
Folding over the concatenation of two lists $L ++ L'$ is equivalent to folding over $L$ and then folding over $L'$ from the resulting accumulator.
rt3_fold_alloc_mono
Running any sequence of picking turns from an initial state only accumulates goods: the initially allocated set is a subset of the final allocated set.

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

private lemma rt3_fold_alloc_mono {N G : Type*} [DecidableEq N] [DecidableEq G]    (f : N → List G) (L : List N) (st : (N → Finset G) × Finset G) :    st.2 ⊆ (L.foldl (fun s a => picking_turn (f a) a s) st).2 := by  induction L generalizing st with  | nil => exact subset_refl _  | cons a L ih =>    exact (picking_turn_alloc_subset (f a) a st).trans (ih _)/-- Running the picking turns of a prefix of a bidder sequence allocates a subset of what the full sequence allocates; this is the fold-level form of monotonicity in the number of turns. -/theorem foldl_picking_turn_alloc_subset_of_prefix {N G : Type*} [DecidableEq N] [DecidableEq G]    (f : N → List G) (L₁ L₂ : List N) (hL : L₁ <+: L₂) (st : (N → Finset G) × Finset G) :    (L₁.foldl (fun s a => picking_turn (f a) a s) st).2 ⊆      (L₂.foldl (fun s a => picking_turn (f a) a s) st).2 := by  obtain ⟨tail,rfl⟩ := hL  rw [List.foldl_append]  exact rt3_fold_alloc_mono f tail _
See it in the graphDiscuss this resultChallenge it