additive_valuation_bundle_sum_ite
An additive value of an allocated bundle equals the sum over all goods of the item value when that good has the specified owner, and zero otherwise.
Statement
theorem additive_valuation_bundle_sum_ite {m n : ℕ} (u : Fin m → ℝ) (σ : Fin m → Fin n) (i : Fin n) : additive_valuation u (bundle_of σ i) = ∑ g, if σ g = i then u g 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 4
- efx_three_bonus_distinct_no_realFor the explicit positive four-agent seven-good instance, if an EFX allocation assigns its four old goods to distinct agents and its three…
- is_efx_goods_equiv_goodsRelabeling a finite set of goods through a bijection, both in the valuation profile and allocation, preserves and reflects EFX.
- chore_prop_share_le_maximin_shareFor any number of agents n >= 1, items m, and additive chore cost function u, the proportional share (sum of costs divided by n) is at…
- efx_three_small_goods_obstruction_no_current_irIn the explicit eleven-good instance cast to real values, every EFX coarse completion has some agent whose utility is strictly less than…
The proof, explained
By definition, agent i's bundle consists of all goods mapped to i by the allocation σ, and the additive valuation of this bundle is the sum of the utilities u(g) over those goods. The result follows by unfolding these two definitions and applying Finset.sum_filter to express the sum over the filtered set of goods as a sum over all goods with an indicator conditional.
The additive valuation of the bundle assigned to agent i equals the sum over all goods g of u(g) when σ(g) = i, and 0 otherwise.
Unfolding the definition of additive_valuation expresses the valuation of bundle_of σ i as the sum ∑ g ∈ bundle_of σ i, u g. Unfolding bundle_of σ i shows that this bundle is defined by filtering the universe of all goods for those satisfying σ g = i. Finally, Finset.sum_filter transforms this sum over the filtered set into the sum over all goods g of the conditional expression if σ g = i then u g else 0.
uses
Finset.sum_filtersimp [additive_valuation, bundle_of, Finset.sum_filter]
Finset.sum_filter- The sum of a function f over the sub-finset of elements in s satisfying predicate p is equal to the sum over all elements of s of the conditional (if p a then f a else 0).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Function Finsettheorem additive_valuation_bundle_sum_ite {m n : ℕ} (u : Fin m → ℝ) (σ : Fin m → Fin n) (i : Fin n) : additive_valuation u (bundle_of σ i) = ∑ g, if σ g = i then u g else 0 := by simp [additive_valuation, bundle_of, Finset.sum_filter]