𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The price of anarchy is independent of the network topology

✍ Scribed by Tim Roughgarden


Book ID
104147700
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
258 KB
Volume
67
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis


We study the degradation in network performance caused by the selfish behavior of noncooperative network users. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. The quality of a routing of traffic is measured by the sum of travel times, also called the total latency. The outcome of selfish routing-a Nash equilibrium-does not in general minimize the total latency; hence, selfish behavior carries the cost of decreased network performance. We quantify this degradation in network performance via the price of anarchy, the worst-possible ratio between the total latency of a Nash equilibrium and of an optimal routing of the traffic. In this paper, we show that the price of anarchy is determined only by the simplest of networks. Specifically, we prove that under weak hypotheses on the class of allowable edge latency functions, the worst-case ratio between the total latency of a Nash equilibrium and of a minimum-latency routing for any multicommodity flow network is achieved by a single-commodity instance in a network of parallel links. In the special case where the class of allowable latency functions includes all of the constant functions, we prove that a network with only two parallel links suffices to achieve the worst-possible ratio. Our guarantee that simple networks always furnish worstpossible examples provides a powerful method for computing the price of anarchy with respect to an arbitrary class of latency functions. We apply this method to function classes that have been well studied in the literature, including degree-bounded polynomials and queuing delay functions. These are the first tight analyses of the price of anarchy for significant classes of latency functions outside the class of linear functions.


πŸ“œ SIMILAR VOLUMES


The Price of Independence
✍ Renato Baserga πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 64 KB