AFTD Auto-Formalizing Theoretical Domains

is_efx_goods_scale

theoremverified

Multiplying each agent's additive valuation vector by a positive constant c_i > 0 preserves and reflects whether an allocation is EFX.

Statement

theorem is_efx_goods_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)
    (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) :
    is_efx_goods (fun i g => c i * u i g) σ ↔ is_efx_goods u σ
Source
step towards scaled_common_ratio_bivalued_efx_fpo_envyfreeable
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • 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.

The proof, explained

The proof shows that the EFX property of an allocation is invariant under scaling each agent's valuation vector by a strictly positive factor c_i > 0. It first establishes an auxiliary lemma showing that an additive valuation scales linearly by factoring c_i out of the sum over any bundle. It then proves both directions of the equivalence by applying this scaling identity to the envy-freeness comparisons and canceling or introducing the factor c_i via the strict monotonicity of positive multiplication.

  1. For every agent i and bundle S, the scaled additive valuation satisfies v'_i(S) = c_i * v_i(S).

    By definition, the additive valuation of a bundle S is the sum of the item valuations over S. Factoring the scalar c_i out of the sum using distributivity (`Finset.mul_sum`) shows that scaling each item's value by c_i scales the total bundle value by c_i.

    lines 5–7

    uses Finset.mul_sum

      have h : ∀ (i : Fin n) (S : Finset (Fin m)), additive_valuation (fun g => c i * u i g) S = c i * additive_valuation (u i) S := by
        intro i S
        simp [additive_valuation, Finset.mul_sum]
  2. The equivalence reduces to checking both directions of the definition of an EFX allocation.

    Unfolding `is_efx_goods`, an allocation σ is EFX if for every pair of distinct agents i ≠ j and any good g in j's bundle, agent i values their own bundle at least as much as j's bundle with g removed. The `constructor` tactic splits the if-and-only-if into the forward and backward implications.

    lines 8–9

      unfold is_efx_goods
      constructor
  3. If the allocation is EFX under the scaled valuations, then it is EFX under the original valuations.

    Assume the scaled valuation profile is EFX. For any distinct agents i ≠ j and item g in j's bundle, the hypothesis gives that i's scaled value for j's bundle without g is at most i's scaled value for their own bundle. Rewriting both values using the scaling lemma yields c_i * v_i(A_j \ {g}) ≤ c_i * v_i(A_i). Because c_i > 0, canceling c_i via `mul_le_mul_iff_of_pos_left` yields the unscaled EFX inequality.

    lines 10–13

    uses mul_le_mul_iff_of_pos_left

      · intro H i j hij g hg
        have h1 := H i j hij g hg
        rw [h, h] at h1
        exact (mul_le_mul_iff_of_pos_left (hc i)).mp h1
  4. If the allocation is EFX under the original valuations, then it is EFX under the scaled valuations.

    Assume the allocation is EFX under the original valuations. For any distinct agents i ≠ j and item g in j's bundle, we have v_i(A_j \ {g}) ≤ v_i(A_i). Rewriting the goal using the scaling lemma expresses both sides as c_i times the unscaled bundle valuations. Since c_i > 0, multiplying the known inequality by c_i via `mul_le_mul_iff_of_pos_left` proves the scaled EFX inequality.

    lines 14–17

    uses mul_le_mul_iff_of_pos_left

      · intro H i j hij g hg
        have h1 := H i j hij g hg
        rw [h, h]
        exact (mul_le_mul_iff_of_pos_left (hc i)).mpr h1
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
mul_le_mul_iff_of_pos_left
For a strictly positive factor a > 0, multiplication on the left preserves and reflects inequalities: a * b ≤ a * c ↔ b ≤ c.

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

/-- The EFX property of an allocation is invariant under multiplying each agent's valuation vector by a positive constant. -/theorem is_efx_goods_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)    (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) :    is_efx_goods (fun i g => c i * u i g) σ ↔ is_efx_goods u σ := by  have h : ∀ (i : Fin n) (S : Finset (Fin m)), additive_valuation (fun g => c i * u i g) S = c i * additive_valuation (u i) S := by    intro i S    simp [additive_valuation, Finset.mul_sum]  unfold is_efx_goods  constructor  · intro H i j hij g hg    have h1 := H i j hij g hg    rw [h, h] at h1    exact (mul_le_mul_iff_of_pos_left (hc i)).mp h1  · intro H i j hij g hg    have h1 := H i j hij g hg    rw [h, h]    exact (mul_le_mul_iff_of_pos_left (hc i)).mpr h1
See it in the graphDiscuss this resultChallenge it