Source-linked AI summary
Maximum Nash Welfare and Other Stories About EFX
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, Alexandros A. Voudouris
TL;DR
The paper studies when maximum Nash welfare allocations guarantee envy-freeness up to any good. It proves this implication for two-value instances, identifies its failure for three or more values, and develops approaches for constructing EFX allocations and interpreting approximate EFX more broadly.
Problem
The paper asks when maximum Nash welfare implies EFX, since this implication fails in general and the relationships between these notions remain open.
Method
The paper characterizes the value-restricted cases where MNW implies EFX0, examines computational complexity, and develops direct procedures for computing EFX0 allocations.
Results
For all 2-value instances, every MNW allocation is EFX0; this is tight because the implication fails for instances with three or more distinct values.
Takeaways & Limitations
The two-value result establishes EFX0 existence for restricted valuation functions, while the paper also studies direct EFX0 computation and a new approximate-EFX interpretation.
Takeaways & Limitations
A polynomial-time algorithm for computing MNW allocations remains open beyond the binary case, motivating algorithms that compute EFX0 without necessarily maximizing Nash welfare.
Abstract
from arXiv · showhide
We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash welfare (MNW) and envy-freeness up to any good (EFX). We establish that an MNW allocation is always EFX as long as there are at most two possible values for the goods, whereas this implication is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for these restricted valuation functions. While the efficient computation of an MNW allocation for two possible values remains an open problem, we present a novel algorithm for directly constructing EFX allocations in this setting. Finally, we study the question of whether an MNW allocation implies any EFX guarantee for general additive valuation functions under a natural new interpretation of approximate EFX allocations.
1 Introduction
The paper studies EFX and MNW for indivisible goods with additive valuations, identifying restricted domains where MNW guarantees EFX and developing direct EFX algorithms. It also examines limitations of this implication and introduces an alternative approximate-EFX interpretation.
- 1 Introduction: EFX relaxes envy-freeness by allowing envy up to the least desirable good in another agent’s bundle.Its existence was open even for four additive-valuation agents.
- 1 Introduction: The paper investigates when MNW allocations imply EFX, how to compute EFX allocations efficiently, and how MNW relates to a new approximate-EFX benchmark.The analysis is organized around the number of distinct good values and general additive valuations.
- 1.1 Our contribution: For 2-value instances, every MNW allocation is EFX0, implying that an EFX0 allocation exists for any number of agents and goods.This is presented as an existence result for non-identical valuations.
- 1.1 Our contribution: For binary valuations, an allocation that is both MNW and EFX0 can be efficiently constructed.The construction adapts an algorithm of Barman et al.
- 1.1 Our contribution: The implication MNW ⇒ EFX0 fails for instances with three or more distinct values.Thus, the two-value guarantee is tight with respect to the number of distinct values.
- 1.1 Our contribution: The paper also gives a polynomial-time EFX algorithm for instances whose maximum-to-minimum value ratio is at most 2.The method is a variation of round-robin.
- 1.1 Our contribution: For general additive valuations, MNW gives no non-trivial EFX approximation, while the proposed EFX-value interpretation yields a 1/2-approximation.The paper motivates this benchmark by considering hypothetical augmentation toward an EFX-like condition.
- 1.2 Related work: Computing MNW remains an active challenge because the general problem is APX-hard, despite efficient algorithms for binary additive valuations and approximation algorithms.Related work includes a factor-2 approximation and a currently best-known factor of 1.45.
2 Preliminaries and Notation
The paper formalizes indivisible-goods fair division with additive valuations and defines EFX, EFX0, and MNW. It establishes a polynomial reduction from EFX0 to EFX for k-value instances and records the relevant implication hierarchy.
- Model: Instances contain indivisible goods, complete allocations, and agents with additive non-negative valuations.A valuation of a bundle is the sum of its agents’ values for the goods it contains.
- Fairness notions: EFX requires that an agent does not envy another agent after removing any positively valued good from the other bundle.EFX0 imposes the same condition for every good, including goods valued at zero.
- Fairness notions: The fairness notions satisfy EF ⇒ EFX0 ⇒ EFX ⇒ EF1, with no implication holding in the reverse direction.
- Nash welfare: MNW allocations maximize the product of agents’ bundle values, equivalently maximizing Nash welfare defined via the geometric mean.The paper uses the product formulation because it yields the same exact maximizers.
- EFX and EFX0: For k-value instances, computing EFX0 reduces to computing EFX, in polynomial time when values are rational.The reduction replaces zero values by a sufficiently small positive ε and transfers an EFX allocation back to EFX0.
3 Maximum Nash Welfare: EFX and Computational Complexity
This section characterizes when MNW implies EFX-type guarantees and examines computation. Any MNW allocation is EFX0 for binary instances and EFX for positive 2-value instances, while the implication fails for three values; binary MNW is polynomial-time computable, but 3-value MNW is NP-hard.
- Technical treatment: When Nash welfare is zero, maximizing welfare alone does not distinguish allocations, so the paper refines MNW selection using positive-agent count and then product.Zero-valued goods are handled separately because they can affect EFX0 despite not affecting Nash welfare.
- MNW and EFX: Three distinct values suffice to invalidate the implication from MNW to EFX and EFX0.The counterexample remains an interval-value instance with arbitrarily small interval length.
- MNW and EFX: Any MNW allocation is EFX0 for binary instances and EFX for positive 2-value instances.Thus these valuation classes admit EFX allocations through MNW allocations.
- Computational complexity: Binary instances admit polynomial-time computation of an MNW allocation, and therefore of an EFX0 allocation.The procedure combines maximum bipartite matching with a binary Nash-welfare algorithm, including the zero-Nash-welfare case.
- Computational complexity: Computing an MNW allocation is NP-hard even for 3-value instances.The hardness proof reduces from 2P2N-3SAT.
4 Computing EFX Allocations for Restricted Domains
For restricted valuation domains, the paper develops efficient procedures for constructing EFX allocations, including Match&Freeze for 2-value instances and modified round-robin for interval instances.
- A polynomial-time algorithm remains open for computing MNW allocations beyond the binary case, despite MNW implying EFX0 for 2-value instances.
- Match&Freeze repeatedly computes maximum matchings, allocates matched goods, and freezes agents whose allocations create value disparities.
- Frozen agents receive no further rounds for a period determined by the ratio a/b, while remaining active agents continue to receive goods.
- The algorithm outputs an EFX0 allocation in polynomial time for every 2-value instance.
- Agents receive value-a goods before their freezing round, can freeze only once, and value all remaining goods at b afterward.
- Interval-value instances: For interval instances with each agent’s values in [x_i, 2x_i], modified round-robin computes an EFX allocation in polynomial time.
5 MNW and the EFX-value
The paper introduces the EFX-value to study approximate EFX and shows that MNW guarantees a constant vEFX approximation even when it may provide no constant standard EFX guarantee.
- Under the standard approximation notion, MNW need not provide any meaningful β-EFX guarantee for β ∈(0, 1).
- A three-value instance can have a unique MNW allocation that is only 1/w-EFX, with the approximation arbitrarily close to zero as w grows.
- The EFX-value χ_i(A) is the maximum value agent i needs after adding a minimally sufficient subset from another agent’s bundle.
- An α-EFX allocation is also an α/(1+α)-vEFX allocation, and this guarantee is tight.
- An α-vEFX allocation need not be β-EFX for any α, β ∈(0, 1), because its EFX approximation can approach zero.
- Every MNW allocation is 1/2-vEFX, and the bound is tight.
6 Directions for Future Work
The paper leaves open efficient MNW computation beyond binary valuations, while offering a polynomial-time EFX0 algorithm for 2-value instances and a new approximate-EFX connection through the EFX-value.
- Whether MNW allocations can be computed in polynomial time for general 2-value instances remains open.
- For 2-value instances, Match&Freeze computes EFX0 allocations in polynomial time even without maximizing Nash welfare.
- Generalizing Match&Freeze to k-value instances with k ≥3 is identified as a highly non-trivial direction for future work.
- Under the new EFX-value interpretation, MNW provides an approximate-EFX guarantee despite lacking a meaningful guarantee under the commonly used definition.