Research map / Learning theory and algorithms / Submodular and game algorithms
Epistemic EFX Allocations Exist for Monotone Valuations
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 that epistemic EFX (EEFX) allocations always exist for any number of agents with general monotone valuations, and shows PLS-hardness and exponential query lower bounds for identical submodular valuations.
Problem
Whether epistemic EFX allocations, a relaxation of EFX, exist for an arbitrary number of agents with general monotone valuations, and how hard they are to compute.
Approach
Builds an EEFX-graph over the bundles of an EFX allocation for identical valuations, finds a matching of bundles whose neighbourhood is exactly a set of agents, allocates those bundles and recurses on the remaining agents; hardness is obtained by reducing two-agent EFX computation to EEFX via heavy dummy items.
Key results
- EEFX allocations are shown to exist for any number of agents with general monotone valuations, answering an open question affirmatively.
- Computing EEFX for identical submodular valuations is PLS-hard, even for three agents, via reduction from two-agent EFX.
- Any deterministic algorithm needs Omega((1/k) C(2k+1,k)) value queries to compute EEFX with identical submodular valuations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| extend EEFX existence guarantees to arbitrary numbers of agents with general monotone valuations | EEFX allocation · Fair division with monotone valuations | existence of EEFX allocation | Helped |
| consider arbitrary numbers of agents with identical submodular valuations | EEFX allocation problem · Identical submodular valuations | computational complexity | Hurt |
| consider EEFX allocation for arbitrary numbers of agents with identical submodular valuations | EEFX allocation problem · Identical submodular valuations; |M|=2k+n-1 items | query complexity: Ω(\frac{1}{k} {2k+1 \choose k}) | Hurt |
Surprising findings
- Maximum Nash welfare allocations may fail to be EEFX, shown by a two-agent three-item example.
Limitations
- Existence is non-constructive in polynomial time: hardness results show the problem is PLS-hard and query-expensive for submodular valuations.
- Polynomial-time computability for monotone valuations is not established; the existence algorithm relies on an EFX allocation for identical valuations, which itself is only known to exist.
- Open whether EEFX is compatible with EF1 or Nash welfare.
Experimental setup
Builds on: EFX epistemic EFX EF1 Hall's marriage theorem
Closest papers by meaning
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.96)
- (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.94)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.94)
- Epistemic Pairwise Maximin Share (NeurIPS 2026 · similarity 0.94)
- EF2X Exists for Four Agents (AAAI 2025 · similarity 0.94)
- Nearly Equitable Allocations beyond Additivity and Monotonicity (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.