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

Andrey Parfenov
Additional contact information
Andrey Parfenov: St. Petersburg State University, Russia2St. Petersburg Institute for Economics and Mathematics, Russia

International Game Theory Review (IGTR), 2018, vol. 20, issue 04, 1-13

Abstract: 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.

Keywords: Nonatomic routing games; user equilibrium; piecewise linear functions; min-cost network flow (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198918500068
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:20:y:2018:i:04:n:s0219198918500068

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198918500068

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().