chore_insertion_upgrade_recourse
For any number of agents n : ℕ, picking sequence σ : ℕ → Fin n, and chore costs c : Fin n → ℕ → ℝ, chore insertion satisfies upgrade recourse: has_upgrade_recourse n c (chore_insertion_allocation σ c).
Statement
theorem chore_insertion_upgrade_recourse (n : ℕ) (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) : has_upgrade_recourse n c (chore_insertion_allocation σ c)- Source
- arXiv:2611.00432, Lemma 3.1
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- chore_insertion_allocationGiven an implicit number of agents n, an agent sequence σ : ℕ → Fin n, costs c : Fin n → ℕ → ℝ, and m : ℕ, chore_insertion_allocation σ c…
- 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_slotsGiven an implicit number of agents n, an agent sequence σ : ℕ → Fin n, and costs c : Fin n → ℕ → ℝ, chore_insertion_slots m : ℕ → ℕ…
- chore_insert_passGiven an implicit number of agents n, an agent sequence σ : ℕ → Fin n, costs c : Fin n → ℕ → ℝ, slot count k : ℕ, slot assignment slots :…
- 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…
Read back from the Lean
For any number of agents $n : \mathbb{N}$, sequence of agents $\sigma : \mathbb{N} \to \mathrm{Fin}(n)$, and cost function $c : \mathrm{Fin}(n) \to \mathbb{N} \to \mathbb{R}$, the online allocation family generated by chore insertion (chore_insertion_allocation σ c) has upgrade recourse (has_upgrade_recourse n c).
Specifically, for every step $m : \mathbb{N}$ and for every agent $i : \mathrm{Fin}(n)$, there exists an injective map $\varphi$ from the set of chores allocated to $i$ at step $m$ (i.e., $\{d : \mathrm{Fin}(m) \mid A_m(d) = i\}$) to the set of chores allocated to $i$ at step $m + 1$ (i.e., $\{d : \mathrm{Fin}(m + 1) \mid A_{m+1}(d) = i\}$) such that for every chore $d$ held by $i$ at step $m$, the cost to agent $i$ of the newly matched chore $\varphi(d)$ is weakly less than the cost of $d$ (that is, $c(i, \varphi(d).\mathrm{val}) \le c(i, d.\mathrm{val})$).
Here, the allocation at step $m$, $A_m(d)$, assigns chore $d : \mathrm{Fin}(m)$ to agent $\sigma(k)$, where $k < m$ is a slot index such that slot $k$ at step $m$ contains chore $d$ (or to $\sigma(0)$ if no such slot exists). The slot assignments are computed recursively by chore_insertion_slots: at step $m + 1$, chore $m$ is inserted via a pass chore_insert_pass across slots $0, \dots, m - 1$, where at each slot $k$, agent $\sigma(k)$ swaps their current chore with the incoming chore whenever the incoming chore is strictly cheaper or has equal cost and smaller index, passing the displaced chore to the next slot, and placing the final displaced chore into slot $m$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Chore insertion proceeds in rounds, where the arrival of chore m triggers an insertion pass that may bump existing chores to earlier slots. Because each step of the pass only replaces a chore with a weakly preferred one, every slot's chore cost monotonically non-increases. Since the assignment of chores to slots is a permutation, matching each agent's chore at round m to their chore in the same slot at round m+1 defines an injection showing that every agent's chore bundle weakly improves.
Pass does not change slots with index at least k
By induction on k. Base case is trivial. In the inductive step, if the pass modifies slot k, any slot j >= k+1 is unaffected.
uses
chore_insert_pass,Function.update_applytheorem chore_insertion_upgrade_recourse_pass_ge {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (k : ℕ) (slots : ℕ → ℕ) (b : ℕ) (j : ℕ) (hj : k ≤ j) : (chore_insert_pass σ c k slots b).1 j = slots j := by induction k generalizing slots b with | zero => rfl | succ k ih => rw [chore_insert_pass] dsimp only split · simp only rw [Function.update_apply] split_ifs with h · subst h; omega · exact ih slots b (by omega) · exact ih slots b (by omega)
Pass step k+1 does not change slots with index less than k
The step k+1 only considers modifying slot k, so slot j < k is unchanged.
uses
chore_insert_pass,Function.update_applytheorem chore_insertion_upgrade_recourse_pass_lt {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (k : ℕ) (slots : ℕ → ℕ) (b : ℕ) (j : ℕ) (hj : j < k) : (chore_insert_pass σ c (k + 1) slots b).1 j = (chore_insert_pass σ c k slots b).1 j := by rw [chore_insert_pass] dsimp only split · simp only rw [Function.update_apply] split_ifs with h · omega · rfl · rfl
Slots less than m do not change after step j+1
By induction on m.
uses
chore_insertion_upgrade_recourse_pass_lttheorem chore_insertion_upgrade_recourse_pass_lt_m {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (j m : ℕ) (slots : ℕ → ℕ) (b : ℕ) (hj : j < m) : (chore_insert_pass σ c m slots b).1 j = (chore_insert_pass σ c (j + 1) slots b).1 j := by induction m with | zero => omega | succ m ih => by_cases h : j < m · rw [chore_insertion_upgrade_recourse_pass_lt σ c m slots b j h] exact ih h · have : m = j := by omega subst this rfl
Cost at slot j does not increase after step j+1
Slot j either keeps its chore or takes a cheaper one.
uses
chore_insert_pass,chore_insertion_upgrade_recourse_pass_ge,Function.update_selftheorem chore_insertion_upgrade_recourse_pass_cost_le {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (j : ℕ) (slots : ℕ → ℕ) (b : ℕ) : c (σ j) ((chore_insert_pass σ c (j + 1) slots b).1 j) ≤ c (σ j) (slots j) := by rw [chore_insert_pass] dsimp only rw [chore_insertion_upgrade_recourse_pass_ge σ c j slots b j (by omega)] split · rename_i h simp only rw [Function.update_self] cases h with | inl h1 => linarith | inr h2 => linarith · simp only rw [chore_insertion_upgrade_recourse_pass_ge σ c j slots b j (by omega)]
Cost at slot j does not increase after m steps
Combine previous lemmas.
uses
chore_insertion_upgrade_recourse_pass_lt_m,chore_insertion_upgrade_recourse_pass_cost_letheorem chore_insertion_upgrade_recourse_pass_cost_le_m {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (j m : ℕ) (slots : ℕ → ℕ) (b : ℕ) (hj : j < m) : c (σ j) ((chore_insert_pass σ c m slots b).1 j) ≤ c (σ j) (slots j) := by rw [chore_insertion_upgrade_recourse_pass_lt_m σ c j m slots b hj] exact chore_insertion_upgrade_recourse_pass_cost_le σ c j slots b
Chore conservation during pass
Induction on k.
uses
chore_insert_pass,chore_insertion_upgrade_recourse_pass_ge,le_refl,range_add_one,image_insert,insert_union,Function.update_self,image_congr,mem_range,mem_coe,Function.update_of_ne,mem_insert,mem_union,mem_singletontheorem chore_insertion_upgrade_recourse_pass_image {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (k : ℕ) (slots : ℕ → ℕ) (b : ℕ) : Finset.image (chore_insert_pass σ c k slots b).1 (Finset.range k) ∪ {(chore_insert_pass σ c k slots b).2} = Finset.image slots (Finset.range k) ∪ {b} := by induction k generalizing slots b with | zero => rw [chore_insert_pass] | succ k ih => rw [chore_insert_pass] dsimp only set res := chore_insert_pass σ c k slots b have h_ih := ih slots b have h_ge : res.1 k = slots k := chore_insertion_upgrade_recourse_pass_ge σ c k slots b k (le_refl k) rw [range_add_one, image_insert, insert_union] split · rename_i h dsimp only rw [Function.update_self] have h_eq : Finset.image (Function.update res.1 k res.2) (range k) = Finset.image res.1 (range k) := by apply Finset.image_congr intro x hx have : x < k := mem_range.mp (mem_coe.mp hx) rw [Function.update_of_ne (by omega)] rw [h_eq] have h1 : insert res.2 (image res.1 (range k) ∪ {res.1 k}) = insert (res.1 k) (image res.1 (range k) ∪ {res.2}) := by ext x; simp only [mem_insert, mem_union, mem_singleton]; tauto rw [h1, h_ge] have h2 : insert (slots k) (image res.1 (range k) ∪ {res.2}) = insert (slots k) (image slots (range k) ∪ {b}) := by rw [h_ih] rw [h2] ext x simp only [mem_insert, mem_union, mem_singleton, image_insert] tauto · rename_i h dsimp only rw [h_ge] have h2 : insert (slots k) (image res.1 (range k) ∪ {res.2}) = insert (slots k) (image slots (range k) ∪ {b}) := by rw [h_ih] rw [h2] ext x simp only [mem_insert, mem_union, mem_singleton, image_insert] tauto
Image of slots at round m is range m
Induction on m.
uses
chore_insertion_slots,range_zero,image_empty,range_add_one,image_insert,Function.update_self,image_congr,mem_range,mem_coe,Function.update_of_ne,mem_insert,mem_union,mem_singleton,chore_insertion_upgrade_recourse_pass_image,union_comm,insert_eqtheorem chore_insertion_upgrade_recourse_slots_image {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m : ℕ) : Finset.image (chore_insertion_slots σ c m) (Finset.range m) = Finset.range m := by induction m with | zero => rw [chore_insertion_slots] simp only [range_zero, image_empty] | succ m ih => rw [chore_insertion_slots] dsimp only set prev := chore_insertion_slots σ c m set pass := chore_insert_pass σ c m prev m rw [range_add_one, image_insert] rw [Function.update_self] have h_eq : Finset.image (Function.update pass.1 m pass.2) (range m) = Finset.image pass.1 (range m) := by apply Finset.image_congr intro x hx have : x < m := mem_range.mp (mem_coe.mp hx) rw [Function.update_of_ne (by omega)] rw [h_eq] have h_union : insert pass.2 (image pass.1 (range m)) = image pass.1 (range m) ∪ {pass.2} := by ext x; simp only [mem_insert, mem_union, mem_singleton]; tauto rw [h_union, chore_insertion_upgrade_recourse_pass_image σ c m prev m, ih] rw [union_comm, ← insert_eq]
Slots produce elements less than m
Membership in range m.
uses
mem_image,mem_range,chore_insertion_upgrade_recourse_slots_imagetheorem chore_insertion_upgrade_recourse_slots_lt {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m k : ℕ) (hk : k < m) : chore_insertion_slots σ c m k < m := by have : chore_insertion_slots σ c m k ∈ Finset.image (chore_insertion_slots σ c m) (Finset.range m) := by rw [mem_image] exact ⟨k, mem_range.mpr hk, rfl⟩ rw [chore_insertion_upgrade_recourse_slots_image, mem_range] at this exact this
Slots map is injective on range m
From cardinality of image.
uses
injOn_of_card_image_eq,chore_insertion_upgrade_recourse_slots_imagetheorem chore_insertion_upgrade_recourse_slots_injOn {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m : ℕ) : Set.InjOn (chore_insertion_slots σ c m) (Finset.range m : Set ℕ) := by apply injOn_of_card_image_eq rw [chore_insertion_upgrade_recourse_slots_image]
Slots map is surjective onto range m
By preimage in range m.
uses
mem_range,chore_insertion_upgrade_recourse_slots_image,mem_imagetheorem chore_insertion_upgrade_recourse_slots_surj {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m d : ℕ) (hd : d < m) : ∃ k < m, chore_insertion_slots σ c m k = d := by have hd' : d ∈ Finset.range m := mem_range.mpr hd rw [← chore_insertion_upgrade_recourse_slots_image σ c m] at hd' rcases mem_image.mp hd' with ⟨k, hk, rfl⟩ exact ⟨k, mem_range.mp hk, rfl⟩
Cost at each slot does not increase from round m to m+1
Unfold slots definition.
uses
chore_insertion_slots,Function.update_apply,chore_insertion_upgrade_recourse_pass_cost_le_mtheorem chore_insertion_upgrade_recourse_slots_cost_le {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m k : ℕ) (hk : k < m) : c (σ k) (chore_insertion_slots σ c (m + 1) k) ≤ c (σ k) (chore_insertion_slots σ c m k) := by have h_succ : chore_insertion_slots σ c (m + 1) k = (chore_insert_pass σ c m (chore_insertion_slots σ c m) m).1 k := by rw [chore_insertion_slots] dsimp only rw [Function.update_apply] split_ifs with h · omega · rfl rw [h_succ] exact chore_insertion_upgrade_recourse_pass_cost_le_m σ c k m (chore_insertion_slots σ c m) m hk
Allocation at slot k is agent sigma k
By injectivity of slots.
uses
chore_insertion_allocation,dif_pos,Classical.choose_spec,mem_range,chore_insertion_upgrade_recourse_slots_injOntheorem chore_insertion_upgrade_recourse_allocation_eq {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m : ℕ) (k : ℕ) (hk : k < m) : chore_insertion_allocation σ c m ⟨chore_insertion_slots σ c m k, chore_insertion_upgrade_recourse_slots_lt σ c m k hk⟩ = σ k := by unfold chore_insertion_allocation dsimp only have h : ∃ k' < m, chore_insertion_slots σ c m k' = chore_insertion_slots σ c m k := ⟨k, hk, rfl⟩ rw [dif_pos h] have h_choose := Classical.choose_spec h have h1 : Classical.choose h ∈ (range m : Set ℕ) := mem_range.mpr h_choose.1 have h2 : k ∈ (range m : Set ℕ) := mem_range.mpr hk have := chore_insertion_upgrade_recourse_slots_injOn σ c m h1 h2 h_choose.2 rw [this]
Upgrade recourse holds
Construct injection slot-by-slot.
uses
is_upgrade_feasible,chore_insertion_upgrade_recourse_slots_surj,Classical.choose,Classical.choose_spec,chore_insertion_allocation,dif_pos,mem_range,chore_insertion_upgrade_recourse_slots_injOn,chore_insertion_upgrade_recourse_slots_lt,chore_insertion_upgrade_recourse_allocation_eq,Subtype.ext,Fin.ext,chore_insertion_upgrade_recourse_slots_cost_letheorem chore_insertion_upgrade_recourse (n : ℕ) (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) : has_upgrade_recourse n c (chore_insertion_allocation σ c) := by intro m unfold is_upgrade_feasible intro i let slot_of (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : ℕ := Classical.choose (chore_insertion_upgrade_recourse_slots_surj σ c m d.val.val d.val.isLt) have h_slot (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : slot_of d < m ∧ chore_insertion_slots σ c m (slot_of d) = d.val.val := Classical.choose_spec (chore_insertion_upgrade_recourse_slots_surj σ c m d.val.val d.val.isLt) have h_owner (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : σ (slot_of d) = i := by have hd_prop := d.prop unfold chore_insertion_allocation at hd_prop have h : ∃ k < m, chore_insertion_slots σ c m k = d.val.val := ⟨slot_of d, (h_slot d).1, (h_slot d).2⟩ rw [dif_pos h] at hd_prop have h_ch := Classical.choose_spec h have h1 : Classical.choose h ∈ (range m : Set ℕ) := mem_range.mpr h_ch.1 have h2 : slot_of d ∈ (range m : Set ℕ) := mem_range.mpr (h_slot d).1 have h_eq : Classical.choose h = slot_of d := chore_insertion_upgrade_recourse_slots_injOn σ c m h1 h2 (h_ch.2.trans (h_slot d).2.symm) rwa [h_eq] at hd_prop have h_slot_lt_succ (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : slot_of d < m + 1 := by have := (h_slot d).1; omega let φ (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : {d' : Fin (m + 1) // chore_insertion_allocation σ c (m + 1) d' = i} := ⟨⟨chore_insertion_slots σ c (m + 1) (slot_of d), chore_insertion_upgrade_recourse_slots_lt σ c (m + 1) (slot_of d) (h_slot_lt_succ d)⟩, by have := chore_insertion_upgrade_recourse_allocation_eq σ c (m + 1) (slot_of d) (h_slot_lt_succ d) rw [this, h_owner d]⟩ refine ⟨φ, ?_, ?_⟩ · intro d1 d2 h_eq apply Subtype.ext apply Fin.ext injection h_eq with h_val injection h_val with h_slot_eq have hk1 : slot_of d1 ∈ (range (m + 1) : Set ℕ) := mem_range.mpr (h_slot_lt_succ d1) have hk2 : slot_of d2 ∈ (range (m + 1) : Set ℕ) := mem_range.mpr (h_slot_lt_succ d2) have h_slot_same : slot_of d1 = slot_of d2 := chore_insertion_upgrade_recourse_slots_injOn σ c (m + 1) hk1 hk2 h_slot_eq have hd1 := (h_slot d1).2 have hd2 := (h_slot d2).2 rw [h_slot_same] at hd1 exact hd1.symm.trans hd2 · intro d dsimp only [φ] have h_cost := chore_insertion_upgrade_recourse_slots_cost_le σ c m (slot_of d) (h_slot d).1 rw [h_owner d] at h_cost rw [(h_slot d).2] at h_cost exact h_cost
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsettheorem chore_insertion_upgrade_recourse_pass_ge {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (k : ℕ) (slots : ℕ → ℕ) (b : ℕ) (j : ℕ) (hj : k ≤ j) : (chore_insert_pass σ c k slots b).1 j = slots j := by induction k generalizing slots b with | zero => rfl | succ k ih => rw [chore_insert_pass] dsimp only split · simp only rw [Function.update_apply] split_ifs with h · subst h; omega · exact ih slots b (by omega) · exact ih slots b (by omega)theorem chore_insertion_upgrade_recourse_pass_lt {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (k : ℕ) (slots : ℕ → ℕ) (b : ℕ) (j : ℕ) (hj : j < k) : (chore_insert_pass σ c (k + 1) slots b).1 j = (chore_insert_pass σ c k slots b).1 j := by rw [chore_insert_pass] dsimp only split · simp only rw [Function.update_apply] split_ifs with h · omega · rfl · rfltheorem chore_insertion_upgrade_recourse_pass_lt_m {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (j m : ℕ) (slots : ℕ → ℕ) (b : ℕ) (hj : j < m) : (chore_insert_pass σ c m slots b).1 j = (chore_insert_pass σ c (j + 1) slots b).1 j := by induction m with | zero => omega | succ m ih => by_cases h : j < m · rw [chore_insertion_upgrade_recourse_pass_lt σ c m slots b j h] exact ih h · have : m = j := by omega subst this rfltheorem chore_insertion_upgrade_recourse_pass_cost_le {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (j : ℕ) (slots : ℕ → ℕ) (b : ℕ) : c (σ j) ((chore_insert_pass σ c (j + 1) slots b).1 j) ≤ c (σ j) (slots j) := by rw [chore_insert_pass] dsimp only rw [chore_insertion_upgrade_recourse_pass_ge σ c j slots b j (by omega)] split · rename_i h simp only rw [Function.update_self] cases h with | inl h1 => linarith | inr h2 => linarith · simp only rw [chore_insertion_upgrade_recourse_pass_ge σ c j slots b j (by omega)]theorem chore_insertion_upgrade_recourse_pass_cost_le_m {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (j m : ℕ) (slots : ℕ → ℕ) (b : ℕ) (hj : j < m) : c (σ j) ((chore_insert_pass σ c m slots b).1 j) ≤ c (σ j) (slots j) := by rw [chore_insertion_upgrade_recourse_pass_lt_m σ c j m slots b hj] exact chore_insertion_upgrade_recourse_pass_cost_le σ c j slots btheorem chore_insertion_upgrade_recourse_pass_image {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (k : ℕ) (slots : ℕ → ℕ) (b : ℕ) : Finset.image (chore_insert_pass σ c k slots b).1 (Finset.range k) ∪ {(chore_insert_pass σ c k slots b).2} = Finset.image slots (Finset.range k) ∪ {b} := by induction k generalizing slots b with | zero => rw [chore_insert_pass] | succ k ih => rw [chore_insert_pass] dsimp only set res := chore_insert_pass σ c k slots b have h_ih := ih slots b have h_ge : res.1 k = slots k := chore_insertion_upgrade_recourse_pass_ge σ c k slots b k (le_refl k) rw [range_add_one, image_insert, insert_union] split · rename_i h dsimp only rw [Function.update_self] have h_eq : Finset.image (Function.update res.1 k res.2) (range k) = Finset.image res.1 (range k) := by apply Finset.image_congr intro x hx have : x < k := mem_range.mp (mem_coe.mp hx) rw [Function.update_of_ne (by omega)] rw [h_eq] have h1 : insert res.2 (image res.1 (range k) ∪ {res.1 k}) = insert (res.1 k) (image res.1 (range k) ∪ {res.2}) := by ext x; simp only [mem_insert, mem_union, mem_singleton]; tauto rw [h1, h_ge] have h2 : insert (slots k) (image res.1 (range k) ∪ {res.2}) = insert (slots k) (image slots (range k) ∪ {b}) := by rw [h_ih] rw [h2] ext x simp only [mem_insert, mem_union, mem_singleton, image_insert] tauto · rename_i h dsimp only rw [h_ge] have h2 : insert (slots k) (image res.1 (range k) ∪ {res.2}) = insert (slots k) (image slots (range k) ∪ {b}) := by rw [h_ih] rw [h2] ext x simp only [mem_insert, mem_union, mem_singleton, image_insert] tautotheorem chore_insertion_upgrade_recourse_slots_image {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m : ℕ) : Finset.image (chore_insertion_slots σ c m) (Finset.range m) = Finset.range m := by induction m with | zero => rw [chore_insertion_slots] simp only [range_zero, image_empty] | succ m ih => rw [chore_insertion_slots] dsimp only set prev := chore_insertion_slots σ c m set pass := chore_insert_pass σ c m prev m rw [range_add_one, image_insert] rw [Function.update_self] have h_eq : Finset.image (Function.update pass.1 m pass.2) (range m) = Finset.image pass.1 (range m) := by apply Finset.image_congr intro x hx have : x < m := mem_range.mp (mem_coe.mp hx) rw [Function.update_of_ne (by omega)] rw [h_eq] have h_union : insert pass.2 (image pass.1 (range m)) = image pass.1 (range m) ∪ {pass.2} := by ext x; simp only [mem_insert, mem_union, mem_singleton]; tauto rw [h_union, chore_insertion_upgrade_recourse_pass_image σ c m prev m, ih] rw [union_comm, ← insert_eq]theorem chore_insertion_upgrade_recourse_slots_lt {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m k : ℕ) (hk : k < m) : chore_insertion_slots σ c m k < m := by have : chore_insertion_slots σ c m k ∈ Finset.image (chore_insertion_slots σ c m) (Finset.range m) := by rw [mem_image] exact ⟨k, mem_range.mpr hk, rfl⟩ rw [chore_insertion_upgrade_recourse_slots_image, mem_range] at this exact thistheorem chore_insertion_upgrade_recourse_slots_injOn {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m : ℕ) : Set.InjOn (chore_insertion_slots σ c m) (Finset.range m : Set ℕ) := by apply injOn_of_card_image_eq rw [chore_insertion_upgrade_recourse_slots_image]theorem chore_insertion_upgrade_recourse_slots_surj {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m d : ℕ) (hd : d < m) : ∃ k < m, chore_insertion_slots σ c m k = d := by have hd' : d ∈ Finset.range m := mem_range.mpr hd rw [← chore_insertion_upgrade_recourse_slots_image σ c m] at hd' rcases mem_image.mp hd' with ⟨k, hk, rfl⟩ exact ⟨k, mem_range.mp hk, rfl⟩theorem chore_insertion_upgrade_recourse_slots_cost_le {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m k : ℕ) (hk : k < m) : c (σ k) (chore_insertion_slots σ c (m + 1) k) ≤ c (σ k) (chore_insertion_slots σ c m k) := by have h_succ : chore_insertion_slots σ c (m + 1) k = (chore_insert_pass σ c m (chore_insertion_slots σ c m) m).1 k := by rw [chore_insertion_slots] dsimp only rw [Function.update_apply] split_ifs with h · omega · rfl rw [h_succ] exact chore_insertion_upgrade_recourse_pass_cost_le_m σ c k m (chore_insertion_slots σ c m) m hktheorem chore_insertion_upgrade_recourse_allocation_eq {n : ℕ} (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) (m : ℕ) (k : ℕ) (hk : k < m) : chore_insertion_allocation σ c m ⟨chore_insertion_slots σ c m k, chore_insertion_upgrade_recourse_slots_lt σ c m k hk⟩ = σ k := by unfold chore_insertion_allocation dsimp only have h : ∃ k' < m, chore_insertion_slots σ c m k' = chore_insertion_slots σ c m k := ⟨k, hk, rfl⟩ rw [dif_pos h] have h_choose := Classical.choose_spec h have h1 : Classical.choose h ∈ (range m : Set ℕ) := mem_range.mpr h_choose.1 have h2 : k ∈ (range m : Set ℕ) := mem_range.mpr hk have := chore_insertion_upgrade_recourse_slots_injOn σ c m h1 h2 h_choose.2 rw [this]/-- Chore insertion satisfies upgrade recourse at every arrival. -/theorem chore_insertion_upgrade_recourse (n : ℕ) (σ : ℕ → Fin n) (c : Fin n → ℕ → ℝ) : has_upgrade_recourse n c (chore_insertion_allocation σ c) := by intro m unfold is_upgrade_feasible intro i let slot_of (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : ℕ := Classical.choose (chore_insertion_upgrade_recourse_slots_surj σ c m d.val.val d.val.isLt) have h_slot (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : slot_of d < m ∧ chore_insertion_slots σ c m (slot_of d) = d.val.val := Classical.choose_spec (chore_insertion_upgrade_recourse_slots_surj σ c m d.val.val d.val.isLt) have h_owner (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : σ (slot_of d) = i := by have hd_prop := d.prop unfold chore_insertion_allocation at hd_prop have h : ∃ k < m, chore_insertion_slots σ c m k = d.val.val := ⟨slot_of d, (h_slot d).1, (h_slot d).2⟩ rw [dif_pos h] at hd_prop have h_ch := Classical.choose_spec h have h1 : Classical.choose h ∈ (range m : Set ℕ) := mem_range.mpr h_ch.1 have h2 : slot_of d ∈ (range m : Set ℕ) := mem_range.mpr (h_slot d).1 have h_eq : Classical.choose h = slot_of d := chore_insertion_upgrade_recourse_slots_injOn σ c m h1 h2 (h_ch.2.trans (h_slot d).2.symm) rwa [h_eq] at hd_prop have h_slot_lt_succ (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : slot_of d < m + 1 := by have := (h_slot d).1; omega let φ (d : {d : Fin m // chore_insertion_allocation σ c m d = i}) : {d' : Fin (m + 1) // chore_insertion_allocation σ c (m + 1) d' = i} := ⟨⟨chore_insertion_slots σ c (m + 1) (slot_of d), chore_insertion_upgrade_recourse_slots_lt σ c (m + 1) (slot_of d) (h_slot_lt_succ d)⟩, by have := chore_insertion_upgrade_recourse_allocation_eq σ c (m + 1) (slot_of d) (h_slot_lt_succ d) rw [this, h_owner d]⟩ refine ⟨φ, ?_, ?_⟩ · intro d1 d2 h_eq apply Subtype.ext apply Fin.ext injection h_eq with h_val injection h_val with h_slot_eq have hk1 : slot_of d1 ∈ (range (m + 1) : Set ℕ) := mem_range.mpr (h_slot_lt_succ d1) have hk2 : slot_of d2 ∈ (range (m + 1) : Set ℕ) := mem_range.mpr (h_slot_lt_succ d2) have h_slot_same : slot_of d1 = slot_of d2 := chore_insertion_upgrade_recourse_slots_injOn σ c (m + 1) hk1 hk2 h_slot_eq have hd1 := (h_slot d1).2 have hd2 := (h_slot d2).2 rw [h_slot_same] at hd1 exact hd1.symm.trans hd2 · intro d dsimp only [φ] have h_cost := chore_insertion_upgrade_recourse_slots_cost_le σ c m (slot_of d) (h_slot d).1 rw [h_owner d] at h_cost rw [(h_slot d).2] at h_cost exact h_cost