Research map / Multi-agent systems and games / Games and equilibria
The Complexity of Fair Division of Indivisible Items with Externalities
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.
Studies the computational complexity of deciding EF, EF1 and EFX allocations for indivisible items under additive externalities, giving NP-completeness, FPT/XP and W[1]-hardness results and showing that agent/item-correlated valuations reduce to the standard no-externalities setting.
Problem
Deciding whether a fair (EF, EF1, or EFX) allocation of indivisible items exists when agents' valuations have additive externalities, i.e., agents also value items given to other agents.
Approach
Shows NP-completeness of EFX existence even with three agents or six value levels, gives FPT results parameterized by number of agents plus item types (or agents plus values), proves binary/bi-valued instances have EFX=EF1, and reduces agent/item-correlated valuations to the no-externality setting.
Key results
- EFX allocation existence under externalities is NP-complete even with three agents and no weak-chores.
- The problem remains NP-complete with only 6 distinct valuation values and 3 item types.
- Binary-valued instances have EFX and EF1 allocations coinciding, so three agents with binary valuations always admit a polynomial-time computable EFX allocation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow additive externalities in the allocation model | EFX existence decision · General valuations; three agents; no weak-chores | computational complexity | Hurt |
| Restrict valuations to six values and three item types | EFX existence decision · General valuations; no weak-chores | computational complexity | Hurt |
| Bound both the number of item types and the number of agents | EF, EF1, and EFX existence decision · Additive externalities | computational complexity | Helped |
| Bound both the number of different values and the number of agents | EF, EF1, and EFX existence decision · Additive externalities | computational complexity | Helped |
| Parameterize by the number of items | EF existence decision · Binary valuations; no chores | computational complexity | Hurt |
| Use binary valuations with three agents and no weak-chores | EFX existence · Three agents; no weak-chores | existence and algorithm | Helped |
| Replace each agent's two possible valuation values with binary values | EF, EF1, and EFX allocations · Instances where each agent has at most two values | fairness equivalence | No clear effect |
| Use binary valuations instead of general valuations | EFX versus EF1 · Fair division with externalities | fairness equivalence | No clear effect |
| Use agent-item-correlated valuations | EF, EF1, and EFX allocations · Instances with externalities | fairness equivalence | No clear effect |
| Use team-based valuations | EF1 existence · Fair division with externalities | existence and algorithm | Helped |
| Use network-based valuations | EF1 existence · Fair division with externalities | existence and algorithm | Helped |
| Maximize Nash social welfare | Nash-social-welfare-maximizing allocation · Fair division with externalities | EFX fairness | Hurt |
Surprising findings
- Maximizing Nash social welfare does not guarantee EFX under externalities, even with 3 agents and 4 identical-type items.
- EF is W[1]-hard parameterized by the number of items, even for binary valuations without chores.
Limitations
- Hardness results leave open the case of small fixed numbers of agents with general valuations beyond the tractable fragments.
- FPT results require both number of agents and item types (or value count) to be bounded; EF with items as parameter is W[1]-hard.
Experimental setup
Builds on: EF1 EFX Equal-Cardinality-Partition Min Bisection Multicolored Clique
Closest papers by meaning
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.95)
- Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.93)
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.93)
- (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.93)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.92)
- EF2X Exists for Four Agents (AAAI 2025 · 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.