AFTD Auto-Formalizing Theoretical Domains

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

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