AFTD Auto-Formalizing Theoretical Domains

additive_valuation_bundle_last_cases

theoremverified

Assigning the additional last good to agent s adds exactly its value to the old bundle value of s and leaves every other bundle value unchanged.

Statement

theorem additive_valuation_bundle_last_cases {m n : ℕ} (u : Fin (m+1) → ℝ)
    (σ : Fin m → Fin n) (s j : Fin n) :
    additive_valuation u (bundle_of (Fin.lastCases s σ) j) =
      additive_valuation (fun g => u g.castSucc) (bundle_of σ j) +
        if s = j then u (Fin.last m) else 0
Source
Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 2

The proof, explained

To evaluate agent j's bundle under the extended assignment where the (m+1)-th good is given to agent s, the proof expands the bundle valuations into sums over all goods using indicator terms. It then splits the sum over the m + 1 goods into the sum over the first m goods and the term for the final good. Finally, simplifying the piecewise assignment on the earlier goods and the last good shows that the valuation equals the previous valuation plus the value of the last good if j = s, and 0 otherwise.

  1. The bundle valuations are rewritten from sums over filtered subsets into sums over all goods using indicator functions.

    Unfolding the definitions of `additive_valuation` and `bundle_of`, the valuation of agent j's bundle is the sum of utilities over goods allocated to j. Applying `Finset.sum_filter` turns each restricted sum into an unrestricted sum over the entire universe of goods, replacing the membership condition with an if-then-else indicator term.

    line 8

    uses Finset.sum_filter

      simp only [additive_valuation, bundle_of, Finset.sum_filter]
  2. The sum over the m + 1 goods on the left-hand side splits into a sum over the first m goods and a separate term for the last good.

    Rewriting with `Fin.sum_univ_castSucc` decomposes the summation over Fin (m + 1) into the sum over the first m goods (embedded via `Fin.castSucc`) plus the single term evaluated at the final good `Fin.last m`.

    line 9

    uses Fin.sum_univ_castSucc

      rw [Fin.sum_univ_castSucc]
  3. Both sides of the equation are identical, completing the proof.

    Simplification reduces the case analysis on goods: on the first m goods (`i.castSucc`), the extended assignment `Fin.lastCases s σ` evaluates to the old assignment `σ i`, while on the last good (`Fin.last m`), it evaluates to agent s. This makes the left-hand side identical to the right-hand side.

    line 10

      simp
Finset.sum_filter
The sum of a function over a filtered subset of a finite set equals the sum over the entire set with terms outside the subset replaced by zero.
Fin.sum_univ_castSucc
A sum of values indexed by Fin (n + 1) can be partitioned into the sum over the first n elements (via castSucc) plus the value at the last element (Fin.last n).

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 additive_valuation_bundle_last_cases {m n : ℕ} (u : Fin (m+1) → ℝ)    (σ : Fin m → Fin n) (s j : Fin n) :    additive_valuation u (bundle_of (Fin.lastCases s σ) j) =      additive_valuation (fun g => u g.castSucc) (bundle_of σ j) +        if s = j then u (Fin.last m) else 0 := by  simp only [additive_valuation, bundle_of, Finset.sum_filter]  rw [Fin.sum_univ_castSucc]  simp
See it in the graphDiscuss this resultChallenge it