M.Sc Thesis | |

M.Sc Student | Richman Oran |
---|---|

Subject | Uniqueness of the Nash Equilibrium in Competitive Routing Problems |

Department | Department of Electrical and Computer Engineering |

Supervisor | PROF. Nahum Shimkin |

Congestion-prone
networks have long been an object of interest in engineering
and operational research, with particular interest for traffic
engineering and communication networks. In many of the relevant applications,
the network is not centrally controlled but rather shared by a number of users
who pursue their own objectives. We consider the problem of selfish routing in
networks with a finite number of users, which may differ in their cost
functions. Our main concern is existence and uniqueness of the Nash equilibrium.
Previous work had shown that in parallel network topology the Nash equilibrium
is always unique under some mild convexity assumptions. We show that there is a
larger class of networks for which the Nash equilibrium is always unique (under
the same convexity assumptions). We further show that for every network which
does not belong to that class, one can find an assignment of cost functions for
which the equilibrium is not unique. Thus, our work provides a complete
characterization of two-terminal network topologies, for which the Nash
equilibrium is unique, under broad conditions on the cost functions, and for
any number and size of network users. Our work is related to a recent paper of I.
Milchtaich, where a similar result is obtained for the problem of multi-class
routing with infinitesimal users, known also as multi-class Wardrop equilibrium
problem. We show that the problem of routing in a network with infinitesimal
users from *K* different classes can be modeled as a routing problem in
the same network but with *K* players, each with a cost function derived
from the corresponding class of users' cost functions. Therefore our results
apply also for Wardrop equilibrium analysis and, in a sense, generalize the
uniqueness results in Miltchtaich's work.