New Results on Approximate EFX Allocations for Indivisible Goods
A new paper on arXiv (2406.12413) presents improved existence guarantees for approximate envy-free allocations of indivisible goods. The authors show that 2/3-EFX allocations exist when there are at most seven agents, when agents' valuations take at most three values, or when valuations are represented by a multigraph. This extends prior work which established exact EFX for up to three agents and 0.618-EFX for any number of agents. The results relax the notion of EFX to achieve broader existence.
Key facts
- Paper arXiv:2406.12413
- Studies allocation of indivisible goods to agents with additive valuations
- Goal is approximate envy-freeness up to any good (α-EFX)
- Exact EFX known for ≤3 agents, two-valued valuations, or graph-representable valuations
- 0.618-EFX known for any number of agents
- New result: 2/3-EFX exists for ≤7 agents
- New result: 2/3-EFX exists for three-valued valuations
- New result: 2/3-EFX exists for multigraph-representable valuations
Entities
Institutions
- arXiv