Maximum Nash welfare and other stories about EFX
From MaRDI portal
Publication:2658044
DOI10.1016/J.TCS.2021.02.020zbMATH Open1500.91079arXiv2001.09838OpenAlexW3034338406MaRDI QIDQ2658044FDOQ2658044
Authors: Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, Alexandros A. Voudouris 
Publication date: 18 March 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/2001.09838
Recommendations
Cites Work
- Approximating the Nash Social Welfare with Indivisible Items
- Improving Nash social welfare approximations of indivisible goods
- Fair Allocation of Indivisible Goods
- Cake cutting algorithms
- Almost envy-freeness with general valuations
- Approximation Algorithms for Computing Maximin Share Allocations
- Fair enough: guaranteeing approximate maximin shares
- On the number of almost envy-free allocations
- Term Rewriting and Applications
- Truthful fair division without free disposal
- A Little Charity Guarantees Almost Envy-Freeness
- Title not available (Why is that?)
- Near fairness in matroids
- APX-hardness of maximizing Nash social welfare with indivisible items
- Asymptotic existence of fair divisions for groups
- Approximate maximin shares for groups of agents
- Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
- Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
- Almost envy-freeness in group resource allocation
Cited In (31)
- Two birds with one stone: fairness and welfare via transfers
- Fair division of mixed divisible and indivisible goods
- Almost proportional allocations of indivisible chores: computation, approximation and efficiency
- Approximately EFX allocations for indivisible chores
- On existence of truthful fair cake cutting mechanisms
- The price of fairness for indivisible goods
- EFX allocation to chores over small graph
- Computing fair and efficient allocations with few utility values
- Generalized binary utility functions and fair allocations
- Dividing good and great items among agents with bivalued submodular valuations
- One quarter each (on average) ensures proportionality
- Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
- Almost envy-freeness with general valuations
- Almost envy-freeness with general valuations
- On the existence of EFX allocations
- Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness
- Picking sequences and monotonicity in weighted fair division
- Existence of EFX for two additive valuations
- EFX allocations for indivisible chores: matching-based approach
- On maximum weighted Nash welfare for binary valuations
- Fair division with binary valuations: one rule to rule them all
- Approximating Nash social welfare by matching and local search
- Fair division of indivisible goods: recent progress and open questions
- EFX under budget constraint
- Extending the characterization of maximum Nash welfare
- Computing fair and efficient allocations with few utility values
- EFX allocations for indivisible chores: matching-based approach
- The frontier of intractability for EFX with two agents
- The price of equity with binary valuations and few agent types
- Envy-free relaxations for goods, chores, and mixed items
- A characterization of maximum Nash welfare for indivisible goods
This page was built for publication: Maximum Nash welfare and other stories about EFX
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658044)
