Bounds on benefits and harms of adding connections to noncooperative networks.pdfVIP

Bounds on Benefits and Harms of Adding Connections to Noncooperative Networks Hisao Kameda University of Tsukuba, Tsukuba Science City 305-8573, Japan kameda@is.tsukuba.ac.jp WWW home page: http://www.osdp.is.tsukuba.ac.jp/ ˜ hkameda/ Abstract. In computer networks (and, say, transportation networks), we can con- sider the situation where each user has its own routing decision so as to minimize noncooperatively the expected passage time of its packet/job given the routing de- cisions of other users. Intuitively, it is anticipated that adding connections to such a noncooperative network may bring benefits at least to some users. The Braess paradox is, however, the first example of paradoxical cases where it is not always the case. This paper studies the bounds on the degrees of coincident cost improve- ment (benefits) and degradation (harms) for all users by adding connections to noncooperative networks. For Wardrop networks (noncooperative networks with infinitesimal users), the degree of benefits for all users can increase without bound by adding connections whereas no Wardrop network has been found for which the degree of harms can increase without bound for all users. In contrast, for Nash networks (noncooperative networks with a finite number of users), the degrees of both benefits and harms can increase without bound for all users. On the other hand, we see that, for some category of Wardrop networks, adding connections to them can bring neither benefits nor harms to all users, and that, for some ho- mogeneous networks, adding connections to them can never bring benefits to all users under any static policy including cooperative and noncooperative ones. Keywor