AFTD Auto-Formalizing Theoretical Domains

ido_opposite_pair_cost_le_four_thirds

theoremverified

In 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, for every agent i : Fin n and index j : Fin n, the additive valuation of chore_opposite_pair h2n j under c i is at most 4/3.

Statement

lemma ido_opposite_pair_cost_le_four_thirds
    (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) (j : Fin n) :
    additive_valuation (c i) (chore_opposite_pair h2n j) ≤ 4 / 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_opposite_pairGiven implicit natural numbers m and n, a hypothesis h2n : 2 * n ≤ m, and an element j : Fin n, chore_opposite_pair is defined as the…
  • 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.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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 LinearOrder is a TotalPreorder.
Used by 1

Read back from the Lean

Given natural numbers $n$ and $m$ such that $2n \le m$, and a cost function $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ representing the costs of $m$ chores to $n$ agents, suppose: 1. Every cost is non-negative: $0 \le c(i, e)$ for all agents $i$ and chores $e$. 2. Chores are identically ordered: for every agent $i$, the cost function $c(i, \cdot)$ is antitone (non-increasing with respect to chore indices). 3. For every agent $i$, the chore maximin share (the minimum over all partitions of $m$ chores among $n$ agents of the maximum bundle cost) under $c(i)$ equals $1$. Then for any agent $i \in \text{Fin } n$ and any index $j \in \text{Fin } n$, the additive cost to agent $i$ of the "opposite pair" of chores $\{j, 2n - 1 - j\}$ is at most $4/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

The theorem states that in an identically ordered chore allocation instance where each agent's maximin share (MMS) is 1, the additive cost of any opposite pair {e₁, e₂} (with e₁ = j and e₂ = 2n - 1 - j) to agent i is at most 4/3. First, e₁ alone costs at most 1 because it is contained in some bundle in every partition. Next, for any partition P, counting the chores allocated from the initial segments up to e₂ (size 2n - j) and up to e₁ (size j + 1) shows via pigeonholing that some bundle either contains at least three chores ≤ e₂ (costing at least 3 c(i, e₂)) or contains a chore ≤ e₁ and another distinct chore ≤ e₂ (costing at least c(i, e₁) + c(i, e₂)). Thus the maximin share 1 upper bounds min(3 c(i, e₂), c(i, e₁) + c(i, e₂)), from which c(i, e₁) + c(i, e₂) ≤ 4/3 follows immediately.

  1. The chore indices e₁ = j and e₂ = 2n - 1 - j of the opposite pair satisfy e₁ ≤ e₂.

    The elements e₁ and e₂ are defined in Fin m with values j and 2n - 1 - j, which are valid indices because 2n ≤ m and j < n. Since j < n, integer linear arithmetic gives j ≤ 2n - 1 - j, so e₁ ≤ e₂.

    lines 9–15

      have hj : (j : ℕ) < n := j.isLt
      let e1 : Fin m := ⟨j.val, by omega⟩
      let e2 : Fin m := ⟨2 * n - 1 - j.val, by omega⟩
      have he12 : e1 ≤ e2 := by
        change e1.val ≤ e2.val
        dsimp [e1, e2]
        omega
  2. The additive valuation of the chore opposite pair {e₁, e₂} under agent i's valuation equals c(i, e₁) + c(i, e₂).

    The indices j and 2n - 1 - j cannot be equal because 2j = 2n - 1 has no integer solution (even versus odd). Since e₁ ≠ e₂, Finset.sum_pair evaluates the additive valuation over {e₁, e₂} as the sum of their individual costs c(i, e₁) + c(i, e₂).

    lines 16–23

    uses Fin.ext_iff.mp, Finset.sum_pair

      have h_pair_val : additive_valuation (c i) (chore_opposite_pair h2n j) = c i e1 + c i e2 := by
        unfold additive_valuation chore_opposite_pair
        dsimp only
        have hne : (⟨j.val, by omega⟩ : Fin m) ≠ ⟨2 * n - 1 - j.val, by omega⟩ := by
          intro h
          have h' : j.val = 2 * n - 1 - j.val := Fin.ext_iff.mp h
          omega
        rw [Finset.sum_pair hne]
  3. The individual cost c(i, e₁) is at most 1.

    In any partition P of chores among the n agents, chore e₁ is allocated to bundle P(e₁). By nonnegativity of costs, the valuation of bundle P(e₁) is at least c(i, e₁), so the maximum bundle valuation under P is at least c(i, e₁). Because this lower bound holds for all partitions P, the infimum over all partitions (which is agent i's maximin share, equal to 1) is at least c(i, e₁), yielding c(i, e₁) ≤ 1.

    lines 24–48

    uses Finset.mem_filter.mpr, Finset.mem_univ, Finset.sum_le_sum_of_subset_of_nonneg, Finset.mem_singleton, le_ciSup, Finite.bddAbove_range, le_ciInf

      have h_e1_le_one : c i e1 ≤ 1 := by
        have hP : ∀ P : Fin m → Fin n, c i e1 ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by
          intro P
          have he_in : e1 ∈ bundle_of P (P e1) := Finset.mem_filter.mpr ⟨Finset.mem_univ e1, rfl⟩
          have he_le : c i e1 ≤ additive_valuation (c i) (bundle_of P (P e1)) := by
            dsimp [additive_valuation]
            have : c i e1 = ∑ x ∈ {e1}, c i x := by simp
            rw [this]
            apply Finset.sum_le_sum_of_subset_of_nonneg
            · intro x hx
              simp only [Finset.mem_singleton] at hx
              rw [hx]
              exact he_in
            · intro x _ _
              exact hc_nonneg i x
          have h_le_sup : additive_valuation (c i) (bundle_of P (P e1)) ≤ ⨆ k', additive_valuation (c i) (bundle_of P k') :=
            le_ciSup (Finite.bddAbove_range (fun k' => additive_valuation (c i) (bundle_of P k'))) (P e1)
          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 h_le_inf : c i e1 ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) :=
          le_ciInf hP
        rw [h_mms_i] at h_le_inf
        exact h_le_inf
  4. The initial segments {x | x ≤ e₂} and {x | x ≤ e₁} have cardinalities 2n - j and j + 1, respectively, and {x | x ≤ e₁} ⊆ {x | x ≤ e₂}.

    By Fin.card_Iic, the number of chores up to index b is b + 1, so the segment up to e₂ = 2n - 1 - j has size (2n - 1 - j) + 1 = 2n - j, while that up to e₁ = j has size j + 1. Since e₁ ≤ e₂, the smaller segment is a subset of the larger one by Finset.Iic_subset_Iic.mpr.

    lines 49–55

    uses Fin.card_Iic, Finset.Iic_subset_Iic.mpr

      have hT_card : (Finset.Iic e2).card = 2 * n - j.val := by
        rw [Fin.card_Iic e2]
        dsimp [e2]
        omega
      have hT0_card : (Finset.Iic e1).card = j.val + 1 := by
        rw [Fin.card_Iic e1]
      have hT0_sub_T : Finset.Iic e1 ⊆ Finset.Iic e2 := Finset.Iic_subset_Iic.mpr he12
  5. For an arbitrary partition P, the bundles partition the initial segments up to e₂ and e₁ into fibers S(k) and S₀(k) with S₀(k) ⊆ S(k), having total sizes 2n - j and j + 1.

    For each agent k, S(k) and S₀(k) are defined as the chores allocated to bundle k within the segments {x ≤ e₂} and {x ≤ e₁}, respectively. Since {x ≤ e₁} ⊆ {x ≤ e₂}, each fiber satisfies S₀(k) ⊆ S(k). Summing the fiber cardinalities over all n agents by Finset.card_eq_sum_card_fiberwise recovers the total sizes of the segments: ∑ |S(k)| = 2n - j and ∑ |S₀(k)| = j + 1.

    lines 56–69

    uses Finset.mem_filter, Finset.card_eq_sum_card_fiberwise, Finset.mem_univ

      have hP_bound : ∀ P : Fin m → Fin n, min (3 * c i e2) (c i e1 + c i e2) ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by
        intro P
        let S (k : Fin n) : Finset (Fin m) := (Finset.Iic e2).filter (fun x => P x = k)
        let S0 (k : Fin n) : Finset (Fin m) := (Finset.Iic e1).filter (fun x => P x = k)
        have hS_sub : ∀ k, S0 k ⊆ S k := by
          intro k x hx
          rw [Finset.mem_filter] at hx ⊢
          exact ⟨hT0_sub_T hx.1, hx.2⟩
        have hS_sum : ∑ k : Fin n, (S k).card = 2 * n - j.val := by
          rw [← hT_card]
          exact (Finset.card_eq_sum_card_fiberwise (fun x _ => Finset.mem_univ (P x))).symm
        have hS0_sum : ∑ k : Fin n, (S0 k).card = j.val + 1 := by
          rw [← hT0_card]
          exact (Finset.card_eq_sum_card_fiberwise (fun x _ => Finset.mem_univ (P x))).symm
  6. If some bundle receives at least three chores from {x ≤ e₂}, the maximum bundle cost in partition P is at least 3 c(i, e₂), which is at least min(3 c(i, e₂), c(i, e₁) + c(i, e₂)).

    Suppose there is an agent k with |S(k)| ≥ 3. Because the cost function c(i) is antitone (identical ordering), every chore x ≤ e₂ has cost at least c(i, e₂). The bundle of agent k contains S(k), so by nonnegativity its cost is at least |S(k)| * c(i, e₂) ≥ 3 c(i, e₂). The maximum bundle cost in partition P is bounded below by this bundle's cost, and min(3 c(i, e₂), c(i, e₁) + c(i, e₂)) ≤ 3 c(i, e₂) by min_le_left.

    lines 70–100

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.sum_le_sum_of_subset_of_nonneg, Finset.mem_Iic.mp, Finset.sum_le_sum, le_ciSup, Finite.bddAbove_range, min_le_left

        by_cases h_ge3 : ∃ k : Fin n, 3 ≤ (S k).card
        · obtain ⟨k, hk⟩ := h_ge3
          have hSy_sub : S k ⊆ bundle_of P k := 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 ∈ S k, c i x ≤ ∑ x ∈ bundle_of P k, 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 ∈ S k, c i e2 ≤ c i x := by
            intro x hx
            rw [Finset.mem_filter] at hx
            have hxb : x ≤ e2 := Finset.mem_Iic.mp hx.1
            exact h_ido i hxb
          have h_sum_cg : ((S k).card : ℝ) * c i e2 ≤ ∑ x ∈ S k, c i x := by
            have : ∑ _x ∈ S k, c i e2 ≤ ∑ x ∈ S k, c i x := Finset.sum_le_sum h_cg_le_x
            simpa using this
          have h3_card : 3 * c i e2 ≤ ((S k).card : ℝ) * c i e2 := by
            have hcie2 : 0 ≤ c i e2 := hc_nonneg i e2
            have h3_le : (3 : ℝ) ≤ ((S k).card : ℝ) := by
              exact_mod_cast hk
            nlinarith
          have h3_bundle : 3 * c i e2 ≤ additive_valuation (c i) (bundle_of P k) := by
            dsimp [additive_valuation]
            linarith
          have h_le_sup : additive_valuation (c i) (bundle_of P k) ≤ ⨆ k', additive_valuation (c i) (bundle_of P k') :=
            le_ciSup (Finite.bddAbove_range (fun k' => additive_valuation (c i) (bundle_of P k'))) k
          have : min (3 * c i e2) (c i e1 + c i e2) ≤ 3 * c i e2 := min_le_left _ _
          linarith
  7. If every bundle receives at most two chores from {x ≤ e₂}, some bundle contains a chore ≤ e₁ and another distinct chore ≤ e₂, giving bundle cost at least c(i, e₁) + c(i, e₂); thus every partition P satisfies min(3 c(i, e₂), c(i, e₁) + c(i, e₂)) ≤ ⨆ k, val(c i, bundle_of P k).

    If |S(k)| ≤ 2 for all k, we show by contradiction that some agent k₀ must have |S₀(k₀)| ≥ 1 and |S(k₀)| ≥ 2. Otherwise, every agent would have |S(k)| + |S₀(k)| ≤ 2, which would force the total sum over all n agents to be at most 2n; but the sum of the two totals is (2n - j) + (j + 1) = 2n + 1, a contradiction. For such an agent k₀, taking an element a ∈ S₀(k₀) (so a ≤ e₁) and a distinct element b ∈ S(k₀) \\ {a} (so b ≤ e₂), antitonicity implies c(i, a) ≥ c(i, e₁) and c(i, b) ≥ c(i, e₂). Since bundle k₀ contains both a and b, its valuation is at least c(i, e₁) + c(i, e₂), completing the partition bound.

    lines 101–162

    uses Finset.card_le_card, Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, Finset.card_pos.mp, Finset.card_erase_of_mem, Finset.mem_of_mem_erase, Finset.ne_of_mem_erase, Finset.mem_filter.mp, Finset.mem_Iic.mp, Finset.mem_insert, Finset.mem_singleton, Finset.mem_filter, Finset.mem_univ, true_and, Finset.sum_pair, Finset.sum_le_sum_of_subset_of_nonneg, le_ciSup, Finite.bddAbove_range, min_le_right

        · have h_le2 : ∀ k : Fin n, (S k).card ≤ 2 := by
            intro k
            by_contra h_gt
            apply h_ge3
            exact ⟨k, by omega⟩
          have hex : ∃ k : Fin n, 1 ≤ (S0 k).card ∧ 2 ≤ (S k).card := by
            by_contra h_none
            have h_sum_le : ∀ k : Fin n, (S k).card + (S0 k).card ≤ 2 := by
              intro k
              have := h_le2 k
              have := Finset.card_le_card (hS_sub k)
              have hk_not : ¬(1 ≤ (S0 k).card ∧ 2 ≤ (S k).card) := fun h => h_none ⟨k, h⟩
              omega
            have h_total : ∑ k : Fin n, ((S k).card + (S0 k).card) ≤ ∑ k : Fin n, 2 := by
              apply Finset.sum_le_sum
              intro k _
              exact h_sum_le k
            rw [Finset.sum_add_distrib, hS_sum, hS0_sum] at h_total
            simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h_total
            omega
          obtain ⟨k0, hk0_1, hk0_2⟩ := hex
          obtain ⟨a, ha⟩ := Finset.card_pos.mp (by omega : 0 < (S0 k0).card)
          have ha_in_S : a ∈ S k0 := hS_sub k0 ha
          have hS_erase_card : 1 ≤ ((S k0).erase a).card := by
            rw [Finset.card_erase_of_mem ha_in_S]
            omega
          obtain ⟨b, hb_mem⟩ := Finset.card_pos.mp (by omega : 0 < ((S k0).erase a).card)
          have hb_in_S : b ∈ S k0 := Finset.mem_of_mem_erase hb_mem
          have hba : b ≠ a := Finset.ne_of_mem_erase hb_mem
          have hab : a ≠ b := hba.symm
          have ha_le_e1 : a ≤ e1 := by
            have := (Finset.mem_filter.mp ha).1
            exact Finset.mem_Iic.mp this
          have hb_le_e2 : b ≤ e2 := by
            have := (Finset.mem_filter.mp hb_in_S).1
            exact Finset.mem_Iic.mp this
          have h_pair_sub : {a, b} ⊆ bundle_of P k0 := by
            intro x hx
            simp only [Finset.mem_insert, Finset.mem_singleton] at hx
            rcases hx with rfl | rfl
            · have := (Finset.mem_filter.mp ha_in_S).2
              simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and]
              exact this
            · have := (Finset.mem_filter.mp hb_in_S).2
              simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and]
              exact this
          have h_sum_le : c i a + c i b ≤ additive_valuation (c i) (bundle_of P k0) := by
            dsimp [additive_valuation]
            have h_pair_sum : c i a + c i b = ∑ x ∈ {a, b}, c i x := by
              rw [Finset.sum_pair hab]
            rw [h_pair_sum]
            apply Finset.sum_le_sum_of_subset_of_nonneg h_pair_sub
            intro x _ _
            exact hc_nonneg i x
          have h_cia : c i e1 ≤ c i a := h_ido i ha_le_e1
          have h_cib : c i e2 ≤ c i b := h_ido i hb_le_e2
          have h_bundle_le : c i e1 + c i e2 ≤ additive_valuation (c i) (bundle_of P k0) := by
            linarith
          have h_le_sup : additive_valuation (c i) (bundle_of P k0) ≤ ⨆ k', additive_valuation (c i) (bundle_of P k') :=
            le_ciSup (Finite.bddAbove_range (fun k' => additive_valuation (c i) (bundle_of P k'))) k0
          have : min (3 * c i e2) (c i e1 + c i e2) ≤ c i e1 + c i e2 := min_le_right _ _
          linarith
  8. The sum c(i, e₁) + c(i, e₂) is at most 4/3.

    Because min(3 c(i, e₂), c(i, e₁) + c(i, e₂)) lower bounds the maximum bundle cost for every partition P, taking the infimum over all partitions bounds it by agent i's maximin share, which is 1. Thus 3 c(i, e₂) ≤ 1 or c(i, e₁) + c(i, e₂) ≤ 1. In the first case, c(i, e₂) ≤ 1/3, and using c(i, e₁) ≤ 1 from Step 3 yields c(i, e₁) + c(i, e₂) ≤ 1 + 1/3 = 4/3. In the second case, c(i, e₁) + c(i, e₂) ≤ 1 ≤ 4/3 directly.

    lines 163–175

    uses le_ciInf, min_le_iff.mp

      have h_mms_i := h_mms i
      dsimp [chore_maximin_share] at h_mms_i
      have : Nonempty (Fin m → Fin n) := ⟨fun _ => i⟩
      have h_le_inf : min (3 * c i e2) (c i e1 + c i e2) ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) :=
        le_ciInf hP_bound
      rw [h_mms_i] at h_le_inf
      have h_cases : 3 * c i e2 ≤ 1 ∨ c i e1 + c i e2 ≤ 1 := by
        exact min_le_iff.mp h_le_inf
      have h_sum_le_four_thirds : c i e1 + c i e2 ≤ 4 / 3 := by
        rcases h_cases with h1 | h2
        · have : c i e2 ≤ 1 / 3 := by linarith
          linarith
        · linarith
  9. The additive valuation of chore_opposite_pair h2n j under c(i) is at most 4/3.

    Rewriting the additive valuation of the opposite pair as c(i, e₁) + c(i, e₂) and applying the inequality c(i, e₁) + c(i, e₂) ≤ 4/3 finishes the proof.

    lines 176–177

      rw [h_pair_val]
      exact h_sum_le_four_thirds
Fin.ext_iff.mp
If two elements of Fin n are equal, their underlying natural numbers are equal.
Finset.sum_pair
For two distinct elements a and b, the sum of a function over the pair {a, b} equals f(a) + f(b).
Finset.mem_filter.mpr
If an element is in a finset and satisfies a predicate, it belongs to the filtered subset.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.sum_le_sum_of_subset_of_nonneg
If s ⊆ t and the summands on t \\ s are nonnegative, then the sum over s is at most the sum over t.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
le_ciSup
For a function whose range is bounded above in a conditionally complete lattice, any value f(c) is at most the supremum ⨆ x, f(x).
Finite.bddAbove_range
The range of a function from a finite domain into 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 domain, then c ≤ ⨅ x, f(x).
Fin.card_Iic
In Fin n, the cardinality of the initial segment {x | x ≤ b} is b + 1.
Finset.Iic_subset_Iic.mpr
In a preorder, if a ≤ b, then the initial segment {x | x ≤ a} is a subset of {x | x ≤ b}.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filtering predicate.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finset s equals the sum of the cardinalities of the fibers of a function f over all elements of the target finset.
true_and
The proposition True ∧ p is equivalent to p.
Finset.mem_Iic.mp
If an element belongs to the initial segment {x | x ≤ b}, then x ≤ b.
Finset.sum_le_sum
If f(x) ≤ g(x) for all x in a finset s, then the sum of f over s is at most the sum of g over s.
min_le_left
For any elements a and b in a linear order, min(a, b) ≤ a.
Finset.card_le_card
If s ⊆ t for finsets s and t, then the cardinality of s is at most that of t.
Finset.sum_add_distrib
The sum of f(x) + g(x) over a finset equals the sum of f(x) plus the sum of g(x).
Finset.sum_const
The sum of a constant b over a finset s equals |s| • b.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
smul_eq_mul
Scalar multiplication of natural numbers is standard multiplication.
Finset.card_pos.mp
If a finset has strictly positive cardinality, it is nonempty.
Finset.card_erase_of_mem
Removing an element belonging to a finset decreases its cardinality by 1.
Finset.mem_of_mem_erase
An element in s.erase a also belongs to s.
Finset.ne_of_mem_erase
An element in s.erase a is not equal to a.
Finset.mem_filter.mp
If an element belongs to a filtered finset, it belongs to the original finset and satisfies the predicate.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
min_le_right
For any elements a and b in a linear order, min(a, b) ≤ b.
min_le_iff.mp
If min(b, c) ≤ a in a linear order, then b ≤ a or c ≤ a.

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

/-- In an IDO instance with MMS 1, each opposite pair has additive cost at most 4/3. -/lemma ido_opposite_pair_cost_le_four_thirds    (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) (j : Fin n) :    additive_valuation (c i) (chore_opposite_pair h2n j) ≤ 4 / 3 := by  have hj : (j : ℕ) < n := j.isLt  let e1 : Fin m := ⟨j.val, by omega⟩  let e2 : Fin m := ⟨2 * n - 1 - j.val, by omega⟩  have he12 : e1 ≤ e2 := by    change e1.val ≤ e2.val    dsimp [e1, e2]    omega  have h_pair_val : additive_valuation (c i) (chore_opposite_pair h2n j) = c i e1 + c i e2 := by    unfold additive_valuation chore_opposite_pair    dsimp only    have hne : (⟨j.val, by omega⟩ : Fin m) ≠ ⟨2 * n - 1 - j.val, by omega⟩ := by      intro h      have h' : j.val = 2 * n - 1 - j.val := Fin.ext_iff.mp h      omega    rw [Finset.sum_pair hne]  have h_e1_le_one : c i e1 ≤ 1 := by    have hP : ∀ P : Fin m → Fin n, c i e1 ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by      intro P      have he_in : e1 ∈ bundle_of P (P e1) := Finset.mem_filter.mpr ⟨Finset.mem_univ e1, rfl⟩      have he_le : c i e1 ≤ additive_valuation (c i) (bundle_of P (P e1)) := by        dsimp [additive_valuation]        have : c i e1 = ∑ x ∈ {e1}, c i x := by simp        rw [this]        apply Finset.sum_le_sum_of_subset_of_nonneg        · intro x hx          simp only [Finset.mem_singleton] at hx          rw [hx]          exact he_in        · intro x _ _          exact hc_nonneg i x      have h_le_sup : additive_valuation (c i) (bundle_of P (P e1)) ≤ ⨆ k', additive_valuation (c i) (bundle_of P k') :=        le_ciSup (Finite.bddAbove_range (fun k' => additive_valuation (c i) (bundle_of P k'))) (P e1)      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 h_le_inf : c i e1 ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) :=      le_ciInf hP    rw [h_mms_i] at h_le_inf    exact h_le_inf  have hT_card : (Finset.Iic e2).card = 2 * n - j.val := by    rw [Fin.card_Iic e2]    dsimp [e2]    omega  have hT0_card : (Finset.Iic e1).card = j.val + 1 := by    rw [Fin.card_Iic e1]  have hT0_sub_T : Finset.Iic e1 ⊆ Finset.Iic e2 := Finset.Iic_subset_Iic.mpr he12  have hP_bound : ∀ P : Fin m → Fin n, min (3 * c i e2) (c i e1 + c i e2) ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by    intro P    let S (k : Fin n) : Finset (Fin m) := (Finset.Iic e2).filter (fun x => P x = k)    let S0 (k : Fin n) : Finset (Fin m) := (Finset.Iic e1).filter (fun x => P x = k)    have hS_sub : ∀ k, S0 k ⊆ S k := by      intro k x hx      rw [Finset.mem_filter] at hx ⊢      exact ⟨hT0_sub_T hx.1, hx.2⟩    have hS_sum : ∑ k : Fin n, (S k).card = 2 * n - j.val := by      rw [← hT_card]      exact (Finset.card_eq_sum_card_fiberwise (fun x _ => Finset.mem_univ (P x))).symm    have hS0_sum : ∑ k : Fin n, (S0 k).card = j.val + 1 := by      rw [← hT0_card]      exact (Finset.card_eq_sum_card_fiberwise (fun x _ => Finset.mem_univ (P x))).symm    by_cases h_ge3 : ∃ k : Fin n, 3 ≤ (S k).card    · obtain ⟨k, hk⟩ := h_ge3      have hSy_sub : S k ⊆ bundle_of P k := 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 ∈ S k, c i x ≤ ∑ x ∈ bundle_of P k, 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 ∈ S k, c i e2 ≤ c i x := by        intro x hx        rw [Finset.mem_filter] at hx        have hxb : x ≤ e2 := Finset.mem_Iic.mp hx.1        exact h_ido i hxb      have h_sum_cg : ((S k).card : ℝ) * c i e2 ≤ ∑ x ∈ S k, c i x := by        have : ∑ _x ∈ S k, c i e2 ≤ ∑ x ∈ S k, c i x := Finset.sum_le_sum h_cg_le_x        simpa using this      have h3_card : 3 * c i e2 ≤ ((S k).card : ℝ) * c i e2 := by        have hcie2 : 0 ≤ c i e2 := hc_nonneg i e2        have h3_le : (3 : ℝ) ≤ ((S k).card : ℝ) := by          exact_mod_cast hk        nlinarith      have h3_bundle : 3 * c i e2 ≤ additive_valuation (c i) (bundle_of P k) := by        dsimp [additive_valuation]        linarith      have h_le_sup : additive_valuation (c i) (bundle_of P k) ≤ ⨆ k', additive_valuation (c i) (bundle_of P k') :=        le_ciSup (Finite.bddAbove_range (fun k' => additive_valuation (c i) (bundle_of P k'))) k      have : min (3 * c i e2) (c i e1 + c i e2) ≤ 3 * c i e2 := min_le_left _ _      linarith    · have h_le2 : ∀ k : Fin n, (S k).card ≤ 2 := by        intro k        by_contra h_gt        apply h_ge3        exact ⟨k, by omega⟩      have hex : ∃ k : Fin n, 1 ≤ (S0 k).card ∧ 2 ≤ (S k).card := by        by_contra h_none        have h_sum_le : ∀ k : Fin n, (S k).card + (S0 k).card ≤ 2 := by          intro k          have := h_le2 k          have := Finset.card_le_card (hS_sub k)          have hk_not : ¬(1 ≤ (S0 k).card ∧ 2 ≤ (S k).card) := fun h => h_none ⟨k, h⟩          omega        have h_total : ∑ k : Fin n, ((S k).card + (S0 k).card) ≤ ∑ k : Fin n, 2 := by          apply Finset.sum_le_sum          intro k _          exact h_sum_le k        rw [Finset.sum_add_distrib, hS_sum, hS0_sum] at h_total        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h_total        omega      obtain ⟨k0, hk0_1, hk0_2⟩ := hex      obtain ⟨a, ha⟩ := Finset.card_pos.mp (by omega : 0 < (S0 k0).card)      have ha_in_S : a ∈ S k0 := hS_sub k0 ha      have hS_erase_card : 1 ≤ ((S k0).erase a).card := by        rw [Finset.card_erase_of_mem ha_in_S]        omega      obtain ⟨b, hb_mem⟩ := Finset.card_pos.mp (by omega : 0 < ((S k0).erase a).card)      have hb_in_S : b ∈ S k0 := Finset.mem_of_mem_erase hb_mem      have hba : b ≠ a := Finset.ne_of_mem_erase hb_mem      have hab : a ≠ b := hba.symm      have ha_le_e1 : a ≤ e1 := by        have := (Finset.mem_filter.mp ha).1        exact Finset.mem_Iic.mp this      have hb_le_e2 : b ≤ e2 := by        have := (Finset.mem_filter.mp hb_in_S).1        exact Finset.mem_Iic.mp this      have h_pair_sub : {a, b} ⊆ bundle_of P k0 := by        intro x hx        simp only [Finset.mem_insert, Finset.mem_singleton] at hx        rcases hx with rfl | rfl        · have := (Finset.mem_filter.mp ha_in_S).2          simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and]          exact this        · have := (Finset.mem_filter.mp hb_in_S).2          simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and]          exact this      have h_sum_le : c i a + c i b ≤ additive_valuation (c i) (bundle_of P k0) := by        dsimp [additive_valuation]        have h_pair_sum : c i a + c i b = ∑ x ∈ {a, b}, c i x := by          rw [Finset.sum_pair hab]        rw [h_pair_sum]        apply Finset.sum_le_sum_of_subset_of_nonneg h_pair_sub        intro x _ _        exact hc_nonneg i x      have h_cia : c i e1 ≤ c i a := h_ido i ha_le_e1      have h_cib : c i e2 ≤ c i b := h_ido i hb_le_e2      have h_bundle_le : c i e1 + c i e2 ≤ additive_valuation (c i) (bundle_of P k0) := by        linarith      have h_le_sup : additive_valuation (c i) (bundle_of P k0) ≤ ⨆ k', additive_valuation (c i) (bundle_of P k') :=        le_ciSup (Finite.bddAbove_range (fun k' => additive_valuation (c i) (bundle_of P k'))) k0      have : min (3 * c i e2) (c i e1 + c i e2) ≤ c i e1 + c i e2 := min_le_right _ _      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 h_le_inf : min (3 * c i e2) (c i e1 + c i e2) ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) :=    le_ciInf hP_bound  rw [h_mms_i] at h_le_inf  have h_cases : 3 * c i e2 ≤ 1 ∨ c i e1 + c i e2 ≤ 1 := by    exact min_le_iff.mp h_le_inf  have h_sum_le_four_thirds : c i e1 + c i e2 ≤ 4 / 3 := by    rcases h_cases with h1 | h2    · have : c i e2 ≤ 1 / 3 := by linarith      linarith    · linarith  rw [h_pair_val]  exact h_sum_le_four_thirds
See it in the graphDiscuss this resultChallenge it