mnw2_sum_groups
theoremverified
For allocations O, N of m goods to two agents, item values u and weights c(a, b), ∑_g c(O g, N g) u_g equals ∑_{a,b} c(a, b) · u(G_{ab}), where G_{ab} is the set of goods that O gives to a and N gives to b.
Statement
theorem mnw2_sum_groups {m : ℕ} (u : Fin m → ℝ) (O N : Fin m → Fin 2) (c : Fin 2 → Fin 2 → ℝ) : ∑ g, c (O g) (N g) * u g = c 0 0 * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 0), u g + c 1 0 * ∑ g ∈ Finset.univ.filter (fun g => O g = 1 ∧ N g = 0), u g + c 0 1 * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 1), u g + c 1 1 * ∑ g ∈ Finset.univ.filter (fun g => O g = 1 ∧ N g = 1), u g
- Source
- step towards mnw_two_agents_welfare_le (grouping goods by owners, The Price of Fairness for Indivisible Goods, arXiv:1905.04910, Theorem 5.4)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- mnw_two_agents_welfare_leFor two agents with additive, nonnegative, normalized valuations (v_i(M) = 1) over any number m of goods, every maximum Nash welfare…
- mnw2_bundle_valueIf τ(g) = T(O g, N g) for a map T : {0,1}² → {0,1}, then the value u(X_k) of agent k's bundle under τ is the sum of the group sums…
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.
/-- A sum whose weight depends only on the pair (O g, N g) splits into the four group sums. -/theorem mnw2_sum_groups {m : ℕ} (u : Fin m → ℝ) (O N : Fin m → Fin 2) (c : Fin 2 → Fin 2 → ℝ) : ∑ g, c (O g) (N g) * u g = c 0 0 * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 0), u g + c 1 0 * ∑ g ∈ Finset.univ.filter (fun g => O g = 1 ∧ N g = 0), u g + c 0 1 * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 1), u g + c 1 1 * ∑ g ∈ Finset.univ.filter (fun g => O g = 1 ∧ N g = 1), u g := by simp only [Finset.sum_filter, Finset.mul_sum, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun g _ => ?_ have h2 : ∀ x : Fin 2, x = 0 ∨ x = 1 := by decide rcases h2 (O g) with ho | ho <;> rcases h2 (N g) with hn | hn <;> simp [ho, hn]