AFTD Auto-Formalizing Theoretical Domains

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

/-- 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]
See it in the graphDiscuss this resultChallenge it