Algorithm for Searching an Equilibrium in a Routing Game with Piecewise Constant Cost Functions

摘要

We consider nonatomic routing games which are used to model transportation systems with a large number of agents and suggest an algorithm to search for the user equilibrium in such games, which is a generalization of the notion of Nash equilibrium. In general, finding a user equilibrium in routing games is computationally a hard problem. We consider the following subclass of routing games: games with piecewise constant cost functions, and construct an algorithm finding equilibrium in such games. This algorithm is based on the potential function method and the method of piecewise linear (PWL) costs enumeration which finds min-cost flow in a network with PWL cost functions. If each cost function increases, then the complexity of our algorithm is polynomial in the parameters of the network. But if some cost functions have decreasing points, then the complexity is exponential by the number of such points.