Maximum Nash welfare and other stories about EFX

DOI10.1016/j.tcs.2021.02.020zbMath1500.91079arXiv2001.09838OpenAlexW3034338406MaRDI QIDQ2658044

Georgios Birmpas, Alexandros A. Voudouris, Aris Filos-Ratsikas, Alexandros Hollender, Georgios Amanatidis

Publication date: 18 March 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.09838

zbMATH Keywords

approximationfair divisionEFXNash welfare

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (12)

Computing fair and efficient allocations with few utility values ⋮ On maximum weighted Nash welfare for binary valuations ⋮ Existence of EFX for two additive valuations ⋮ Generalized binary utility functions and fair allocations ⋮ EFX under budget constraint ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ Approximately EFX allocations for indivisible chores ⋮ On existence of truthful fair cake cutting mechanisms ⋮ Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness ⋮ Fair division of mixed divisible and indivisible goods ⋮ Computing fair and efficient allocations with few utility values ⋮ Picking sequences and monotonicity in weighted fair division

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of almost envy-free allocations
• Truthful fair division without free disposal
• 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
• Almost envy-freeness in group resource allocation
• Approximation Algorithms for Computing Maximin Share Allocations
• Fair Enough
• Approximating the Nash Social Welfare with Indivisible Items
• Improving Nash Social Welfare Approximations
• Fair Allocation of Indivisible Goods
• Cake Cutting Algorithms
• A Little Charity Guarantees Almost Envy-Freeness
• Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
• Term Rewriting and Applications

This page was built for publication: Maximum Nash welfare and other stories about EFX