AFTD Auto-Formalizing Theoretical Domains

irr_step

def

One step of iterated picking sequences restricted to admissible bids adm: some agent i that has a strictly profitable admissible manipulation changes its bid to a best response among its admissible bids, the other bids unchanged. Utilities are additive with item values v.

Statement

def irr_step {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) : Prop
Defined in
arXiv:2610.23040 Sec. 2 (Iterated setting) and Sec. 3 (restricted manipulations)
Verified
19 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 3

Lean source view module on GitHub

/-- One step of the iterated picking-sequence dynamics `IPS_π` restricted to the admissible bids `adm b i`: an agent `i` with a strictly profitable admissible manipulation replaces its bid by a best response among its admissible bids; the other bids are unchanged. Utilities are additive with item values `v`. -/
def irr_step {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) : Prop :=
  ∃ i : N,
    (∃ r, adm b i r ∧ ∑ g ∈ picking_sequence_outcome seq b i, v i g <
        ∑ g ∈ picking_sequence_outcome seq (Function.update b i r) i, v i g) ∧
    ∃ r, adm b i r ∧ b' = Function.update b i r ∧
      ∀ r', adm b i r' → ∑ g ∈ picking_sequence_outcome seq (Function.update b i r') i, v i g ≤
        ∑ g ∈ picking_sequence_outcome seq b' i, v i g
See it in the graphDiscuss this resultChallenge it