irr_step_ne
An iterated best-response step always changes the bid profile, since the moving agent strictly improves.
Statement
theorem irr_step_ne {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') : b' ≠ b
- Source
- Sanity lemma for irr_step.
- Verified
- 19 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
The proof proceeds by contradiction, assuming that the updated bid profile equals the original one ($b' = b$). By definition of an iterated best-response step, some agent $i$ has an admissible deviation that strictly increases their utility over the initial profile. However, the step also requires that the updated profile is a best response for agent $i$, meaning that no admissible deviation can achieve higher utility than the outcome. Evaluating this optimality condition at the strictly improving deviation produces a contradiction between strict improvement and weak maximality.
Assuming for contradiction that $b' = b$, there exists an agent $i$ with an admissible deviation $r$ that strictly improves $i$'s payoff over $b'$, while $b'$ weakly maximizes $i$'s payoff among all admissible deviations.
We argue by contradiction, assuming that the updated bid profile $b'$ equals the original profile $b$ (substituting $b$ for $b'$). By the definition of an iterated best-response step (`irr_step`), some agent $i$ must have an admissible deviation $r$ (`hr_adm`) that strictly increases their utility over $b'$ (`hr_lt`). At the same time, the definition specifies that the resulting profile $b'$ is a best response for $i$, so every admissible deviation yields at most the utility achieved under $b'$ (`h_max`).
rintro rfl rcases h with ⟨i, ⟨r, hr_adm, hr_lt⟩, ⟨r_br, hr_br_adm, hr_br_eq, h_max⟩⟩
A contradiction arises between the strict improvement from deviation $r$ and the optimality of $b'$. automation
Specializing the optimality hypothesis (`h_max`) to the admissible deviation $r$ gives that $i$'s utility under $r$ is at most their utility under $b'$ (`h_le`). This directly conflicts with the assumption that $r$ yields strictly higher utility than $b'$ (`hr_lt`). Linear arithmetic (`linarith`) recognizes the contradiction between $x < y$ and $y \le x$, completing the proof.
have h_le := h_max 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.
theorem irr_step_ne {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') : b' ≠ b := by rintro rfl rcases h with ⟨i, ⟨r, hr_adm, hr_lt⟩, ⟨r_br, hr_br_adm, hr_br_eq, h_max⟩⟩ have h_le := h_max r hr_adm linarith