Bounds on the degree of paradoxical performance degradation in noncooperative networks

Networks, like the Internet, and distributed systems, like GRID, are shared by a number of independent users and organizations that may be regarded as independent/noncooperative decision makers. It may be expected that the entire performance of the networks will be guided to overall improvement, by the, so-called, Invisible Hand of God, if each decision maker pursues unilaterally its own performance objective by means of noncooperative decisions on, say, routing and/or load balancing. In addition, noncooperative and competitive decision making by independent decision makers will be preferred in many respects to top-down overall decision making. Nevertheless, mutually independent noncooperative decision making may bring about situations where all decision makers may suffer lower benefits than some other ways of decision making may do, as exemplified by the prisoners' dilemma mentioned in game theory. In particular, the Braess paradox shows the existence of cases where, under the scheme of independent decision making, if the degree of freedom of choices for each decision maker increases by adding new connections and/or facilities to the network, all decision makers suffer degradation of their utilities. Other examples of similar degradation have also been reported. We call such phenomena of degradation of utilities ‘paradoxes.’ This article gives an overview on various research results on the paradoxes with emphasis on the possible degrees of performance degradation in such paradoxes.