Source-linked AI summary
Characterizing Maximum Nash Welfare: Envy-Freeness and Proportionality
Karen Frilya Celine, Warut Suksompong, Nicholas Teh
TL;DR
Indivisible goods can prevent classic fairness guarantees, and prior work characterized MNW using EF1. This paper tests weaker EFk and PROPk guarantees and finds MNW remains uniquely characterized, even on identical-good profiles.
Problem
Whether another welfarist rule can guarantee the weaker EFk or PROPk fairness relaxations remains open, despite reported utilitarian-welfare advantages of MHW over MNW [2026].
Source: §1 · pp. 1–2Method
The proof uses identical-good profiles with nL goods and per-good utility x_i/L, deriving bounds on each agent’s goods from PROPk.
Source: §3 · p. 4Results
For every n ≥2 and k ≥1, MNW is the unique welfarist rule guaranteeing EFk for all n-agent profiles; the same characterization holds for PROPk, including identical-good profiles.
Source: §1 · p. 2, §3 · pp. 3–4Takeaways & Limitations
No other family of welfare functions satisfying the theorem’s conditions can guarantee envy-freeness or proportionality up to h(n) goods for each agent count n.
Source: §3 · p. 5
Abstract
from arXiv · showhide
When allocating indivisible goods, the maximum Nash welfare rule is known to be the unique welfarist rule satisfying envy-freeness up to one good. We strengthen this characterization by showing that envy-freeness up to one good can be replaced by substantially weaker fairness requirements: envy-freeness up to $k$ goods or proportionality up to $k$ goods, for any fixed $k$. Our characterization holds even for profiles with identical goods.
1 Introduction
Indivisible goods can make envy-freeness and proportionality impossible, motivating relaxed fairness guarantees. The paper shows that even these weaker guarantees uniquely characterize maximum Nash welfare among welfarist rules, including on identical-good profiles.
1 Introduction
- Indivisibility can preclude classic envy-freeness and proportionality; with more agents than positively valued goods, someone must receive nothing.That agent is necessarily envious and deprived of her proportional share.Source: §1 · p. 1
- MNW selects an allocation maximizing the product of agents’ utilities, equivalently the sum of their logarithms.For additive utilities, every MNW allocation satisfies EF1, and prior work characterized MNW as the unique welfarist rule ensuring EF1 [2019; 2023].Source: §1 · p. 1
- The open question is whether another welfarist rule can guarantee EFk or PROPk, which are relaxations of EF1; PROPk is fundamentally weaker than EFk.The question is motivated in part by reported utilitarian-welfare advantages of MHW over MNW [2026].Source: §1 · pp. 1–2
- For every n ≥2 and fixed k ≥1, MNW is the unique welfarist rule guaranteeing EFk for all n-agent profiles; the characterization also holds for PROPk and identical-good profiles.The paper says this remains true even when all goods are identical.Source: §1 · p. 2
2 Preliminaries
The preliminaries define the additive-utility profiles, allocations, fairness relaxations, and welfare functions used to state the characterization.
2 Preliminaries
- Utilities are additive, and a profile comprises the agents, goods, and their utility functions; goods are identical when each agent values every good equally.An allocation partitions the goods into possibly empty bundles, one for each agent.Source: §2 · p. 2
- EFk requires that each agent’s envy of another’s bundle can be eliminated by removing at most k goods from that bundle.The comparison is between the agent’s own utility and the other agent’s remaining bundle.Source: §2 · p. 2
- PROPk requires that each agent can reach at least 1/n of her total-goods utility by adding at most k goods to her bundle.The added goods must be outside that agent’s bundle.Source: §2 · p. 2
- For any positive integer k, EFk implies PROPk; a rule maps each profile to an allocation..Source: §2 · p. 2
- A welfarist rule chooses an allocation maximizing a non-decreasing welfare function of the agents’ allocated utilities.If several allocations maximize welfare, the rule may choose any of them.Source: §2 · p. 2
3 The Result
For fixed n and k, Theorem 2 characterizes welfare rules with EFk guarantees through an existence test on identical-good profiles. The characterization also holds for PROPk and identifies rules effectively equivalent to MNW.
3 The Result
- For continuous, strictly increasing welfare functions, universal EFk for every chosen allocation is equivalent to an EFk allocation being selectable on every positive-admitting identical-good profile.The theorem states these conditions as equivalent parts of its characterization for fixed n and k.Source: §3 · p. 3
- The characterized functions are strictly increasing transformations of the product on positive utilities and rank positive vectors above nonnegative vectors with a zero coordinate.The product representation is fn(x) = q(x1x2 · · · xn), with q strictly increasing and continuous.Source: §3 · pp. 4–5
- The same equivalence holds when PROPk replaces EFk in both the universal-guarantee and identical-good existence conditions.For every positive integer k, EFk implies PROPk.Source: §3 · p. 4
- The necessity argument uses identical-good profiles with nL goods, where proportionality forces each agent to receive between L−k and L+(n−1)k goods.As L grows, these allocations approximate arbitrary positive utility vectors, constraining the welfare function.Source: §3 · p. 4
- Under the characterized conditions, the selectable allocations on every positive-admitting profile are exactly those selectable by MNW.Thus the welfare rule is effectively equivalent to MNW.Source: §3 · p. 5
- No other family of welfare functions satisfying the theorem's conditions can guarantee EF or proportionality up to h(n) goods for each n.The theorem rules this out even for a specific number of agents.Source: §3 · p. 5