efx_exists_of_positive_perturbations
For any finite real additive valuation profile, if adding every strictly positive common real epsilon to every item value admits a complete EFX allocation, then the original profile admits a complete EFX allocation.
Statement
theorem efx_exists_of_positive_perturbations {m n : ℕ} (u : Fin n → Fin m → ℝ) (h : ∀ ε : ℝ, 0 < ε → ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + ε) σ) : ∃ σ : Fin m → Fin n, is_efx_goods u σ
- Source
- Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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.
- Used by 1
- efx_exists_of_strictly_positive_profilesFor fixed finite numbers of goods and agents, existence of complete EFX for every strictly positive real additive profile implies complete…
The proof, explained
The proof proceeds by a topological closure argument. Because the set of items and agents is finite, there are only finitely many allocations, making the set of perturbations ε that admit an EFX allocation a finite union of closed sets (defined by non-strict affine inequalities), and hence closed. Since this set contains all ε > 0 by hypothesis, it contains the closure [0, ∞), and thus contains ε = 0, which corresponds to the original unperturbed valuation profile.
For any fixed allocation σ, the set of perturbation values ε for which σ is an EFX allocation is closed in ℝ.
By definition, an allocation σ is EFX if for every pair of distinct agents i and j and every good g in agent j's bundle, agent i's valuation for bundle j without g is at most agent i's valuation for their own bundle. Unfolding this, the set of such ε is the intersection over all agents i, j, inequalities i ≠ j, and goods g of the sublevel sets where one additive valuation sum is bounded by another. Each side of the inequality is a continuous affine function of ε, so each sublevel set is closed by `isClosed_le`. Because arbitrary intersections of closed sets are closed (`isClosed_iInter`), the resulting set of ε is closed.
uses
Set.ofPred_forall,isClosed_iInter,isClosed_leclassical have hσ (σ : Fin m → Fin n) : IsClosed {ε : ℝ | is_efx_goods (fun i g => u i g + ε) σ} := by simp only [is_efx_goods, Set.ofPred_forall] refine isClosed_iInter (fun i => isClosed_iInter (fun j => isClosed_iInter (fun hij => isClosed_iInter (fun g => isClosed_iInter (fun hg => ?_))))) dsimp [additive_valuation] apply isClosed_le <;> fun_prop
The set of perturbations ε admitting at least one complete EFX allocation is closed in ℝ.
The set of ε for which there exists an EFX allocation is the union over all allocations σ : Fin m → Fin n of the sets where σ is EFX (`Set.ofPred_exists`). Because the number of goods m and agents n are finite, the type of allocations is finite. A union of closed sets over a finite index type is closed (`isClosed_iUnion_of_finite`).
uses
Set.ofPred_exists,isClosed_iUnion_of_finitehave hC : IsClosed {ε : ℝ | ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + ε) σ} := by simp only [Set.ofPred_exists] exact isClosed_iUnion_of_finite hσ
The point 0 belongs to the topological closure of the positive open ray (0, ∞).
In the standard topology on ℝ, the closure of the open ray (0, ∞) is the closed ray [0, ∞) (`closure_Ioi`). Since 0 ≤ 0 by reflexivity (`le_rfl`), 0 belongs to [0, ∞) and therefore to the closure of (0, ∞).
uses
closure_Ioi,le_rflhave hz : (0 : ℝ) ∈ closure (Set.Ioi (0 : ℝ)) := by rw [closure_Ioi] exact (show (0 : ℝ) ≤ 0 from le_rfl)
The original valuation profile u admits a complete EFX allocation.
By assumption, every ε > 0 admits an EFX allocation, so (0, ∞) is a subset of the set of perturbations admitting an EFX allocation. Since that set is closed, it contains the closure of (0, ∞) (`closure_minimal`), which contains 0. Thus, there exists an allocation σ that is EFX for the profile perturbed by ε = 0. Simplifying u(i, g) + 0 to u(i, g) with `add_zero` shows that σ is an EFX allocation for the original profile u.
uses
closure_minimal,add_zerohave hh := (closure_minimal (show Set.Ioi (0 : ℝ) ⊆ {ε : ℝ | ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + ε) σ} from h) hC) hz change ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + 0) σ at hh simpa only [add_zero] using hh
Set.ofPred_forall- A set defined by a universal quantifier {x | ∀ i, p i x} equals the intersection ⋂ i, {x | p i x}.
isClosed_iInter- An arbitrary intersection of closed sets is closed.
isClosed_le- If f and g are continuous functions into an ordered space with closed order topology, then {x | f x ≤ g x} is closed.
Set.ofPred_exists- A set defined by an existential quantifier {x | ∃ i, p i x} equals the union ⋃ i, {x | p i x}.
isClosed_iUnion_of_finite- The union of a family of closed sets indexed by a finite type is closed.
closure_Ioi- In a densely ordered order topology with no maximal element, the closure of the open interval (a, ∞) is the closed interval [a, ∞).
le_rfl- The inequality relation ≤ is reflexive: a ≤ a.
closure_minimal- If a set s is contained in a closed set t, then the closure of s is also contained in t.
add_zero- Adding zero to an element leaves it unchanged: a + 0 = a.
- On line 14, the `fun_prop` tactic automatically discharges the continuity goals for the finite sums of affine functions ε ↦ u(i, g) + ε.
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 Function Finsettheorem efx_exists_of_positive_perturbations {m n : ℕ} (u : Fin n → Fin m → ℝ) (h : ∀ ε : ℝ, 0 < ε → ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + ε) σ) : ∃ σ : Fin m → Fin n, is_efx_goods u σ := by classical have hσ (σ : Fin m → Fin n) : IsClosed {ε : ℝ | is_efx_goods (fun i g => u i g + ε) σ} := by simp only [is_efx_goods, Set.ofPred_forall] refine isClosed_iInter (fun i => isClosed_iInter (fun j => isClosed_iInter (fun hij => isClosed_iInter (fun g => isClosed_iInter (fun hg => ?_))))) dsimp [additive_valuation] apply isClosed_le <;> fun_prop have hC : IsClosed {ε : ℝ | ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + ε) σ} := by simp only [Set.ofPred_exists] exact isClosed_iUnion_of_finite hσ have hz : (0 : ℝ) ∈ closure (Set.Ioi (0 : ℝ)) := by rw [closure_Ioi] exact (show (0 : ℝ) ≤ 0 from le_rfl) have hh := (closure_minimal (show Set.Ioi (0 : ℝ) ⊆ {ε : ℝ | ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + ε) σ} from h) hC) hz change ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g + 0) σ at hh simpa only [add_zero] using hh