ido_opposite_pair_cost_le_four_thirds
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 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.
- 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$ 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.
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₂.
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
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₂).
uses
Fin.ext_iff.mp,Finset.sum_pairhave 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]
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.
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_ciInfhave 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
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.
uses
Fin.card_Iic,Finset.Iic_subset_Iic.mprhave 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
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.
uses
Finset.mem_filter,Finset.card_eq_sum_card_fiberwise,Finset.mem_univhave 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
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.
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_leftby_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
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.
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
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.
uses
le_ciInf,min_le_iff.mphave 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
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.
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
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 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