AFTD Auto-Formalizing Theoretical Domains

mnw2_lb_opt_welfare

theoremverifiedformalization

Giving goods 0 and 1 to agent 0 and good 2 to agent 1 yields social welfare 2/3 + 1/3 + 2/7 = 9/7.

Statement

theorem mnw2_lb_opt_welfare (ε : ℝ) : utilitarian_welfare (mnw2_lb_val ε) ![0, 0, 1] = 9 / 7
Formalizes
The Price of Fairness for Indivisible Goods, arXiv:1905.04910, Theorem 5.4, lower-bound instance (m = 3, utilities (2/3, 1/3, 0) and (4/7 - eps, 1/7 + eps, 2/7), 0 < eps < 1/7)
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 − ε,…
  • mnw2_lb_bundleIn 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.
  • utilitarian_welfareUtilitarian social welfare of an allocation σ with additive valuations v_i: SW(σ) = ∑_i v_i(X_i), where X_i is the bundle of agent i under…
Used by 1
  • mnw_two_agents_price_lower_boundFor every c < 27/23 there are two agents with additive, nonnegative, normalized valuations over three goods and an allocation O such that…

Lean source view module on GitHub

/-- In the lower-bound instance the allocation (0, 0, 1) has utilitarian welfare 9/7. -/theorem mnw2_lb_opt_welfare (ε : ℝ) : utilitarian_welfare (mnw2_lb_val ε) ![0, 0, 1] = 9 / 7 := by  simp only [utilitarian_welfare, Fin.sum_univ_two, mnw2_lb_bundle]  have a0 : (![0, 0, 1] : Fin 3 → Fin 2) 0 = 0 := rfl  have a1 : (![0, 0, 1] : Fin 3 → Fin 2) 1 = 0 := rfl  have a2 : (![0, 0, 1] : Fin 3 → Fin 2) 2 = 1 := rfl  simp [mnw2_lb_val, a0, a1, a2] <;> norm_num
See it in the graphDiscuss this resultChallenge it