picking_sequence_outcome_update_mem
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
- round_robin_three_agents_pne_not_alpha_ef1_of_three_quarters_ltWith three agents and eight goods, there is an instance with nonnegative additive valuations and a pure Nash equilibrium of Round-Robin…
- round_robin_pne_not_ef1_three_agents_eight_goodsThere is an instance with 3 agents, 8 goods and strictly positive additive valuations, and a pure Nash equilibrium of the Round-Robin…
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.
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.
uses
List.mem_map.mprunfold picking_sequence_outcome refine List.mem_map.mpr ⟨_, ?_, rfl⟩
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.
uses
foldl_mem_picking_runs_anyhave := foldl_mem_picking_runs_any U hU i (fun a => List.ofFn (rank a)) (List.ofFn r) seq (fun _ => ∅, ∅)
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).
uses
Function.update_of_nehave 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]
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.
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.
- In Lean, updating the ranking profile (of type N → Fin m ≃ G) at agent i before converting it to a list of goods is syntactically distinct from converting all rankings to lists first and then updating the resulting function (of type N → List G) at i. Lines 8–13 bridge this purely formal distinction via pointwise case analysis.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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