AFTD Auto-Formalizing Theoretical Domains

has_upgrade_recourse

def

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))
See it in the graphDiscuss this resultChallenge it