Fair and efficient allocation of indivisible items under category constraints

We study the problem of fairly allocating indivisible goods and chores under category constraints. There are n agents and m items, partitioned into categories with capacity limits, and an allocation is feasible if every bundle respects these limits. For two agents, Shoshan et al. (2023) gave a polynomial-time algorithm for finding a Pareto-optimal allocation satisfying EF[1,1], a relaxed form of envy-freeness. Extending this beyond two agents was open. We show that for any number n of agents and any number k of categories, there exists a Pareto-optimal allocation such that each agent can be made envy-free by reallocating at most min{k+1,n}(n−1) items. We also give a polynomial-time algorithm for computing such an allocation when n is a constant. Our approach uses a new application of the Knaster-Kuratowski-Mazurkiewicz (KKM) lemma on a simplex of agent weights, which may be of independent interest.