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
- A Little Charity Guarantees Almost Envy-Freeness
- 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
- APX-hardness of maximizing Nash social welfare with indivisible items
- Asymptotic existence of fair divisions for groups
- Cake cutting algorithms
- Fair Allocation of Indivisible Goods
- Fair enough: guaranteeing approximate maximin shares
- scientific article; zbMATH DE number 3136641 (Why is no real title available?)
- 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
(50)- Picking sequences and monotonicity in weighted fair division
- Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
- On the existence of EFX allocations
- Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
- The price of fairness for indivisible goods
- Fair division of mixed divisible and indivisible goods
- Computing fair and efficient allocations with few utility values
- Two birds with one stone: fairness and welfare via transfers
- On maximum weighted Nash welfare for binary valuations
- A characterization of maximum Nash welfare for indivisible goods
- Generalized binary utility functions and fair allocations
- Fair division with binary valuations: one rule to rule them all
- Extending the characterization of maximum Nash welfare
- Almost envy-freeness with general valuations
- Almost envy-freeness with general valuations
- Existence of EFX for two additive valuations
- EFX under budget constraint
- Fair division of indivisible goods: recent progress and open questions
- Approximately EFX allocations for indivisible chores
- Computing fair and efficient allocations with few utility values
- On existence of truthful fair cake cutting mechanisms
- Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness
- Approximating Nash social welfare by matching and local search
- EFX allocations for indivisible chores: matching-based approach
- The price of equity with binary valuations and few agent types
- The frontier of intractability for EFX with two agents
- Envy-free relaxations for goods, chores, and mixed items
- Almost proportional allocations of indivisible chores: computation, approximation and efficiency
- EFX allocation to chores over small graph
- Dividing good and great items among agents with bivalued submodular valuations
- One quarter each (on average) ensures proportionality
- EFX allocations for indivisible chores: matching-based approach
- When is truthfully allocating chores no harder than goods?
- Online fair division for personalized 2-value instances
- Fairness under equal-sized bundles: impossibility results and approximation guarantees
- On the price of fairness of allocating contiguous blocks
- The price of EF1 for few agents with additive ternary valuations
- Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods
- The frontier of intractability for EFX with two agents
- Weighted EF1 allocations for indivisible chores
- Fair and truthful allocations under leveled valuations
- The incentive guarantees behind Nash welfare in divisible resources allocation
- On the existence of EFX (and Pareto-optimal) allocations for binary chores
- On the existence of EFX (and Pareto-optimal) allocations for binary chores
- Proportional allocation of indivisible goods up to the least valued good on average
- Achieving envy-freeness through items sale
- The fairness of maximum Nash social welfare under matroid constraints and beyond
- Best-of-both-worlds fair allocation of indivisible and mixed goods
- Approximating EFX through a new notion of fairness
- Fair division of indivisible items: envy-freeness vs. efficiency revisited
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)
