Maximum Nash welfare and other stories about EFX
From MaRDI portal
Publication:2658044
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3136641 (Why is no real title available?)
- A Little Charity Guarantees Almost Envy-Freeness
- APX-hardness of maximizing Nash social welfare with indivisible items
- Almost envy-freeness in group resource allocation
- Almost envy-freeness with general valuations
- Approximate maximin shares for groups of agents
- Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
- Approximating the Nash Social Welfare with Indivisible Items
- Approximation Algorithms for Computing Maximin Share Allocations
- Asymptotic existence of fair divisions for groups
- Cake cutting algorithms
- Fair Allocation of Indivisible Goods
- Fair enough: guaranteeing approximate maximin shares
- Improving Nash social welfare approximations of indivisible goods
- Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
- Near fairness in matroids
- On the number of almost envy-free allocations
- Term Rewriting and Applications
- Truthful fair division without free disposal
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
- The price of fairness for indivisible goods
- Approximately EFX allocations for indivisible chores
- On existence of truthful fair cake cutting mechanisms
- 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
- On maximum weighted Nash welfare for binary valuations
- EFX allocations for indivisible chores: matching-based approach
- 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
- Extending the characterization of maximum Nash welfare
- EFX under budget constraint
- 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)
