AFTD Auto-Formalizing Theoretical Domains

picking_turn_mem_any

theoremverified

Whatever ranking agent i reports, its turn leads to one of the states of picking_turn_any (when U lists every good).

Statement

theorem picking_turn_mem_any {N G : Type*} [DecidableEq N] [DecidableEq G] (U : List G)
    (hU : ∀ g, g ∈ U) (l : List G) (i : N) (st : (N → Finset G) × Finset G) :
    picking_turn l i st ∈ picking_turn_any U i 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 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_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
  • foldl_mem_picking_runs_anyRunning the picking sequence with an arbitrary list for agent i ends in one of the states of picking_runs_any.

The proof, explained

The theorem shows that whatever preference list l an agent uses, their turn produces a state in picking_turn_any U i st, provided the universe U contains every good. The proof unfolds the definitions and performs a case split on whether an unallocated good is found in l. If an unallocated good g is found, it is an available element of U, so the updated state appears in the list of valid picks; if no unallocated good is found, the state remains unchanged, which is explicitly included as the default option at the head of the list.

  1. It suffices to consider whether the agent finds an available good in the preference list l or finds none.

    Unfolding the definitions of picking_turn and picking_turn_any, picking_turn inspects l for the first good not already allocated (not in st.2). Splitting on the match expression divides the goal into two cases: either an available good g is found, or no available good exists in l.

    lines 4–5

      unfold picking_turn picking_turn_any
      split
  2. In the case where an item g is found in l, g is not yet allocated (g ∉ st.2).

    By List.find?_some, any element g returned by List.find? satisfies the search condition decide (g ∉ st.2) = true. Simplifying this with decide_eq_true_eq establishes that g ∉ st.2.

    lines 6–8

    uses List.find?_some, decide_eq_true_eq

      · rename_i g hg
        have := List.find?_some hg
        simp only [decide_eq_true_eq] at this
  3. The state obtained by allocating g to agent i belongs to picking_turn_any U i st.

    Because U contains all goods (hU), g is in U. Since g ∉ st.2, g belongs to the filtered list List.filter (· ∉ st.2) U by List.mem_filter.mpr. Thus, the state updated with good g belongs to the mapped list by List.mem_map.mpr. Because that mapped list is the tail of picking_turn_any U i st, the updated state belongs to the overall list by List.mem_cons_of_mem.

    line 9

    uses List.mem_cons_of_mem, List.mem_map.mpr, List.mem_filter.mpr

        exact List.mem_cons_of_mem _ (List.mem_map.mpr ⟨g, List.mem_filter.mpr ⟨hU g, by simpa using this⟩, rfl⟩)
  4. When no available good is found in l, the unchanged state st belongs to picking_turn_any U i st.

    When List.find? returns none, picking_turn leaves the state as st. Since st is prepended as the head of picking_turn_any U i st, it belongs to the list by List.mem_cons_self.

    line 10

    uses List.mem_cons_self

      · exact List.mem_cons_self
List.find?_some
If finding an element satisfying predicate p in list l returns some a, then p a = true.
decide_eq_true_eq
The boolean evaluation decide p equals true if and only if the proposition p holds.
List.mem_cons_of_mem
If an element belongs to a list, it also belongs to that list prepended with any element (a ∈ l implies a ∈ y :: l).
List.mem_map.mpr
An element belongs to List.map f l if it is the image under f of some element in l.
List.mem_filter.mpr
An element belongs to List.filter p l if it belongs to l and satisfies p.
List.mem_cons_self
An element is always a member of the list of which it is the head (a ∈ a :: l).

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 picking_turn_mem_any {N G : Type*} [DecidableEq N] [DecidableEq G] (U : List G)    (hU : ∀ g, g ∈ U) (l : List G) (i : N) (st : (N → Finset G) × Finset G) :    picking_turn l i st ∈ picking_turn_any U i st := by  unfold picking_turn picking_turn_any  split  · rename_i g hg    have := List.find?_some hg    simp only [decide_eq_true_eq] at this    exact List.mem_cons_of_mem _ (List.mem_map.mpr ⟨g, List.mem_filter.mpr ⟨hU g, by simpa using this⟩, rfl⟩)  · exact List.mem_cons_self
See it in the graphDiscuss this resultChallenge it