AFTD Auto-Formalizing Theoretical Domains

nash_welfare

def

Nash 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 agent i under σ.

Statement

def nash_welfare {m n : ℕ} (v : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : ℝ
Defined in
The Price of Fairness for Indivisible Goods, arXiv:1905.04910, Sec. 2 (Nash welfare / utilitarian social welfare of an allocation, additive valuations)
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • 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 4
  • 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…
  • is_mnw_allocationAn allocation σ is a maximum Nash welfare (MNW) allocation if no allocation τ has larger Nash welfare. When the maximum Nash welfare is…
  • 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…

Lean source view module on GitHub

/-- The Nash welfare of the allocation `σ` under additive valuations `v`: the product of the agents' values for their bundles. -/
def nash_welfare {m n : ℕ} (v : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : ℝ :=
  ∏ i, additive_valuation (v i) (bundle_of σ i)
See it in the graphDiscuss this resultChallenge it