AFTD Auto-Formalizing Theoretical Domains

ef1_implies_two_sub_one_div_n_mms_chores

theoremverified

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.

  1. 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).

    lines 1–11

    uses le_ciInf, le_trans, le_ciSup, Finset.single_le_sum

    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 this
  2. 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).

    lines 13–22

    uses le_ciInf, le_trans, le_ciSup, Finset.sum_nonneg

    private 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)
  3. 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.

    lines 24–47

    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_lt

    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)
  4. 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).

    lines 49–53

    uses Finset.sum_fiberwise

    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 this
  5. 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).

    lines 55–70

    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_mms

    private 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
  6. 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.

    lines 71–86

    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_mul

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

    lines 87–95

    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
  8. 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)).

    lines 98–100

    uses ef1_implies_two_sub_one_div_n_mms_chores_main

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

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

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)
See it in the graphDiscuss this resultChallenge it