AFTD Auto-Formalizing Theoretical Domains

efx_of_bundle_card_le_one

theoremverified

An allocation where each agent receives at most one good is unconditionally EFX for any nonnegative additive valuations.

Statement

theorem efx_of_bundle_card_le_one {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hinj : Function.Injective σ) : is_efx_goods u σ
Source
step towards efx_four_agents_additive_exists
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • 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 the allocation is EFX, consider any two distinct agents i ≠ j and any good g assigned to j. Because the allocation function σ is injective, at most one good is assigned to agent j, so removing g leaves j with an empty bundle. The additive valuation of an empty bundle is 0. Since agent i's valuation is additive and nonnegative for all goods, i's valuation for their own bundle is at least 0, satisfying the EFX requirement.

  1. Fix two distinct agents i and j, and a good g assigned to j.

    To prove the allocation is EFX (is_efx_goods), we introduce arbitrary distinct agents i ≠ j and an item g in agent j's bundle. It suffices to show that agent i values j's bundle after removing g at most as much as i values their own bundle.

    line 3

      intro i j hij g hg
  2. Removing good g from agent j's bundle leaves an empty bundle.

    By set extensionality, we show no item x can belong to (bundle_of σ j).erase g. Any such x would have to be distinct from g and satisfy σ x = j. However, since g is in j's bundle, σ g = j as well. By the injectivity of σ, σ x = σ g implies x = g, which contradicts x ≠ g. Hence the erased bundle is empty.

    lines 4–10

    uses Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty, iff_false

      have herase : (bundle_of σ j).erase g = ∅ := by
        ext x
        simp only [Finset.mem_erase, bundle_of, Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty, iff_false]
        rintro ⟨hne, hx⟩
        have hg_eq : σ g = j := by
          simpa [bundle_of] using hg
        exact hne (hinj (hx.trans hg_eq.symm))
  3. The EFX inequality holds.

    Substituting the empty set for the erased bundle, agent i's valuation for j's bundle without g becomes the sum over the empty set, which is 0. By assumption, agent i assigns a nonnegative utility to every good, so the sum over i's own bundle is at least 0. Thus the valuation of the reduced bundle is at most the valuation of i's bundle.

    lines 11–13

    uses Finset.sum_nonneg

      rw [herase]
      dsimp [additive_valuation]
      exact Finset.sum_nonneg (fun x _ => hu i x)
Finset.mem_erase
An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
true_and
The conjunction True ∧ p is equal to p.
Finset.notMem_empty
No element belongs to the empty finset.
iff_false
The equivalence (p ↔ False) simplifies to ¬p.
Finset.sum_nonneg
If each term in a finite sum is nonnegative, the sum is nonnegative.

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

/-- An allocation where each agent receives at most one good (e.g. an injective assignment of goods to agents) is unconditionally EFX for any nonnegative additive valuations. -/theorem efx_of_bundle_card_le_one {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hinj : Function.Injective σ) : is_efx_goods u σ := by  intro i j hij g hg  have herase : (bundle_of σ j).erase g = ∅ := by    ext x    simp only [Finset.mem_erase, bundle_of, Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty, iff_false]    rintro ⟨hne, hx⟩    have hg_eq : σ g = j := by      simpa [bundle_of] using hg    exact hne (hinj (hx.trans hg_eq.symm))  rw [herase]  dsimp [additive_valuation]  exact Finset.sum_nonneg (fun x _ => hu i x)
See it in the graphDiscuss this resultChallenge it