On the Complexity of Maximizing Social Welfare within Fair Allocations of Indivisible Goods
share
Fair division is a classical topic studied in various disciplines and captures many real applications. One important issue in fair division is to cope with (economic) efficiency and fairness. A natural question along this direction that receives considerable attention is: How to obtain the most efficient allocations among all the fair allocations? In this paper, we study the complexity of maximizing social welfare within envy-free up to one item (EF1) allocations of indivisible goods for both normalized and unnormalized valuations. With two agents, we show a fully polynomial time approximation scheme (FPTAS) and complement this positive result with the NP-hardness result where the latter resolves an open problem raised by the previous work. Further, when the number of agents n is a constant, we provide a bi-criteria algorithm that finds the optimal social welfare while relaxing EF1 by a factor arbitrarily close to 1. We complement this by providing several strong inapproximability results if EF1 is not allowed to relax. In particular, we demonstrate that the inapproximability becomes stronger as n increases. Last, we consider the case with general number of agents. In this case, we give a variant of the round-robin algorithm with an approximation ratio of 1/n for unnormalized valuations and provide inapproximability results of n^1/3-ε and m^1/2-ε for normalized valuations. In addition, we show that our results of bi-criteria optimization for constant n cannot be extended to the setting here, unless P=NP.
READ FULL TEXT