complete_pmms_matroid_rank_sharp_mms_factor
For every integer n ≥ 2, every finite set of m indivisible goods, every profile of matroid-rank valuations v_1, ..., v_n on the goods, and every complete allocation σ that is pairwise maximin-share (PMMS) fair, every agent i receives at least a 1/(n-1) fraction of her maximin share: MMS_i(n, M) ≤ (n - 1) * v_i(bundle_of σ i).
Statement
theorem complete_pmms_matroid_rank_sharp_mms_factor :
∀ (n m : ℕ) (hn : 2 ≤ n) (v : Fin n → Finset (Fin m) → ℝ),
(∀ i, is_matroid_rank_valuation (v i)) →
∀ σ : Fin m → Fin n, (∀ i, is_pmms_fair v σ i) →
∀ i : Fin n, maximin_share (v i) n ≤ (n - 1 : ℝ) * v i (bundle_of σ i)- Formalizes
- arXiv:2012.12710
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- is_matroid_rank_valuationA set function on a finite set of indivisible goods is a matroid-rank valuation if it evaluates the empty set to 0, is submodular, and has…
- is_pmms_fairAn allocation is pairwise-MMS-fair to agent i if, for every other agent j, i's bundle is worth to i at least i's two-agent maximin share…
- maximin_shareThe maximin share of a valuation among n agents: the maximum, over partitions of the items into n bundles, of the value of the worst bundle.
- 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.
- has_binary_marginalsEvery marginal value of the set function is 0 or 1.
- is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
- pairwise_maximin_shareThe maximin share of a valuation when the items U are split into two bundles: the maximum over T inside U of min(v(T), v(U - T)).
- submod_union_marginal_leFor a monotone submodular set function and S inside T, adding a set U gains at most as much on top of T as on top of S.
- submod_biUnion_le_sumA monotone submodular set function with v(empty) = 0 is subadditive over a finite family of sets.
Read back from the Lean
For all natural numbers $n, m$ such that $2 \le n$, and for all valuation profiles $v : \mathrm{Fin}\ n \to \mathrm{Finset}(\mathrm{Fin}\ m) \to \mathbb{R}$, if for every agent $i \in \mathrm{Fin}\ n$, $v(i)$ is a matroid rank valuation, then for every allocation $\sigma : \mathrm{Fin}\ m \to \mathrm{Fin}\ n$, if $\sigma$ is pairwise maximin share (PMMS) fair for all agents $i \in \mathrm{Fin}\ n$, then for every agent $i \in \mathrm{Fin}\ n$, the $n$-agent maximin share of $v(i)$ is at most $(n - 1)$ times the value $v(i)$ of agent $i$'s bundle under $\sigma$ (i.e., $\mathrm{MMS}_n(v_i) \le (n - 1) \cdot v_i(\sigma^{-1}(i))$).
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 proof bounds the maximin share MMS_i(n, M) by showing that in any partition of the goods into n bundles, at least one bundle has rank at most (n - 1) v_i(A_i). For each other agent j ≠ i, pairwise maximin-share (PMMS) fairness implies that at most one bundle in the partition can have an overlap with A_i ∪ A_j valued strictly above v_i(A_i), as otherwise two disjoint bundles would both exceed v_i(A_i) and violate the PMMS condition. Across the n - 1 other agents, the pigeonhole principle implies that some bundle k* is not oversized for any pair involving agent i. Finally, covering bundle k* with one two-agent pool A_i ∪ A_{j_0} and the remaining n - 2 individual bundles A_j, submodularity and monotonicity bound its total rank by v_i(A_i) + (n - 2) v_i(A_i) = (n - 1) v_i(A_i).
The valuation r = v_i is normalized, monotone, non-negative, and subadditive.
We fix agent i and write r for v_i. Since v_i is a matroid rank valuation, it satisfies r(∅) = 0, submodularity, and has binary marginal gains in {0, 1}. Because adding an element cannot decrease r, an induction on the elements added establishes that r is monotone (S ⊆ T implies r(S) ≤ r(T)), which in turn gives non-negativity since r(S) ≥ r(∅) = 0. Comparing ∅ with S in the diminishing marginal returns inequality shows that r is subadditive: r(S ∪ T) ≤ r(S) + r(T).
uses
Finset.induction_on,Finset.union_insert,Finset.insert_eq_of_mem,Finset.union_sdiff_of_subset,Finset.empty_subset,submod_union_marginal_le,Finset.empty_union,le_transintro n m hn v hv σ hpmms i set r : Finset (Fin m) → ℝ := v i with hr obtain ⟨hzero, hsub, hbin⟩ := hv i have hz : r ∅ = 0 := hzero have hstep : ∀ (S : Finset (Fin m)) (x : Fin m), x ∉ S → r S ≤ r (insert x S) := by intro S x hx rcases hbin S x hx with h | h <;> linarith have hmono : Monotone r := by have key : ∀ (U S : Finset (Fin m)), r S ≤ r (S ∪ U) := by intro U induction U using Finset.induction_on with | empty => intro S; simp | insert x U hx ih => intro S rw [Finset.union_insert] by_cases hxS : x ∈ S · rw [Finset.insert_eq_of_mem (by simp [hxS])]; exact ih S · exact le_trans (ih S) (hstep (S ∪ U) x (by simp [hxS, hx])) intro S T hST have h := key (T \ S) S rwa [Finset.union_sdiff_of_subset hST] at h have hnonneg : ∀ S : Finset (Fin m), 0 ≤ r S := by intro S have h := hmono (Finset.empty_subset S) rwa [hz] at h have hadd : ∀ S T : Finset (Fin m), r (S ∪ T) ≤ r S + r T := by intro S T have h := submod_union_marginal_le r hmono hsub (S := ∅) (T := S) (Finset.empty_subset S) T simp only [Finset.empty_union, hz] at h linarith
For any other agent j ≠ i and any subset T ⊆ A_i ∪ A_j, the minimum of r(T) and r((A_i ∪ A_j) \ T) is at most a = r(A_i).
Let A_i = bundle_of σ i and a = r(A_i). By pairwise maximin-share (PMMS) fairness, agent i's pairwise maximin share on the two-agent pool A_i ∪ A_j is at most a. Since the PMMS value is the supremum over all subbundles of the minimum of the two partition pieces, every specific subbundle T ⊆ A_i ∪ A_j has min(r(T), r((A_i ∪ A_j) \ T)) ≤ a.
uses
min_le_left,le_ciSup,le_transset A : Finset (Fin m) := bundle_of σ i with hA set a : ℝ := r A with ha have hpair : ∀ j, j ≠ i → ∀ T : Finset (Fin m), T ⊆ A ∪ bundle_of σ j → min (r T) (r ((A ∪ bundle_of σ j) \ T)) ≤ a := by intro j hj T hT have hsup : pairwise_maximin_share r (A ∪ bundle_of σ j) ≤ a := by have h := hpmms i j hj rwa [hr, hA, ha] have hbdd : BddAbove (Set.range fun T : {T : Finset (Fin m) // T ⊆ A ∪ bundle_of σ j} => min (r T.1) (r ((A ∪ bundle_of σ j) \ T.1))) := by refine ⟨r (A ∪ bundle_of σ j), ?_⟩ rintro _ ⟨T, rfl⟩ exact le_trans (min_le_left _ _) (hmono T.2) have hle : min (r T) (r ((A ∪ bundle_of σ j) \ T)) ≤ pairwise_maximin_share r (A ∪ bundle_of σ j) := by rw [pairwise_maximin_share] exact le_ciSup hbdd ⟨T, hT⟩ linarith
To bound the maximin share MMS_i(n, M), it suffices to show that every partition P contains a bundle of value at most (n - 1)a.
The maximin share MMS_i(n, M) is defined as the supremum over all n-bundle partitions P of the minimum bundle value inf_k r(bundle_of P k). Hence, proving MMS_i(n, M) ≤ (n - 1)a reduces to proving that inf_k r(bundle_of P k) ≤ (n - 1)a for an arbitrary fixed partition P.
uses
ciSup_lerw [maximin_share] haveI : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, by omega⟩⟩ apply ciSup_le intro P
For each agent j ≠ i, at most one bundle k of P has r(bundle_of P k ∩ (A_i ∪ A_j)) > a.
Define bad(j) as the set of bundle indices k whose overlap with A_i ∪ A_j has value strictly greater than a. If there were two distinct bundles k ≠ k' in bad(j), they would be disjoint. Setting T = bundle_of P k ∩ (A_i ∪ A_j), the overlap of bundle k' is contained in the complement (A_i ∪ A_j) \ T. Monotonicity implies that the complement also has value greater than a, so min(r(T), r((A_i ∪ A_j) \ T)) > a, which contradicts the PMMS bound from the previous step. Therefore, |bad(j)| ≤ 1.
uses
Finset.card_le_one,Finset.disjoint_left,Finset.inter_subset_right,lt_of_lt_of_le,lt_minlet bad : Fin n → Finset (Fin n) := fun j => Finset.univ.filter (fun k : Fin n => a < r (bundle_of P k ∩ (A ∪ bundle_of σ j))) have hcard : ∀ j ∈ (Finset.univ.erase i), (bad j).card ≤ 1 := by intro j hj rw [Finset.card_le_one] intro k hk k' hk' by_contra hne have hk1 : a < r (bundle_of P k ∩ (A ∪ bundle_of σ j)) := (Finset.mem_filter.mp hk).2 have hk2 : a < r (bundle_of P k' ∩ (A ∪ bundle_of σ j)) := (Finset.mem_filter.mp hk').2 have hji : j ≠ i := (Finset.mem_erase.mp hj).1 have hdisj : Disjoint (bundle_of P k) (bundle_of P k') := by rw [Finset.disjoint_left] intro x hx hx' simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at hx hx' exact hne (hx.symm.trans hx') have hsub' : bundle_of P k' ∩ (A ∪ bundle_of σ j) ⊆ (A ∪ bundle_of σ j) \ (bundle_of P k ∩ (A ∪ bundle_of σ j)) := by intro x hx simp only [Finset.mem_inter, Finset.mem_sdiff] at hx ⊢ exact ⟨hx.2, fun h => Finset.disjoint_left.mp hdisj h.1 hx.1⟩ have hT := hpair j hji (bundle_of P k ∩ (A ∪ bundle_of σ j)) Finset.inter_subset_right have hgt : a < r ((A ∪ bundle_of σ j) \ (bundle_of P k ∩ (A ∪ bundle_of σ j))) := lt_of_lt_of_le hk2 (hmono hsub') have hlt : a < min (r (bundle_of P k ∩ (A ∪ bundle_of σ j))) (r ((A ∪ bundle_of σ j) \ (bundle_of P k ∩ (A ∪ bundle_of σ j)))) := lt_min hk1 hgt linarith
There exists a bundle k* of P that is not bad for any agent j ≠ i.
There are n - 1 agents other than i. Because each |bad(j)| ≤ 1, the union ⋃_{j ≠ i} bad(j) contains at most n - 1 bundles. Since partition P has n bundles and n > n - 1, the pigeonhole principle yields a bundle k* outside this union. For this bundle k*, the overlap with A_i ∪ A_j has rank at most a for all j ≠ i.
uses
Finset.card_biUnion_le,Finset.sum_le_sum,Finset.sum_const,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_fin,Finset.eq_univ_of_forallhave hScard : ((Finset.univ.erase i).biUnion bad).card ≤ n - 1 := by have h1 : ((Finset.univ.erase i).biUnion bad).card ≤ ∑ j ∈ (Finset.univ.erase i), (bad j).card := Finset.card_biUnion_le have h2 : ∑ j ∈ (Finset.univ.erase i), (bad j).card ≤ ∑ j ∈ (Finset.univ.erase i), (1:ℕ) := Finset.sum_le_sum hcard have h3 : ∑ j ∈ (Finset.univ.erase i), (1:ℕ) = n - 1 := by rw [Finset.sum_const, Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] simp omega have hex : ∃ k : Fin n, k ∉ (Finset.univ.erase i).biUnion bad := by by_contra h simp only [not_exists, not_not] at h have hSfull : (Finset.univ.erase i).biUnion bad = Finset.univ := Finset.eq_univ_of_forall h have hc : ((Finset.univ.erase i).biUnion bad).card = n := by rw [hSfull, Finset.card_univ, Fintype.card_fin] omega obtain ⟨kstar, hkstar⟩ := hex have hkstar_le : ∀ j, j ≠ i → r (bundle_of P kstar ∩ (A ∪ bundle_of σ j)) ≤ a := by intro j hj have hmem : j ∈ Finset.univ.erase i := Finset.mem_erase.mpr ⟨hj, Finset.mem_univ j⟩ have hnot : kstar ∉ bad j := by intro hk exact hkstar (Finset.mem_biUnion.mpr ⟨j, hmem, hk⟩) have hnot' : ¬ (a < r (bundle_of P kstar ∩ (A ∪ bundle_of σ j))) := by intro hlt exact hnot (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hlt⟩) exact not_lt.mp hnot'
The rank of bundle k* is at most (n - 1)a.
Since n ≥ 2, we choose an agent j_0 ≠ i. Bundle k* is covered by the two-agent pool overlap bundle_of P k* ∩ (A_i ∪ A_{j_0}) together with the single-agent overlaps bundle_of P k* ∩ A_j for the remaining n - 2 agents j ∉ {i, j_0}. Subadditivity bounds r(bundle_of P k*) by the rank of the first term plus the rank of the union of the remaining n - 2 pieces. The first term is at most a because k* ∉ bad(j_0). By submodularity, the rank of the union is bounded by the sum of the individual ranks. Each individual piece is contained in bundle_of P k* ∩ (A_i ∪ A_j), so monotonicity and k* ∉ bad(j) ensure each of the n - 2 terms is at most a. Summing these bounds gives r(bundle_of P k*) ≤ a + (n - 2)a = (n - 1)a.
uses
le_trans,submod_biUnion_le_sum,Finset.sum_le_sum,Finset.sum_const,nsmul_eq_mul,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_fin,Nat.cast_subhave hJpos : 0 < (Finset.univ.erase i : Finset (Fin n)).card := by rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] omega obtain ⟨j0, hj0mem⟩ := Finset.card_pos.mp hJpos have hj0ne : j0 ≠ i := (Finset.mem_erase.mp hj0mem).1 have hcover : bundle_of P kstar ⊆ (bundle_of P kstar ∩ (A ∪ bundle_of σ j0)) ∪ (((Finset.univ.erase i).erase j0).biUnion (fun j => bundle_of P kstar ∩ bundle_of σ j)) := by intro x hx by_cases hxi : σ x = i · refine Finset.mem_union_left _ (Finset.mem_inter.mpr ⟨hx, ?_⟩) exact Finset.mem_union_left _ (by simp [A, bundle_of, hxi]) · by_cases hxj : σ x = j0 · refine Finset.mem_union_left _ (Finset.mem_inter.mpr ⟨hx, ?_⟩) exact Finset.mem_union_right _ (by simp [bundle_of, hxj]) · refine Finset.mem_union_right _ (Finset.mem_biUnion.mpr ⟨σ x, ?_, ?_⟩) · simp only [Finset.mem_erase, Finset.mem_univ, and_true] exact ⟨hxj, hxi⟩ · exact Finset.mem_inter.mpr ⟨hx, by simp [bundle_of]⟩ have h1 : r (bundle_of P kstar) ≤ r (bundle_of P kstar ∩ (A ∪ bundle_of σ j0)) + r (((Finset.univ.erase i).erase j0).biUnion (fun j => bundle_of P kstar ∩ bundle_of σ j)) := le_trans (hmono hcover) (hadd _ _) have h2 : r (bundle_of P kstar ∩ (A ∪ bundle_of σ j0)) ≤ a := hkstar_le j0 hj0ne have h3 : r (((Finset.univ.erase i).erase j0).biUnion (fun j => bundle_of P kstar ∩ bundle_of σ j)) ≤ ∑ j ∈ (Finset.univ.erase i).erase j0, r (bundle_of P kstar ∩ bundle_of σ j) := submod_biUnion_le_sum r hmono hsub hz _ _ have h4 : ∑ j ∈ (Finset.univ.erase i).erase j0, r (bundle_of P kstar ∩ bundle_of σ j) ≤ ∑ j ∈ (Finset.univ.erase i).erase j0, a := by apply Finset.sum_le_sum intro j hj have hji : j ≠ i := (Finset.mem_erase.mp (Finset.mem_erase.mp hj).2).1 have hBJ : bundle_of P kstar ∩ bundle_of σ j ⊆ bundle_of P kstar ∩ (A ∪ bundle_of σ j) := by intro x hx simp only [Finset.mem_inter] at hx ⊢ exact ⟨hx.1, Finset.mem_union_right _ hx.2⟩ exact le_trans (hmono hBJ) (hkstar_le j hji) have h5 : ∑ j ∈ (Finset.univ.erase i).erase j0, a = (((Finset.univ.erase i).erase j0 : Finset (Fin n)).card : ℝ) * a := by rw [Finset.sum_const, nsmul_eq_mul] have h6 : ((Finset.univ.erase i).erase j0 : Finset (Fin n)).card = n - 2 := by rw [Finset.card_erase_of_mem (Finset.mem_erase.mpr ⟨hj0ne, Finset.mem_univ j0⟩)] rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] omega have h7 : ((n - 2 : ℕ) : ℝ) = (n : ℝ) - 2 := Nat.cast_sub (by omega : 2 ≤ n) have hbound : r (bundle_of P kstar) ≤ (n - 1 : ℝ) * a := by have h6' : ((((Finset.univ.erase i).erase j0 : Finset (Fin n)).card : ℕ) : ℝ) = ((n - 2 : ℕ) : ℝ) := by rw [h6] rw [h6', h7] at h5 nlinarith [h1, h2, h3, h4, h5]
The maximin share MMS_i(n, M) is at most (n - 1)a.
The infimum of bundle values under partition P is bounded above by r(bundle_of P k*) ≤ (n - 1)a. Since this holds for every partition P, taking the supremum over all partitions yields MMS_i(n, M) ≤ (n - 1)a = (n - 1) v_i(bundle_of σ i).
uses
ciInf_le,le_transhave hbdd : BddBelow (Set.range fun k : Fin n => r (bundle_of P k)) := ⟨0, by rintro _ ⟨k, rfl⟩; exact hnonneg _⟩ exact le_trans (ciInf_le hbdd kstar) hbound
Finset.induction_on- Every property holding for the empty set and preserved by inserting a fresh element holds for all finite sets.
Finset.union_insert- Union distributes over inserting an element: S ∪ ({x} ∪ T) = {x} ∪ (S ∪ T).
Finset.insert_eq_of_mem- Inserting an element already present in a finite set leaves the set unchanged.
Finset.union_sdiff_of_subset- If S ⊆ T, then S ∪ (T \ S) = T.
Finset.empty_subset- The empty set is a subset of every finite set.
submod_union_marginal_le- For a monotone submodular function v and S ⊆ T, the marginal gain v(T ∪ U) - v(T) is bounded by v(S ∪ U) - v(S).
Finset.empty_union- The union of the empty set with any finite set S equals S.
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
min_le_left- The minimum min(a, b) is less than or equal to a.
le_ciSup- For a conditionally complete lattice and an upper-bounded function, any value f(c) is bounded by sup f.
ciSup_le- For a conditionally complete lattice with nonempty index, if f(x) ≤ c for all x, then sup f ≤ c.
Finset.card_le_one- A finite set has at most one element if and only if any two of its elements are identical.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.inter_subset_right- The intersection of two sets is a subset of the second set.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
lt_min- If a < b and a < c, then a < min(b, c).
Finset.card_biUnion_le- The cardinality of a union of finite sets is bounded by the sum of their individual cardinalities.
Finset.sum_le_sum- If f(x) ≤ g(x) for all x in a finite set, the sum of f is at most the sum of g.
Finset.sum_const- The sum of a constant value over a finite set s is |s| times that value.
Finset.card_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1.
Finset.card_univ- The cardinality of Finset.univ for a finite type is the cardinality of the type itself.
Fintype.card_fin- The cardinality of the standard finite type Fin n is n.
Finset.eq_univ_of_forall- A subset of a finite type containing every element is the entire universal set.
submod_biUnion_le_sum- For a normalized monotone submodular function, the value on a finite union of sets is at most the sum of values of the sets.
nsmul_eq_mul- Natural number scalar multiplication n • a equals the product n * a.
Nat.cast_sub- If m ≤ n, casting n - m to a ring with subtraction equals the difference of the casts.
ciInf_le- For a conditionally complete lattice and a lower-bounded function, inf f is at most any value f(c).
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.
/-- OP-598: In complete PMMS allocations under matroid-rank valuations, is (n-1) v_i(A_i) ≥ MMS_i(n, M) for all agents? -/theorem complete_pmms_matroid_rank_sharp_mms_factor : ∀ (n m : ℕ) (hn : 2 ≤ n) (v : Fin n → Finset (Fin m) → ℝ), (∀ i, is_matroid_rank_valuation (v i)) → ∀ σ : Fin m → Fin n, (∀ i, is_pmms_fair v σ i) → ∀ i : Fin n, maximin_share (v i) n ≤ (n - 1 : ℝ) * v i (bundle_of σ i) := by intro n m hn v hv σ hpmms i set r : Finset (Fin m) → ℝ := v i with hr obtain ⟨hzero, hsub, hbin⟩ := hv i have hz : r ∅ = 0 := hzero have hstep : ∀ (S : Finset (Fin m)) (x : Fin m), x ∉ S → r S ≤ r (insert x S) := by intro S x hx rcases hbin S x hx with h | h <;> linarith have hmono : Monotone r := by have key : ∀ (U S : Finset (Fin m)), r S ≤ r (S ∪ U) := by intro U induction U using Finset.induction_on with | empty => intro S; simp | insert x U hx ih => intro S rw [Finset.union_insert] by_cases hxS : x ∈ S · rw [Finset.insert_eq_of_mem (by simp [hxS])]; exact ih S · exact le_trans (ih S) (hstep (S ∪ U) x (by simp [hxS, hx])) intro S T hST have h := key (T \ S) S rwa [Finset.union_sdiff_of_subset hST] at h have hnonneg : ∀ S : Finset (Fin m), 0 ≤ r S := by intro S have h := hmono (Finset.empty_subset S) rwa [hz] at h have hadd : ∀ S T : Finset (Fin m), r (S ∪ T) ≤ r S + r T := by intro S T have h := submod_union_marginal_le r hmono hsub (S := ∅) (T := S) (Finset.empty_subset S) T simp only [Finset.empty_union, hz] at h linarith set A : Finset (Fin m) := bundle_of σ i with hA set a : ℝ := r A with ha have hpair : ∀ j, j ≠ i → ∀ T : Finset (Fin m), T ⊆ A ∪ bundle_of σ j → min (r T) (r ((A ∪ bundle_of σ j) \ T)) ≤ a := by intro j hj T hT have hsup : pairwise_maximin_share r (A ∪ bundle_of σ j) ≤ a := by have h := hpmms i j hj rwa [hr, hA, ha] have hbdd : BddAbove (Set.range fun T : {T : Finset (Fin m) // T ⊆ A ∪ bundle_of σ j} => min (r T.1) (r ((A ∪ bundle_of σ j) \ T.1))) := by refine ⟨r (A ∪ bundle_of σ j), ?_⟩ rintro _ ⟨T, rfl⟩ exact le_trans (min_le_left _ _) (hmono T.2) have hle : min (r T) (r ((A ∪ bundle_of σ j) \ T)) ≤ pairwise_maximin_share r (A ∪ bundle_of σ j) := by rw [pairwise_maximin_share] exact le_ciSup hbdd ⟨T, hT⟩ linarith rw [maximin_share] haveI : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, by omega⟩⟩ apply ciSup_le intro P let bad : Fin n → Finset (Fin n) := fun j => Finset.univ.filter (fun k : Fin n => a < r (bundle_of P k ∩ (A ∪ bundle_of σ j))) have hcard : ∀ j ∈ (Finset.univ.erase i), (bad j).card ≤ 1 := by intro j hj rw [Finset.card_le_one] intro k hk k' hk' by_contra hne have hk1 : a < r (bundle_of P k ∩ (A ∪ bundle_of σ j)) := (Finset.mem_filter.mp hk).2 have hk2 : a < r (bundle_of P k' ∩ (A ∪ bundle_of σ j)) := (Finset.mem_filter.mp hk').2 have hji : j ≠ i := (Finset.mem_erase.mp hj).1 have hdisj : Disjoint (bundle_of P k) (bundle_of P k') := by rw [Finset.disjoint_left] intro x hx hx' simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at hx hx' exact hne (hx.symm.trans hx') have hsub' : bundle_of P k' ∩ (A ∪ bundle_of σ j) ⊆ (A ∪ bundle_of σ j) \ (bundle_of P k ∩ (A ∪ bundle_of σ j)) := by intro x hx simp only [Finset.mem_inter, Finset.mem_sdiff] at hx ⊢ exact ⟨hx.2, fun h => Finset.disjoint_left.mp hdisj h.1 hx.1⟩ have hT := hpair j hji (bundle_of P k ∩ (A ∪ bundle_of σ j)) Finset.inter_subset_right have hgt : a < r ((A ∪ bundle_of σ j) \ (bundle_of P k ∩ (A ∪ bundle_of σ j))) := lt_of_lt_of_le hk2 (hmono hsub') have hlt : a < min (r (bundle_of P k ∩ (A ∪ bundle_of σ j))) (r ((A ∪ bundle_of σ j) \ (bundle_of P k ∩ (A ∪ bundle_of σ j)))) := lt_min hk1 hgt linarith have hScard : ((Finset.univ.erase i).biUnion bad).card ≤ n - 1 := by have h1 : ((Finset.univ.erase i).biUnion bad).card ≤ ∑ j ∈ (Finset.univ.erase i), (bad j).card := Finset.card_biUnion_le have h2 : ∑ j ∈ (Finset.univ.erase i), (bad j).card ≤ ∑ j ∈ (Finset.univ.erase i), (1:ℕ) := Finset.sum_le_sum hcard have h3 : ∑ j ∈ (Finset.univ.erase i), (1:ℕ) = n - 1 := by rw [Finset.sum_const, Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] simp omega have hex : ∃ k : Fin n, k ∉ (Finset.univ.erase i).biUnion bad := by by_contra h simp only [not_exists, not_not] at h have hSfull : (Finset.univ.erase i).biUnion bad = Finset.univ := Finset.eq_univ_of_forall h have hc : ((Finset.univ.erase i).biUnion bad).card = n := by rw [hSfull, Finset.card_univ, Fintype.card_fin] omega obtain ⟨kstar, hkstar⟩ := hex have hkstar_le : ∀ j, j ≠ i → r (bundle_of P kstar ∩ (A ∪ bundle_of σ j)) ≤ a := by intro j hj have hmem : j ∈ Finset.univ.erase i := Finset.mem_erase.mpr ⟨hj, Finset.mem_univ j⟩ have hnot : kstar ∉ bad j := by intro hk exact hkstar (Finset.mem_biUnion.mpr ⟨j, hmem, hk⟩) have hnot' : ¬ (a < r (bundle_of P kstar ∩ (A ∪ bundle_of σ j))) := by intro hlt exact hnot (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hlt⟩) exact not_lt.mp hnot' have hJpos : 0 < (Finset.univ.erase i : Finset (Fin n)).card := by rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] omega obtain ⟨j0, hj0mem⟩ := Finset.card_pos.mp hJpos have hj0ne : j0 ≠ i := (Finset.mem_erase.mp hj0mem).1 have hcover : bundle_of P kstar ⊆ (bundle_of P kstar ∩ (A ∪ bundle_of σ j0)) ∪ (((Finset.univ.erase i).erase j0).biUnion (fun j => bundle_of P kstar ∩ bundle_of σ j)) := by intro x hx by_cases hxi : σ x = i · refine Finset.mem_union_left _ (Finset.mem_inter.mpr ⟨hx, ?_⟩) exact Finset.mem_union_left _ (by simp [A, bundle_of, hxi]) · by_cases hxj : σ x = j0 · refine Finset.mem_union_left _ (Finset.mem_inter.mpr ⟨hx, ?_⟩) exact Finset.mem_union_right _ (by simp [bundle_of, hxj]) · refine Finset.mem_union_right _ (Finset.mem_biUnion.mpr ⟨σ x, ?_, ?_⟩) · simp only [Finset.mem_erase, Finset.mem_univ, and_true] exact ⟨hxj, hxi⟩ · exact Finset.mem_inter.mpr ⟨hx, by simp [bundle_of]⟩ have h1 : r (bundle_of P kstar) ≤ r (bundle_of P kstar ∩ (A ∪ bundle_of σ j0)) + r (((Finset.univ.erase i).erase j0).biUnion (fun j => bundle_of P kstar ∩ bundle_of σ j)) := le_trans (hmono hcover) (hadd _ _) have h2 : r (bundle_of P kstar ∩ (A ∪ bundle_of σ j0)) ≤ a := hkstar_le j0 hj0ne have h3 : r (((Finset.univ.erase i).erase j0).biUnion (fun j => bundle_of P kstar ∩ bundle_of σ j)) ≤ ∑ j ∈ (Finset.univ.erase i).erase j0, r (bundle_of P kstar ∩ bundle_of σ j) := submod_biUnion_le_sum r hmono hsub hz _ _ have h4 : ∑ j ∈ (Finset.univ.erase i).erase j0, r (bundle_of P kstar ∩ bundle_of σ j) ≤ ∑ j ∈ (Finset.univ.erase i).erase j0, a := by apply Finset.sum_le_sum intro j hj have hji : j ≠ i := (Finset.mem_erase.mp (Finset.mem_erase.mp hj).2).1 have hBJ : bundle_of P kstar ∩ bundle_of σ j ⊆ bundle_of P kstar ∩ (A ∪ bundle_of σ j) := by intro x hx simp only [Finset.mem_inter] at hx ⊢ exact ⟨hx.1, Finset.mem_union_right _ hx.2⟩ exact le_trans (hmono hBJ) (hkstar_le j hji) have h5 : ∑ j ∈ (Finset.univ.erase i).erase j0, a = (((Finset.univ.erase i).erase j0 : Finset (Fin n)).card : ℝ) * a := by rw [Finset.sum_const, nsmul_eq_mul] have h6 : ((Finset.univ.erase i).erase j0 : Finset (Fin n)).card = n - 2 := by rw [Finset.card_erase_of_mem (Finset.mem_erase.mpr ⟨hj0ne, Finset.mem_univ j0⟩)] rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] omega have h7 : ((n - 2 : ℕ) : ℝ) = (n : ℝ) - 2 := Nat.cast_sub (by omega : 2 ≤ n) have hbound : r (bundle_of P kstar) ≤ (n - 1 : ℝ) * a := by have h6' : ((((Finset.univ.erase i).erase j0 : Finset (Fin n)).card : ℕ) : ℝ) = ((n - 2 : ℕ) : ℝ) := by rw [h6] rw [h6', h7] at h5 nlinarith [h1, h2, h3, h4, h5] have hbdd : BddBelow (Set.range fun k : Fin n => r (bundle_of P k)) := ⟨0, by rintro _ ⟨k, rfl⟩; exact hnonneg _⟩ exact le_trans (ciInf_le hbdd kstar) hbound