Research map / Multi-agent systems and games / Games and equilibria
EF2X Exists for Four Agents
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.
Proves EF2X allocations always exist for four agents with cancelable (and one monotone) valuations via a pseudo-polynomial constructive algorithm, and gives a polynomial-time algorithm for three agents.
Problem
Existence of EFX allocations of indivisible goods for four agents is open; this work studies the relaxation EF2X (envy vanishes after removing any two goods) for four agents with cancelable valuations.
Approach
Constructive algorithm that transforms partitions through stages (A, B, B1, B2, B2i, B2ii) using a potential function (agent 1's value for the first bundle), swap-optimization between two agents' bundles, and EF2X-best bundles so that the under-demanded bundle gains goods while other agents remain satisfied.
Key results
- EF2X allocations exist for any instance with four agents and cancelable valuations (one agent may have arbitrary monotone valuation), computed in pseudo-polynomial time.
- For three agents with cancelable valuations, an EF2X allocation can be computed in polynomial time, in contrast to EFX whose fastest known three-agent algorithm is pseudo-polynomial.
Surprising findings
- The allocation computed for four agents is often EFX, not just EF2X.
Limitations
- Result is only for four agents; general n remains open for EFX/EF2X with cancelable valuations.
- Algorithm and proof are long and technically demanding.
- Four-agent algorithm is pseudo-polynomial rather than polynomial.
Experimental setup
Baselines: EFX existence for three agents (additive) EF2X for bounded valuations
Builds on: EFX PR algorithm cancelable valuations MMS-feasible valuations
Closest papers by meaning
- (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.97)
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.94)
- Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.94)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.93)
- Approximate Envy-Free Allocations up to any k Goods (NeurIPS 2026 · similarity 0.92)
- On Optimal Tradeoffs between EFX and Nash Welfare (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.