Research map / Learning theory and algorithms / Submodular and game algorithms
On Optimal Tradeoffs between EFX and Nash Welfare
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the optimal tradeoff between alpha-EFX and beta-MNW for additive and subadditive valuations, giving algorithms that achieve alpha-EFX with a 1/(alpha+1) fraction of max Nash welfare, which is tight.
Problem
Fair division of indivisible goods: whether an alpha-EFX allocation can simultaneously guarantee a beta fraction of maximum Nash welfare, i.e., the tradeoff between approximate EFX fairness and Nash welfare efficiency.
Approach
Starting from a max Nash welfare allocation, iteratively shrink bundles and match agents to bundles (removing envy-causing items conservatively) so each agent keeps at least a 1/(alpha+1) fraction of her initial value; for subadditive valuations, additionally reallocate removed items and use swapping with singletons. A separation property then converts partial into complete allocations.
Key results
- For additive valuations, a partial allocation that is alpha-EFX, EF1 and 1/(alpha+1)-MNW exists for all alpha in [0,1], and this tradeoff is tight.
- For additive valuations and alpha up to phi-1 (~0.618), the partial allocation can be completed to a complete alpha-EFX, EF1, 1/(alpha+1)-MNW allocation.
- For subadditive valuations and alpha up to 1/2, a complete alpha-EFX allocation with 1/(alpha+1)-MNW exists, e.g., 1/2-EFX with 2/3-MNW.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Extend the additive partial-allocation guarantee from a fixed 1/2-MNW result to the α-dependent 1/(α+1)-MNW tradeoff | Additive valuations, partial allocations · Additive valuations | MNW approximation: 1/2 -> 1/(α+1) | Helped |
| Add an MNW guarantee to complete (φ-1)-EFX allocations | Additive valuations, complete allocations · Additive valuations | MNW approximation: (φ-1)-MNW | Helped |
| Improve the MNW guarantee while retaining complete 1/2-EFX allocations | Subadditive valuations, complete allocations · Subadditive valuations | MNW approximation: 1/2 -> 2/3 | Helped |
| Require an MNW approximation β greater than 1/(α+1) together with α-EFX | Additive valuations, partial or complete allocations · Additive valuations | MNW approximation: β > 1/(α+1) | Hurt |
Limitations
- Complete allocations for additive valuations only for alpha up to phi-1
- Existence results require an MNW allocation as input; NP-hard to compute exactly
- Subadditive complete result limited to alpha <= 1/2
Experimental setup
Metrics: EFX approximation Nash welfare approximation
Baselines: Caragiannis et al. partial EFX 1/2-MNW (phi-1)-EFX complete allocation 1/2-EFX 1/2-MNW subadditive
Builds on: envy-cycles procedure alpha-EFX existence (golden ratio) EFX partial allocation with 1/2-MNW
Closest papers by meaning
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.95)
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.94)
- Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.93)
- (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.93)
- EF2X Exists for Four Agents (AAAI 2025 · similarity 0.92)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.92)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.