Topological uniqueness of the Nash equilibrium for selfish routing with atomic users

Topological uniqueness of the Nash equilibrium for selfish routing with atomic users

0.00 Avg rating0 Votes
Article ID: iaor200948532
Country: United States
Volume: 32
Issue: 1
Start Page Number: 215
End Page Number: 232
Publication Date: Feb 2007
Journal: Mathematics of Operations Research
Authors: ,
Keywords: networks: flow
Abstract:

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 (2005) 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.

Reviews

Required fields are marked *. Your email address will not be published.