AFTD Auto-Formalizing Theoretical Domains

irr_step_ne

theoremverified

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.

  1. 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`).

    lines 4–5

      rintro rfl
      rcases h with ⟨i, ⟨r, hr_adm, hr_lt⟩, ⟨r_br, hr_br_adm, hr_br_eq, h_max⟩⟩
  2. 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.

    lines 6–7

      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

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
See it in the graphDiscuss this resultChallenge it