The price of anarchy is independent of the network topology

Abstract

We study the degradation in network performance caused by the selfish behavior of noncooperative network users. We consider a directed network in which each edge possesses a latency function describing the common latency incurred by all traffic on the edge as a function of the edge congestion. Given a rate of traffic between each pair of nodes in the network, we aspire toward an assignment of traffic to paths in which the sum of all travel times (the total latency) is minimized; however, in many settings network users are free to route their traffic in a selfish manner, without regard to the total latency. We therefore assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths (a Nash equilibrium) will not 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, defined as the worst possible ratio between the total latency of a Nash equilibrium and of a minimum-latency routing of the traffic.In this paper, we show that the underlying network topology plays no role in the determination of the price of anarchy. Specifically, we show 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 on a set 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. Informally, these results imply that the inefficiency inherent in a flow at Nash equilibrium stems from the inability of selfish users to discern which of two competing routes is superior and not from the topological complexity arising from the diverse intersections of many paths belonging to different commoditie.Our proof techniques also give powerful methods for computing the price of anarchy with respect to an arbitrary class of latency functions. We apply these methods to function classes that have been well studied in the literature (such as degree-bounded polynomials and functions of the form $\ell(x) = (u—x)—1} that are used to model edges with capacity u), thereby achieving the first tight analyses of the price of anarchy for significant classes of latency functions outside the class of linear functions.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 212 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.