AFTD Auto-Formalizing Theoretical Domains

is_efx_goods_iff_bundle_totals

theoremverified

For real additive valuations, EFX is equivalent to the following total-value inequalities: for every pair of distinct agents i,j and each good g assigned to j, the total value of j's bundle to i is at most i's own total plus i's value of g.

Statement

theorem is_efx_goods_iff_bundle_totals {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) :
    is_efx_goods u σ ↔ ∀ i j : Fin n, i ≠ j → ∀ g : Fin m, σ g = j →
      additive_valuation (u i) (bundle_of σ j) ≤
        additive_valuation (u i) (bundle_of σ i) + u i g
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 4
  • additive_valuation_erase_of_memRemoving a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.
  • 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 1
  • is_efx_goods_equiv_goodsRelabeling a finite set of goods through a bijection, both in the valuation profile and allocation, preserves and reflects EFX.

The proof, explained

The equivalence between the EFX condition and the total-bundle value inequality relies directly on the additivity of valuations. Because valuations are additive, the value to an agent of another agent's bundle after removing a single good g is simply the bundle's total value minus the value of g. The EFX requirement that the bundle minus g is worth at most the agent's own bundle then translates to an inequality of the form A - C ≤ B, which rearranges algebraically to A ≤ B + C.

  1. An allocation satisfying EFX satisfies the bundle-total condition: for any distinct agents i ≠ j and any good g allocated to j, agent i's valuation of j's bundle is at most i's valuation of their own bundle plus i's valuation of g.

    We use constructor to split the if-and-only-if into two directions. For the forward direction, assume the allocation is EFX (h), fix distinct agents i, j (hij), and let g be a good assigned to j (hg). By definition of bundle_of, σ g = j means that g belongs to j's bundle (hmem). Instantiating the EFX hypothesis with g ∈ bundle_of σ j gives that agent i values j's bundle with g removed at most as much as i's own bundle (hh). By additivity of valuations, additive_valuation_erase_of_mem rewrites this punctured bundle valuation as the total valuation of j's bundle minus u i g. Finally, sub_le_iff_le_add.mp rearranges this inequality from A - C ≤ B to A ≤ B + C.

    lines 7–12

    uses additive_valuation_erase_of_mem, sub_le_iff_le_add.mp

      constructor
      · intro h i j hij g hg
        have hmem : g ∈ bundle_of σ j := by simpa [bundle_of] using hg
        have hh := h i j hij g hmem
        rw [additive_valuation_erase_of_mem _ _ _ hmem] at hh
        exact sub_le_iff_le_add.mp hh
  2. Conversely, if the bundle-total condition holds for all distinct agents i ≠ j and goods g allocated to j, then the allocation satisfies EFX.

    For the reverse direction, assume the bundle-total inequality holds for all distinct agents and assigned goods (h). To establish EFX, fix distinct agents i, j (hij) and a good g in j's bundle (hg). By definition of bundle_of, this means σ g = j (heq). Using additive_valuation_erase_of_mem rewrites the goal—that i values j's bundle without g at most i's own bundle—into the inequality additive_valuation (u i) (bundle_of σ j) - u i g ≤ additive_valuation (u i) (bundle_of σ i). Rearranging the assumed bound via sub_le_iff_le_add.mpr completes the proof.

    lines 13–16

    uses additive_valuation_erase_of_mem, sub_le_iff_le_add.mpr

      · intro h i j hij g hg
        have heq : σ g = j := by simpa [bundle_of] using hg
        rw [additive_valuation_erase_of_mem _ _ _ hg]
        exact sub_le_iff_le_add.mpr (h i j hij g heq)
additive_valuation_erase_of_mem
For an additive valuation u, finite set of goods S, and good g ∈ S, the valuation of S ∖ {g} equals the valuation of S minus u(g).
sub_le_iff_le_add.mp
If a - c ≤ b, then a ≤ b + c.
sub_le_iff_le_add.mpr
If a ≤ b + c, then a - c ≤ 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 is_efx_goods_iff_bundle_totals {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) :    is_efx_goods u σ ↔ ∀ i j : Fin n, i ≠ j → ∀ g : Fin m, σ g = j →      additive_valuation (u i) (bundle_of σ j) ≤        additive_valuation (u i) (bundle_of σ i) + u i g := by  constructor  · intro h i j hij g hg    have hmem : g ∈ bundle_of σ j := by simpa [bundle_of] using hg    have hh := h i j hij g hmem    rw [additive_valuation_erase_of_mem _ _ _ hmem] at hh    exact sub_le_iff_le_add.mp hh  · intro h i j hij g hg    have heq : σ g = j := by simpa [bundle_of] using hg    rw [additive_valuation_erase_of_mem _ _ _ hg]    exact sub_le_iff_le_add.mpr (h i j hij g heq)
See it in the graphDiscuss this resultChallenge it