ef1_implies_two_sub_one_div_n_mms_chores
For any n ≥ 2 agents with nonnegative additive costs over m indivisible chores, any EF1 allocation satisfies (2 - 1/n)-MMS.
Statement
theorem ef1_implies_two_sub_one_div_n_mms_chores (n m : ℕ) [NeZero n] (hn : 2 ≤ n) (c : Fin n → Fin m → ℝ) (hc : ∀ i d, 0 ≤ c i d) (σ : Fin m → Fin n) (hef1 : is_ef1_chores c σ) : is_alpha_mms_chores (2 - 1 / (n : ℝ)) c σ- Source
- arXiv:2611.00432, Theorem 3.2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- is_alpha_mms_choresAn allocation σ of m chores among n agents is α-MMS for cost functions c if each agent i's total cost for her assigned bundle bundle_of σ…
- is_ef1_choresEF1 for chores with additive costs: whenever agent i envies agent j, removing some chore from i's own bundle removes the envy.
- 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…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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.
Read back from the Lean
For any natural numbers $n$ and $m$, with $n \ne 0$ and $2 \le n$, any cost function $c : \mathrm{Fin}\ n \to \mathrm{Fin}\ m \to \mathbb{R}$ such that $0 \le c(i, d)$ for all agents $i \in \mathrm{Fin}\ n$ and chores $d \in \mathrm{Fin}\ m$, and any chore allocation $\sigma : \mathrm{Fin}\ m \to \mathrm{Fin}\ n$: if $\sigma$ is an EF1 allocation for chores under $c$, then $\sigma$ is a $(2 - 1/n)$-MMS allocation for chores under $c$.
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 EF1 chore allocation among n ≥ 2 agents satisfies (2 - 1/n)-MMS, we bound each agent i's cost by comparing it to all other agents. The EF1 condition implies that agent i's cost exceeds any other agent j's cost by at most the cost of a single chore, which is always bounded above by the chore maximin share MMS. Summing this comparison over all n - 1 other agents and using the fact that the total chore cost is at most n * MMS yields n times agent i's cost is at most (2n - 1) * MMS. Dividing by n establishes that agent i's cost is at most (2 - 1/n) * MMS.
For any chore e, its cost u(e) is at most the chore maximin share MMS(u).
By definition, the chore maximin share is the infimum over all partitions P of the maximum bundle cost in P. In any partition P, chore e belongs to some bundle P(e). Since costs are nonnegative, the cost of e is at most the sum of costs in bundle P(e), which in turn is at most the maximum bundle cost in P. Taking the infimum over all partitions P gives u(e) ≤ MMS(u).
uses
le_ciInf,le_trans,le_ciSup,Finset.single_le_sumprivate lemma ef1_implies_two_sub_one_div_n_mms_chores_item_le_mms {m n : ℕ} (hn : 1 ≤ n) (u : Fin m → ℝ) (hu : ∀ d, 0 ≤ u d) (e : Fin m) : u e ≤ chore_maximin_share n u := by haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ simp only [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun k : Fin n => additive_valuation u (bundle_of P k)) := (Set.finite_range _).bddAbove refine le_trans ?_ (le_ciSup hbdd (P e)) have hmem : e ∈ bundle_of P (P e) := by simp [bundle_of] have := Finset.single_le_sum (f := u) (fun d _ => hu d) hmem simpa [additive_valuation] using this
The chore maximin share MMS(u) is nonnegative.
In any partition P, bundle 0 has cost equal to a sum of nonnegative costs, so its cost is nonnegative. The maximum bundle cost in P is at least the cost of bundle 0, hence also nonnegative. Taking the infimum over all partitions P proves 0 ≤ MMS(u).
uses
le_ciInf,le_trans,le_ciSup,Finset.sum_nonnegprivate lemma ef1_implies_two_sub_one_div_n_mms_chores_mms_nonneg {m n : ℕ} (hn : 1 ≤ n) (u : Fin m → ℝ) (hu : ∀ d, 0 ≤ u d) : 0 ≤ chore_maximin_share n u := by haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ simp only [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun k : Fin n => additive_valuation u (bundle_of P k)) := (Set.finite_range _).bddAbove refine le_trans ?_ (le_ciSup hbdd ⟨0, hn⟩) simp only [additive_valuation] exact Finset.sum_nonneg (fun d _ => hu d)
The total cost of all chores ∑ d, u(d) is at most n * MMS(u).
In any partition P, the sum of all n bundle costs equals the total chore cost ∑ d, u(d). Since each bundle cost is at most the maximum bundle cost max_k u(P_k), the sum of the n bundle costs is at most n * max_k u(P_k). Dividing by n > 0 shows the average chore cost is at most max_k u(P_k). Taking the infimum over all partitions P gives (∑ d, u(d)) / n ≤ MMS(u), and multiplying by n yields the claim.
uses
le_ciInf,Finset.sum_fiberwise,Finset.sum_le_sum,le_ciSup,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_comm,div_le_iff₀,mul_le_mul_of_nonneg_left,le_of_ltprivate lemma ef1_implies_two_sub_one_div_n_mms_chores_sum_le_mms {m n : ℕ} (hn : 1 ≤ n) (u : Fin m → ℝ) : (∑ d, u d) ≤ (n : ℝ) * chore_maximin_share n u := by haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ have hnpos : (0:ℝ) < n := by exact_mod_cast hn have hle : (∑ d, u d) / n ≤ chore_maximin_share n u := by simp only [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun k : Fin n => additive_valuation u (bundle_of P k)) := (Set.finite_range _).bddAbove have hsum : ∑ k, additive_valuation u (bundle_of P k) = ∑ d, u d := by have := Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) P u simpa [bundle_of, additive_valuation] using this have h2 : ∑ k : Fin n, additive_valuation u (bundle_of P k) ≤ (⨆ k, additive_valuation u (bundle_of P k)) * (n:ℝ) := by calc ∑ k : Fin n, additive_valuation u (bundle_of P k) ≤ ∑ _k : Fin n, (⨆ k, additive_valuation u (bundle_of P k)) := Finset.sum_le_sum (fun k _ => le_ciSup hbdd k) _ = (⨆ k, additive_valuation u (bundle_of P k)) * (n:ℝ) := by simp [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_comm] rw [div_le_iff₀ hnpos] linarith [hsum ▸ h2] calc (∑ d, u d) = (n:ℝ) * ((∑ d, u d) / n) := by field_simp _ ≤ (n:ℝ) * chore_maximin_share n u := mul_le_mul_of_nonneg_left hle (le_of_lt hnpos)
In any allocation σ, the sum of bundle costs equals the total cost of all chores: ∑ j, u(bundle_of σ j) = ∑ d, u(d).
Partitioning the chores according to which agent receives them and summing their costs yields the total cost of all chores, by fiberwise summation (Finset.sum_fiberwise).
uses
Finset.sum_fiberwiseprivate lemma ef1_implies_two_sub_one_div_n_mms_chores_fiber_sum {m n : ℕ} (u : Fin m → ℝ) (σ : Fin m → Fin n) : ∑ j : Fin n, additive_valuation u (bundle_of σ j) = ∑ d : Fin m, u d := by have := Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) σ u simpa [bundle_of, additive_valuation] using this
For every other agent j ≠ i, agent i's bundle cost is at most agent j's bundle cost plus MMS(u).
By the EF1 condition, either agent i's bundle cost is already at most agent j's, or there is a chore e in agent i's bundle such that removing e leaves agent i's cost at most agent j's. Since the cost of any single chore satisfies u(e) ≤ MMS(u), in either case agent i's bundle cost is at most agent j's bundle cost plus MMS(u).
uses
ef1_implies_two_sub_one_div_n_mms_chores_mms_nonneg,ef1_implies_two_sub_one_div_n_mms_chores_sum_le_mms,ef1_implies_two_sub_one_div_n_mms_chores_fiber_sum,ef1_implies_two_sub_one_div_n_mms_chores_item_le_mmsprivate lemma ef1_implies_two_sub_one_div_n_mms_chores_main {m n : ℕ} (hn1 : 1 ≤ n) (u : Fin m → ℝ) (hu : ∀ d, 0 ≤ u d) (σ : Fin m → Fin n) (i : Fin n) (hef1 : ∀ j, additive_valuation u (bundle_of σ i) ≤ additive_valuation u (bundle_of σ j) ∨ ∃ e ∈ bundle_of σ i, additive_valuation u (bundle_of σ i) - u e ≤ additive_valuation u (bundle_of σ j)) : additive_valuation u (bundle_of σ i) ≤ (2 - 1/(n:ℝ)) * chore_maximin_share n u := by have hnn : 0 ≤ chore_maximin_share n u := ef1_implies_two_sub_one_div_n_mms_chores_mms_nonneg hn1 u hu have hTM : (∑ d : Fin m, u d) ≤ (n:ℝ) * chore_maximin_share n u := ef1_implies_two_sub_one_div_n_mms_chores_sum_le_mms hn1 u have hfib := ef1_implies_two_sub_one_div_n_mms_chores_fiber_sum (n := n) u σ have hperj : ∀ j ∈ (Finset.univ.erase i : Finset (Fin n)), additive_valuation u (bundle_of σ i) ≤ additive_valuation u (bundle_of σ j) + chore_maximin_share n u := by intro j _ rcases hef1 j with h | ⟨e, _, hle⟩ · linarith · have h1 : u e ≤ chore_maximin_share n u := ef1_implies_two_sub_one_div_n_mms_chores_item_le_mms hn1 u hu e linarith
Summing over all n - 1 other agents j ≠ i gives (n - 1) * u(bundle_of σ i) ≤ (∑ d, u(d) - u(bundle_of σ i)) + (n - 1) * MMS(u).
Summing the EF1 inequality u(bundle_of σ i) ≤ u(bundle_of σ j) + MMS(u) over all j ∈ {0, ..., n-1} \ {i} produces n - 1 copies of agent i's cost on the left. On the right, the sum of bundle costs for all j ≠ i equals the total cost of all chores minus agent i's bundle cost, while the constant MMS(u) is summed over the n - 1 other agents.
uses
Finset.sum_erase_add,Finset.mem_univ,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_fin,Nat.cast_sub,Finset.sum_le_sum,Finset.sum_add_distrib,Finset.sum_const,nsmul_eq_mulhave hsumerase : ∑ j ∈ Finset.univ.erase i, additive_valuation u (bundle_of σ j) = (∑ d : Fin m, u d) - additive_valuation u (bundle_of σ i) := by have h := Finset.sum_erase_add (Finset.univ : Finset (Fin n)) (fun j => additive_valuation u (bundle_of σ j)) (Finset.mem_univ i) rw [hfib] at h linarith have hcard : ((Finset.univ.erase i : Finset (Fin n)).card : ℝ) = (n:ℝ) - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] push_cast [Nat.cast_sub hn1] ring have hstep : ((n:ℝ) - 1) * additive_valuation u (bundle_of σ i) ≤ ((∑ d : Fin m, u d) - additive_valuation u (bundle_of σ i)) + ((n:ℝ) - 1) * chore_maximin_share n u := by have h := Finset.sum_le_sum (s := (Finset.univ.erase i : Finset (Fin n))) hperj simp only [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul, hcard, hsumerase] at h exact h
Agent i's bundle cost satisfies u(bundle_of σ i) ≤ (2 - 1/n) * MMS(u).
Moving u(bundle_of σ i) to the left side gives n * u(bundle_of σ i) ≤ ∑ d, u(d) + (n - 1) * MMS(u). Using ∑ d, u(d) ≤ n * MMS(u), this simplifies to n * u(bundle_of σ i) ≤ (2n - 1) * MMS(u). Dividing by n > 0 yields u(bundle_of σ i) ≤ ((2n - 1) / n) * MMS(u) = (2 - 1/n) * MMS(u).
uses
le_div_iff₀have hmain : (n:ℝ) * additive_valuation u (bundle_of σ i) ≤ (2*(n:ℝ) - 1) * chore_maximin_share n u := by linarith have hn0 : (0:ℝ) < n := by exact_mod_cast hn1 have hrw : (2 - 1/(n:ℝ)) * chore_maximin_share n u = ((2*(n:ℝ) - 1) * chore_maximin_share n u) / (n:ℝ) := by field_simp rw [hrw] rw [le_div_iff₀ hn0] linarith
Any EF1 allocation of chores among n ≥ 2 agents satisfies (2 - 1/n)-MMS.
For each agent i, since n ≥ 2 implies n ≥ 1, applying the main lemma with cost function c(i) shows that agent i's bundle cost is at most (2 - 1/n) * MMS(c(i)).
uses
ef1_implies_two_sub_one_div_n_mms_chores_maintheorem ef1_implies_two_sub_one_div_n_mms_chores (n m : ℕ) [NeZero n] (hn : 2 ≤ n) (c : Fin n → Fin m → ℝ) (hc : ∀ i d, 0 ≤ c i d) (σ : Fin m → Fin n) (hef1 : is_ef1_chores c σ) : is_alpha_mms_chores (2 - 1 / (n : ℝ)) c σ := by intro i exact ef1_implies_two_sub_one_div_n_mms_chores_main (by omega) (c i) (hc i) σ i (hef1 i)
le_ciInf- A value c is at most the infimum of a family of values if it is at most each value in the family.
le_ciSup- Any element in a family is at most the supremum of that family (provided the family is bounded above).
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
Finset.single_le_sum- For a nonnegative function on a finite set, the value at any single element is at most the sum over the entire set.
Finset.sum_nonneg- The sum of nonnegative terms is nonnegative.
Finset.sum_fiberwise- Summing a function fiberwise over the preimages of a map partitions the finite set and preserves the total sum.
Finset.sum_le_sum- If f(x) ≤ g(x) for all x in a finite set, then the sum of f over the set is at most the sum of g.
Finset.sum_const- Summing a constant over a finite set equals the cardinality of the set times that constant.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
nsmul_eq_mul- Scalar multiplication by a natural number n equals multiplication by the natural number cast into the ring.
mul_comm- Multiplication is commutative.
div_le_iff₀- For a positive divisor c, b / c ≤ a is equivalent to b ≤ a * c.
mul_le_mul_of_nonneg_left- Multiplying an inequality on the left by a nonnegative element preserves the inequality.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
Finset.sum_erase_add- Splitting off an element a from a sum over a finite set s gives the sum over s \ {a} plus the value at a.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.card_erase_of_mem- Erasing an element from a finite set decreases its cardinality by 1.
Fintype.card_fin- The standard finite type Fin n has cardinality n.
Nat.cast_sub- Subtraction of natural numbers casts to real subtraction when the subtrahend is at most the minuend.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set distributes into the sum of each function.
le_div_iff₀- For a positive divisor c, a ≤ b / c is equivalent to a * c ≤ b.
ef1_implies_two_sub_one_div_n_mms_chores_item_le_mms- For nonnegative additive costs, the cost of any single chore is at most the chore maximin share.
ef1_implies_two_sub_one_div_n_mms_chores_mms_nonneg- For nonnegative additive costs, the chore maximin share is nonnegative.
ef1_implies_two_sub_one_div_n_mms_chores_sum_le_mms- The total cost of all chores is at most n times the chore maximin share.
ef1_implies_two_sub_one_div_n_mms_chores_fiber_sum- In any partition of chores among n agents, the sum of all bundle costs equals the total cost of all chores.
ef1_implies_two_sub_one_div_n_mms_chores_main- If an agent with nonnegative costs perceives an allocation as EF1 towards all other agents, their bundle cost is at most (2 - 1/n) times their chore maximin share.
- In chore allocation, an agent seeks to minimize their chore cost, so the maximin share MMS is defined as the infimum over partitions of the maximum bundle cost; hence achieving an MMS approximation means an agent's cost is at most a multiple of MMS.
- Minor arithmetic obligations such as establishing 1 ≤ n from 2 ≤ n and clearing denominators are discharged by the automated tactics omega, field_simp, and linarith.
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.
private lemma ef1_implies_two_sub_one_div_n_mms_chores_item_le_mms {m n : ℕ} (hn : 1 ≤ n) (u : Fin m → ℝ) (hu : ∀ d, 0 ≤ u d) (e : Fin m) : u e ≤ chore_maximin_share n u := by haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ simp only [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun k : Fin n => additive_valuation u (bundle_of P k)) := (Set.finite_range _).bddAbove refine le_trans ?_ (le_ciSup hbdd (P e)) have hmem : e ∈ bundle_of P (P e) := by simp [bundle_of] have := Finset.single_le_sum (f := u) (fun d _ => hu d) hmem simpa [additive_valuation] using thisprivate lemma ef1_implies_two_sub_one_div_n_mms_chores_mms_nonneg {m n : ℕ} (hn : 1 ≤ n) (u : Fin m → ℝ) (hu : ∀ d, 0 ≤ u d) : 0 ≤ chore_maximin_share n u := by haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ simp only [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun k : Fin n => additive_valuation u (bundle_of P k)) := (Set.finite_range _).bddAbove refine le_trans ?_ (le_ciSup hbdd ⟨0, hn⟩) simp only [additive_valuation] exact Finset.sum_nonneg (fun d _ => hu d)private lemma ef1_implies_two_sub_one_div_n_mms_chores_sum_le_mms {m n : ℕ} (hn : 1 ≤ n) (u : Fin m → ℝ) : (∑ d, u d) ≤ (n : ℝ) * chore_maximin_share n u := by haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ have hnpos : (0:ℝ) < n := by exact_mod_cast hn have hle : (∑ d, u d) / n ≤ chore_maximin_share n u := by simp only [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun k : Fin n => additive_valuation u (bundle_of P k)) := (Set.finite_range _).bddAbove have hsum : ∑ k, additive_valuation u (bundle_of P k) = ∑ d, u d := by have := Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) P u simpa [bundle_of, additive_valuation] using this have h2 : ∑ k : Fin n, additive_valuation u (bundle_of P k) ≤ (⨆ k, additive_valuation u (bundle_of P k)) * (n:ℝ) := by calc ∑ k : Fin n, additive_valuation u (bundle_of P k) ≤ ∑ _k : Fin n, (⨆ k, additive_valuation u (bundle_of P k)) := Finset.sum_le_sum (fun k _ => le_ciSup hbdd k) _ = (⨆ k, additive_valuation u (bundle_of P k)) * (n:ℝ) := by simp [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_comm] rw [div_le_iff₀ hnpos] linarith [hsum ▸ h2] calc (∑ d, u d) = (n:ℝ) * ((∑ d, u d) / n) := by field_simp _ ≤ (n:ℝ) * chore_maximin_share n u := mul_le_mul_of_nonneg_left hle (le_of_lt hnpos)private lemma ef1_implies_two_sub_one_div_n_mms_chores_fiber_sum {m n : ℕ} (u : Fin m → ℝ) (σ : Fin m → Fin n) : ∑ j : Fin n, additive_valuation u (bundle_of σ j) = ∑ d : Fin m, u d := by have := Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) σ u simpa [bundle_of, additive_valuation] using thisprivate lemma ef1_implies_two_sub_one_div_n_mms_chores_main {m n : ℕ} (hn1 : 1 ≤ n) (u : Fin m → ℝ) (hu : ∀ d, 0 ≤ u d) (σ : Fin m → Fin n) (i : Fin n) (hef1 : ∀ j, additive_valuation u (bundle_of σ i) ≤ additive_valuation u (bundle_of σ j) ∨ ∃ e ∈ bundle_of σ i, additive_valuation u (bundle_of σ i) - u e ≤ additive_valuation u (bundle_of σ j)) : additive_valuation u (bundle_of σ i) ≤ (2 - 1/(n:ℝ)) * chore_maximin_share n u := by have hnn : 0 ≤ chore_maximin_share n u := ef1_implies_two_sub_one_div_n_mms_chores_mms_nonneg hn1 u hu have hTM : (∑ d : Fin m, u d) ≤ (n:ℝ) * chore_maximin_share n u := ef1_implies_two_sub_one_div_n_mms_chores_sum_le_mms hn1 u have hfib := ef1_implies_two_sub_one_div_n_mms_chores_fiber_sum (n := n) u σ have hperj : ∀ j ∈ (Finset.univ.erase i : Finset (Fin n)), additive_valuation u (bundle_of σ i) ≤ additive_valuation u (bundle_of σ j) + chore_maximin_share n u := by intro j _ rcases hef1 j with h | ⟨e, _, hle⟩ · linarith · have h1 : u e ≤ chore_maximin_share n u := ef1_implies_two_sub_one_div_n_mms_chores_item_le_mms hn1 u hu e linarith have hsumerase : ∑ j ∈ Finset.univ.erase i, additive_valuation u (bundle_of σ j) = (∑ d : Fin m, u d) - additive_valuation u (bundle_of σ i) := by have h := Finset.sum_erase_add (Finset.univ : Finset (Fin n)) (fun j => additive_valuation u (bundle_of σ j)) (Finset.mem_univ i) rw [hfib] at h linarith have hcard : ((Finset.univ.erase i : Finset (Fin n)).card : ℝ) = (n:ℝ) - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] push_cast [Nat.cast_sub hn1] ring have hstep : ((n:ℝ) - 1) * additive_valuation u (bundle_of σ i) ≤ ((∑ d : Fin m, u d) - additive_valuation u (bundle_of σ i)) + ((n:ℝ) - 1) * chore_maximin_share n u := by have h := Finset.sum_le_sum (s := (Finset.univ.erase i : Finset (Fin n))) hperj simp only [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul, hcard, hsumerase] at h exact h have hmain : (n:ℝ) * additive_valuation u (bundle_of σ i) ≤ (2*(n:ℝ) - 1) * chore_maximin_share n u := by linarith have hn0 : (0:ℝ) < n := by exact_mod_cast hn1 have hrw : (2 - 1/(n:ℝ)) * chore_maximin_share n u = ((2*(n:ℝ) - 1) * chore_maximin_share n u) / (n:ℝ) := by field_simp rw [hrw] rw [le_div_iff₀ hn0] linarith/-- EF1 implies (2 - 1/n)-MMS for nonnegative additive chores. -/theorem ef1_implies_two_sub_one_div_n_mms_chores (n m : ℕ) [NeZero n] (hn : 2 ≤ n) (c : Fin n → Fin m → ℝ) (hc : ∀ i d, 0 ≤ c i d) (σ : Fin m → Fin n) (hef1 : is_ef1_chores c σ) : is_alpha_mms_chores (2 - 1 / (n : ℝ)) c σ := by intro i exact ef1_implies_two_sub_one_div_n_mms_chores_main (by omega) (c i) (hc i) σ i (hef1 i)