AFTD Auto-Formalizing Theoretical Domains

irr_step_changed_agent_strict

theoremverified

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.

  1. 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₂.

    lines 8–9

      obtain ⟨i, ⟨r₁, _hr₁adm, hr₁⟩, r₂, hr₂adm, hb', hbr⟩ := h
      have hbi : b' i = r₂ := by rw [hb']; simp
  2. 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.

    line 10

      refine ⟨i, ?_, ?_, ?_⟩
  3. 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.

    lines 11–12

      · show adm b i (b' i)
        rw [hbi]; exact hr₂adm
  4. 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.

    lines 13–14

      · show b' = Function.update b i (b' i)
        rw [hbi]; exact hb'
  5. 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 ℝ.

    lines 15–19

      · 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

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