Efficiency loss in a network resource allocation game: the case of elastic supply
- 14 November 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 50 (11), 1712-1724
- https://doi.org/10.1109/tac.2005.858687
Abstract
We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent through the link. It is known that as long as users do not anticipate the effect of their actions on prices, a simple proportional pricing mechanism can maximize the sum of users' utilities minus the cost (called aggregate surplus). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, we consider the possibility that users anticipate the effect of their actions on link prices. Under the assumption that the links' marginal cost functions are convex, we establish existence of a Nash equilibrium. We show that the aggregate surplus at a Nash equilibrium is no worse than a factor of 4/spl radic/2-5 times the optimal aggregate surplus; thus, the efficiency loss when users are selfish is no more than approximately 34%.Keywords
This publication has 22 references indexed in Scilit:
- Selfish Routing in Capacitated NetworksMathematics of Operations Research, 2004
- An Adaptive Virtual Queue (AVQ) Algorithm for Active Queue ManagementIEEE/ACM Transactions on Networking, 2004
- End-to-end congestion control schemes: utility functions, random losses and ecn marksIEEE/ACM Transactions on Networking, 2003
- The Addition of Explicit Congestion Notification (ECN) to IP2001
- The price of selfish routingPublished by Association for Computing Machinery (ACM) ,2001
- REM: active queue managementIEEE Network, 2001
- Models for a self–managed InternetPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2000
- Resource pricing and the evolution of congestion controlAutomatica, 1999
- Charging and rate control for elastic trafficEuropean Transactions on Telecommunications, 1997
- Convex AnalysisPublished by Walter de Gruyter GmbH ,1970