M.Sc Thesis

M.Sc StudentRichman Oran
SubjectUniqueness of the Nash Equilibrium in Competitive Routing
DepartmentDepartment 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.