research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleCost-Balancing Tolls for Atomic Network Congestion Games
Bibtex cite IDRACTI-RU1-2007-105
Booktitle Workshop on Internet and Network Economics (WINE 2007)
Year published 2007
Pages 179-190
We investigate the existence of optimal tolls for atomic symmetric network congestion games with unsplittable traffic and arbitrary non-negative and non-decreasing latency functions.We focus on pure Nash equilibria and a natural toll mechanism, which we call cost-balancing tolls. A set of cost-balancing tolls turns every path with positive traffic on its edges into a minimum cost path. Hence any given configuration is induced as a pure Nash equilibrium of the modified game with the corresponding cost-balancing tolls. We show how to compute in linear time a set of cost-balancing tolls for the optimal solution such that the total amount of tolls paid by any player in any pure Nash equilibrium of the modified game does not exceed the latency on the maximum latency path in the optimal solution. Our main result is that for congestion games on series-parallel networks with increasing latencies, the optimal solution is induced as the unique pure Nash equilibrium of the game with the corresponding cost-balancing tolls. To the best of our knowledge, only linear congestion games on parallel links were known to admit optimal tolls prior to this work. To demonstrate the difficulty of computing a better set of optimal tolls, we show that even for 2-player linear congestion games on series-parallel networks, it is NP-hard to decide whether the optimal solution is the unique pure Nash equilibrium or there is another equilibrium of total cost at least 6/5 times the optimal cost.
Fotakis, Dimitris
Spirakis, Paul
wine019.pdf (main file)
Publication ID331