DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2018.151

Demand-Independent Optimal Tolls

Authors: Riccardo Colini-Baldeschi, Max Klimm, and Marco Scarsini

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{colinibaldeschi_et_al:LIPIcs.ICALP.2018.151,
  author =	{Colini-Baldeschi, Riccardo and Klimm, Max and Scarsini, Marco},
  title =	{{Demand-Independent Optimal Tolls}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{151:1--151:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.151},
  URN =		{urn:nbn:de:0030-drops-91553},
  doi =		{10.4230/LIPIcs.ICALP.2018.151},
  annote =	{Keywords: nonatomic congestion games, efficiency of equlibria, tolls}
}

Search Results

Documents authored by Colini-Baldeschi, Riccardo

Demand-Independent Optimal Tolls

Abstract

Cite as

Thanks for your feedback!

Could not send message