Polynomial-Time Approximate EFX for Chores via Flow and Matching

Abstract

We study approximate EFX allocations of indivisible chores under nonnegative additive costs. Exact EFX allocations need not exist in general. We develop a polynomial-time algorithm that computes a complete $(3+\epsilon )$-EFX allocation for any rational $0<\epsilon \le 1$, improving the previous approximation guarantee from a factor depending on the number of agents to a constant. The algorithm extends to EF$k$X, achieving a $(2+1/k+\epsilon )$-approximation for every integer $k\ge 1$. For instances with relatively few chores, the polynomial-time BRBI algorithm gives stronger guarantees. It finds exact EF$k$X allocations when $m\le 2kn$ and achieves a factor of at most $2-1/k$ when $m\le (3k-1)n$. In particular, $k=1$ and $m\le 2n$ give exact EFX. We further show that the approximation factor \(2+1/k\) is asymptotically tight for our main algorithm. We also construct a four-agent, ten-chore instance in which every complete allocation has EFX approximation factor at least $11/10$, improving upon the $20/19$ lower bound for submodular costs even under additive costs.