Efficiency of Market-Based Resource Allocation among Many Participants

Market mechanisms have been suggested in the last few years as a tool for allocating shared networks resources among several competing users. In this paper, we consider the efficiency loss of such mechanisms in the presence of a large number of users. We model the user interactions as a game with a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE journal on selected areas in communications 2007-08, Vol.25 (6), p.1244-1259
Main Authors: Jia Yuan Yu, Mannor, S.
Format: Article
Language:English
Subjects:
Aggregates
Bandwidth
Broadband communication
Communication networks
Delay
Economic models
Efficiency
Game theory
Games
Large-scale systems
Markets
Mathematical models
Networks
Optimization
Resource allocation
Resource management
Routing
Sampling
Sampling methods
Studies
Utilities
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Market mechanisms have been suggested in the last few years as a tool for allocating shared networks resources among several competing users. In this paper, we consider the efficiency loss of such mechanisms in the presence of a large number of users. We model the user interactions as a game with a heterogeneous population of players characterized by random utility functions. If the utility functions are bounded, then the non-cooperative equilibrium are nearly as efficient as the social optimum with high probability when the number of users is large. This efficiency result holds for a single link with a fixed or an increasing capacity. Using a standard probabilistic analysis, we show that the efficiency loss incurred by the market mechanism decreases almost exponentially in the number of users. If, however, the utility functions are not bounded, then the loss of efficiency does not converge to zero. We also provide results for networks by sampling the users at random based on their paths.
ISSN:0733-8716
1558-0008
DOI:10.1109/JSAC.2007.070818