AFTD Auto-Formalizing Theoretical Domains

envied_subset_contains_added_good

theoremverified

For nonnegative additive item values, if every agent values a bundle S at most her threshold, any subset of S union a singleton g that some agent values strictly above her threshold must contain g.

Statement

theorem envied_subset_contains_added_good {m n : ℕ}
    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)
    (b : Fin n → ℝ) (S T : Finset (Fin m)) (g : Fin m)
    (hT : T ⊆ insert g S) (hS : ∀ i, additive_valuation (u i) S ≤ b i)
    (henv : ∃ j, b j < additive_valuation (u j) T) : g ∈ T
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

We argue by contradiction, assuming that the added item g is not in T. Because T ⊆ {g} ∪ S and g ∉ T, every element of T belongs to S, so T ⊆ S. Since all item valuations are nonnegative, each agent's additive valuation of T is at most their valuation of S. This contradicts the assumption that some agent values T strictly above their threshold while valuing S at or below it.

  1. Assume for contradiction that g ∉ T.

    We set up a proof by contradiction, assuming that the added item g is not in T (labeled hg).

    lines 8–9

      classical
      by_contra hg
  2. T is a subset of S (T ⊆ S).

    Let x ∈ T. Since T ⊆ insert g S, Finset.mem_insert.mp implies that either x = g or x ∈ S. If x = g, then g ∈ T, directly contradicting the assumption hg (g ∉ T). Thus x must be in S, which establishes T ⊆ S.

    lines 10–14

    uses Finset.mem_insert.mp

      have hsub : T ⊆ S := by
        intro x hx
        rcases Finset.mem_insert.mp (hT hx) with h | h
        · exact (hg (h ▸ hx)).elim
        · exact h
  3. For an agent j who envies bundle T, their valuation of T is at most their valuation of S.

    From the hypothesis that some agent values T strictly above their threshold, let j be such an agent (so b(j) < additive_valuation(u j) T). Because T ⊆ S and all item values are nonnegative (hu), the sum of values over T is bounded above by the sum over S via Finset.sum_le_sum_of_subset_of_nonneg.

    lines 15–17

    uses Finset.sum_le_sum_of_subset_of_nonneg

      obtain ⟨j, hj⟩ := henv
      have hle : additive_valuation (u j) T ≤ additive_valuation (u j) S :=
        Finset.sum_le_sum_of_subset_of_nonneg hsub (fun x _ _ => hu j x)
  4. A contradiction is reached, completing the proof that g ∈ T.

    Chaining the inequality additive_valuation(u j) T ≤ additive_valuation(u j) S with the threshold bound additive_valuation(u j) S ≤ b(j) (from hS) shows that additive_valuation(u j) T ≤ b(j). By not_lt_of_ge, this directly contradicts b(j) < additive_valuation(u j) T.

    line 18

    uses not_lt_of_ge

      exact (not_lt_of_ge (hle.trans (hS j))) hj
Finset.mem_insert.mp
If an element belongs to the insertion of an item into a finite set, then it is either equal to that item or belongs to the set.
Finset.sum_le_sum_of_subset_of_nonneg
If one finite set is a subset of another and the terms are nonnegative on the elements outside the subset, the sum over the subset is at most the sum over the superset.
not_lt_of_ge
If a ≤ b, then it is false that b < a.

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 envied_subset_contains_added_good {m n : ℕ}    (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)    (b : Fin n → ℝ) (S T : Finset (Fin m)) (g : Fin m)    (hT : T ⊆ insert g S) (hS : ∀ i, additive_valuation (u i) S ≤ b i)    (henv : ∃ j, b j < additive_valuation (u j) T) : g ∈ T := by  classical  by_contra hg  have hsub : T ⊆ S := by    intro x hx    rcases Finset.mem_insert.mp (hT hx) with h | h    · exact (hg (h ▸ hx)).elim    · exact h  obtain ⟨j, hj⟩ := henv  have hle : additive_valuation (u j) T ≤ additive_valuation (u j) S :=    Finset.sum_le_sum_of_subset_of_nonneg hsub (fun x _ _ => hu j x)  exact (not_lt_of_ge (hle.trans (hS j))) hj
See it in the graphDiscuss this resultChallenge it