AFTD Auto-Formalizing Theoretical Domains

is_alpha_ef1_goods_one_of_ef1_goods

theoremverified

If an allocation is exactly EF1 (in the is_ef1_goods sense) for nonnegative additive valuations, then it is 1-EF1 in the is_alpha_ef1_goods sense.

Statement

theorem is_alpha_ef1_goods_one_of_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (hpos : ∀ i g, 0 ≤ u i g) (h : is_ef1_goods u σ) : is_alpha_ef1_goods u 1 σ
Source
step towards op561_ratio_gt_sqrt5
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_ef1_goodsEF1 for goods: every agent i either does not envy agent j, or stops envying j after some single good is removed from j's bundle.
  • is_alpha_ef1_goodsAn allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • 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

To show that an EF1 allocation is 1-EF1 for nonnegative additive valuations, consider any distinct agents i and j where j holds a nonempty bundle. By EF1, either agent i already does not envy agent j, or there is a good in j's bundle whose removal eliminates envy. In the first case, any good in j's bundle witnesses 1-EF1 because removing an item with nonnegative value cannot increase the bundle's value. In the second case, the good guaranteed by EF1 directly serves as the witness because scaling by 1 is the identity.

  1. Fix two distinct agents i and j with j's bundle nonempty; by EF1, either i does not envy j, or some good in j's bundle eliminates envy.

    To establish the definition of 1-EF1 (is_alpha_ef1_goods), we introduce arbitrary agents i and j, assuming i ≠ j and that j's bundle is nonempty (hjne). Applying the EF1 hypothesis (h) to i and j yields two cases: either agent i does not envy agent j at all (u_i(bundle(j)) ≤ u_i(bundle(i))), or there exists a good g in j's bundle whose removal eliminates envy.

    lines 2–3

      intro i j _ hjne
      rcases h i j with hle | ⟨g, hg, hgle⟩
  2. When agent i does not envy agent j, any good g₀ in j's bundle witnesses 1-EF1.

    Since j's bundle is nonempty, we select an arbitrary good g₀ ∈ bundle(j) as the required witness (lines 4–5). Rewriting with one_mul simplifies 1 * u_i(...) to u_i(...) (line 6). To show u_i(bundle(j) \ {g₀}) ≤ u_i(bundle(i)), we establish the auxiliary inequality hsub: removing g₀ cannot increase the valuation (lines 7–13). By definition, the additive valuation is a sum over the bundle; because bundle(j) \ {g₀} ⊆ bundle(j) (by Finset.mem_of_mem_erase) and all valuations are nonnegative (hpos), Finset.sum_le_sum_of_subset_of_nonneg bounds the smaller sum by the original sum. Finally, linear arithmetic (linarith, line 14) combines hsub with the case hypothesis u_i(bundle(j)) ≤ u_i(bundle(i)) to close the goal by transitivity.

    lines 4–14

    uses one_mul, Finset.sum_le_sum_of_subset_of_nonneg, Finset.mem_of_mem_erase

      · obtain ⟨g0, hg0⟩ := hjne
        refine ⟨g0, hg0, ?_⟩
        rw [one_mul]
        have hsub : additive_valuation (u i) ((bundle_of σ j).erase g0) ≤ additive_valuation (u i) (bundle_of σ j) := by
          dsimp [additive_valuation]
          apply Finset.sum_le_sum_of_subset_of_nonneg
          · intro x hx
            exact Finset.mem_of_mem_erase hx
          · intro x _ _
            exact hpos i x
        linarith
  3. When removing a good g eliminates envy, that good g directly witnesses 1-EF1.

    In the second case, the EF1 hypothesis provides a specific good g ∈ bundle(j) whose removal eliminates envy. Using this g as the witness (line 15) and simplifying the multiplication by 1 via one_mul (line 16), the goal matches the EF1 hypothesis (hgle, line 17) directly.

    lines 15–17

    uses one_mul

      · refine ⟨g, hg, ?_⟩
        rw [one_mul]
        exact hgle
one_mul
Multiplying any element by 1 on the left leaves it unchanged: 1 * a = a.
Finset.sum_le_sum_of_subset_of_nonneg
If s ⊆ t are finite sets and f is nonnegative on t \ s, then the sum of f over s is at most the sum of f over t.
Finset.mem_of_mem_erase
If an element belongs to a finite set with an element removed (s.erase a), then it belongs to the original set s.

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

theorem is_alpha_ef1_goods_one_of_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (hpos : ∀ i g, 0 ≤ u i g) (h : is_ef1_goods u σ) : is_alpha_ef1_goods u 1 σ := by  intro i j _ hjne  rcases h i j with hle | ⟨g, hg, hgle⟩  · obtain ⟨g0, hg0⟩ := hjne    refine ⟨g0, hg0, ?_⟩    rw [one_mul]    have hsub : additive_valuation (u i) ((bundle_of σ j).erase g0) ≤ additive_valuation (u i) (bundle_of σ j) := by      dsimp [additive_valuation]      apply Finset.sum_le_sum_of_subset_of_nonneg      · intro x hx        exact Finset.mem_of_mem_erase hx      · intro x _ _        exact hpos i x    linarith  · refine ⟨g, hg, ?_⟩    rw [one_mul]    exact hgle
See it in the graphDiscuss this resultChallenge it