is_mnw_allocation
def
An allocation σ is a maximum Nash welfare (MNW) allocation if no allocation τ has larger Nash welfare. When the maximum Nash welfare is positive this coincides with the usual MNW notion (as in arXiv:1905.04910); when it is 0, this set contains the allocations the usual tie-breaking rule (maximize the number of agents with positive value, then the product over them) would select, so upper bounds on the welfare loss of all such allocations are at least as strong.
Statement
def is_mnw_allocation {m n : ℕ} (v : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop
- Defined in
- The Price of Fairness for Indivisible Goods, arXiv:1905.04910, Sec. 2 (maximum Nash welfare allocation); differs from the paper only when the maximum Nash welfare is 0, where every allocation counts as MNW here
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- 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…
- 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…
- 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
/-- `σ` maximizes Nash welfare among all allocations of the goods. -/ def is_mnw_allocation {m n : ℕ} (v : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop := ∀ τ, nash_welfare v τ ≤ nash_welfare v σ