Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1094.68122
Roughgarden, Tim
On the severity of Braess's paradox: designing networks for selfish users is hard. (English)
[J] J. Comput. Syst. Sci. 72, No. 5, 922-953 (2006). ISSN 0022-0000

Summary: We consider a directed network in which every edge possesses a latency function that specifies the time needed to traverse the edge given its congestion. Selfish, noncooperative agents constitute the network traffic and wish to travel from a source vertex $s$ to a destination $t$ as quickly as possible. Since the route chosen by one network user affects the congestion experienced by others, we model the problem as a noncooperative game. Assuming that 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. A natural measure for the performance of a network used by selfish agents is the common latency experienced by users in a Nash equilibrium. Braess's Paradox is the counterintuitive but well-known fact that removing edges from a network can improve its performance. Braess's Paradox motivates the following network design problem: given a network, which edges should be removed to obtain the best flow at Nash equilibrium? Equivalently, given a network of edges that can be built, which subnetwork will exhibit the best performance when used selfishly? We give optimal inapproximability results and approximation algorithms for this network design problem. For example, we prove that there is no approximation algorithm for this problem with approximation ratio less than $n/2$, where $n$ is the number of network vertices, unless P = NP. We further show that this hardness result is the best possible, by exhibiting an $(n/2)$-approximation algorithm. We also prove tight inapproximability results when additional structure, such as linearity, is imposed on the network latency functions.Moreover, we prove that an optimal approximation algorithm for these problems is the trivial algorithm: given a network of candidate edges, build the entire network. As a consequence, we show that Braess's Paradox -- even in its worst-possible manifestations -- is impossible to detect efficiently. En route to these results, we give a fundamental generalization of Braess's Paradox: the improvement in performance that can be effected by removing edges can be arbitrarily large in large networks. Even though Braess's Paradox has enjoyed 35 years as a textbook example, our result is the first to extend its severity beyond that in Braess's original four-node network.

MSC 2000:: *68W25 Approximation algorithms
68Q17 Computational difficulty of problems
90B10 Flows in networks
90B20 Highway traffic
91A10 Noncooperative games

Keywords: selfish routing; Braess's paradox; network design; approximation algorithms

Cited in: Zbl 1103.68018

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]