is_efx_goods_iff_bundle_totals
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.
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.
uses
additive_valuation_erase_of_mem,sub_le_iff_le_add.mpconstructor · 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
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.
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.
- The equivalence between bundle membership (g ∈ bundle_of σ j) and item assignment (σ g = j) follows immediately from the definition of bundle_of as a filtered set, which Lean resolves using simpa.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)