This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Richman, O. Articles by Shimkin, N. Search for Related Content

Topological Uniqueness of the Nash Equilibrium for Selfish Routing with Atomic Users

Department of Electrical Engineering, Technion–Israel Institute of Technology, Haifa 32000, Israel
Department of Electrical Engineering, Technion–Israel Institute of Technology, Haifa 32000, Israel
roran{at}tx.technion.ac.il
shimkin{at}ee.technion.ac.il, http://www.ee.technion.ac.il/people/shimkin/

We consider the problem of selfish routing in a congested network shared by several users, where each user wishes to minimize the cost of its own flow. Users are atomic, in the sense that each has a nonnegligible amount of flow demand, and flows may be split over different routes. The total cost for each user is the sum of its link costs, which, in turn, may depend on the user’s own flow as well as the total flow on that link. Our main interest here is network topologies that ensure uniqueness of the Nash equilibrium for any set of users and link cost functions that satisfy some mild convexity conditions. We characterize the class of two-terminal network topologies for which this uniqueness property holds, and show that it coincides with the class of nearly parallel networks that was recently shown by Milchtaich [Milchtaich, I. 2005. Topological conditions for uniqueness of equilibrium in networks. Math. Oper. Res. 30 225–244] to ensure uniqueness in nonatomic (or Wardrop) routing games. We further show that uniqueness of the link flows holds under somewhat weaker convexity conditions, which apply to the mixed Nash-Wardrop equilibrium problem. We finally propose a generalized continuum-game formulation of the routing problem that allows for a unified treatment of atomic and nonatomic users.

Key Words: selfish routing; congested networks; Nash equilibrium; Wardrop equilibrium; continuum games
History: Received: October 21, 2004; revision received: September 21, 2005;