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%.
Efficiency loss in a network resource allocation game: the case of elastic supply
Ramesh Johari,Shie Mannor,J. Tsitsiklis
Published 2004 in IEEE Transactions on Automatic Control
ABSTRACT
PUBLICATION RECORD
- Publication year
2004
- Venue
IEEE Transactions on Automatic Control
- Publication date
2004-08-01
- Fields of study
Mathematics, Computer Science, Economics
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
CONCEPTS
- aggregate surplus
The total user utility minus the total network cost for a feasible allocation.
- convex marginal cost functions
Link cost derivatives that are assumed to be convex functions of the total rate on each link.
Aliases: MCF
- nash equilibrium
A stable allocation in which no user can improve its own outcome by changing its strategy alone.
- network resource allocation game
A game in which users choose data rates over a network while link costs depend on the total flow through each link.
- optimal aggregate surplus
The maximum feasible value of aggregate surplus over all allocations considered in the network model.
- proportional pricing mechanism
A pricing rule in which the charge on a link scales proportionally with the rate sent through that link.
- selfish behavior
Users acting while accounting for how their own actions influence link prices.
REFERENCES
Showing 1-50 of 50 references · Page 1 of 1