The efficiency and fairness of a fixed budget resource allocation game

  • Li Zhang

Proceedings of 32nd International Colloquium on Automata, Languages and Programming |

Publication

We study the resource allocation game in which price anticipating players compete for multiple divisible resources. In the scheme, each player submits a bid to a resource and receives a share of the resource according to the proportion of his bid to the total bids. Unlike the previous study (e.g.[5]), we consider the case when the players have budget constraints, i.e. each player’s total bids is fixed. We show that there always exists a Nash equilibrium when the players’ utility functions are strongly competitive. We study the efficiency and fairness at the Nash equilibrium. We show the tight efficiency bound of θ(1/m)">θ(1/m−−√) for the m player balanced game. For the special cases when there is only one resource or when there are two players with linear utility functions, the efficiency is 3/4. We extend the classical notion of envy-freeness to measure fairness. We show that despite a possibly large utility gap, any Nash equilibrium is 0.828-approximately envy-free in this game.