AFTD Auto-Formalizing Theoretical Domains

foldl_mem_picking_runs_any

theoremverified

Running the picking sequence with an arbitrary list for agent i ends in one of the states of picking_runs_any.

Statement

theorem foldl_mem_picking_runs_any {N G : Type*} [DecidableEq N] [DecidableEq G] (U : List G)
    (hU : ∀ g, g ∈ U) (i : N) (lists : N → List G) (l : List G) (seq : List N) :
    ∀ st, seq.foldl (fun st a => picking_turn (Function.update lists i l a) a st) st ∈
      picking_runs_any U i lists seq st
Source
Helper for round_robin_pne_not_ef1_three_agents_eight_goods (arXiv:2610.23686 Proposition 1): reduces a pure-Nash check over all rankings of one agent to the finitely many runs where that agent takes any available good.
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_runs_anyThe final states of a picking-sequence run in which agent i may take any available good at its turns while every other agent follows its…
  • picking_turn_mem_anyWhatever ranking agent i reports, its turn leads to one of the states of picking_turn_any (when U lists every good).
  • picking_turn_anyAll states a turn of agent i can lead to, whatever its ranking: the state unchanged, or any not yet allocated good of the list U added to…
Used by 1
  • picking_sequence_outcome_update_memWhatever ranking r agent i reports, its bundle is the bundle of agent i in one of the runs of picking_runs_any: a finite set of candidate…

The proof, explained

The proof proceeds by induction on the picking sequence seq. The base case for an empty sequence is immediate since the state does not change and picking_runs_any returns the singleton list containing the initial state. For the inductive step with sequence a :: seq, we split into cases depending on whether the active agent a is i. If a = i, agent i picks according to list l, which is a valid choice in picking_turn_any, so the induction hypothesis combined with List.mem_flatMap places the final state in the set of reachable outcomes. If a ≠ i, agent a picks deterministically using their original list, and the claim follows directly from the induction hypothesis applied to the resulting state.

  1. The theorem holds when the picking sequence seq is empty: for any initial state st, the state after zero turns is in picking_runs_any U i lists [] st.

    We proceed by induction on seq. In the base case seq = [], folding over the empty list leaves the initial state st unchanged. By definition, picking_runs_any U i lists [] st evaluates to [st], and st ∈ [st] holds immediately.

    lines 5–6

      induction seq with
      | nil => intro st; simp [picking_runs_any]
  2. For the inductive step with sequence a :: seq, the goal reduces to analyzing whether agent a is agent i.

    We introduce the initial state st and expand the first turn of the sequence using List.foldl_cons. By the definition of picking_runs_any on a non-empty sequence, the reachable states branch on whether a = i, so we split on this condition.

    lines 7–10

    uses List.foldl_cons

      | cons a seq ih =>
        intro st
        simp only [List.foldl_cons, picking_runs_any]
        split
  3. When the active agent is i (a = i), the state reached after the full sequence belongs to picking_runs_any U i lists (i :: seq) st.

    Substituting a = i, agent i uses list l instead of lists i by Function.update_self, moving the system to st' = picking_turn l i st. By picking_turn_mem_any, st' is an element of picking_turn_any U i st. Applying the induction hypothesis to st' shows that the remainder of the sequence lands in picking_runs_any U i lists seq st'. By List.mem_flatMap.mpr, this witnesses that the final state belongs to the flat-map over all possible turns for agent i.

    lines 11–13

    uses Function.update_self, List.mem_flatMap.mpr, picking_turn_mem_any

        · subst a
          simp only [Function.update_self]
          exact List.mem_flatMap.mpr ⟨_, picking_turn_mem_any U hU l _ st, ih _⟩
  4. When the active agent is not i (a ≠ i), the state reached after the full sequence belongs to picking_runs_any U i lists (a :: seq) st.

    Because a ≠ i, Function.update_of_ne ensures agent a still uses lists a, transitioning to st' = picking_turn (lists a) a st. By definition of picking_runs_any for a ≠ i, the set of reachable states is exactly picking_runs_any U i lists seq st'. The induction hypothesis applied directly to st' concludes this case.

    lines 14–16

    uses Function.update_of_ne

        · rename_i h
          rw [Function.update_of_ne h]
          exact ih _
List.foldl_cons
Folding a function over a non-empty list a :: l starting from accumulator b equals folding over l starting from f b a.
Function.update_self
Updating a function f at point a with value v and evaluating at a yields v.
List.mem_flatMap.mpr
An element b belongs to List.flatMap f l if there exists an element a ∈ l such that b ∈ f a.
picking_turn_mem_any
For any preference list l, the state resulting from taking a turn with l belongs to the list of all possible turn outcomes picking_turn_any U i st.
Function.update_of_ne
Updating a function f at a different key a' ≠ a leaves the value at a unchanged.

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

theorem foldl_mem_picking_runs_any {N G : Type*} [DecidableEq N] [DecidableEq G] (U : List G)    (hU : ∀ g, g ∈ U) (i : N) (lists : N → List G) (l : List G) (seq : List N) :    ∀ st, seq.foldl (fun st a => picking_turn (Function.update lists i l a) a st) st ∈      picking_runs_any U i lists seq st := by  induction seq with  | nil => intro st; simp [picking_runs_any]  | cons a seq ih =>    intro st    simp only [List.foldl_cons, picking_runs_any]    split    · subst a      simp only [Function.update_self]      exact List.mem_flatMap.mpr ⟨_, picking_turn_mem_any U hU l _ st, ih _⟩    · rename_i h      rw [Function.update_of_ne h]      exact ih _
See it in the graphDiscuss this resultChallenge it