Document Open Access Logo

Demand-Independent Optimal Tolls

Authors Riccardo Colini-Baldeschi , Max Klimm , Marco Scarsini

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.151.pdf
  • Filesize: 453 kB
  • 14 pages

Document Identifiers

Author Details

Riccardo Colini-Baldeschi
  • Core Data Science Group, Facebook Inc., 1 Rathbone Place, London, W1T 1FB, UK
Max Klimm
  • School of Business and Economics, HU Berlin, Spandauer Str. 1, 10099 Berlin, Germany
Marco Scarsini
  • Dipartimento di Economia e Finanza, LUISS, Viale Romania 32, 00197 Roma, Italy

Cite As Get BibTex

Riccardo Colini-Baldeschi, Max Klimm, and Marco Scarsini. Demand-Independent Optimal Tolls. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 151:1-151:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.151

Abstract

Wardrop equilibria in nonatomic congestion games are in general inefficient as they do not induce an optimal flow that minimizes the total travel time. Network tolls are a prominent and popular way to induce an optimum flow in equilibrium. The classical approach to find such tolls is marginal cost pricing which requires the exact knowledge of the demand on the network. In this paper, we investigate under which conditions demand-independent optimum tolls exist that induce the system optimum flow for any travel demand in the network. We give several characterizations for the existence of such tolls both in terms of the cost structure and the network structure of the game. Specifically we show that demand-independent optimum tolls exist if and only if the edge cost functions are shifted monomials as used by the Bureau of Public Roads. Moreover, non-negative demand-independent optimum tolls exist when the network is a directed acyclic multi-graph. Finally, we show that any network with a single origin-destination pair admits demand-independent optimum tolls that, although not necessarily non-negative, satisfy a budget constraint.

Subject Classification

ACM Subject Classification
  • Theory of computation → Network games
Keywords
  • nonatomic congestion games
  • efficiency of equlibria
  • tolls

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Lihud Bai, Donald W. Hearn, and Siriphong Lawphongpanich. Decomposition techniques for the minimum toll revenue problem. Networks, 44:142-150, 2004. URL: http://dx.doi.org/10.1002/net.20024.
  2. Lihud Bai, Donald W. Hearn, and Siriphong Lawphongpanich. A heuristic method for the minimum toll booth problem. Journal of Global Optimization, 48:533-548, 2010. URL: http://dx.doi.org/10.1007/s10898-010-9527-7.
  3. Lihud Bai and Paul A. Rubin. Combinatorial Benders cuts for the minimum tollbooth problem. Operations Research, 57:1510-1522, 2009. URL: http://dx.doi.org/10.1287/opre.1090.0694.
  4. Martin J. Beckmann, C. B. McGuire, and Christopher B. Winsten. Studies in the Economics of Transportation. Yale University Press, New Haven, CT, 1956. Google Scholar
  5. Pia Bergendorff, Donald W. Hearn, and Motakuri V. Ramana. Congestion toll pricing of traffic networks. In P. Pardalos, D. Hearn, and W. Hager, editors, Network Optimization, volume 450 of LNE, pages 51-71. Springer, 1997. URL: http://dx.doi.org/10.1007/978-3-642-59179-2_4.
  6. Umang Bhaskar, Katrina Ligett, Leonard J. Schulman, and Chaitanya Swamy. Achieving target equilibria in network routing games without knowing the latency functions. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 31-40. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.12.
  7. Vittorio Bilò and Cosimo Vinci. Dynamic taxes for polynomial congestion games. In Proceedings of the 17th ACM Conference on Economics and Computation (EC), pages 839-856, 2016. URL: http://dx.doi.org/10.1145/2940716.2940750.
  8. Vincenzo Bonifaci, Mahyar Salek, and Guido Schäfer. Efficiency of restricted tolls in non-atomic network routing games. In G. Persiano, editor, Proceedings of the 4th Symposium on Algorithmic Game Theory (SAGT), volume 6982 of LNCS, pages 302-313, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24829-0_27.
  9. Philip N. Brown and Jason R. Marden. Avoiding perverse incentives in affine congestion games. In Proceedings of the 55th IEEE Conference on Decision and Control (CDC), pages 7010-7015, 2016. URL: http://dx.doi.org/10.1109/CDC.2016.7799349.
  10. Philip N. Brown and Jason R. Marden. The robustness of marginal-cost taxes in affine congestion games. IEEE Transactions on Automatic Control, 62:3999-4004, 2017. URL: http://dx.doi.org/10.1109/TAC.2016.2619674.
  11. Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Taxes for linear atomic congestion games. In Y. Azar and T. Erlebach, editors, Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pages 184-195. Springer, 2006. URL: http://dx.doi.org/10.1007/11841036_19.
  12. Giorgos Christodoulou, Kurt Mehlhorn, and Evangelia Pyrga. Improving the price of anarchy for selfish routing via coordination mechanisms. Algorithmica, 69:619-640, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9753-8.
  13. Richard Cole, Yevgeniy Dodis, and Tim Roughgarden. Pricing network edges for heterogeneous selfish users. In Proceedings of the 35th Annual Symposium on Theory of Computing (STOC), pages 521-530, 2003. URL: http://dx.doi.org/10.1145/780542.780618.
  14. Richard Cole, Yevgeniy Dodis, and Tim Roughgarden. How much can taxes help selfish routing? Journal of Computer and System Sciences, 72:444-467, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.09.010.
  15. Riccardo Colini-Baldeschi, Max Klimm, and Marco Scarsini. Demand-independent optimal tolls. arXiv, 2017. URL: http://arxiv.org/abs/1708.02737.
  16. Robert B. Dial. Minimal-revenue congestion pricing part I: A fast algorithm for the single-origin case. Transportation Research, Part B, 33:189-202, 1999. URL: http://dx.doi.org/10.1016/S0191-2615(98)00026-5.
  17. Robert B. Dial. Minimal-revenue congestion pricing part II: An efficient algorithm for the general case. Transportation Research, Part B, 34:645-665, 2000. URL: http://dx.doi.org/10.1016/S0191-2615(99)00046-6.
  18. Lisa Fleischer. Linear tolls suffice: New bounds and algorithms for tolls in single source networks. Theoretical Computer Science, 348:217-225, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.014.
  19. Lisa Fleischer, Kamal Jain, and Mohammad Mahdian. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 277-285, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.69.
  20. Dimitris Fotakis, George Karakostas, and Stavros G. Kolliopoulos. On the existence of optimal taxes for network congestion games with heterogeneous users. In S. Kontogiannis, E. Koutsoupias, and P. G. Spirakis, editors, Proceedings of the 3rd Symposium on Algorithmic Game Theory (SAGT), volume 6386 of LNCS, pages 162-173, 2010. URL: http://dx.doi.org/10.1007/978-3-642-16170-4_15.
  21. Dimitris Fotakis and Paul G. Spirakis. Cost-balancing tolls for atomic network congestion games. Internet Mathematics, 5(4):343-364, 2008. URL: http://dx.doi.org/10.1080/15427951.2008.10129175.
  22. Jose A. Gómez-Ibáñez and Kenneth A. Small. Road Pricing for Congestion Management: A Survey of International Practice, volume 210 of NCHRP Synthesis. National Academy Press, Washington, D.C., 1994. Google Scholar
  23. Michael A. Hall. Properties of the equilibrium state in transportation networks. Transportation Science, 12:208-216, 1978. URL: http://dx.doi.org/10.1287/trsc.12.3.208.
  24. Deren Han, Hong K. Lo, Jie Sun, and Hai Yang. The toll effect on price of anarchy when costs are nonlinear and asymmetric. European Journal of Operational Research, 186:300-316, 2008. URL: http://dx.doi.org/10.1016/j.ejor.2007.01.027.
  25. Tobias Harks, Ingo Kleinert, Max Klimm, and Rolf H. Möhring. Computing network tolls with support constraints. Networks, 65:62-285, 2015. URL: http://dx.doi.org/10.1002/net.21604.
  26. Donald W. Hearn and Motakuri V. Ramana. Solving congestion toll pricing models. In P. Marcotte and S. Nguyen, editors, Equilibrium and advanced transportation modeling, pages 109-124. Springer, New York, 1998. URL: http://dx.doi.org/10.1007/978-1-4615-5757-9_6.
  27. Martin Hoefer, Lars Olbrich, and Alexander Skopalik. Taxing subnetworks. In C. Papadimitriou and S. Zhang, editors, Proceedings of the 4th Workshop on Internet and Network Economics (WINE), volume 5385 of LNCS, pages 286-294, 2008. Google Scholar
  28. George Karakostas and Stavros G. Kolliopoulos. Edge pricing of multicommodity networks for heterogeneous selfish users. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 268-276, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.26.
  29. George Karakostas and Stavros G. Kolliopoulos. The efficiency of optimal taxes. In A. López-Ortiz and A. Hamel, editors, Proceedings of the 1st Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN), volume 3405 of LNCS, pages 3-12. Springer, 2005. URL: http://dx.doi.org/10.1007/11527954_2.
  30. George Karakostas and Stavros G. Kolliopoulos. Edge pricing of multicommodity networks for selfish users with elastic demands. Algorithmica, 53:225-249, 2009. URL: http://dx.doi.org/10.1007/s00453-008-9181-3.
  31. Frank H. Knight. Some fallacies in the interpretation of social cost. Quarterly Journal of Economics, 38(4):582-606, 1924. URL: http://dx.doi.org/10.2307/1884592.
  32. Torbjörn Larsson and Michael Patriksson. Side constrained traffic equilibrium models - analysis, computation and applications. Transportation Research, Part B, 33(4):233-264, 1999. URL: http://dx.doi.org/10.1016/S0191-2615(98)00024-1.
  33. Reshef Meir and David Parkes. When are marginal congestion tolls optimal? In Proceedings of the 9th Workshop on Agents in Traffic and Transportation (ATT), volume 1678 of CEUR Workshop Proceedings, 2016. Google Scholar
  34. Arthur C. Pigou. The Economics of Welfare. Macmillan and Co., London, 1st edition, 1920. Google Scholar
  35. Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. Watch and learn: optimizing from revealed preferences feedback. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 949-962. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897579.
  36. William H. Sandholm. Evolutionary implementation and congestion pricing. Review of Economic Studies, 69(3):667-689, 2002. URL: http://dx.doi.org/10.1111/1467-937X.t01-1-00026.
  37. William H. Sandholm. Pigouvian pricing and stochastic evolutionary implementation. Journal of Economic Theory, 132(1):367-382, 2007. URL: http://dx.doi.org/10.1016/j.jet.2005.09.005.
  38. Chandramani Singh. Marginal cost pricing for atomic network congestion games. Technical report, Department of Electrical Communication Engineering, Indian Institute of Science, 2008. Google Scholar
  39. Kenneth A. Small and Jose A. Gómez-Ibáñez. Road pricing for congestion management: the transition from theory to policy. In Tae Hoon Oum, editor, Transport Economics, chapter 16, pages 373-403. Routledge, London, 1997. Google Scholar
  40. U.S. Bureau of Public Roads. Traffic assignment manual. U.S. Department of Commerce, Urban Planning Division, 1964. Google Scholar
  41. John Glen Wardrop. Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, Part II, volume 1, pages 325-378, 1952. Google Scholar
  42. Hai Yang and Hai-Jun Huang. The multi-class, multi-criteria traffic network equilibrium and systems optimum problem. Transportation Research, Part B, 38:1-15, 2004. URL: http://dx.doi.org/10.1016/S0191-2615(02)00074-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact