Research map / Learning theory and algorithms / Submodular and game algorithms
Understanding EFX Allocations: Counting and Variants
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.
Counts the minimum number of EFX allocations in restricted instances, extends the analysis to weighted EFX (WEFX) and a new variant EFX+, and gives polynomial-time and approximation results for WEFX.
Problem
Existence of EFX allocations of indivisible goods is an open problem; the minimum number of EFX allocations, and analogous questions for weighted EFX and EFX+, are largely unexplored.
Approach
Study how many EFX allocations must exist (lower bounds) and how few can exist (upper bounds) for restricted instances with few goods, showing counting EFX is #P-complete; introduce EFX+ (adding the dropped good to the evaluating agent's bundle) and show WEFX results for binary additive valuations and a 1/4-WEFX for two agents.
Key results
- Counting EFX allocations is #P-complete in general; for m = n+1 the minimum number of EFX allocations is exactly n.
- For binary additive valuations with n agents, a WEFX and PO allocation exists and is computable in polynomial time; with n=2 and m>=3 there can be only one WEFX allocation.
- For two agents with additive valuations, a 1/4-WEFX allocation always exists; for n=2 there are at least two EFX+ allocations, but EFX+ may fail to exist for n=3, m=4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict to identical valuations | EFX allocation counting · m ≥ n | minimum number of EFX allocations: n! | Helped |
| Use binary additive valuations with n = 2 and m ≥ 3 | WEFX allocation counting · WEFX | minimum number of WEFX allocations: 2 -> 1 | Mixed |
| Generalize binary additive valuations to binary submodular valuations | WEFX · n = 2 | existence of a WEFX allocation | Hurt |
| Generalize binary additive valuations to restricted additive valuations | WEFX · n = 2 | existence of a WEFX allocation | Hurt |
| Relax WEFX to WWEFX under binary submodular valuations | WEFX · n = 2 | existence of a fair allocation | Hurt |
| Relax WEFX to WWEFX under restricted additive valuations | WEFX · n = 2 | existence of a fair allocation | Hurt |
| Approximate WEFX for two agents under additive valuations | WEFX · n = 2 | WEFX approximation factor: \frac{1}{4} | Helped |
| Replace EFX with EFX+ under general monotone valuations | EFX · n = 3, m = 4 | existence of a fair allocation | Hurt |
| Count EFX allocations instead of only finding one | EFX counting problem · General instances | computational complexity | Hurt |
Surprising findings
- EFX+ may fail to exist with three agents and four goods, despite existing for two agents.
- Weak WEFX may fail to exist for two agents under restricted additive or binary submodular valuations.
Experimental setup
Builds on: EFX EF1 leximin++ cut-and-choose
Closest papers by meaning
- Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.96)
- (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.95)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.95)
- EF2X Exists for Four Agents (AAAI 2025 · similarity 0.94)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.94)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.93)
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.