is_efx_goods_nat_cast_iff
For natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each foreign total to the own total plus the value of any removed foreign good.
Statement
theorem is_efx_goods_nat_cast_iff {m n : ℕ} (v : Fin n → Fin m → ℕ) (σ : Fin m → Fin n) : is_efx_goods (fun i g => (v i g : ℝ)) σ ↔ ∀ i j : Fin n, i ≠ j → ∀ g ∈ bundle_of σ j, (∑ h ∈ bundle_of σ j, v i h) ≤ (∑ h ∈ bundle_of σ i, v i h) + v i g
- 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 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 22
- efx_intact_obstruction_no_coarseNo assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to…
- efx_allsource_three_pair_perturbed_strict_sanityThe perturbed partial state is strictly envy-free, and the explicit complete allocation remains EFX.
- efx_allsource_pair_sanityThe old state is envy-free with all values positive and charity small for each owner; the explicit complete witness is EFX and IR.
- efx_three_bonus_distinct_sanityEvery value in the explicit matrix is positive and each bonus is no larger than every old good for each agent. The old allocation…
- efx_three_bonus_distinct_no_realFor the explicit positive four-agent seven-good instance, if an EFX allocation assigns its four old goods to distinct agents and its three…
- efx_no_self_three_split_full_efxA complete EFX allocation of the matrix has owners (2,1,2,1,3,2,3,1,0,0,0,0,0).
- efx_three_split_sanityAll values are positive. In the initial partial allocation (0,0,1,1,2,2,3,3), each agent values all four old bundles equally, values the…
- efx_anchor_lock_full_efxThe nondegenerate instance has a complete EFX allocation with owners (3,1,1,1,2,2,1,2,1,0,3,0).
- efx_min_cycle_full_efxThe instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1) that strictly improves all four original utilities; it…
- efx_anchor_two_locks_preserve_threeIn the two-lock anchor family, a complete EFX allocation can preserve the original three agents’ starting utilities for every positive…
- efx_no_self_three_split_sanityThe matrix is positive; each agent values every old triple equally at her baseline, values every good in her own triple at least as much…
- efx_pareto_lock_sanityAll values are positive. The partial allocation (1,0,0,0,1,2,4,3), where 4 means unallocated, is EFX and meets the baseline utilities; the…
- efx_no_self_three_split_perturbed_fullThe nondegenerate perturbation admits a complete EFX allocation with owners (2,1,2,1,3,2,3,1,0,0,0,0,0).
- efx_three_small_goods_obstruction_sanityIn the explicit eleven-good instance all natural item values are strictly positive, and each of goods 8,9,10 is no more valuable than…
- efx_source_two_full_efxThe explicit complete EFX allocation preserves the other three initial utilities.
- efx_allsource_three_pair_sanityThe partial allocation is envy-free; all values are positive and charity is owner-small; the explicit full EFX allocation preserves all…
- efx_nondeg_cycle_full_efxThe nondegenerate instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1).
- efx_intact_obstruction_partial_efxIn the explicit seven-good instance restricted to the first six goods, assigning {5} to agent 0, {0,1} to agent 1, {2,3} to agent 2, and…
- efx_three_pair_anchor_sanityThe starting allocation is envy-free with r+2 goods per bundle and one charity good; the lifted complete witness is EFX.
- efx_pair_binary_full_efxFor the explicit binary nine-good valuation matrix cast to real values, the full allocation (3,3,1,2,0,2,1,1,0), listing the owner of each…
- efx_pair_binary_no_one_splitFor the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is EFX.
- efx_three_small_goods_obstruction_no_current_irIn the explicit eleven-good instance cast to real values, every EFX coarse completion has some agent whose utility is strictly less than…
The proof, explained
The equivalence is proved by unfolding the definition of an EFX goods allocation for additive valuations and splitting into both directions of the bi-implication. For any two distinct agents and any good in the other agent's bundle, the valuation of the bundle without that good is the total bundle valuation minus the good's value. Rearranging the subtraction across the inequality matches the real-valued EFX condition with the natural-number sum condition, and casting between ℕ and ℝ completes both directions.
The bi-implication reduces to proving the forward and backward directions separately.
Applying the `constructor` tactic splits the if-and-only-if goal into two implications: that EFX over the reals implies the natural-number inequality, and that the natural-number inequality implies EFX over the reals.
constructorIf the allocation is EFX with values cast to the reals, then for all distinct agents i ≠ j and every item g in j's bundle, the sum of values of j's bundle for agent i is at most the sum of values of i's bundle plus the value of g, in the natural numbers.
Assume the allocation is EFX over the reals. For any distinct agents i, j and any item g in j's bundle, the EFX hypothesis states that i's valuation of j's bundle without g is at most i's valuation of their own bundle. By `additive_valuation_erase_of_mem`, the valuation of j's bundle without g equals the total valuation of j's bundle minus v(i, g). Rearranging this subtraction using `sub_le_iff_le_add.mp` bounds the total valuation of j's bundle by the valuation of i's bundle plus v(i, g). Unfolding `additive_valuation` into sums and casting from ℝ to ℕ via `exact_mod_cast` yields the inequality in ℕ.
uses
additive_valuation_erase_of_mem,sub_le_iff_le_add.mp· intro h i j hij g hg have hh := h i j hij g hg rw [additive_valuation_erase_of_mem _ _ _ hg] at hh have h' := sub_le_iff_le_add.mp hh dsimp [additive_valuation] at h' exact_mod_cast h'
Conversely, if the natural-number inequality holds for all distinct agents i ≠ j and items g in j's bundle, then the allocation is EFX with values cast to the reals.
Assume the natural-number inequality holds for all pairs of distinct agents and items. To prove EFX over the reals, fix distinct agents i, j and an item g in j's bundle. By `additive_valuation_erase_of_mem`, the value of j's bundle without g is rewritten as the total value of j's bundle minus v(i, g). Applying `sub_le_iff_le_add.mpr` reduces the goal to showing that the total value of j's bundle is at most the value of i's bundle plus v(i, g). Specializing the assumption to i, j, and g, unfolding the definition of `additive_valuation`, and casting the inequality from ℕ to ℝ via `exact_mod_cast` finishes the proof.
uses
additive_valuation_erase_of_mem,sub_le_iff_le_add.mpr· intro h i j hij g hg rw [additive_valuation_erase_of_mem _ _ _ hg] apply sub_le_iff_le_add.mpr have hh := h i j hij g hg dsimp [additive_valuation] exact_mod_cast hh
additive_valuation_erase_of_mem- For an additive valuation, the value of a bundle with an element removed equals the total value of the bundle minus the value of that element.
sub_le_iff_le_add.mp- Subtracting a quantity is at most a bound implies that the original quantity is at most the bound plus that quantity: a - c ≤ b → a ≤ b + c.
sub_le_iff_le_add.mpr- A quantity is at most a bound plus an added term implies that subtracting the term is at most the bound: a ≤ b + c → 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
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_nat_cast_iff {m n : ℕ} (v : Fin n → Fin m → ℕ) (σ : Fin m → Fin n) : is_efx_goods (fun i g => (v i g : ℝ)) σ ↔ ∀ i j : Fin n, i ≠ j → ∀ g ∈ bundle_of σ j, (∑ h ∈ bundle_of σ j, v i h) ≤ (∑ h ∈ bundle_of σ i, v i h) + v i g := by constructor · intro h i j hij g hg have hh := h i j hij g hg rw [additive_valuation_erase_of_mem _ _ _ hg] at hh have h' := sub_le_iff_le_add.mp hh dsimp [additive_valuation] at h' exact_mod_cast h' · intro h i j hij g hg rw [additive_valuation_erase_of_mem _ _ _ hg] apply sub_le_iff_le_add.mpr have hh := h i j hij g hg dsimp [additive_valuation] exact_mod_cast hh