On Fair and Efficient Solutions for Budget Apportionment

This works deals with an apportionment problem recently introduced in [9]. In this problem involving multiple agents, it is desirable to propose fair and efficient solutions. Several alternative notions of fairness exist but combining efficiency with fairness is often impossible, and a trade-off has to be made. We first study the computation of almost fair and approximately efficient solutions, and we determine when these two goals can be met. Afterwards, we characterize the price of fairness which bounds the loss of efficiency caused by imposing fairness or one of its relaxations.