Designing networks for selfish users is hard
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 9 (15525244), 472-481
- https://doi.org/10.1109/sfcs.2001.959923
Abstract
We consider a directed network in which every edge possesses a latency function specifying the time needed to traverse the edge given its congestion. Selfish, noncooperative agents constitute the network traffic and wish to travel from a source s to a sink t as quickly as possible. Since the route chosen by one network user affects the congestion (and hence the latency) experienced by others, we model the problem as a noncooperative game. Assuming each agent controls only a negligible portion of the overall traffic, Nash equilibria in this noncooperative game correspond to s-t flows in which all flow paths have equal latency. We give optimal inapproximability results and approximation algorithms for several network design problems of this type. For example, we prove that for networks with n nodes and continuous, nondecreasing latency functions, there is no approximation algorithm for this problem with approximation ratio less than n/2 (unless P = NP). We also prove this hardness result to be best possible by exhibiting an n/2-approximation algorithm. For networks in which the latency of each edge is a linear function of the congestion, we prove that there is no (4/3 - /spl epsi/)-approximation algorithm for the problem (for any /spl epsi/ > 0, unless P = NP); the existence of a 4/3-approximation algorithm follows easily from existing work, proving this hardness result sharp.Keywords
This publication has 28 references indexed in Scilit:
- Achieving network optima using Stackelberg routing strategiesIEEE/ACM Transactions on Networking, 1997
- Making greed work in networks: a game-theoretic analysis of switch service disciplinesIEEE/ACM Transactions on Networking, 1995
- Pricing in computer networks: motivation, formulation, and exampleIEEE/ACM Transactions on Networking, 1993
- Competitive routing in multiuser communication networksIEEE/ACM Transactions on Networking, 1993
- Exact and approximate algorithms for optimal network designNetworks, 1979
- Braess's paradox of traffic flowTransportation Research, 1970
- The optimal network problem: Some computational proceduresTransportation Research, 1969
- An investment policy to reduce the travel time in a transportation networkTransportation Research, 1968
- CORRESPONDENCE. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952
- ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952