eefx_bundle_imp_approx_efk
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).
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).
unfold eefx_bundle_imp_approx_efk_pick_one split_ifs · simp · simp
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.
uses
mem_singleton,Classical.choose_spec,empty_subsetunfold 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 _
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.
unfold additive_valuation simp
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).
uses
sum_le_sum_of_subset_of_nonnegunfold additive_valuation exact sum_le_sum_of_subset_of_nonneg h (fun i _ _ => hu i)
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.
uses
sum_nonnegunfold additive_valuation exact sum_nonneg (fun i _ => hu i)
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.
uses
mem_biUnion,mem_inter,mem_univ,true_and,Disjoint.mono,inter_subset_right,sum_biUnionhave 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
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).
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_nonnegby_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
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).
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
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).
rcases h_eefx with ⟨Y, hY_disj, hY_union, hY_bound⟩
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).
uses
card_pair,card_univ,Fintype.card_fin,mem_insert,mem_singleton,not_or,congr_arghave ⟨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⟩
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₀.
uses
mem_filter,mem_univ,true_and,mem_sdiff,mem_biUnionobtain ⟨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⟩
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.
uses
mem_filter,mem_erase,card_le_card,card_erase_of_mem,card_univ,Fintype.card_finhave 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
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).
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_oneset 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
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.
uses
mem_sdiff,mem_filter,mem_univ,true_andhave 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⟩
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).
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_subhave 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
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.
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
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.
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)