New Hypergraph Study Achieves 2/3-EFX Fairness for Additive Valuations

A new paper from Ioannis Kakatelis, Thanasis Lianeas, Alkmini Sgouritsa, and Minas Marios Sotiriou, posted on arXiv on June 25, 2026, tackles the long-standing challenge of envy-free allocation of indivisible goods. They work in the multi-hypergraph setting introduced by Christodoulou et al. (2023), where agents and goods are vertices and edges respectively, and only edge endpoints derive value. The team provides significantly simpler constructions for EFX (envy-free up to any good) allocations, a concept stronger than the well-known EF1, while extending previous results by Kaviani et al. (WINE 2024).

Their first contribution is an EF2X allocation for general monotone valuations in hypergraphs with girth at least 3, built in polynomial time. For additive valuations where each edge can have multiplicity 2, they show an EF3X allocation always exists and is also polynomial-time constructible. On the approximation side, they give a simpler construction for √2/2-EFX (about 70.7%) under subadditive valuations, and improve the best known guarantee to 2/3-EFX for additive valuations with edge multiplicity 2—both in pseudo-polynomial time. These results are a significant step toward resolving the existence of exact EFX in more general settings relevant to multi-agent resource allocation.