is_efx_goods_equiv_goods
Relabeling a finite set of goods through a bijection, both in the valuation profile and allocation, preserves and reflects EFX.
Statement
theorem is_efx_goods_equiv_goods {m k n : ℕ} (e : Fin m ≃ Fin k) (u : Fin n → Fin k → ℝ) (σ : Fin k → Fin n) : is_efx_goods (fun i g => u i (e g)) (fun g => σ (e g)) ↔ is_efx_goods u σ
- 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 5
- additive_valuation_bundle_sum_iteAn additive value of an allocated bundle equals the sum over all goods of the item value when that good has the specified owner, and zero…
- is_efx_goods_iff_bundle_totalsFor real additive valuations, EFX is equivalent to the following total-value inequalities: for every pair of distinct agents i,j and each…
- 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
- efx_exists_of_common_pair_order_evenFor any positive number of agents and an even number 2k of goods with nonnegative additive values, suppose every agent weakly prefers…
The proof, explained
The equivalence is proved by first establishing that relabeling goods via a bijection preserves every agent's total valuation for any bundle, which follows by reindexing the sum. Using a characterization where EFX is expressed as an inequality on bundle totals, the goal splits into two implications. In each direction, instantiating the assumed EFX property with the corresponding good (under the bijection or its inverse) and substituting the invariant bundle values completes the step.
For every pair of agents i and j, the additive valuation of agent i for bundle j is unchanged under the goods relabeling: v_i'(A_j') = v_i(A_j).
Rewriting each bundle valuation with `additive_valuation_bundle_sum_ite` expresses it as the sum over all goods of an indicator taking value u_i(g) when the good is assigned to j and 0 otherwise. The two sums then differ only by precomposition with the bijection e, so they are equal by `e.sum_comp`.
uses
additive_valuation_bundle_sum_ite,e.sum_comphave hval (i j : Fin n) : additive_valuation (fun g => u i (e g)) (bundle_of (fun g => σ (e g)) j) = additive_valuation (u i) (bundle_of σ j) := by rw [additive_valuation_bundle_sum_ite, additive_valuation_bundle_sum_ite] exact e.sum_comp (fun g => if σ g = j then u i g else 0)
The equivalence between the relabeled and original EFX conditions reduces to checking both directions under the bundle-totals characterization.
Applying `is_efx_goods_iff_bundle_totals` on both sides reformulates EFX from bundle-erasure inequalities into inequalities comparing total bundle values. The if-and-only-if goal is then split into two implications.
uses
is_efx_goods_iff_bundle_totalsrw [is_efx_goods_iff_bundle_totals, is_efx_goods_iff_bundle_totals] constructor
If the relabeled allocation is EFX, then the original allocation is EFX.
Assume the relabeled allocation is EFX. To check the EFX inequality for the original allocation given agents i ≠ j and a good g assigned to j, instantiate the assumption with i, j, and the pre-image good e⁻¹(g). Using the bundle valuation invariance `hval` and simplifying e(e⁻¹(g)) = g via `e.apply_symm_apply`, the inequality becomes v_i(A_j) ≤ v_i(A_i) + u_i(g), as required.
uses
e.apply_symm_apply· intro h i j hij g hg have hh := h i j hij (e.symm g) (by simpa using hg) simpa only [hval, e.apply_symm_apply] using hh
If the original allocation is EFX, then the relabeled allocation is EFX.
Assume the original allocation is EFX. For agents i ≠ j and a good g in the relabeled problem assigned to j (so σ(e(g)) = j), evaluate the assumption at i, j, and the good e(g). Substituting the relabeled bundle valuations for the original ones via `hval` yields the EFX inequality for the relabeled instance.
· intro h i j hij g hg simpa only [hval] using h i j hij (e g) hg
additive_valuation_bundle_sum_ite- The additive valuation of bundle σ⁻¹(i) equals the sum over all goods g of u(g) when σ(g) = i, and 0 otherwise.
e.sum_comp- Summing a function over a finite domain is invariant under precomposing with an equivalence (bijection) e.
is_efx_goods_iff_bundle_totals- An allocation is EFX if and only if for all distinct agents i ≠ j and each good g allocated to j, the valuation of bundle j is at most the valuation of bundle i plus the valuation of g.
e.apply_symm_apply- Applying an equivalence to the image of its inverse is the identity: e(e⁻¹(x)) = x.
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_equiv_goods {m k n : ℕ} (e : Fin m ≃ Fin k) (u : Fin n → Fin k → ℝ) (σ : Fin k → Fin n) : is_efx_goods (fun i g => u i (e g)) (fun g => σ (e g)) ↔ is_efx_goods u σ := by have hval (i j : Fin n) : additive_valuation (fun g => u i (e g)) (bundle_of (fun g => σ (e g)) j) = additive_valuation (u i) (bundle_of σ j) := by rw [additive_valuation_bundle_sum_ite, additive_valuation_bundle_sum_ite] exact e.sum_comp (fun g => if σ g = j then u i g else 0) rw [is_efx_goods_iff_bundle_totals, is_efx_goods_iff_bundle_totals] constructor · intro h i j hij g hg have hh := h i j hij (e.symm g) (by simpa using hg) simpa only [hval, e.apply_symm_apply] using hh · intro h i j hij g hg simpa only [hval] using h i j hij (e g) hg