has_upgrade_recourse
An online chore allocation sequence A : ∀ m : ℕ, Fin m → Fin n for n agents has upgrade recourse with respect to chore costs c : Fin n → ℕ → ℝ if for every arrival m : ℕ, the update from allocation A m to A (m + 1) is upgrade-feasible (is_upgrade_feasible) under the costs fun i (d : Fin (m + 1)) => c i d.val.
Statement
def has_upgrade_recourse (n : ℕ) (c : Fin n → ℕ → ℝ) (A : ∀ m : ℕ, Fin m → Fin n) : Prop
- Defined in
- arXiv:2611.00432, Definition 2.1
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- is_upgrade_feasibleAn update from an allocation A : Fin m → Fin n to an allocation A' : Fin (m + 1) → Fin n is upgrade-feasible for costs c if each agent i…
- Used by 2
- DeterministicOnlineChoreRuleA deterministic prediction-free online chore allocation algorithm for n agents with upgrade recourse: for each sequence of arrival costs…
- chore_insertion_upgrade_recourseFor any number of agents n : ℕ, picking sequence σ : ℕ → Fin n, and chore costs c : Fin n → ℕ → ℝ, chore insertion satisfies upgrade…
Read back from the Lean
Given a natural number n, a cost function c : Fin n → ℕ → ℝ, and a family of assignments A : ∀ m : ℕ, Fin m → Fin n, has_upgrade_recourse n c A asserts that for every natural number m : ℕ, the transition from assignment A m to A (m + 1) is upgrade-feasible (is_upgrade_feasible) with respect to the cost function (fun i d => c i d.val) : Fin n → Fin (m + 1) → ℝ.
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
/-- An online chore allocation algorithm has upgrade recourse if every single-arrival update is upgrade-feasible. -/ def has_upgrade_recourse (n : ℕ) (c : Fin n → ℕ → ℝ) (A : ∀ m : ℕ, Fin m → Fin n) : Prop := ∀ m : ℕ, is_upgrade_feasible (fun i d => c i d.val) (A m) (A (m + 1))