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)- Almost envy-freeness with general valuations
- Two birds with one stone: fairness and welfare via transfers
- Picking sequences and monotonicity in weighted fair division
- Approximately EFX allocations for indivisible chores
- Computing fair and efficient allocations with few utility values
- On existence of truthful fair cake cutting mechanisms
- Dividing good and great items among agents with bivalued submodular valuations
- One quarter each (on average) ensures proportionality
- Fair division with binary valuations: one rule to rule them all
- Fair division of indivisible goods: recent progress and open questions
- Existence of EFX for two additive valuations
- EFX allocations for indivisible chores: matching-based approach
- Approximating Nash social welfare by matching and local search
- 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
- EFX allocation to chores over small graph
- Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness
- The price of fairness for indivisible goods
- A characterization of maximum Nash welfare for indivisible goods
- EFX allocations for indivisible chores: matching-based approach
- EFX under budget constraint
- Almost proportional allocations of indivisible chores: computation, approximation and efficiency
- Computing fair and efficient allocations with few utility values
- Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
- On maximum weighted Nash welfare for binary valuations
- Extending the characterization of maximum Nash welfare
- Fair division of mixed divisible and indivisible goods
- Generalized binary utility functions and fair allocations
- On the existence of EFX allocations
- Almost envy-freeness with general valuations
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)
