AFTD Auto-Formalizing Theoretical Domains

eefx_bundle_imp_approx_efk

theoremverified

Let n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is nonempty. If agent i's bundle is EEFX for agent i, then for every agent j ≠ i, agent i's valuation of her bundle is at least 1/(n-1) times the value of agent j's bundle after removing the n-2 most valuable goods for agent i.

Statement

theorem eefx_bundle_imp_approx_efk {m n : ℕ} (hn : 3 ≤ n)
    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)
    (σ : Fin m → Fin n) (h_nonempty : ∀ k : Fin n, (bundle_of σ k).Nonempty)
    (i j : Fin n) (hij : i ≠ j)
    (h_eefx : is_alpha_eefx_bundle (additive_valuation (u i)) n 1 (bundle_of σ i)) :
    (1 / ((n : ℝ) - 1)) * bundle_remove_k_value (additive_valuation (u i)) (n - 2) (bundle_of σ j) ≤
      additive_valuation (u i) (bundle_of σ i)
Source
arXiv:2610.34625, Lemma 3.2
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • bundle_remove_k_valueGiven a type of goods α with decidable equality, a valuation function v : Finset α → ℝ, a natural number k : ℕ, and a bundle S : Finset α,…
  • bundle_remove_k_value_leGiven a type of goods α with decidable equality, a valuation function v : Finset α → ℝ, a natural number k : ℕ, a bundle S : Finset α, and…
  • is_alpha_eefx_bundleA bundle S of goods is alpha-EEFX for an agent with valuation v if there exists a partition of the remaining goods into n-1 parts such…
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 1
  • eefx_imp_approx_efkLet n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is…

Read back from the Lean

Let $m, n \in \mathbb{N}$ with $n \ge 3$. Let $u : \mathrm{Fin}\ n \to \mathrm{Fin}\ m \to \mathbb{R}$ be a profile of utility functions such that $u(i, g) \ge 0$ for all $i \in \mathrm{Fin}\ n$ and all $g \in \mathrm{Fin}\ m$. Let $\sigma : \mathrm{Fin}\ m \to \mathrm{Fin}\ n$ be an allocation of goods to agents such that every agent $k \in \mathrm{Fin}\ n$ receives a non-empty bundle $\sigma^{-1}(\{k\})$. Let $i, j \in \mathrm{Fin}\ n$ with $i \ne j$. Assume that agent $i$'s bundle $\sigma^{-1}(\{i\})$ is $1$-EEFX with respect to agent $i$'s additive valuation (meaning there exists a partition of the remaining goods $\mathrm{Fin}\ m \setminus \sigma^{-1}(\{i\})$ into $n - 1$ pairwise disjoint subsets $Y_0, \dots, Y_{n-2}$ such that for all $p \in \mathrm{Fin}\ (n - 1)$ and all $g \in Y_p$, the valuation of $Y_p \setminus \{g\}$ under $u(i)$ is at most the valuation of $\sigma^{-1}(\{i\})$ under $u(i)$). Then, $\frac{1}{n - 1}$ times the minimum valuation (under $u(i)$) of agent $j$'s bundle after removing at most $n - 2$ goods is at most the valuation of agent $i$'s bundle under $u(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 establishes that if agent i's bundle A_i is 1-EEFX, her valuation of A_i is at least 1/(n - 1) times the value of any other agent j's bundle A_j after removing the n - 2 most valuable items for i. First, helper lemmas establish basic properties of picking an item, monotonicity and additivity of valuations, and show that removing at most one good from each partition part bounds the remaining value of each part by v_i(A_i). In the main theorem, since n ≥ 3 and bundles are nonempty, a third agent k owns a good outside A_i ∪ A_j, which ensures that at most n - 2 of the n - 1 parts in the EEFX partition of the goods outside A_i are contained in A_j. By picking at most one good from each of these at most n - 2 parts, we form a set X ⊆ A_j with |X| ≤ n - 2 such that every partition part has an item excluded from A_j \ X, bounding the value of each piece of A_j \ X by v_i(A_i) and summing to at most (n - 1) v_i(A_i).

  1. The finset pick_one(s) contains at most one element.

    By definition, pick_one(s) is either a singleton {Classical.choose h} if s is nonempty (with cardinality 1 ≤ 1) or the empty set ∅ if s is empty (with cardinality 0 ≤ 1).

    lines 8–11

      unfold eefx_bundle_imp_approx_efk_pick_one
      split_ifs
      · simp
      · simp
  2. The finset pick_one(s) is always a subset of s.

    If s is nonempty, pick_one(s) contains the single element Classical.choose h, which belongs to s by Classical.choose_spec (using mem_singleton). If s is empty, ∅ ⊆ s holds by empty_subset.

    lines 15–21

    uses mem_singleton, Classical.choose_spec, empty_subset

      unfold eefx_bundle_imp_approx_efk_pick_one
      split_ifs with h
      · intro x hx
        simp only [mem_singleton] at hx
        subst hx
        exact Classical.choose_spec h
      · exact empty_subset _
  3. The additive valuation of the empty set is 0.

    Unfolding additive_valuation, the sum of values over the empty set is 0 by definition of empty sums.

    lines 25–27

      unfold additive_valuation
      simp
    
  4. Additive valuation with nonnegative weights is monotonic under set inclusion.

    Unfolding additive_valuation, if S ⊆ T and every item has nonnegative valuation, sum_le_sum_of_subset_of_nonneg implies ∑_{j ∈ S} u(j) ≤ ∑_{j ∈ T} u(j).

    lines 31–33

    uses sum_le_sum_of_subset_of_nonneg

      unfold additive_valuation
      exact sum_le_sum_of_subset_of_nonneg h (fun i _ _ => hu i)
    
  5. Additive valuation with nonnegative weights is nonnegative on any bundle.

    Unfolding additive_valuation, the sum of nonnegative numbers over any finite set is nonnegative by sum_nonneg.

    lines 37–39

    uses sum_nonneg

      unfold additive_valuation
      exact sum_nonneg (fun i _ => hu i)
    
  6. If A is covered by a pairwise disjoint family (Y_p), the valuation of A is the sum of valuations of A ∩ Y_p.

    Since A ⊆ ⋃_p Y_p, the family of intersections A ∩ Y_p partitions A (using mem_biUnion, mem_inter, mem_univ, true_and). Pairwise disjointness of the intersections follows from that of the Y_p via Disjoint.mono and inter_subset_right. By sum_biUnion, the sum of u over A equals the sum over p of the valuations of A ∩ Y_p.

    lines 45–62

    uses mem_biUnion, mem_inter, mem_univ, true_and, Disjoint.mono, inter_subset_right, sum_biUnion

      have h_eq : univ.biUnion (fun p => A ∩ Y p) = A := by
        ext x
        simp only [mem_biUnion, mem_inter, mem_univ, true_and]
        constructor
        · rintro ⟨p, hxA, -⟩
          exact hxA
        · intro hxA
          have hx : x ∈ univ.biUnion Y := hA hxA
          rw [mem_biUnion] at hx
          rcases hx with ⟨p, -, hxY⟩
          exact ⟨p, hxA, hxY⟩
      have h_pw : (↑(univ : Finset (Fin (n - 1))) : Set (Fin (n - 1))).PairwiseDisjoint (fun p => A ∩ Y p) := by
        intro p _ q _ hpq
        exact Disjoint.mono inter_subset_right inter_subset_right (hY_disj p q hpq)
      unfold additive_valuation
      nth_rw 1 [← h_eq]
      exact sum_biUnion h_pw
    
  7. When Y_p ⊆ A_j, the valuation of (A_j \ X) ∩ Y_p is at most v_i(A_i).

    If Y_p is nonempty, pick_one(Y_p) chooses an item g ∈ Y_p (by Classical.choose, Classical.choose_spec) that belongs to X (mem_biUnion, mem_singleton_self). Thus (A_j \ X) ∩ Y_p is a subset of Y_p \ {g} (using mem_inter, mem_sdiff, mem_erase), so monotonicity (eefx_bundle_imp_approx_efk_val_mono) and the EEFX hypothesis (one_mul) bound its value by v_i(A_i). If Y_p is empty (not_nonempty_iff_eq_empty), the intersection is empty (inter_empty) with valuation 0 (eefx_bundle_imp_approx_efk_val_empty) ≤ v_i(A_i) (eefx_bundle_imp_approx_efk_val_nonneg).

    lines 74–97

    uses Classical.choose, Classical.choose_spec, mem_biUnion, mem_singleton_self, mem_inter, mem_sdiff, mem_erase, eefx_bundle_imp_approx_efk_val_mono, one_mul, not_nonempty_iff_eq_empty, inter_empty, eefx_bundle_imp_approx_efk_val_empty, eefx_bundle_imp_approx_efk_val_nonneg

      by_cases hp : p ∈ P_sub
      · by_cases hne : (Y p).Nonempty
        · obtain ⟨g, hg_in, hg_pick⟩ : ∃ g ∈ Y p, eefx_bundle_imp_approx_efk_pick_one (Y p) = {g} := by
            unfold eefx_bundle_imp_approx_efk_pick_one
            simp only [hne, dite_true]
            exact ⟨Classical.choose hne, Classical.choose_spec hne, rfl⟩
          have hg_in_X : g ∈ X := by
            rw [hX, mem_biUnion]
            exact ⟨p, hp, by rw [hg_pick]; exact mem_singleton_self g⟩
          have h_sub : (A_j \ X) ∩ Y p ⊆ (Y p).erase g := by
            intro x hx
            simp only [mem_inter, mem_sdiff] at hx
            rw [mem_erase]
            refine ⟨?_, hx.2⟩
            rintro rfl
            exact hx.1.2 hg_in_X
          have h_mono := eefx_bundle_imp_approx_efk_val_mono u hu h_sub
          have h_bound := hY_bound p g hg_in
          rw [one_mul] at h_bound
          exact h_mono.trans h_bound
        · have hY_empty : Y p = ∅ := not_nonempty_iff_eq_empty.mp hne
          have h_inter_empty : (A_j \ X) ∩ Y p = ∅ := by rw [hY_empty, inter_empty]
          rw [h_inter_empty, eefx_bundle_imp_approx_efk_val_empty]
          exact eefx_bundle_imp_approx_efk_val_nonneg u hu A_i
  8. When Y_p is not a subset of A_j, the valuation of (A_j \ X) ∩ Y_p is at most v_i(A_i).

    Since Y_p ⊈ A_j, there exists an item g ∈ Y_p with g ∉ A_j. This again ensures (A_j \ X) ∩ Y_p ⊆ Y_p \ {g} (mem_inter, mem_sdiff, mem_erase). By monotonicity (eefx_bundle_imp_approx_efk_val_mono) and the EEFX bound (one_mul), the value is at most v_i(A_i).

    lines 98–113

    uses mem_inter, mem_sdiff, mem_erase, eefx_bundle_imp_approx_efk_val_mono, one_mul

      · rw [hP_sub] at hp
        have ⟨g, hg_in, hg_not_Aj⟩ : ∃ g ∈ Y p, g ∉ A_j := by
          by_contra! hc
          exact hp hc
        have h_sub : (A_j \ X) ∩ Y p ⊆ (Y p).erase g := by
          intro x hx
          simp only [mem_inter, mem_sdiff] at hx
          rw [mem_erase]
          refine ⟨?_, hx.2⟩
          rintro rfl
          exact hg_not_Aj hx.1.1
        have h_mono := eefx_bundle_imp_approx_efk_val_mono u hu h_sub
        have h_bound := hY_bound p g hg_in
        rw [one_mul] at h_bound
        exact h_mono.trans h_bound
    
  9. Agent i's bundle satisfies the EEFX condition with respect to a partition (Y_p)_{p ∈ Fin(n-1)} of the goods outside A_i.

    We unpack the EEFX hypothesis on agent i's bundle: there exists a partition of all items outside A_i into n-1 pairwise disjoint bundles Y_p such that removing any single item g from any part Y_p leaves a bundle with valuation at most v_i(A_i).

    line 122

      rcases h_eefx with ⟨Y, hY_disj, hY_union, hY_bound⟩
  10. There exists a third agent k distinct from both i and j.

    Since i ≠ j, the pair {i, j} has cardinality 2 by card_pair. Because n ≥ 3, the total number of agents exceeds 2, so {i, j} cannot equal the universal set of agents (by card_univ and Fintype.card_fin). Thus there exists an agent k not in {i, j}, meaning k ≠ i and k ≠ j (using mem_insert, mem_singleton, not_or, and congr_arg).

    lines 123–134

    uses card_pair, card_univ, Fintype.card_fin, mem_insert, mem_singleton, not_or, congr_arg

      have ⟨k, hki, hkj⟩ : ∃ k : Fin n, k ≠ i ∧ k ≠ j := by
        have h_card : ({i, j} : Finset (Fin n)).card = 2 := card_pair hij
        have : ∃ k : Fin n, k ∉ ({i, j} : Finset (Fin n)) := by
          by_contra! hc
          have heq : ({i, j} : Finset (Fin n)) = univ := by
            ext x; simp [hc x]
          have hlen := congr_arg Finset.card heq
          rw [h_card, card_univ, Fintype.card_fin] at hlen
          omega
        rcases this with ⟨k, hk⟩
        simp only [mem_insert, mem_singleton, not_or] at hk
        exact ⟨k, hk.1, hk.2⟩
  11. Agent k's bundle contains an item g₀ that belongs to some partition part Y_{p₀} and does not belong to A_j.

    By the nonemptiness assumption, agent k has an item g₀. Because k ≠ i and k ≠ j, g₀ is in neither A_i nor A_j (unfolding bundle_of with mem_filter, mem_univ, true_and). Hence g₀ lies in the complement of A_i (mem_sdiff), which is covered by the union of the parts Y_p (mem_biUnion), placing g₀ in Y_{p₀} for some index p₀.

    lines 135–154

    uses mem_filter, mem_univ, true_and, mem_sdiff, mem_biUnion

      obtain ⟨g0, hg0⟩ := h_nonempty k
      have hg0_σ : σ g0 = k := by
        unfold bundle_of at hg0
        simp only [mem_filter, mem_univ, true_and] at hg0
        exact hg0
      have hg0_not_i : g0 ∉ bundle_of σ i := by
        unfold bundle_of
        simp only [mem_filter, mem_univ, true_and]
        intro h
        exact hki (hg0_σ.symm.trans h)
      have hg0_not_j : g0 ∉ bundle_of σ j := by
        unfold bundle_of
        simp only [mem_filter, mem_univ, true_and]
        intro h
        exact hkj (hg0_σ.symm.trans h)
      have hg0_in_diff : g0 ∈ Finset.univ \ bundle_of σ i := by
        rw [mem_sdiff]
        exact ⟨mem_univ _, hg0_not_i⟩
      rw [← hY_union, mem_biUnion] at hg0_in_diff
      rcases hg0_in_diff with ⟨p0, -, hg0_in_Y⟩
  12. At most n - 2 of the partition parts Y_p are completely contained in agent j's bundle A_j.

    Because g₀ ∈ Y_{p₀} but g₀ ∉ A_j, the part Y_{p₀} is not a subset of A_j. Let P_sub be the set of indices p such that Y_p ⊆ A_j. Then p₀ ∉ P_sub, which means P_sub is contained in the universal set minus {p₀} (mem_erase). By card_le_card, card_erase_of_mem, card_univ, and Fintype.card_fin, the size of P_sub is at most (n - 1) - 1 = n - 2.

    lines 155–167

    uses mem_filter, mem_erase, card_le_card, card_erase_of_mem, card_univ, Fintype.card_fin

      have hp0_not_sub : ¬ (Y p0 ⊆ bundle_of σ j) := by
        intro hsub
        exact hg0_not_j (hsub hg0_in_Y)
      set P_sub : Finset (Fin (n - 1)) := univ.filter (fun p => Y p ⊆ bundle_of σ j)
      have hp0_not_in_P : p0 ∉ P_sub := fun h => hp0_not_sub (mem_filter.mp h).2
      have hP_sub_card : P_sub.card ≤ n - 2 := by
        have h_sub : P_sub ⊆ univ.erase p0 := by
          intro p hp
          rw [mem_erase]
          exact ⟨fun h => hp0_not_in_P (h ▸ hp), mem_univ _⟩
        have h_le := card_le_card h_sub
        rw [card_erase_of_mem (mem_univ p0), card_univ, Fintype.card_fin] at h_le
        omega
  13. There exists a subset X ⊆ A_j of at most n - 2 goods obtained by picking at most one good from each part Y_p contained in A_j.

    We form X as the union over p ∈ P_sub of pick_one(Y_p). Since each pick_one(Y_p) is a subset of Y_p (by eefx_bundle_imp_approx_efk_pick_one_subset) and Y_p ⊆ A_j for p ∈ P_sub, we have X ⊆ A_j. Furthermore, each pick_one(Y_p) has cardinality at most 1 (by eefx_bundle_imp_approx_efk_pick_one_card_le), so by card_biUnion_le and sum_le_sum, |X| is at most |P_sub| ≤ n - 2 (simplifying with sum_const, smul_eq_mul, mul_one).

    lines 168–180

    uses mem_biUnion, mem_filter, eefx_bundle_imp_approx_efk_pick_one_subset, card_biUnion_le, sum_le_sum, eefx_bundle_imp_approx_efk_pick_one_card_le, sum_const, smul_eq_mul, mul_one

      set X : Finset (Fin m) := P_sub.biUnion (fun p => eefx_bundle_imp_approx_efk_pick_one (Y p))
      have hX_sub_Aj : X ⊆ bundle_of σ j := by
        intro x hx
        rw [mem_biUnion] at hx
        rcases hx with ⟨p, hp, hx_pick⟩
        have hp_sub : Y p ⊆ bundle_of σ j := (mem_filter.mp hp).2
        exact hp_sub (eefx_bundle_imp_approx_efk_pick_one_subset (Y p) hx_pick)
      have hX_card : X.card ≤ n - 2 := by
        calc
          X.card ≤ ∑ p ∈ P_sub, (eefx_bundle_imp_approx_efk_pick_one (Y p)).card := card_biUnion_le
          _ ≤ ∑ p ∈ P_sub, 1 := sum_le_sum (fun p _ => eefx_bundle_imp_approx_efk_pick_one_card_le (Y p))
          _ = P_sub.card := by rw [sum_const, smul_eq_mul, mul_one]
          _ ≤ n - 2 := hP_sub_card
  14. The remaining items A_j \ X are contained in the union of the partition parts Y_p.

    Every good g ∈ A_j \ X belongs to agent j. Since j ≠ i, g cannot belong to agent i's bundle A_i (using mem_sdiff, bundle_of, mem_filter, mem_univ, true_and). Therefore g belongs to the complement of A_i, which is the union of all Y_p.

    lines 181–194

    uses mem_sdiff, mem_filter, mem_univ, true_and

      have h_Aj_sub : (bundle_of σ j \ X) ⊆ univ.biUnion Y := by
        intro g hg
        have hg_j : g ∈ bundle_of σ j := (mem_sdiff.mp hg).1
        have hg_σ_j : σ g = j := by
          unfold bundle_of at hg_j
          simp only [mem_filter, mem_univ, true_and] at hg_j
          exact hg_j
        have hg_not_i_2 : g ∉ bundle_of σ i := by
          unfold bundle_of
          simp only [mem_filter, mem_univ, true_and]
          intro h
          exact hij (hg_σ_j.symm.trans h).symm
        rw [hY_union, mem_sdiff]
        exact ⟨mem_univ _, hg_not_i_2⟩
  15. Agent i's valuation of A_j \ X is at most (n - 1) times her valuation of A_i.

    By eefx_bundle_imp_approx_efk_sum_val_partition, v_i(A_j \ X) splits into the sum of v_i((A_j \ X) ∩ Y_p) over all p. By lemma eefx_bundle_imp_approx_efk_part_val_le (with mem_filter, and_iff_right, mem_univ), each piece has valuation at most v_i(A_i): if p ∈ P_sub, an item was removed from Y_p by X; if p ∉ P_sub, Y_p already had an item not in A_j. Summing these n - 1 bounds via sum_le_sum and sum_const (with card_univ, Fintype.card_fin, nsmul_eq_mul, Nat.cast_sub) yields v_i(A_j \ X) ≤ (n - 1) v_i(A_i).

    lines 195–211

    uses eefx_bundle_imp_approx_efk_sum_val_partition, eefx_bundle_imp_approx_efk_part_val_le, mem_filter, and_iff_right, mem_univ, sum_le_sum, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul, Nat.cast_sub

      have h_sum_split := eefx_bundle_imp_approx_efk_sum_val_partition (u i) (bundle_of σ j \ X) Y hY_disj h_Aj_sub
      have h_term_le : ∀ p : Fin (n - 1),
          additive_valuation (u i) ((bundle_of σ j \ X) ∩ Y p) ≤ additive_valuation (u i) (bundle_of σ i) := by
        intro p
        exact eefx_bundle_imp_approx_efk_part_val_le (u i) (hu i) (bundle_of σ i) (bundle_of σ j) Y hY_bound P_sub
          (fun q => mem_filter.trans (and_iff_right (mem_univ q))) X rfl p
      have h_val_le : additive_valuation (u i) (bundle_of σ j \ X) ≤ ((n : ℝ) - 1) * additive_valuation (u i) (bundle_of σ i) := by
        rw [h_sum_split]
        calc
          ∑ p : Fin (n - 1), additive_valuation (u i) ((bundle_of σ j \ X) ∩ Y p)
            ≤ ∑ _p : Fin (n - 1), additive_valuation (u i) (bundle_of σ i) := sum_le_sum (fun p _ => h_term_le p)
          _ = ((n : ℝ) - 1) * additive_valuation (u i) (bundle_of σ i) := by
            rw [sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul]
            have h1 : 1 ≤ n := by omega
            rw [Nat.cast_sub h1]
            push_cast
            rfl
  16. Agent i's valuation of A_i is at least 1/(n - 1) times the value of A_j after removing the n - 2 most valuable goods for i.

    By bundle_remove_k_value_le, the value after removing the optimal n - 2 goods is bounded above by v_i(A_j \ X), since X ⊆ A_j and |X| ≤ n - 2. Combined with the bound v_i(A_j \ X) ≤ (n - 1) v_i(A_i), this yields bundle_remove_k_value ≤ (n - 1) v_i(A_i). Since n ≥ 3 implies n - 1 > 0, dividing both sides by n - 1 (using div_mul_eq_mul_div, one_mul, div_le_iff₀) gives the theorem.

    lines 212–222

    uses bundle_remove_k_value_le, div_mul_eq_mul_div, one_mul, div_le_iff₀

      have h_rem_le : bundle_remove_k_value (additive_valuation (u i)) (n - 2) (bundle_of σ j) ≤
          additive_valuation (u i) (bundle_of σ j \ X) :=
        bundle_remove_k_value_le (additive_valuation (u i)) (n - 2) (bundle_of σ j) X hX_sub_Aj hX_card
      have h_trans : bundle_remove_k_value (additive_valuation (u i)) (n - 2) (bundle_of σ j) ≤
          ((n : ℝ) - 1) * additive_valuation (u i) (bundle_of σ i) :=
        h_rem_le.trans h_val_le
      have hn_pos : 0 < (n : ℝ) - 1 := by
        have : (3 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
        linarith
      rw [div_mul_eq_mul_div, one_mul]
      exact (div_le_iff₀ hn_pos).mpr (by linarith)
mem_singleton
An element belongs to {a} if and only if it equals a.
Classical.choose_spec
For an existential statement ∃ x, p x, Classical.choose_spec guarantees that the chosen element satisfies p.
empty_subset
The empty finset ∅ is a subset of any finset s.
sum_le_sum_of_subset_of_nonneg
If s ⊆ t and f is nonnegative on t \ s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ t} f(i).
sum_nonneg
If f is nonnegative on s, then ∑_{i ∈ s} f(i) ≥ 0.
mem_biUnion
An element belongs to a union ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
mem_inter
An element belongs to s ∩ t if and only if it belongs to s and to t.
mem_univ
Every element of a finite type belongs to Finset.univ.
true_and
The proposition True ∧ p is equivalent to p.
Disjoint.mono
If a ≤ b, c ≤ d, and b and d are disjoint, then a and c are disjoint.
inter_subset_right
For finsets s and t, s ∩ t ⊆ t.
sum_biUnion
If a family of finsets is pairwise disjoint, the sum of f over their union equals the sum of the sums over each set.
Classical.choose
Given a proof of ∃ x, p x, Classical.choose returns an element x satisfying p.
mem_singleton_self
An element a belongs to the singleton {a}.
mem_sdiff
An element belongs to s \ t if and only if it belongs to s and not to t.
mem_erase
An element x belongs to s \ {a} if and only if x ≠ a and x ∈ s.
eefx_bundle_imp_approx_efk_val_mono
If u is nonnegative and S ⊆ T, then additive_valuation u S ≤ additive_valuation u T.
one_mul
Multiplying 1 by any element on the left leaves it unchanged: 1 * a = a.
not_nonempty_iff_eq_empty
A finset is not nonempty if and only if it is empty.
inter_empty
The intersection of any finset with the empty set is empty.
eefx_bundle_imp_approx_efk_val_empty
The additive valuation of the empty set is 0.
eefx_bundle_imp_approx_efk_val_nonneg
If u is nonnegative, then additive_valuation u S ≥ 0.
card_pair
For distinct elements a ≠ b, the unordered pair {a, b} has cardinality 2.
card_univ
The cardinality of Finset.univ for a finite type is the cardinality of that type.
Fintype.card_fin
The cardinality of Fin n is n.
mem_insert
An element is in {a} ∪ s if and only if it equals a or belongs to s.
not_or
The negation ¬(P ∨ Q) is equivalent to ¬P ∧ ¬Q.
congr_arg
Applying a function to equal arguments yields equal values: a₁ = a₂ implies f(a₁) = f(a₂).
mem_filter
An element x belongs to {y ∈ s | P(y)} if and only if x ∈ s and P(x) holds.
card_le_card
If s ⊆ t, then |s| ≤ |t|.
card_erase_of_mem
Removing an element a ∈ s decreases the cardinality of s by 1.
eefx_bundle_imp_approx_efk_pick_one_subset
The set pick_one(s) is always a subset of s.
card_biUnion_le
The cardinality of a union ⋃_{a ∈ s} t(a) is at most the sum of the cardinalities ∑_{a ∈ s} |t(a)|.
sum_le_sum
If f(x) ≤ g(x) for all x ∈ s, then ∑_{x ∈ s} f(x) ≤ ∑_{x ∈ s} g(x).
eefx_bundle_imp_approx_efk_pick_one_card_le
The cardinality of pick_one(s) is at most 1.
sum_const
The sum of a constant c over a finset s equals |s| • c.
smul_eq_mul
Scalar multiplication in a ring or module coincides with ordinary multiplication.
mul_one
Multiplying any element by 1 on the right leaves it unchanged: a * 1 = a.
eefx_bundle_imp_approx_efk_sum_val_partition
If a set A is covered by a pairwise disjoint family (Y_p), the additive valuation of A equals the sum of the valuations of the intersections A ∩ Y_p.
eefx_bundle_imp_approx_efk_part_val_le
For each partition part Y_p, removing the selected set X leaves an intersection (A_j \ X) ∩ Y_p whose valuation is at most v_i(A_i).
and_iff_right
If proposition A holds, then A ∧ B is equivalent to B.
nsmul_eq_mul
Natural scalar multiplication n • a on real numbers equals (n : ℝ) * a.
Nat.cast_sub
For natural numbers m ≤ n, the real cast of their difference (n - m) equals (n : ℝ) - (m : ℝ).
bundle_remove_k_value_le
Removing any specific subset X ⊆ S with |X| ≤ k provides an upper bound on the infimum bundle_remove_k_value v k S.
div_mul_eq_mul_div
For elements in a division commutative monoid, (a / b) * c = (a * c) / b.
div_le_iff₀
For a positive divisor c > 0, b / c ≤ a if and only if b ≤ a * 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

open Finsetnoncomputable def eefx_bundle_imp_approx_efk_pick_one {α : Type*} (s : Finset α) : Finset α :=  if h : s.Nonempty then {Classical.choose h} else ∅lemma eefx_bundle_imp_approx_efk_pick_one_card_le {α : Type*} (s : Finset α) :    (eefx_bundle_imp_approx_efk_pick_one s).card ≤ 1 := by  unfold eefx_bundle_imp_approx_efk_pick_one  split_ifs  · simp  · simplemma eefx_bundle_imp_approx_efk_pick_one_subset {α : Type*} (s : Finset α) :    eefx_bundle_imp_approx_efk_pick_one s ⊆ s := by  unfold eefx_bundle_imp_approx_efk_pick_one  split_ifs with h  · intro x hx    simp only [mem_singleton] at hx    subst hx    exact Classical.choose_spec h  · exact empty_subset _lemma eefx_bundle_imp_approx_efk_val_empty {m : ℕ} (u : Fin m → ℝ) :    additive_valuation u ∅ = 0 := by  unfold additive_valuation  simplemma eefx_bundle_imp_approx_efk_val_mono {m : ℕ} (u : Fin m → ℝ) (hu : ∀ g, 0 ≤ u g)    {S T : Finset (Fin m)} (h : S ⊆ T) :    additive_valuation u S ≤ additive_valuation u T := by  unfold additive_valuation  exact sum_le_sum_of_subset_of_nonneg h (fun i _ _ => hu i)lemma eefx_bundle_imp_approx_efk_val_nonneg {m : ℕ} (u : Fin m → ℝ) (hu : ∀ g, 0 ≤ u g)    (S : Finset (Fin m)) :    0 ≤ additive_valuation u S := by  unfold additive_valuation  exact sum_nonneg (fun i _ => hu i)lemma eefx_bundle_imp_approx_efk_sum_val_partition {m n : ℕ} (u : Fin m → ℝ)    (A : Finset (Fin m)) (Y : Fin (n - 1) → Finset (Fin m))    (hY_disj : ∀ p q : Fin (n - 1), p ≠ q → Disjoint (Y p) (Y q))    (hA : A ⊆ Finset.univ.biUnion Y) :    additive_valuation u A = ∑ p : Fin (n - 1), additive_valuation u (A ∩ Y p) := by  have h_eq : univ.biUnion (fun p => A ∩ Y p) = A := by    ext x    simp only [mem_biUnion, mem_inter, mem_univ, true_and]    constructor    · rintro ⟨p, hxA, -⟩      exact hxA    · intro hxA      have hx : x ∈ univ.biUnion Y := hA hxA      rw [mem_biUnion] at hx      rcases hx with ⟨p, -, hxY⟩      exact ⟨p, hxA, hxY⟩  have h_pw : (↑(univ : Finset (Fin (n - 1))) : Set (Fin (n - 1))).PairwiseDisjoint (fun p => A ∩ Y p) := by    intro p _ q _ hpq    exact Disjoint.mono inter_subset_right inter_subset_right (hY_disj p q hpq)  unfold additive_valuation  nth_rw 1 [← h_eq]  exact sum_biUnion h_pwlemma eefx_bundle_imp_approx_efk_part_val_le {m n : ℕ}    (u : Fin m → ℝ) (hu : ∀ g, 0 ≤ u g)    (A_i A_j : Finset (Fin m))    (Y : Fin (n - 1) → Finset (Fin m))    (hY_bound : ∀ p : Fin (n - 1), ∀ g ∈ Y p, 1 * additive_valuation u ((Y p).erase g) ≤ additive_valuation u A_i)    (P_sub : Finset (Fin (n - 1)))    (hP_sub : ∀ p, p ∈ P_sub ↔ Y p ⊆ A_j)    (X : Finset (Fin m))    (hX : X = P_sub.biUnion (fun p => eefx_bundle_imp_approx_efk_pick_one (Y p)))    (p : Fin (n - 1)) :    additive_valuation u ((A_j \ X) ∩ Y p) ≤ additive_valuation u A_i := by  by_cases hp : p ∈ P_sub  · by_cases hne : (Y p).Nonempty    · obtain ⟨g, hg_in, hg_pick⟩ : ∃ g ∈ Y p, eefx_bundle_imp_approx_efk_pick_one (Y p) = {g} := by        unfold eefx_bundle_imp_approx_efk_pick_one        simp only [hne, dite_true]        exact ⟨Classical.choose hne, Classical.choose_spec hne, rfl⟩      have hg_in_X : g ∈ X := by        rw [hX, mem_biUnion]        exact ⟨p, hp, by rw [hg_pick]; exact mem_singleton_self g⟩      have h_sub : (A_j \ X) ∩ Y p ⊆ (Y p).erase g := by        intro x hx        simp only [mem_inter, mem_sdiff] at hx        rw [mem_erase]        refine ⟨?_, hx.2⟩        rintro rfl        exact hx.1.2 hg_in_X      have h_mono := eefx_bundle_imp_approx_efk_val_mono u hu h_sub      have h_bound := hY_bound p g hg_in      rw [one_mul] at h_bound      exact h_mono.trans h_bound    · have hY_empty : Y p = ∅ := not_nonempty_iff_eq_empty.mp hne      have h_inter_empty : (A_j \ X) ∩ Y p = ∅ := by rw [hY_empty, inter_empty]      rw [h_inter_empty, eefx_bundle_imp_approx_efk_val_empty]      exact eefx_bundle_imp_approx_efk_val_nonneg u hu A_i  · rw [hP_sub] at hp    have ⟨g, hg_in, hg_not_Aj⟩ : ∃ g ∈ Y p, g ∉ A_j := by      by_contra! hc      exact hp hc    have h_sub : (A_j \ X) ∩ Y p ⊆ (Y p).erase g := by      intro x hx      simp only [mem_inter, mem_sdiff] at hx      rw [mem_erase]      refine ⟨?_, hx.2⟩      rintro rfl      exact hg_not_Aj hx.1.1    have h_mono := eefx_bundle_imp_approx_efk_val_mono u hu h_sub    have h_bound := hY_bound p g hg_in    rw [one_mul] at h_bound    exact h_mono.trans h_bound/-- If an allocation among n ≥ 3 agents has only nonempty bundles and agent i's bundle is EEFX, then i's value for her bundle is at least 1/(n-1) times the value of any other bundle after removing n-2 goods. -/theorem eefx_bundle_imp_approx_efk {m n : ℕ} (hn : 3 ≤ n)    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)    (σ : Fin m → Fin n) (h_nonempty : ∀ k : Fin n, (bundle_of σ k).Nonempty)    (i j : Fin n) (hij : i ≠ j)    (h_eefx : is_alpha_eefx_bundle (additive_valuation (u i)) n 1 (bundle_of σ i)) :    (1 / ((n : ℝ) - 1)) * bundle_remove_k_value (additive_valuation (u i)) (n - 2) (bundle_of σ j) ≤      additive_valuation (u i) (bundle_of σ i) := by  rcases h_eefx with ⟨Y, hY_disj, hY_union, hY_bound⟩  have ⟨k, hki, hkj⟩ : ∃ k : Fin n, k ≠ i ∧ k ≠ j := by    have h_card : ({i, j} : Finset (Fin n)).card = 2 := card_pair hij    have : ∃ k : Fin n, k ∉ ({i, j} : Finset (Fin n)) := by      by_contra! hc      have heq : ({i, j} : Finset (Fin n)) = univ := by        ext x; simp [hc x]      have hlen := congr_arg Finset.card heq      rw [h_card, card_univ, Fintype.card_fin] at hlen      omega    rcases this with ⟨k, hk⟩    simp only [mem_insert, mem_singleton, not_or] at hk    exact ⟨k, hk.1, hk.2⟩  obtain ⟨g0, hg0⟩ := h_nonempty k  have hg0_σ : σ g0 = k := by    unfold bundle_of at hg0    simp only [mem_filter, mem_univ, true_and] at hg0    exact hg0  have hg0_not_i : g0 ∉ bundle_of σ i := by    unfold bundle_of    simp only [mem_filter, mem_univ, true_and]    intro h    exact hki (hg0_σ.symm.trans h)  have hg0_not_j : g0 ∉ bundle_of σ j := by    unfold bundle_of    simp only [mem_filter, mem_univ, true_and]    intro h    exact hkj (hg0_σ.symm.trans h)  have hg0_in_diff : g0 ∈ Finset.univ \ bundle_of σ i := by    rw [mem_sdiff]    exact ⟨mem_univ _, hg0_not_i⟩  rw [← hY_union, mem_biUnion] at hg0_in_diff  rcases hg0_in_diff with ⟨p0, -, hg0_in_Y⟩  have hp0_not_sub : ¬ (Y p0 ⊆ bundle_of σ j) := by    intro hsub    exact hg0_not_j (hsub hg0_in_Y)  set P_sub : Finset (Fin (n - 1)) := univ.filter (fun p => Y p ⊆ bundle_of σ j)  have hp0_not_in_P : p0 ∉ P_sub := fun h => hp0_not_sub (mem_filter.mp h).2  have hP_sub_card : P_sub.card ≤ n - 2 := by    have h_sub : P_sub ⊆ univ.erase p0 := by      intro p hp      rw [mem_erase]      exact ⟨fun h => hp0_not_in_P (h ▸ hp), mem_univ _⟩    have h_le := card_le_card h_sub    rw [card_erase_of_mem (mem_univ p0), card_univ, Fintype.card_fin] at h_le    omega  set X : Finset (Fin m) := P_sub.biUnion (fun p => eefx_bundle_imp_approx_efk_pick_one (Y p))  have hX_sub_Aj : X ⊆ bundle_of σ j := by    intro x hx    rw [mem_biUnion] at hx    rcases hx with ⟨p, hp, hx_pick⟩    have hp_sub : Y p ⊆ bundle_of σ j := (mem_filter.mp hp).2    exact hp_sub (eefx_bundle_imp_approx_efk_pick_one_subset (Y p) hx_pick)  have hX_card : X.card ≤ n - 2 := by    calc      X.card ≤ ∑ p ∈ P_sub, (eefx_bundle_imp_approx_efk_pick_one (Y p)).card := card_biUnion_le      _ ≤ ∑ p ∈ P_sub, 1 := sum_le_sum (fun p _ => eefx_bundle_imp_approx_efk_pick_one_card_le (Y p))      _ = P_sub.card := by rw [sum_const, smul_eq_mul, mul_one]      _ ≤ n - 2 := hP_sub_card  have h_Aj_sub : (bundle_of σ j \ X) ⊆ univ.biUnion Y := by    intro g hg    have hg_j : g ∈ bundle_of σ j := (mem_sdiff.mp hg).1    have hg_σ_j : σ g = j := by      unfold bundle_of at hg_j      simp only [mem_filter, mem_univ, true_and] at hg_j      exact hg_j    have hg_not_i_2 : g ∉ bundle_of σ i := by      unfold bundle_of      simp only [mem_filter, mem_univ, true_and]      intro h      exact hij (hg_σ_j.symm.trans h).symm    rw [hY_union, mem_sdiff]    exact ⟨mem_univ _, hg_not_i_2⟩  have h_sum_split := eefx_bundle_imp_approx_efk_sum_val_partition (u i) (bundle_of σ j \ X) Y hY_disj h_Aj_sub  have h_term_le : ∀ p : Fin (n - 1),      additive_valuation (u i) ((bundle_of σ j \ X) ∩ Y p) ≤ additive_valuation (u i) (bundle_of σ i) := by    intro p    exact eefx_bundle_imp_approx_efk_part_val_le (u i) (hu i) (bundle_of σ i) (bundle_of σ j) Y hY_bound P_sub      (fun q => mem_filter.trans (and_iff_right (mem_univ q))) X rfl p  have h_val_le : additive_valuation (u i) (bundle_of σ j \ X) ≤ ((n : ℝ) - 1) * additive_valuation (u i) (bundle_of σ i) := by    rw [h_sum_split]    calc      ∑ p : Fin (n - 1), additive_valuation (u i) ((bundle_of σ j \ X) ∩ Y p)        ≤ ∑ _p : Fin (n - 1), additive_valuation (u i) (bundle_of σ i) := sum_le_sum (fun p _ => h_term_le p)      _ = ((n : ℝ) - 1) * additive_valuation (u i) (bundle_of σ i) := by        rw [sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul]        have h1 : 1 ≤ n := by omega        rw [Nat.cast_sub h1]        push_cast        rfl  have h_rem_le : bundle_remove_k_value (additive_valuation (u i)) (n - 2) (bundle_of σ j) ≤      additive_valuation (u i) (bundle_of σ j \ X) :=    bundle_remove_k_value_le (additive_valuation (u i)) (n - 2) (bundle_of σ j) X hX_sub_Aj hX_card  have h_trans : bundle_remove_k_value (additive_valuation (u i)) (n - 2) (bundle_of σ j) ≤      ((n : ℝ) - 1) * additive_valuation (u i) (bundle_of σ i) :=    h_rem_le.trans h_val_le  have hn_pos : 0 < (n : ℝ) - 1 := by    have : (3 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn    linarith  rw [div_mul_eq_mul_div, one_mul]  exact (div_le_iff₀ hn_pos).mpr (by linarith)
See it in the graphDiscuss this resultChallenge it