Maximum Nash welfare rule linked to flexible fairness guarantees
Characterizing Maximum Nash Welfare: Envy-Freeness and Proportionality
Computer Science and Game Theory
Summary
Dividing things fairly when you can’t split items can be tricky. The authors show that a well-known way to share things fairly, called maximum Nash welfare, works even under weaker fairness ideas than previously thought. Instead of needing almost perfect fairness, it can handle fairness that allows a few small exceptions. This result holds true even when all items being shared are the same. So, the authors help us better understand why this rule is special for fair sharing.
What this means in practice
- •For online marketplaces: Design allocation algorithms that provide fair item distribution under weaker fairness constraints to improve user satisfaction.
- •For resource allocation engineers: Develop systems that assign indivisible resources fairly using maximum Nash welfare properties with relaxed fairness guarantees.
A theory result. No direct application yet.
Authors
Karen Frilya Celine, Warut Suksompong, Nicholas Teh
Abstract
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.