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

作     者：Parfenov, Andrey 

作者机构：St Petersburg State Univ St Petersburg Russia St Petersburg Inst Econ & Math St Petersburg Russia 

出 版 物：《INTERNATIONAL GAME THEORY REVIEW》 (国际博奕理论评论)

年 卷 期：2018年第20卷第4期

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Russian Foundation for Basic Research [16-01-00124] 

主　　题：Nonatomic routing games user equilibrium piecewise linear functions min-cost network flow 

摘      要：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.