irr_step_changed_agent_strict
Every irr_step is carried out by a single agent i: her new bid b' i is an admissible bid for her at b, nothing but her own bid changes (b' = Function.update b i (b' i)), and the additive value of her own picking-sequence bundle strictly increases.
Statement
theorem irr_step_changed_agent_strict {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (v : N → G → ℝ) (seq : List N) (adm : (N → Fin m ≃ G) → N → (Fin m ≃ G) → Prop) (b b' : N → Fin m ≃ G) (h : irr_step v seq adm b b') : ∃ i, adm b i (b' i) ∧ b' = Function.update b i (b' i) ∧ ∑ g ∈ picking_sequence_outcome seq b i, v i g < ∑ g ∈ picking_sequence_outcome seq b' i, v i g
- Source
- step towards round_robin_item_preserving_swaps_polynomial_convergence
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- irr_stepOne step of iterated picking sequences restricted to admissible bids adm: some agent i that has a strictly profitable admissible…
- 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…
The proof, explained
An improving response step (irr_step) represents an agent i updating her bid to an admissible best response r₂, under the precondition that some admissible bid r₁ strictly improves her bundle value over b. Using agent i as the existential witness, her new bid b' i is r₂, which is admissible and accounts for the entire profile change b' = Function.update b i (b' i). Finally, because r₂ weakly dominates all admissible deviations, agent i's bundle value under b' is at least that under r₁, which strictly exceeds her bundle value under b.
From the definition of an improving response step, obtain the moving agent i, a strictly improving admissible bid r₁, and an admissible best response r₂, and deduce that b' i = r₂.
Unpacking the hypothesis that b' is reached by an irr_step from b provides an agent i, an admissible bid r₁ that strictly improves i's picking-sequence bundle value over b, and an admissible best-response bid r₂ such that b' = Function.update b i r₂. Evaluating this updated profile at agent i gives b' i = r₂.
obtain ⟨i, ⟨r₁, _hr₁adm, hr₁⟩, r₂, hr₂adm, hb', hbr⟩ := h have hbi : b' i = r₂ := by rw [hb']; simp
It suffices to show that agent i satisfies admissibility of b' i, the update identity b' = Function.update b i (b' i), and a strict increase in bundle value.
We instantiate the existential quantifier with agent i, which splits the goal into three separate obligations for that agent.
refine ⟨i, ?_, ?_, ?_⟩The new bid b' i is admissible for agent i at profile b.
Rewriting with b' i = r₂ transforms the goal into the admissibility of r₂, which was part of the definition of the irr_step.
· show adm b i (b' i) rw [hbi]; exact hr₂adm
The profile b' differs from b only at agent i, where it takes the value b' i.
Rewriting with b' i = r₂ turns the goal into b' = Function.update b i r₂, which holds by the construction of b' in the irr_step.
· show b' = Function.update b i (b' i) rw [hbi]; exact hb'
Agent i's total value for the bundle obtained from the picking sequence strictly increases from b to b'.
Because b' is an admissible best response for agent i, her bundle value under b' is at least that under the admissible deviation r₁. Since r₁ was chosen to yield a strictly higher bundle value than b, the bundle value under b' is strictly greater than under b by transitivity of strict and weak inequalities over ℝ.
· show ∑ g ∈ picking_sequence_outcome seq b i, v i g < ∑ g ∈ picking_sequence_outcome seq b' i, v i g have h1 : ∑ g ∈ picking_sequence_outcome seq (Function.update b i r₁) i, v i g ≤ ∑ g ∈ picking_sequence_outcome seq b' i, v i g := hbr r₁ _hr₁adm linarith
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.
/-- An irr_step is a single-agent bid change to an admissible best response that strictly raises the mover's own bundle value. -/theorem irr_step_changed_agent_strict {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (v : N → G → ℝ) (seq : List N) (adm : (N → Fin m ≃ G) → N → (Fin m ≃ G) → Prop) (b b' : N → Fin m ≃ G) (h : irr_step v seq adm b b') : ∃ i, adm b i (b' i) ∧ b' = Function.update b i (b' i) ∧ ∑ g ∈ picking_sequence_outcome seq b i, v i g < ∑ g ∈ picking_sequence_outcome seq b' i, v i g := by obtain ⟨i, ⟨r₁, _hr₁adm, hr₁⟩, r₂, hr₂adm, hb', hbr⟩ := h have hbi : b' i = r₂ := by rw [hb']; simp refine ⟨i, ?_, ?_, ?_⟩ · show adm b i (b' i) rw [hbi]; exact hr₂adm · show b' = Function.update b i (b' i) rw [hbi]; exact hb' · show ∑ g ∈ picking_sequence_outcome seq b i, v i g < ∑ g ∈ picking_sequence_outcome seq b' i, v i g have h1 : ∑ g ∈ picking_sequence_outcome seq (Function.update b i r₁) i, v i g ≤ ∑ g ∈ picking_sequence_outcome seq b' i, v i g := hbr r₁ _hr₁adm linarith