AFTD Auto-Formalizing Theoretical Domains

is_efx_goods_all_pairs

theoremverified

For nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.

Statement

theorem is_efx_goods_all_pairs {m n : ℕ} (u : Fin n → Fin m → ℝ)
    (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) :
    ∀ i j : Fin n, ∀ g ∈ bundle_of σ j,
      additive_valuation (u i) ((bundle_of σ j).erase g) ≤
        additive_valuation (u i) (bundle_of σ i)
Source
Helper for efx_four_agents_additive_exists (OP-7), campaign session 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…
  • 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.
Used by 2

The proof, explained

The definition of an EFX allocation for goods (is_efx_goods) stipulates that for every pair of distinct agents i ≠ j, removing any good from agent j's bundle leaves it worth no more to agent i than i's own bundle. To show that this inequality also holds when i = j, the proof divides into cases. If i ≠ j, the claim is immediate from the definition of EFX. If i = j, removing a good leaves a subset of i's bundle; because all utilities are non-negative, the sum of utilities over a sub-bundle cannot exceed the sum over the entire bundle.

  1. Let i, j be agents and g a good in j's bundle; the goal reduces to the cases i = j and i ≠ j.

    We introduce arbitrary agents i, j and an item g in agent j's bundle (bundle_of σ j). We then divide into two cases depending on whether the observer i and target j are identical (i = j) or distinct (i ≠ j).

    lines 8–9

      intro i j g hg
      by_cases hij : i = j
  2. When i = j, the valuation of the bundle with g removed is at most the valuation of the full bundle.

    When i = j, substituting j with i reduces the claim to showing that the additive valuation of agent i's bundle with g removed is at most the additive valuation of agent i's full bundle. By definition, additive valuation is the sum of utilities over a bundle. Removing g leaves a subset of the bundle (by Finset.erase_subset), and since all utilities are non-negative (by assumption hu), summing over the subset yields at most the sum over the full bundle (by Finset.sum_le_sum_of_subset_of_nonneg).

    lines 10–13

    uses Finset.sum_le_sum_of_subset_of_nonneg, Finset.erase_subset

      · subst j
        change (∑ x ∈ (bundle_of σ i).erase g, u i x) ≤ ∑ x ∈ bundle_of σ i, u i x
        exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.erase_subset g _)
          (fun x _ _ => hu i x)
  3. When i ≠ j, the inequality holds directly by the definition of an EFX allocation for goods.

    The hypothesis hσ asserts that the allocation is EFX for goods, meaning that for all distinct agents i ≠ j and any good g in j's bundle, agent i values j's bundle without g at most as much as i values their own bundle. Applying hσ to i, j, the inequality i ≠ j (hij), and g ∈ bundle_of σ j (hg) immediately concludes the proof.

    line 14

      · exact hσ i j hij g hg
Finset.sum_le_sum_of_subset_of_nonneg
If a finite set s is a subset of t and f is non-negative on all elements of t outside of s, then the sum of f over s is at most the sum of f over t.
Finset.erase_subset
Removing an element from a finite set yields a subset of the original set.

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 is_efx_goods_all_pairs {m n : ℕ} (u : Fin n → Fin m → ℝ)    (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) :    ∀ i j : Fin n, ∀ g ∈ bundle_of σ j,      additive_valuation (u i) ((bundle_of σ j).erase g) ≤        additive_valuation (u i) (bundle_of σ i) := by  intro i j g hg  by_cases hij : i = j  · subst j    change (∑ x ∈ (bundle_of σ i).erase g, u i x) ≤ ∑ x ∈ bundle_of σ i, u i x    exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.erase_subset g _)      (fun x _ _ => hu i x)  · exact hσ i j hij g hg
See it in the graphDiscuss this resultChallenge it