Computing Welfare-Maximizing Fair Allocations of Indivisible Goods

We study the computational complexity of computing allocations that are both fair and maximize the utilitarian social welfare, i.e., the sum of agents' utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). In particular, we consider the following two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair according to either EF1 or PROP1; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems.