AFTD Auto-Formalizing Theoretical Domains

is_efx_goods_equiv_goods

theoremverified

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

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.

  1. 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`.

    lines 6–10

    uses additive_valuation_bundle_sum_ite, e.sum_comp

      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)
  2. 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.

    lines 11–12

    uses is_efx_goods_iff_bundle_totals

      rw [is_efx_goods_iff_bundle_totals, is_efx_goods_iff_bundle_totals]
      constructor
  3. 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.

    lines 13–15

    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
  4. 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.

    lines 16–17

      · 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

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
See it in the graphDiscuss this resultChallenge it