Research map / Multi-agent systems and games / Games and equilibria
(Almost Full) EFX for Three (and More) Types of 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.
Shows EFX allocations exist with at most k-2 unallocated goods when agents have k distinct (nice-cancelable or additive) valuations, and complete EFX allocations exist when n-2 of n agents share a valuation (MMS-feasible valuations).
Problem
Existence of envy-free-up-to-any-good (EFX) allocations of indivisible goods among agents with additive valuations, where the general existence question is open; prior results cover 3 agents, two valuation types, and partial allocations with few unallocated goods.
Approach
Extends the Pareto-improvement technique of partial EFX allocations to k valuation types by focusing on leading agents (least valued bundle per group) and replacing their bundles with minimally envied subsets, which keeps EFX for all agents; a potential-function argument handles the two-outlier case with complete allocations.
Key results
- EFX exists with at most k-2 unallocated goods for n agents with k distinct nice-cancelable (including additive) valuations, with no agent envying the unallocated bundle.
- With three distinct nice-cancelable valuations, an EFX allocation with one unallocated good always exists.
- Complete EFX allocations exist for n agents with additive or MMS-feasible valuations when at least n-2 agents share identical valuations (two outliers).
Limitations
- Complete EFX allocation is only shown for the two-outlier case; general k types still leave up to k-2 goods unallocated.
- The Pareto-improvement technique cannot reach complete allocations in general, since some partial allocations Pareto dominate all complete allocations even for three agents.
Experimental setup
Builds on: Plaut and Roughgarden EFX algorithm Chaudhury et al. partial EFX allocation MMS-feasible valuations nice-cancelable valuations
Closest papers by meaning
- EF2X Exists for Four Agents (AAAI 2025 · similarity 0.97)
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.95)
- 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)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.93)
- On Optimal Tradeoffs between EFX and Nash Welfare (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.