AFTD Auto-Formalizing Theoretical Domains

mnw2_lb_mnw_welfare

theoremverifiedformalization

For 0 < ε < 1/7, the allocation (0, 1, 1) is the unique MNW allocation of the three-good instance (all seven other allocations have strictly smaller Nash welfare), so every MNW allocation has social welfare 2/3 + (1/7 + ε + 2/7) = 23/21 + ε.

Statement

theorem mnw2_lb_mnw_welfare (ε : ℝ) (h0 : 0 < ε) (h1 : ε < 1 / 7) (N : Fin 3 → Fin 2) (hN : is_mnw_allocation (mnw2_lb_val ε) N) : utilitarian_welfare (mnw2_lb_val ε) N = 23 / 21 + ε
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 5
  • 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.
  • is_mnw_allocationAn allocation σ is a maximum Nash welfare (MNW) allocation if no allocation τ has larger Nash welfare. When the maximum Nash welfare is…
  • nash_welfareNash welfare of an allocation σ of m goods to n agents with additive valuations v_i: NW(σ) = ∏_i v_i(X_i), where X_i is the bundle of…
  • 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 every MNW allocation has utilitarian welfare 23/21 + ε. -/theorem mnw2_lb_mnw_welfare (ε : ℝ) (h0 : 0 < ε) (h1 : ε < 1 / 7) (N : Fin 3 → Fin 2) (hN : is_mnw_allocation (mnw2_lb_val ε) N) : utilitarian_welfare (mnw2_lb_val ε) N = 23 / 21 + ε := by  have hc := hN ![0, 1, 1]  have h2 : ∀ x : Fin 2, x = 0 ∨ x = 1 := by decide  simp only [nash_welfare, utilitarian_welfare, Fin.prod_univ_two, Fin.sum_univ_two, mnw2_lb_bundle] at hc ⊢  rcases h2 (N 0) with a | a <;> rcases h2 (N 1) with b | b <;> rcases h2 (N 2) with c | c <;>    simp [a, b, c, mnw2_lb_val] at hc ⊢ <;> nlinarith
See it in the graphDiscuss this resultChallenge it