Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods

Envy-freeness is a desirable criterion when one wishes to fairly distribute a finite set of goods among two or more agents. Unfortunately, allocations satisfying this criterion may not exist in the setting where the goods are assumed to be indivisible. In this case, it is useful to settle for allocations with envy as small as possible. Adapting the framework of Chevaleyre et al. (2007), we propose a multiplicative form of the degree of envy of a given allocation and then study the approximability of the corresponding envy minimization problems. We show that these problems are APX-hard to approximate in general, but admit an FPTAS for a fixed number of agents with additive utility functions. We also present a polynomial-time algorithm for the case when the number of agents is equal to the number of goods to be distributed. In addition, we study the problem of maximizing social welfare by the average Nash product. We provide a fast greedy approximation algorithm for this problem when the agents’ utility functions are (sub)additive, and we design a PTAS for the case when all agents have the same additive utility function.