chore_insert_pass
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')