AFTD Auto-Formalizing Theoretical Domains

chore_insert_pass

def

Given an implicit number of agents n, an agent sequence σ : ℕ → Fin n, costs c : Fin n → ℕ → ℝ, slot count k : ℕ, slot assignment slots : ℕ → ℕ, and buffer chore b : ℕ, chore_insert_pass returns a pair (slots', b') : (ℕ → ℕ) × ℕ: for k = 0 it returns (slots, b); for k + 1 it recursively processes the first k slots, and at slot k owned by σ k, swaps the buffer with the occupant if the buffer is cheaper to σ k with smaller-index tie-breaking, returning the updated slots and displaced chore.

Statement

noncomputable def chore_insert_pass {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) : ℕ → (ℕ → ℕ) → ℕ → (ℕ → ℕ) × ℕ
Defined in
arXiv:2611.00432, Algorithm 1
Verified
03 Nov 2026
Axioms
none listed
Used by 2
  • chore_insertion_upgrade_recourseFor any number of agents n : ℕ, picking sequence σ : ℕ → Fin n, and chore costs c : Fin n → ℕ → ℝ, chore insertion satisfies upgrade…
  • chore_insertion_slotsGiven an implicit number of agents n, an agent sequence σ : ℕ → Fin n, and costs c : Fin n → ℕ → ℝ, chore_insertion_slots m : ℕ → ℕ…

Read back from the Lean

chore_insert_pass is a recursively defined function that takes: - an implicit natural number n, - a sequence of agents σ : ℕ → Fin n, - a cost function c : Fin n → ℕ → ℝ, and maps a step count m : ℕ, a slot assignment function slots : ℕ → ℕ, and a candidate item b : ℕ to an updated pair (slots', b') : (ℕ → ℕ) × ℕ as follows: - **Base case (0):** Given (0, slots, b), it returns (slots, b). - **Recursive step (k + 1):** Given (k + 1, slots, b), it first recursively evaluates (slots', b') = chore_insert_pass σ c k slots b. Letting agent i = σ k and current slot occupant o = slots' k, - if c i b' < c i o ∨ (c i b' = c i o ∧ b' < o) (that is, if b' is strictly preferred to o by agent i under the lexicographical order on (c i ·, ·)), it returns (Function.update slots' k b', o); - otherwise, it returns (slots', b').

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- One pass of the chore insertion buffer through existing slots. -/
noncomputable def chore_insert_pass {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) : ℕ → (ℕ → ℕ) → ℕ → (ℕ → ℕ) × ℕ
| 0, slots, b => (slots, b)
| k + 1, slots, b =>
  let (slots', b') := chore_insert_pass σ c k slots b
  let i := σ k
  let o := slots' k
  if c i b' < c i o ∨ (c i b' = c i o ∧ b' < o) then
    (Function.update slots' k b', o)
  else
    (slots', b')
See it in the graphDiscuss this resultChallenge it