AFTD Auto-Formalizing Theoretical Domains

exists_minimally_envied_source_extension

theoremverified

For nonnegative additive values and any family of finite bundles A, suppose A(s) is unenvied by every agent relative to her own A(i), and a good g outside A(s) has strictly positive value for s. Then A(s) union {g} contains a subset T containing g which some agent j strictly prefers to A(j), and deleting any good of T leaves value at most the own A(i) for every agent i.

Statement

theorem exists_minimally_envied_source_extension {m n : ℕ}
    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)
    (A : Fin n → Finset (Fin m)) (s : Fin n) (g : Fin m)
    (hg : g ∉ A s) (hpos : 0 < u s g)
    (hs : ∀ i, additive_valuation (u i) (A s) ≤ additive_valuation (u i) (A i)) :
    ∃ (j : Fin n) (T : Finset (Fin m)), T ⊆ insert g (A s) ∧ g ∈ T ∧
      additive_valuation (u j) (A j) < additive_valuation (u j) T ∧
      ∀ i, ∀ h ∈ T, additive_valuation (u i) (T.erase h) ≤
        additive_valuation (u i) (A 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 3
  • exists_minimally_envied_subsetGiven a real additive valuation profile, a real utility threshold for each agent, and a finite bundle envied by some agent relative to…
  • envied_subset_contains_added_goodFor nonnegative additive item values, if every agent values a bundle S at most her threshold, any subset of S union a singleton g that…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.

The proof, explained

Adding good g to bundle A(s) strictly increases agent s's valuation beyond their own bundle A(s) because g ∉ A(s) and u(s, g) > 0. Applying exists_minimally_envied_subset extracts a subbundle T ⊆ A(s) ∪ {g} envied by some agent j such that deleting any good from T eliminates envy for all agents. Finally, because A(s) was unenvied and valuations are nonnegative, envied_subset_contains_added_good guarantees that the envied subbundle T must contain g.

  1. The extended bundle A(s) ∪ {g} is strictly envied by agent s relative to their own bundle A(s).

    Working classically, we show that agent s serves as a witness to envy for the bundle A(s) ∪ {g}. By definition of additive valuation and because g ∉ A(s), the lemma Finset.sum_insert rewrites the valuation of A(s) ∪ {g} as u(s, g) + ∑_{x ∈ A(s)} u(s, x). Because u(s, g) > 0, linear arithmetic confirms that this sum strictly exceeds the valuation of A(s).

    lines 12–17

    uses Finset.sum_insert

      classical
      have hex : ∃ i, additive_valuation (u i) (A i) <
          additive_valuation (u i) (insert g (A s)) := by
        refine ⟨s, ?_⟩
        simp only [additive_valuation, Finset.sum_insert hg]
        linarith
  2. There exists a subbundle T ⊆ A(s) ∪ {g} that is strictly envied by some agent, but from which removing any good leaves it unenvied by all agents.

    Applying exists_minimally_envied_subset to the extended bundle A(s) ∪ {g} with thresholds given by each agent's valuation of their own bundle A(i) produces a subset T ⊆ A(s) ∪ {g} strictly envied by some agent, such that removing any item h ∈ T reduces the valuation to at most A(i)'s value for every agent i.

    lines 18–19

    uses exists_minimally_envied_subset

      obtain ⟨T, hT, henv, htrim⟩ := exists_minimally_envied_subset u
        (fun i => additive_valuation (u i) (A i)) (insert g (A s)) hex
  3. The minimally envied subbundle T contains the newly added good g.

    By assumption, the original bundle A(s) is unenvied by all agents. Since valuations are nonnegative, any subset of A(s) is also unenvied. Because T ⊆ A(s) ∪ {g} is strictly envied, envied_subset_contains_added_good guarantees that T cannot be contained entirely in A(s), so g ∈ T.

    lines 20–21

    uses envied_subset_contains_added_good

      have hgT := envied_subset_contains_added_good u hu
        (fun i => additive_valuation (u i) (A i)) (A s) T g hT hs henv
  4. The agent j and subbundle T satisfy all required conditions.

    Unpacking the existential envy condition gives an agent j who strictly prefers T to A(j). Combining this with T ⊆ A(s) ∪ {g}, g ∈ T, and the condition that single-good deletions eliminate envy across all agents yields the full existential conclusion.

    lines 22–23

      obtain ⟨j, hj⟩ := henv
      exact ⟨j, T, hT, hgT, hj, htrim⟩
Finset.sum_insert
For a finite set s and an element a ∉ s, the sum of a function over s ∪ {a} equals the value at a plus the sum over s.
exists_minimally_envied_subset
If a bundle has valuation strictly exceeding given thresholds for some agent, it contains a subbundle that strictly exceeds the threshold for some agent, yet removing any single item reduces its valuation to at most the threshold for all agents.
envied_subset_contains_added_good
Under nonnegative valuations, if a bundle S does not exceed thresholds for any agent, any subbundle of S ∪ {g} that exceeds some agent's threshold must contain g.

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_source_extension {m n : ℕ}    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)    (A : Fin n → Finset (Fin m)) (s : Fin n) (g : Fin m)    (hg : g ∉ A s) (hpos : 0 < u s g)    (hs : ∀ i, additive_valuation (u i) (A s) ≤ additive_valuation (u i) (A i)) :    ∃ (j : Fin n) (T : Finset (Fin m)), T ⊆ insert g (A s) ∧ g ∈ T ∧      additive_valuation (u j) (A j) < additive_valuation (u j) T ∧      ∀ i, ∀ h ∈ T, additive_valuation (u i) (T.erase h) ≤        additive_valuation (u i) (A i) := by  classical  have hex : ∃ i, additive_valuation (u i) (A i) <      additive_valuation (u i) (insert g (A s)) := by    refine ⟨s, ?_⟩    simp only [additive_valuation, Finset.sum_insert hg]    linarith  obtain ⟨T, hT, henv, htrim⟩ := exists_minimally_envied_subset u    (fun i => additive_valuation (u i) (A i)) (insert g (A s)) hex  have hgT := envied_subset_contains_added_good u hu    (fun i => additive_valuation (u i) (A i)) (A s) T g hT hs henv  obtain ⟨j, hj⟩ := henv  exact ⟨j, T, hT, hgT, hj, htrim⟩
See it in the graphDiscuss this resultChallenge it