chore_insertion_slots
Given an implicit number of agents n, an agent sequence σ : ℕ → Fin n, and costs c : Fin n → ℕ → ℝ, chore_insertion_slots m : ℕ → ℕ returns the slot assignment of chores after m arrivals in chore insertion: at m = 0 it is id, and at m + 1 it passes the new chore m through the previous m slots using chore_insert_pass and places the remaining buffer chore in slot m.
Statement
noncomputable def chore_insertion_slots {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) : ℕ → (ℕ → ℕ)
- Defined in
- arXiv:2611.00432, Algorithm 1
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- chore_insert_passGiven an implicit number of agents n, an agent sequence σ : ℕ → Fin n, costs c : Fin n → ℕ → ℝ, slot count k : ℕ, slot assignment slots :…
- 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_allocationGiven an implicit number of agents n, an agent sequence σ : ℕ → Fin n, costs c : Fin n → ℕ → ℝ, and m : ℕ, chore_insertion_allocation σ c…
Read back from the Lean
Given an implicit natural number n, a sequence of agents σ : ℕ → Fin n, and a cost function c : Fin n → ℕ → ℝ, chore_insertion_slots σ c is defined recursively on m : ℕ to produce a slot-assignment function ℕ → ℕ:
- Base case m = 0: returns the identity function id : ℕ → ℕ (i.e., x ↦ x).
- Inductive step m + 1:
1. Let prev := chore_insertion_slots σ c m.
2. Let (new_slots, b) := chore_insert_pass σ c m prev m.
3. Returns Function.update new_slots m b (the function new_slots with index m updated to 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
/-- The slot contents after m chore arrivals under chore insertion. -/ noncomputable def chore_insertion_slots {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) : ℕ → (ℕ → ℕ) | 0 => id | m + 1 => let prev := chore_insertion_slots σ c m let (new_slots, b) := chore_insert_pass σ c m prev m Function.update new_slots m b