AFTD Auto-Formalizing Theoretical Domains

picking_sequence_outcome_update_mem

theoremverified

Whatever 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 bundles independent of r.

Statement

theorem picking_sequence_outcome_update_mem {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}
    (U : List G) (hU : ∀ g, g ∈ U) (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G) :
    picking_sequence_outcome seq (Function.update rank i r) i ∈
      (picking_runs_any U i (fun a => List.ofFn (rank a)) seq (fun _ => ∅, ∅)).map (fun st => st.1 i)
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_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
  • 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…
  • 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.
  • 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…
Used by 2

The proof, explained

The theorem states that when agent i unilaterally changes their reported ranking to r, their resulting bundle is one of the candidate bundles produced by picking_runs_any (a set of runs where agent i can make any valid pick at their turns). The proof unfolds picking_sequence_outcome into a fold over the sequence and reduces membership in the mapped list to showing that the full final state belongs to picking_runs_any. It then invokes foldl_mem_picking_runs_any, which proves this property for any preference list for agent i, and bridges the syntactic difference between updating the rankings versus updating the list-valued functions via a case distinction on whether the acting agent is i.

  1. To show that agent i's bundle belongs to the candidate bundles, it suffices to show that the full final state of the sequence belongs to the list of reachable states generated by picking_runs_any.

    Unfolding the definition of picking_sequence_outcome, agent i's bundle is the projection st.1 i of the final state st obtained by folding picking_turn over the sequence. Applying List.mem_map.mpr reduces membership in the image under st ↦ st.1 i to showing that this final state itself is in picking_runs_any.

    lines 5–6

    uses List.mem_map.mpr

      unfold picking_sequence_outcome
      refine List.mem_map.mpr ⟨_, ?_, rfl⟩
  2. The final state obtained by replacing agent i's preference list with List.ofFn r in the list-valued profile belongs to picking_runs_any.

    We instantiate the general lemma foldl_mem_picking_runs_any with the base preference lists fun a => List.ofFn (rank a), agent i's new list List.ofFn r, and the empty initial state (fun _ => ∅, ∅). This guarantees that the run where agent i picks according to r ends up in picking_runs_any.

    line 7

    uses foldl_mem_picking_runs_any

      have := foldl_mem_picking_runs_any U hU i (fun a => List.ofFn (rank a)) (List.ofFn r) seq (fun _ => ∅, ∅)
  3. The transition step using the updated ranking Function.update rank i r is pointwise identical to the transition step using the list-level update Function.update (fun a => List.ofFn (rank a)) i (List.ofFn r).

    By functional extensionality over the state st and the current agent a, we split into cases on whether a = i. If a = i, both sides simplify to a turn with preference list List.ofFn r. If a ≠ i, the lemma Function.update_of_ne ensures neither update affects agent a, so both sides simplify to a turn with List.ofFn (rank a).

    lines 8–13

    uses Function.update_of_ne

      have hfun : (fun st a => picking_turn (List.ofFn (Function.update rank i r a)) a st) =
          (fun st a => picking_turn (Function.update (fun a => List.ofFn (rank a)) i (List.ofFn r) a) a st) := by
        funext st a
        by_cases h : a = i
        · subst h; simp
        · simp [Function.update_of_ne h]
  4. The outcome under the updated ranking is in the projected candidate bundles, completing the proof.

    Rewriting the transition function inside the fold using the equivalence hfun makes the goal identical to the previously proved statement, closing the goal.

    line 14

      rw [hfun]; exact this
List.mem_map.mpr
An element y is in the image of a list under a function f if there exists an element x in the list such that f(x) = y.
foldl_mem_picking_runs_any
Any deterministic run of the picking sequence in which agent i's preference list is replaced by an arbitrary list l produces a state that belongs to the candidate runs generated by picking_runs_any.
Function.update_of_ne
Evaluating a function updated at a' on a distinct input a ≠ a' yields the original function's value at a.

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_sequence_outcome_update_mem {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}    (U : List G) (hU : ∀ g, g ∈ U) (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G) :    picking_sequence_outcome seq (Function.update rank i r) i ∈      (picking_runs_any U i (fun a => List.ofFn (rank a)) seq (fun _ => ∅, ∅)).map (fun st => st.1 i) := by  unfold picking_sequence_outcome  refine List.mem_map.mpr ⟨_, ?_, rfl⟩  have := foldl_mem_picking_runs_any U hU i (fun a => List.ofFn (rank a)) (List.ofFn r) seq (fun _ => ∅, ∅)  have hfun : (fun st a => picking_turn (List.ofFn (Function.update rank i r a)) a st) =      (fun st a => picking_turn (Function.update (fun a => List.ofFn (rank a)) i (List.ofFn r) a) a st) := by    funext st a    by_cases h : a = i    · subst h; simp    · simp [Function.update_of_ne h]  rw [hfun]; exact this
See it in the graphDiscuss this resultChallenge it