AFTD Auto-Formalizing Theoretical Domains

is_upgrade_feasible

def

An 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 has an injective mapping φ from her old bundle {d : Fin m // A d = i} to her new bundle {d : Fin (m + 1) // A' d = i} such that for all d, c i (φ d) ≤ c i (Fin.castSucc d).

Statement

def is_upgrade_feasible {m n : ℕ} (c : Fin n → Fin (m + 1) → ℝ) (A : Fin m → Fin n) (A' : Fin (m + 1) → Fin n) : Prop
Defined in
arXiv:2611.00432, Definition 2.1
Verified
03 Nov 2026
Axioms
none listed
Used by 2
  • has_upgrade_recourseAn online chore allocation sequence A : ∀ m : ℕ, Fin m → Fin n for n agents has upgrade recourse with respect to chore costs c : Fin n → ℕ…
  • 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 natural numbers m and n, a function c : Fin n → Fin (m + 1) → ℝ, and assignments A : Fin m → Fin n and A' : Fin (m + 1) → Fin n, is_upgrade_feasible c A A' asserts that for every i : Fin n, there exists a function φ from {d : Fin m // A d = i} to {d : Fin (m + 1) // A' d = i} such that: 1. φ is injective; 2. for every d in the domain {d : Fin m // A d = i}, c i (φ d).val ≤ c i (Fin.castSucc d.val).

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 update between two chore allocations is upgrade-feasible if each agent receives weakly less costly replacement chores. -/
def is_upgrade_feasible {m n : ℕ} (c : Fin n → Fin (m + 1) → ℝ) (A : Fin m → Fin n) (A' : Fin (m + 1) → Fin n) : Prop := ∀ i : Fin n, ∃ φ : {d : Fin m // A d = i} → {d : Fin (m + 1) // A' d = i}, Function.Injective φ ∧ ∀ d, c i (φ d).val ≤ c i (Fin.castSucc d.val)
See it in the graphDiscuss this resultChallenge it