AFTD Auto-Formalizing Theoretical Domains

mnw2_bundle_value

theoremverified

If τ(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 u(G_{ab}) over the groups (a, b) with T(a, b) = k.

Statement

theorem mnw2_bundle_value {m : ℕ} (u : Fin m → ℝ) (O N τ : Fin m → Fin 2) (T : Fin 2 → Fin 2 → Fin 2) (hτ : ∀ g, τ g = T (O g) (N g)) (k : Fin 2) : additive_valuation u (bundle_of τ k) = (if T 0 0 = k then 1 else 0) * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 0), u g + (if T 1 0 = k then 1 else 0) * ∑ g ∈ Finset.univ.filter (fun g => O g = 1 ∧ N g = 0), u g + (if T 0 1 = k then 1 else 0) * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 1), u g + (if T 1 1 = k then 1 else 0) * ∑ 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
Built on 3
  • mnw2_sum_groupsFor 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}),…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • 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.
Used by 1
  • 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…

Lean source view module on GitHub

/-- If an allocation `τ` decides each good by its group (O g, N g), each bundle value is a sum of group sums. -/theorem mnw2_bundle_value {m : ℕ} (u : Fin m → ℝ) (O N τ : Fin m → Fin 2) (T : Fin 2 → Fin 2 → Fin 2) (hτ : ∀ g, τ g = T (O g) (N g)) (k : Fin 2) : additive_valuation u (bundle_of τ k) = (if T 0 0 = k then 1 else 0) * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 0), u g + (if T 1 0 = k then 1 else 0) * ∑ g ∈ Finset.univ.filter (fun g => O g = 1 ∧ N g = 0), u g + (if T 0 1 = k then 1 else 0) * ∑ g ∈ Finset.univ.filter (fun g => O g = 0 ∧ N g = 1), u g + (if T 1 1 = k then 1 else 0) * ∑ g ∈ Finset.univ.filter (fun g => O g = 1 ∧ N g = 1), u g := by  have e := mnw2_sum_groups u O N (fun a b => if T a b = k then (1 : ℝ) else 0)  try simp only at e  rw [← e]  unfold additive_valuation bundle_of  rw [Finset.sum_filter]  refine Finset.sum_congr rfl fun g _ => ?_  rw [hτ g]  split_ifs <;> simp
See it in the graphDiscuss this resultChallenge it