ON THE NASH PRODUCT SHARE CRITERION FOR FAIR ALLOCATION PROBLEMS

Abstract

Allocating indivisible items between agents in a fair manner is a fundamental problem that has attracted a lot of interests in the last decades due to the wide range of its applications. There are several common criteria for defining what a fair allocation is, including: max-min share, proportional share, min-max share, envy-freeness, CEEI. In this paper, we introduce a new notion of fairness, called Nash-product share, which can be determined through computing an allocation of maximum Nash-product welfare, assuming that all agents have the same additive utilities. An allocation satisfies this fairness criterion is called a Nash-product fair allocation. We first show that computing the Nash-product share of every agent is NP-hard, even with two agents only. In addition, we prove that the problem of testing the existence of a Nash-product fair allocation is an NP-hard problem when the number of agents is part of the input. Finally, since a Nash-product fair allocation does not always exist, we investigate the problem that, given a problem instance, asks for the largest value for which there is an allocation such that every agent receives a subset of items of values of at least times her Nash-product share. For the case where the number of agents is constant, we present a polynomial-time approximation scheme (PTAS).