AFTD Auto-Formalizing Theoretical Domains

exists_minimally_envied_subset

theoremverified

Given a real additive valuation profile, a real utility threshold for each agent, and a finite bundle envied by some agent relative to those thresholds, there is a subset still strictly envied by some agent such that deleting any of its goods leaves value at most the threshold for every agent.

Statement

theorem exists_minimally_envied_subset {m n : ℕ} (u : Fin n → Fin m → ℝ)
    (b : Fin n → ℝ) (S : Finset (Fin m))
    (h : ∃ i, b i < additive_valuation (u i) S) :
    ∃ T ⊆ S, (∃ j, b j < additive_valuation (u j) T) ∧
      ∀ i, ∀ g ∈ T, additive_valuation (u i) (T.erase g) ≤ b i
Source
Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Standard minimal-envied-subset mechanism, arXiv:2002.05119v3 Observation 6 and Corollary 7; no novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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 theorem is proved by strong induction on the bundle S ordered by proper inclusion. If deleting any good from S drops every agent's valuation to at most their threshold, then S itself is the desired subset. Otherwise, some deletion S \ {g} remains strictly envied, and since it is a proper subset of S, the induction hypothesis provides a minimally envied subset T ⊆ S \ {g} ⊆ S.

  1. The problem reduces to proving the claim by strong induction on the bundle S ordered by proper inclusion.

    Working classically, we revert the hypothesis that S is envied so that the induction hypothesis applies to any envied sub-bundle. We then set up strong induction on S using Finset.strongInductionOn, assuming that the claim holds for every proper subset t ⊂ S that is strictly envied by some agent.

    lines 8–11

    uses Finset.strongInductionOn

      classical
      revert h
      refine Finset.strongInductionOn S ?_
      intro S ih h
  2. If deleting any single good from S leaves all agents at or below their thresholds, then S itself satisfies the theorem.

    We perform a case split on whether deleting any element g ∈ S ensures that every agent's valuation is at most their threshold b i. If this condition holds, we can choose T = S: S ⊆ S by Finset.Subset.refl, S is strictly envied by assumption, and every deletion of a single good stays within the thresholds.

    lines 12–13

    uses Finset.Subset.refl

      by_cases hmin : ∀ i, ∀ g ∈ S, additive_valuation (u i) (S.erase g) ≤ b i
      · exact ⟨S, Finset.Subset.refl _, h, hmin⟩
  3. If some single-good deletion is still strictly envied, the induction hypothesis on that strict subset provides the required subset T ⊆ S.

    Otherwise, negating the minimality condition yields an agent i and a good g ∈ S such that deleting g leaves a bundle S \ {g} strictly envied by agent i. Since g ∈ S, the deletion S \ {g} is a proper subset of S by Finset.erase_ssubset. Applying the induction hypothesis to S \ {g} produces a subset T ⊆ S \ {g} that is strictly envied and satisfies the single-deletion threshold bounds. Since S \ {g} ⊆ S by Finset.erase_subset, transitivity of inclusion guarantees T ⊆ S.

    lines 14–17

    uses Finset.erase_ssubset, Finset.erase_subset

      · push Not at hmin
        obtain ⟨i, g, hg, hgt⟩ := hmin
        obtain ⟨T, hT, henv, htrim⟩ := ih (S.erase g) (Finset.erase_ssubset hg) ⟨i, hgt⟩
        exact ⟨T, hT.trans (Finset.erase_subset g S), henv, htrim⟩
Finset.strongInductionOn
strong induction on finite sets: to show a property holds for a finite set s, it suffices to show it holds for any set assuming it holds for all its proper subsets
Finset.Subset.refl
every finite set is a subset of itself
Finset.erase_ssubset
removing an element from a finite set in which it belongs yields a proper subset
Finset.erase_subset
removing an element from a finite set yields a subset of the original set

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 exists_minimally_envied_subset {m n : ℕ} (u : Fin n → Fin m → ℝ)    (b : Fin n → ℝ) (S : Finset (Fin m))    (h : ∃ i, b i < additive_valuation (u i) S) :    ∃ T ⊆ S, (∃ j, b j < additive_valuation (u j) T) ∧      ∀ i, ∀ g ∈ T, additive_valuation (u i) (T.erase g) ≤ b i := by  classical  revert h  refine Finset.strongInductionOn S ?_  intro S ih h  by_cases hmin : ∀ i, ∀ g ∈ S, additive_valuation (u i) (S.erase g) ≤ b i  · exact ⟨S, Finset.Subset.refl _, h, hmin⟩  · push Not at hmin    obtain ⟨i, g, hg, hgt⟩ := hmin    obtain ⟨T, hT, henv, htrim⟩ := ih (S.erase g) (Finset.erase_ssubset hg) ⟨i, hgt⟩    exact ⟨T, hT.trans (Finset.erase_subset g S), henv, htrim⟩
See it in the graphDiscuss this resultChallenge it