Abstract
We consider network congestion games in which a finite number of non-cooperative users select paths. The aim is to mitigate the inefficiency caused by the selfish users by introducing taxes on the network edges. A tax vector is strongly (weakly)-optimal if all (at least one of) the equilibria in the resulting game minimize(s) the total latency. The issue of designing optimal tax vectors for selfish routing games has been studied extensively in the literature. We study for the first time taxation for networks with atomic users which have unsplittable traffic demands and are heterogeneous, i.e., have different sensitivities to taxes. On the positive side, we show the existence of weakly-optimal taxes for single-source network games. On the negative side, we show that the cases of homogeneous and heterogeneous users differ sharply as far as the existence of strongly-optimal taxes is concerned: there are parallel-link games with linear latencies and heterogeneous users that do not admit strongly-optimal taxes.
Research partially supported by an NTUA Basic Research Grant (PEBE 2009) and by an NSERC Discovery grant.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aashtiani, H.Z., Magnanti, T.L.: Equilibria on a congested transportation network. SIAM Journal of Algebraic and Discrete Methods 2, 213–226 (1981)
Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Taxes for linear atomic congestion games. In: Proceedings of the 14th Annual European Symposium on Algorithms, pp. 184–195 (2006)
Cole, R., Dodis, Y., Roughgarden, T.: Pricing network edges for heterogeneous selfish users. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 521–530 (2003)
Fleischer, L., Jain, K., Mahdian, M.: 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, pp. 277–285 (2004)
Fotakis, D.: Stackelberg strategies for atomic congestion games. Theory of Computing Systems 47(1), 218–249 (2010)
Fotakis, D., Spirakis, P.G.: Cost-balancing tolls for atomic network congestion games. Internet Mathematics 5(4), 343–364 (2008)
Gairing, M., Lücking, T., Monien, B., Tiemann, K.: Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 51–65. Springer, Heidelberg (2005)
Karakostas, G., Kolliopoulos, S.G.: Edge pricing of multicommodity networks for heteregoneous selfish users. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 268–276 (2004)
Kontogiannis, S.C., Spirakis, P.G.: Atomic selfish routing in networks: a survey. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol. 3828, pp. 989–1002. Springer, Heidelberg (2005)
Mavronicolas, M., Milchtaich, I., Monien, B., Tiemann, K.: Congestion games with player-specific constants. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 633–644. Springer, Heidelberg (2007)
Pigou, A.C.: The Economics of Welfare. Macmillan and Co., London (1920)
Rosenthal, R.W.: A class of games posessing pure Nash strategy equilibria. International Journal of Game Theory 2, 65–67 (1973)
Swamy, C.: The effectiveness of Stackelberg strategies and tolls for network congestion games. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1133–1142 (2007)
Roughgarden, T.: The price of anarchy is independent of the network topology. Journal of Computer and System Sciences 67(2), 341–364 (2003)
Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civil Engineers, Part II 1, 325–378 (1952)
Yang, H., Huang, H.-J.: The multi-class, multi-criteria traffic network equilibrium and systems optimum problem. Transportation Research B 38, 1–15 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fotakis, D., Karakostas, G., Kolliopoulos, S.G. (2010). On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds) Algorithmic Game Theory. SAGT 2010. Lecture Notes in Computer Science, vol 6386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16170-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-16170-4_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16169-8
Online ISBN: 978-3-642-16170-4
eBook Packages: Computer ScienceComputer Science (R0)