ido_remaining_chores_cost_le_one_third
In an identically ordered instance with nonnegative costs and maximin share 1 for each agent, every remaining chore g in V (with index at least 2n) has cost at most 1/3 for each agent i.
Statement
lemma ido_remaining_chores_cost_le_one_third
(n m : ℕ) (h2n : 2 * n ≤ m) (c : Fin n → Fin m → ℝ)
(hc_nonneg : ∀ i e, 0 ≤ c i e)
(h_ido : is_identically_ordered c)
(h_mms : ∀ i : Fin n, chore_maximin_share n (c i) = 1)
(i : Fin n) (g : Fin m) (hg : g ∈ chore_remaining_set m n) :
c i g ≤ 1 / 3- Source
- arXiv:2611.04884 Lemma 4.1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- is_identically_orderedAn instance of m chores and n agents with cost functions c is identically ordered (IDO) if for every agent i, the cost function c_i is…
- chore_remaining_setFor m chores and n agents, the set V of remaining chores consists of all chores whose index is at least 2n.
- chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 1
- ido_chore_opposite_pairs_cost_boundsIn an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1,…
Read back from the Lean
Given natural numbers $n$ and $m$ satisfying $2n \le m$, and a cost function $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ mapping each agent and chore to a real cost, assume: 1. Every cost is non-negative: $0 \le c(i, e)$ for all $i : \text{Fin } n$ and $e : \text{Fin } m$. 2. Costs are identically ordered: for each agent $i : \text{Fin } n$, the function $c(i)$ is antitone (i.e., non-increasing with respect to the index of the chores). 3. The chore maximin share of each agent $i$ among $n$ partitions equals 1: $\text{chore\_maximin\_share } n (c(i)) = 1$. Then, for any agent $i : \text{Fin } n$ and any chore $g : \text{Fin } m$ whose index satisfies $2n \le g.val$ (i.e., $g \in \text{chore\_remaining\_set } m\ n$), the cost $c(i, g)$ is at most $1/3$.
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
To show that any remaining chore g (with index at least 2n) has cost at most 1/3 for agent i, the proof examines an arbitrary partition P of the chores among the n agents. Since there are 2n + 1 chores with index at most 2n, the pigeonhole principle guarantees that some agent receives at least 3 of these chores. In an identically ordered instance, chore costs are non-increasing with respect to chore index, so each of these at least 3 chores costs at least c i g, making that agent's bundle cost at least 3 * c i g. Consequently, the maximum bundle cost in any partition is at least 3 * c i g, which gives a lower bound of 3 * c i g on the chore maximin share. Since agent i's maximin share is 1, this forces 3 * c i g ≤ 1, yielding c i g ≤ 1/3.
The chore b with index 2n is a valid element of Fin m and satisfies b ≤ g.
The hypothesis that g belongs to the remaining chores means that its index is at least 2n. Because g < m, we have 2n < m, which allows us to define the boundary chore b = 2n in Fin m. Since g has index at least 2n, b ≤ g.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave h2n_lt : 2 * n < m := by simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg omega have hg_val : 2 * n ≤ g.val := by simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg exact hg let b : Fin m := ⟨2 * n, h2n_lt⟩ have hb_le_g : b ≤ g := hg_val
Under any partition P of chores among the n agents, some agent y receives at least 3 chores from {0, …, b}.
Fix an arbitrary chore allocation P : Fin m → Fin n. The initial prefix of chores {0, …, b} contains b + 1 = 2n + 1 chores. By the generalized pigeonhole principle (`Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to`), since there are n agents and 2n + 1 > 2n, some agent y must receive strictly more than 2 chores from this set.
uses
Finset.card_univ,Fintype.card_fin,Fin.card_Iic,Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_tohave hP : ∀ P : Fin m → Fin n, 3 * c i g ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by intro P have hmaps : ∀ a ∈ Finset.Iic b, P a ∈ (Finset.univ : Finset (Fin n)) := by simp have hcard : (Finset.univ : Finset (Fin n)).card * 2 < (Finset.Iic b).card := by rw [Finset.card_univ, Fintype.card_fin, Fin.card_Iic b] dsimp [b] omega obtain ⟨y, -, hy⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to hmaps hcard let Sy := Finset.filter (fun x => P x = y) (Finset.Iic b) have hy' : 2 < Sy.card := hy
The cost to agent i of the sub-collection Sy ⊆ {0, …, b} assigned to agent y is at most the total cost of agent y's bundle.
The set Sy consists of the chores up to b allocated to agent y, which is a subset of agent y's full bundle under P. Because all chore costs are non-negative, the sum of costs over Sy is bounded by the sum of costs over the entire bundle.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.sum_le_sum_of_subset_of_nonneghave hSy_sub : Sy ⊆ bundle_of P y := by intro x hx rw [Finset.mem_filter] at hx simp only [Finset.mem_filter, bundle_of, Finset.mem_univ, true_and] exact hx.2 have hSy_le_bundle : ∑ x ∈ Sy, c i x ≤ ∑ x ∈ bundle_of P y, c i x := by apply Finset.sum_le_sum_of_subset_of_nonneg hSy_sub intro x _ _ exact hc_nonneg i x
Agent y's bundle under partition P has cost at least 3 * c i g for agent i.
Every chore x in Sy satisfies x ≤ b ≤ g. Since the instance is identically ordered, agent i's cost function is antitone (non-increasing with index), so each x ∈ Sy satisfies c i x ≥ c i g. Summing this over Sy gives |Sy| * c i g ≤ ∑ x ∈ Sy, c i x. Since |Sy| ≥ 3 and chore costs are non-negative, 3 * c i g ≤ |Sy| * c i g. Transitivity with the bundle bound shows that agent y's bundle costs at least 3 * c i g.
uses
Finset.mem_filter,Finset.mem_Iic.mp,le_trans,Finset.sum_le_sumhave h_cg_le_x : ∀ x ∈ Sy, c i g ≤ c i x := by intro x hx rw [Finset.mem_filter] at hx have hxb : x ≤ b := Finset.mem_Iic.mp hx.1 have hxg : x ≤ g := le_trans hxb hb_le_g exact h_ido i hxg have h_sum_cg : (Sy.card : ℝ) * c i g ≤ ∑ x ∈ Sy, c i x := by have : ∑ _x ∈ Sy, c i g ≤ ∑ x ∈ Sy, c i x := Finset.sum_le_sum h_cg_le_x simpa using this have h3_card : 3 * c i g ≤ (Sy.card : ℝ) * c i g := by have hcig : 0 ≤ c i g := hc_nonneg i g have h3_le : (3 : ℝ) ≤ (Sy.card : ℝ) := by exact_mod_cast (show 3 ≤ Sy.card by omega) nlinarith have h3_le_bundle : 3 * c i g ≤ additive_valuation (c i) (bundle_of P y) := by dsimp [additive_valuation] linarith
Under any partition P, the maximum bundle cost for agent i is at least 3 * c i g.
The valuation of agent y's bundle is bounded above by the supremum over all agents k of the valuation of agent k's bundle. Since agent y's bundle costs at least 3 * c i g, this supremum is also at least 3 * c i g.
uses
le_ciSup,Finite.bddAbove_rangehave hbundle_le_sup : additive_valuation (c i) (bundle_of P y) ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := le_ciSup (Finite.bddAbove_range (fun k => additive_valuation (c i) (bundle_of P k))) y linarith
The cost c i g of remaining chore g is at most 1/3.
Because 3 * c i g bounds the maximum bundle cost for every partition P, it is at most the infimum over all partitions. By definition, this infimum is agent i's chore maximin share, which is 1. Hence 3 * c i g ≤ 1, which implies c i g ≤ 1/3.
uses
le_ciInfhave h_mms_i := h_mms i dsimp [chore_maximin_share] at h_mms_i have : Nonempty (Fin m → Fin n) := ⟨fun _ => i⟩ have h3_le_inf : 3 * c i g ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) := le_ciInf hP rw [h_mms_i] at h3_le_inf linarith
Finset.mem_filter- An element a belongs to a filtered finset {x ∈ s | p x} if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
true_and- The conjunction True ∧ p simplifies to p.
Finset.card_univ- The cardinality of the universal finset on α equals the cardinality of the finite type α.
Fintype.card_fin- The type Fin n of natural numbers strictly less than n has cardinality n.
Fin.card_Iic- In Fin n, the prefix interval {x | x ≤ b} has cardinality b + 1.
Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to- Generalized pigeonhole principle: if f maps a finset s into a finset t and |t| * k < |s|, then some element y ∈ t has strictly more than k preimages in s.
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and the summands are non-negative outside s, then the sum over s is at most the sum over t.
Finset.mem_Iic.mp- An element of the closed prefix interval {x | x ≤ b} satisfies x ≤ b.
le_trans- The order relation ≤ is transitive: a ≤ b and b ≤ c imply a ≤ c.
Finset.sum_le_sum- If f x ≤ g x for all elements x in a finset s, then the sum of f over s is at most the sum of g over s.
le_ciSup- In a conditionally complete lattice, every element in the range of a bounded-above function is at most its supremum.
Finite.bddAbove_range- The range of a function from a finite type to a preorder is bounded above.
le_ciInf- In a conditionally complete lattice, if c is a lower bound for f(x) for all x in a nonempty type, then c ≤ ⨅ x, f x.
- In this formalization, 'identically ordered' (`is_identically_ordered`) is defined as every agent having an antitone cost function with respect to the chore indices: earlier chores have higher costs, and later chores have lower costs.
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.
/-- In an IDO instance with MMS 1, each remaining chore has cost at most 1/3. -/lemma ido_remaining_chores_cost_le_one_third (n m : ℕ) (h2n : 2 * n ≤ m) (c : Fin n → Fin m → ℝ) (hc_nonneg : ∀ i e, 0 ≤ c i e) (h_ido : is_identically_ordered c) (h_mms : ∀ i : Fin n, chore_maximin_share n (c i) = 1) (i : Fin n) (g : Fin m) (hg : g ∈ chore_remaining_set m n) : c i g ≤ 1 / 3 := by have h2n_lt : 2 * n < m := by simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg omega have hg_val : 2 * n ≤ g.val := by simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg exact hg let b : Fin m := ⟨2 * n, h2n_lt⟩ have hb_le_g : b ≤ g := hg_val have hP : ∀ P : Fin m → Fin n, 3 * c i g ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by intro P have hmaps : ∀ a ∈ Finset.Iic b, P a ∈ (Finset.univ : Finset (Fin n)) := by simp have hcard : (Finset.univ : Finset (Fin n)).card * 2 < (Finset.Iic b).card := by rw [Finset.card_univ, Fintype.card_fin, Fin.card_Iic b] dsimp [b] omega obtain ⟨y, -, hy⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to hmaps hcard let Sy := Finset.filter (fun x => P x = y) (Finset.Iic b) have hy' : 2 < Sy.card := hy have hSy_sub : Sy ⊆ bundle_of P y := by intro x hx rw [Finset.mem_filter] at hx simp only [Finset.mem_filter, bundle_of, Finset.mem_univ, true_and] exact hx.2 have hSy_le_bundle : ∑ x ∈ Sy, c i x ≤ ∑ x ∈ bundle_of P y, c i x := by apply Finset.sum_le_sum_of_subset_of_nonneg hSy_sub intro x _ _ exact hc_nonneg i x have h_cg_le_x : ∀ x ∈ Sy, c i g ≤ c i x := by intro x hx rw [Finset.mem_filter] at hx have hxb : x ≤ b := Finset.mem_Iic.mp hx.1 have hxg : x ≤ g := le_trans hxb hb_le_g exact h_ido i hxg have h_sum_cg : (Sy.card : ℝ) * c i g ≤ ∑ x ∈ Sy, c i x := by have : ∑ _x ∈ Sy, c i g ≤ ∑ x ∈ Sy, c i x := Finset.sum_le_sum h_cg_le_x simpa using this have h3_card : 3 * c i g ≤ (Sy.card : ℝ) * c i g := by have hcig : 0 ≤ c i g := hc_nonneg i g have h3_le : (3 : ℝ) ≤ (Sy.card : ℝ) := by exact_mod_cast (show 3 ≤ Sy.card by omega) nlinarith have h3_le_bundle : 3 * c i g ≤ additive_valuation (c i) (bundle_of P y) := by dsimp [additive_valuation] linarith have hbundle_le_sup : additive_valuation (c i) (bundle_of P y) ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := le_ciSup (Finite.bddAbove_range (fun k => additive_valuation (c i) (bundle_of P k))) y linarith have h_mms_i := h_mms i dsimp [chore_maximin_share] at h_mms_i have : Nonempty (Fin m → Fin n) := ⟨fun _ => i⟩ have h3_le_inf : 3 * c i g ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) := le_ciInf hP rw [h_mms_i] at h3_le_inf linarith