Price of Fairness for Allocating a Bounded Resource
In this paper we study the problem of allocating a scarce resource among several players (or agents). A central decision maker wants to maximize the total utility of all agents. However, such a solution may be unfair for one or more agents in the sense that it can be achieved through a very unbalanced allocation of the resource. On the other hand fair/balanced allocations may be far from being optimal from a central point of view. So, in this paper we are interested in assessing the quality of fair solutions, i.e. in measuring the system efficiency loss under a fair allocation compared to the one that maximizes the sum of agents utilities. This indicator is usually called the Price of Fairness and we study it under three different definitions of fairness, namely maximin, Kalai-Smorodinski and proportional fairness. Our results are of two different types. We first formalize a number of properties holding for any general multi-agent problem without any special assumption on the agents utility sets. Then we introduce an allocation problem, where each agent can consume the resource in given discrete quantities (items), such that the maximization of the total utility is given by a Subset Sum Problem. For the resulting Fair Subset Sum Problem, in the case of two agents, we provide upper and lower bounds on the Price of Fairness as functions of an upper bound on the items size.