Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
The Efficiency and Fairness of a Fixed Budget Resource Allocation Game
verfasst von : Li Zhang
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\theta(1/\sqrt{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.