AFTD Auto-Formalizing Theoretical Domains

complete_pmms_matroid_rank_sharp_mms_factor

theoremverifiedformalization

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

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

    lines 7–36

    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_trans

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

    lines 37–54

    uses min_le_left, le_ciSup, le_trans

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

    lines 55–58

    uses ciSup_le

      rw [maximin_share]
      haveI : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, by omega⟩⟩
      apply ciSup_le
      intro P
  4. 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.

    lines 59–84

    uses Finset.card_le_one, Finset.disjoint_left, Finset.inter_subset_right, lt_of_lt_of_le, lt_min

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

    lines 85–112

    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_forall

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

    lines 113–159

    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_sub

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

    lines 160–162

    uses ciInf_le, le_trans

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

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