is_upgrade_feasible
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)