Algorithm for searching an equilibrium in a routing game with piecewise constant cost functions. (English) Zbl 1411.91148
Summary: 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.
MSC:
| 91A43 | Games involving graphs |
| 91A07 | Games with infinitely many players |
| 90C35 | Programming involving graphs or networks |
| 90B20 | Traffic problems in operations research |
Keywords:
nonatomic routing games; user equilibrium; piecewise linear functions; min-cost network flowReferences:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Some recent advances in network flows, SIAM Rev., 33, 2, 175-219, (1991) · Zbl 0732.90028 |
| [2] | Beckmann, M.; McGuire, C. B.; Winsten, C. B., Studies in the Economics of Transportation, (1956), Yale University press: Yale University press, USA |
| [3] | Christofides, N., Graph Theory. An Algorithmic Approach, (1975), Academic press: Academic press, New York · Zbl 0321.94011 |
| [4] | Correa, J. R.; Schulz, A. S.; Stier-Moses, N. E., Selsh routing in capacitated networks, Math. Oper. Res., 29, 4, 961-976, (2004) · Zbl 1082.90009 |
| [5] | Devarajan, S., A note on network equilibrium and noncooperative games, Trans. Port. Res. B, 15, 6, 421-426, (1981) |
| [6] | De Palma, A. and Nesterov, Y. [1998] Optimization formulations and static equilibrium in congested transportation networks, CORE Discussion Paper 9861, Universite Catholique de Louvain, Louvain-la-Neuve, Belgium. |
| [7] | De Palma, A.; Nesterov, Y., Stationary dynamic solutions in congested transportation networks: Summary and perspectives, Netw. Spat. Econ, 3, 3, 371-395, (2003) |
| [8] | Nisan, N.; Nisan, N.; Roughgarden, T.; Tardos, E.; Vazirani, V. V., Algorithmic Game Theory, (2007), Cambridge University Press: Cambridge University Press, NY, USA · Zbl 1130.91005 |
| [9] | Ovchinnikov, S., Max-Min Representation of piecewise linear functions, Contrib. Algebra Geom., 43, 1, 297-302, (2002) · Zbl 0996.26007 |
| [10] | Parfenov, A. P.; Platonov, A. V.; Smirnov, N. V., Flow optimization in networks with piecewise linear gains and cost functions, Processy Upravleniya I Ustojchivost: Trudy 38 Nauchnoj Konferencii Aspirantov i Studentov, 592-598, (2007), Izdatel’stro SPbGu: Izdatel’stro SPbGu, Saint Petersburg, Russia |
| [11] | Smith, M. J., Two alternative definitions of traffic equilibrium, Transport. Res B, 18, 1, 63-65, (1984) |
| [12] | Wardrop, J. G., Some theoretical aspects of road traffic research, Proc. Inst. Civil Eng. II, 1, 325-378, (1952) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
