AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_positive_perturbations

theoremverified

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

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.

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

    lines 7–14

    uses Set.ofPred_forall, isClosed_iInter, isClosed_le

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

    lines 15–18

    uses Set.ofPred_exists, isClosed_iUnion_of_finite

      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σ
  3. 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, ∞).

    lines 19–21

    uses closure_Ioi, le_rfl

      have hz : (0 : ℝ) ∈ closure (Set.Ioi (0 : ℝ)) := by
        rw [closure_Ioi]
        exact (show (0 : ℝ) ≤ 0 from le_rfl)
  4. 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.

    lines 22–25

    uses closure_minimal, add_zero

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

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