Geodesic
Atomic Routing Game with Capacity Constraints
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 10 (2018) no. 1, pp. 65-82.

Voir la notice de l'article provenant de la source Math-Net.Ru

A model of an atomic routing game is considered. A network in this model has capacity constraints. Players in this game choose routes from some sources to one sink. The cost of passing each arc is determined by an increasing and convex function that depends on the number of players. Algorithms for finding the Nash equilibrium and social optimum are developed. These algorithms have a polynomial time complexity. The model can be used for transport networks with limited traffic flows.
Keywords: network games, routing games, network flows, Nash equilibrium, algorithm for finding equilibrium. 
@article{MGTA_2018_10_1_a3,
     author = {Darya A. Paltseva and Andrey P. Parfyonov},
     title = {Atomic {Routing} {Game} with {Capacity} {Constraints}},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {65--82},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a3/}
}
TY  - JOUR
AU  - Darya A. Paltseva
AU  - Andrey P. Parfyonov
TI  - Atomic Routing Game with Capacity Constraints
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2018
SP  - 65
EP  - 82
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a3/
LA  - ru
ID  - MGTA_2018_10_1_a3
ER  - 
%0 Journal Article
%A Darya A. Paltseva
%A Andrey P. Parfyonov
%T Atomic Routing Game with Capacity Constraints
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2018
%P 65-82
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a3/
%G ru
%F MGTA_2018_10_1_a3
Darya A. Paltseva; Andrey P. Parfyonov. Atomic Routing Game with Capacity Constraints. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 10 (2018) no. 1, pp. 65-82. http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a3/

[1] Parfenov A. P., “Igra marshrutizatsii s ogranicheniyami na propusknuyu sposobnost i postoyannymi funktsiyami stoimosti”, Novaya nauka: istoriya stanovleniya, sovremennoe sostoyanie, perspektivy razvitiya, Sbornik statei Mezhdunarodnoi nauchno-prakticheskoi konferentsii, Saratov, 2016, 3–10

[2] Petrosyan L. A., “Odna transportnaya teoretiko-igrovaya model na seti”, Matematicheskaya teoriya igr i ee prilozheniya, 3:4 (2011), 89–98

[3] Ford L., Falkerson D., Potoki v setyakh, Mir, M., 1966

[4] Khu T., Tselochislennoe programmirovanie i potoki v setyakh, Mir, M., 1974

[5] Beckmann M., McGuire C. B., Winsten C. B., Studies in the Economics of Transportation, Yale University Press, 1956

[6] Jose R. Correa, Andreas S. Schulz, Nicolas E. Stier Moses, “Selfish routing in capacitated networks”, Math. Oper. Res., 29:4 (2004), 961–976 | DOI | MR | Zbl

[7] de Palma A., Nesterov Y., “Stationary Dynamic Solutions in Congested Transportation Networks: Summary and Perspectives”, Networks and Spatial Economics, 2003, no. 3, 371–395

[8] Parfenov A., “Algorithm for Searching an Equilibrium in a Routing Game with Piecewise Constant Cost Functions”, International Game Theory Review, 2018, 1850006 | DOI

[9] Rosenthal W., “The Network Equilibrium Problem in Integers”, Networks, 3:1 (1973), 53–59 | DOI | MR | Zbl

[10] Suri S., Toth C., Zhou Y., “Selfish Load Balancing and Atomic Congestion Games”, Algorithmica, 47:1 (2007), 79–96 | DOI | MR | Zbl

[11] Wardrop J. G., “Some theoretical aspects of road traffic research”, Proc. Institute of Civil Engineers. Pt. II, v. 1, 1952, 325–378 | DOI