AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_strictly_positive_profiles

theoremverified

For fixed finite numbers of goods and agents, existence of complete EFX for every strictly positive real additive profile implies complete EFX existence for every nonnegative real additive profile.

Statement

theorem efx_exists_of_strictly_positive_profiles (m n : ℕ)
    (h : ∀ v : Fin n → Fin m → ℝ, (∀ i g, 0 < v i g) →
      ∃ σ : Fin m → Fin n, is_efx_goods v σ)
    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ 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 2
  • efx_exists_of_positive_perturbationsFor any finite real additive valuation profile, if adding every strictly positive common real epsilon to every item value admits a…
  • 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…

The proof, explained

To show that complete EFX allocations exist for any nonnegative additive valuation profile $u$, the proof reduces the problem via `efx_exists_of_positive_perturbations` to finding EFX allocations for positive perturbations $u + \varepsilon$ with $\varepsilon > 0$. Because each entry $u(i, g) \ge 0$, adding $\varepsilon > 0$ yields a strictly positive valuation profile. The hypothesis that EFX allocations exist for all strictly positive profiles then immediately supplies the required allocation for each perturbation.

  1. To find an EFX allocation for the profile $u$, it suffices to find one for every perturbed profile $(i, g) \mapsto u(i, g) + \varepsilon$ with $\varepsilon > 0$.

    By `efx_exists_of_positive_perturbations`, an EFX allocation for a nonnegative valuation profile $u$ exists whenever an EFX allocation exists for every uniformly perturbed profile $u + \varepsilon$ where $\varepsilon > 0$.

    line 8

    uses efx_exists_of_positive_perturbations

      apply efx_exists_of_positive_perturbations u
  2. For any $\varepsilon > 0$, the perturbed profile $(i, g) \mapsto u(i, g) + \varepsilon$ admits an EFX allocation.

    Fix $\varepsilon > 0$. Since each valuation $u(i, g)$ is nonnegative by assumption and $\varepsilon$ is strictly positive, each perturbed value $u(i, g) + \varepsilon$ is strictly positive by `add_pos_of_nonneg_of_pos`. Therefore, applying the hypothesis $h$ to this strictly positive profile directly yields an EFX allocation.

    lines 9–10

    uses add_pos_of_nonneg_of_pos

      intro ε hε
      exact h (fun i g => u i g + ε) (fun i g => add_pos_of_nonneg_of_pos (hu i g) hε)
efx_exists_of_positive_perturbations
if an EFX allocation exists for every uniform positive perturbation $(i, g) \mapsto u(i, g) + \varepsilon$ ($\varepsilon > 0$), then an EFX allocation exists for $u$
add_pos_of_nonneg_of_pos
the sum of a nonnegative number and a strictly positive number is strictly positive ($0 \le a \to 0 < b \to 0 < a + b$)

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_strictly_positive_profiles (m n : ℕ)    (h : ∀ v : Fin n → Fin m → ℝ, (∀ i g, 0 < v i g) →      ∃ σ : Fin m → Fin n, is_efx_goods v σ)    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) :    ∃ σ : Fin m → Fin n, is_efx_goods u σ := by  apply efx_exists_of_positive_perturbations u  intro ε hε  exact h (fun i g => u i g + ε) (fun i g => add_pos_of_nonneg_of_pos (hu i g) hε)
See it in the graphDiscuss this resultChallenge it