Price of Fairness for allocating a bounded resource

Our results are twofold. We first formalize a number of properties holding for any general multi-agent problem without any special assumptions on the agent utilities. Then we introduce an allocation problem, in which each agent can consume the available bounded resource in given discrete quantities (items). The utility of each agent is given by the sum of these quantities (weights of allocated items). We distinguish two cases depending on whether disjoint sets or a shared set of items is available to the agents. Clearly, 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.