Efficiency loss in a network resource allocation game

Efficiency loss in a network resource allocation game

0.00 Avg rating0 Votes
Article ID: iaor20072542
Country: United States
Volume: 29
Issue: 3
Start Page Number: 407
End Page Number: 435
Publication Date: Aug 2004
Journal: Mathematics of Operations Research
Authors: ,
Abstract:

We explore the properties of a congestion game in which users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we establish that the aggregate utility received by the users is at least 3/4 of the maximum possible aggregate utility. We also consider extensions to a network context, where users submit individual payments for each link in the network they may wish to use. In this network model, we again show that the selfish behavior of the users leads to an aggregate utility that is no worse than 3/4 of the maximum possible aggregate utility. We also show that the same analysis extends to a wide class of resource allocation systems where end users simultaneously require multiple scarce resources. These results form part of a growing literature on the ‘price of anarchy,’ i.e., the extent to which selfish behavior affects system efficiency.

Reviews

Required fields are marked *. Your email address will not be published.