mnw2_lb_bundle
theoremverified
In the three-good instance, agent i's value for her bundle under σ is the sum of her values of the goods g ∈ {0, 1, 2} with σ(g) = i.
Statement
theorem mnw2_lb_bundle (ε : ℝ) (σ : Fin 3 → Fin 2) (i : Fin 2) : additive_valuation (mnw2_lb_val ε i) (bundle_of σ i) = (if σ 0 = i then mnw2_lb_val ε i 0 else 0) + (if σ 1 = i then mnw2_lb_val ε i 1 else 0) + (if σ 2 = i then mnw2_lb_val ε i 2 else 0)
- Source
- step towards mnw2_lb_is_mnw (lower-bound instance of 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_lb_valValuations of two agents over three goods, depending on a parameter ε: agent 0 has values (2/3, 1/3, 0) and agent 1 has values (4/7 − ε,…
- 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 3
- mnw2_lb_is_mnwFor 0 < ε < 1/7, the allocation N = (0, 1, 1) (good 0 to agent 0, goods 1 and 2 to agent 1) has Nash welfare (2/3)(3/7 + ε), the largest…
- mnw2_lb_mnw_welfareFor 0 < ε < 1/7, the allocation (0, 1, 1) is the unique MNW allocation of the three-good instance (all seven other allocations have…
- mnw2_lb_opt_welfareGiving goods 0 and 1 to agent 0 and good 2 to agent 1 yields social welfare 2/3 + 1/3 + 2/7 = 9/7.
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.
/-- Bundle values in the lower-bound instance, good by good. -/theorem mnw2_lb_bundle (ε : ℝ) (σ : Fin 3 → Fin 2) (i : Fin 2) : additive_valuation (mnw2_lb_val ε i) (bundle_of σ i) = (if σ 0 = i then mnw2_lb_val ε i 0 else 0) + (if σ 1 = i then mnw2_lb_val ε i 1 else 0) + (if σ 2 = i then mnw2_lb_val ε i 2 else 0) := by unfold additive_valuation bundle_of rw [Finset.sum_filter, Fin.sum_univ_three]