AAAI 2026 proof: EFX fair allocations always exist for girth-4 hypergraphs

Fair division of indivisible goods among agents is a classic problem in AI and game theory: can we allocate items so no agent envies another's bundle, even after removing any single good from that bundle? That property, called envy-free-up-to-any-good (EFX), is notoriously hard to guarantee. In fact, determining whether EFX allocations always exist even for simple additive valuations remains a major open problem. The new paper, accepted at AAAI 2026, tackles this in a structured setting where agents and goods form a hypergraph—each good (edge) links the agents (vertices) who care about it.

The authors—Thanasis Lianeas, Alkmini Sgouritsa, and Minas Marios Sotiriou—prove that if the hypergraph has girth at least 4 (no short cycles), then an EFX allocation always exists under general monotone valuations, and it can be constructed in polynomial time. For multi-hypergraphs (where multiple edges can connect the same set of vertices), they show EFX allocations also exist provided there is at least one vertex whose incident edge multiplicities do not exceed the edge size minus 2; this construction runs in pseudo-polynomial time. The results generalize prior work by Christodoulou et al. (2023) on graph settings and push the boundary of what is provably achievable in fair resource allocation, with potential applications in multi-agent systems, cloud resource sharing, and AI-driven allocation mechanisms.