Abstract
We consider the Wardrop model with splittable traffic and externalities applied to the parallel transportation network. These externalities are introduced into the players’ latency functions as a tool of the system’s influence on the equilibrium distribution of traffic flows and also on the PoA values. In the general case, the externalities can be interpreted as elements of centralized control, which can be included, e.g., in traffic rules (speed-limit signs, controlled traffic lights), pricing policy for public transport, fuel, etc. This paper investigates the influence of traffic lane rules on the Price of Anarchy. We show that for the parallel transportation system there exist externality values such that the equilibrium and optimal profiles will coincide with one another and the Price of Anarchy will be equal to 1. Also we propose the socialization procedure of user behavior for which the parallel transportation system ensures an optimal profile of user behavior and the same value of the social costs as in the optimal profile with initial externalities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Acemoglu, D., Ozdaglar, A.: Flow control, routing, and performance from service provider viewpoint. LIDS report, 74 (2004)
Azariadis, C., Chen, B.-L., Lu, C.-H., Wang, Y.-C.: A two-sector model of endogenous growth with leisure externalities. J. Econ. Theory 148, 843–857 (2013)
Braess, D.: Uber ein Paradoxon der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1968)
Bramoullè, Y., Kranton, R.: Public goods in networks. J. Econ. Theory 135, 478–494 (2007)
Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. Theor. Comput. Sci. 410, 3327–3336 (2009)
Cole, R. Dodis, Y., Roughgarden, T.: Pricing network edges for heterogeneous selfish users. In: Proceedings of the 4th ACM conference on Electronic commerce. pp. 98–107 (2003)
Cole, R., Dodis, Y., Roughgarden, T.: How much can taxes help selfish routing? J. Comput. Syst. Sci. 72, 444–467 (2006)
Easley, D., Kleinberg, J.: Networks, Crowds, and markets: reasoning about highly connected world. Cambridge University Press, Cambridge (2010)
Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: Proceedings of the Fourty-Fifth Annual IEEE symposium on foundations of computer science. pp. 277-285 (2004)
Fleischer, L.: Linear tolls suffice: new bounds and algorithms for tolls in single source networks. Theor. Comput. Sci. 348, 217–225 (2005)
Gao, H., Mazalov, V.V., Xue, J.: Optimal parameters of service in a public transportation market with pricing. J. Adv. Transp. (2020). https://doi.org/10.1155/2020/6326953
Holzman, R., Monderer, D.: Strong equilibrium in network congestion games: increasing versus decreasing costs. Int. J. Game Theory 44, 647–666 (2015)
Jacobs, J.: The Economy of Cities. Random House, New York (1969)
Jahn, O., Möhring, R.H., Schulz, A.S., Stier-Moses, N.E.: System-optimal routing of traffic flows with user constraints in networks with congestion. Op. Res. 53, 600–616 (2003)
Karakostas, G., Kolliopoulos, S.G.: Edge pricing of multicommodity networks for heterogeneous selfish users. In: Proceedings of the Fourty-Fifth annual IEEE symposium on foundations of computer science. pp. 268-276 (2004)
Karakostas, G., Kim, T., Viglas, A., Xia, H.: On the degradation of performance for traffic networks with oblivious users. J. Transp. Res. Part B. 45, 364–371 (2011)
Kuang, Z., Lian, Z., Lien, J.W., Zheng, J.: Serial and parallel duopoly competition in multi-segment transportation routes. Transp. Res. Part E: Logist. Transp. Rev. 133, 101821 (2020)
Kuang, Z., Mazalov, V.V., Tang, X., Zheng, J.: Transportation network with externalities. J. Comput. Appl. Math. 382, 113091 (2021)
Lien, J.W., Mazalov, V.V., Melnik, A.V., Zheng, J.: Wardrop equilibrium for networks with the BPR latency function. Discr. Optim. Op. Res. LNCS 9869, 37–49 (2016)
Mak, V., Seale, D.A., Gishces, E.J., Braess: The, paradox and coordination failure in directed networks with mixed externalities. Prod. Op. Manag. 27(4), 717–733 (2018)
Mazalov, V., Chirkova, J.: Networking Games. Network Forming Games and Games on Networks, p. 322. Academic Press, Cambridge (2019)
Mazalov, V.V., Melnik, A.V.: Equilibrium prices and flows in the passenger traffic problem. Int Game Theory Rev. 18, 1–19 (2016)
Milchtaich, I.: Network, topology and the efficiency of equilibrium. Games Econ. Behav. 57(2), 321–346 (2006)
Papadimitriou, C.H., Koutsoupias, E.: Worst-case equilibria. LNSC 1563, 404–413 (1999)
Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67, 341–364 (2003)
Roughgarden, T., Tardos, E.: How bad is selfish routing?. In: Proceedings of the 41st annual IEEE symposium on foundations of computer science. pp. 93–102 (2000)
Sheffi, Y.: Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, Englewood Cliffs, New Jersey (1985)
U.S. Bureau of Public Roads: Traffic Assignment Manual, U.S. Department of Commerce, Washington, D.C., (1964)
Wardrop, J.G.: Some theoretical aspects of road traffic research. ICE Proc. Eng. Divi. 1, 325–362 (1952)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is supported by the Russian Science Foundation (grant No. 22-11-20015)
Rights and permissions
About this article
Cite this article
Chirkova, J.V., Mazalov, V.V. Optimal externalities in a parallel transportation network. Optim Lett 16, 1971–1989 (2022). https://doi.org/10.1007/s11590-022-01864-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-022-01864-y