Ioannis Caragiannis
Abstract
We study congestion games where players aim to access a set of resources. Each player has a set of possible strategies and each resource has a function associating the latency it incurs to the players using it. Players are non--cooperative and each wishes to follow a strategy that minimizes her own latency with no regard to the global optimum. Previous work has studied the impact of this selfish behavior on system performance. In this article, we study the question of how much the performance can be improved if players are forced to pay taxes for using resources. Our objective is to extend the original game so that selfish behavior does not deteriorate performance. We consider atomic congestion games with linear latency functions and present both negative and positive results. Our negative results show that optimal system performance cannot be achieved even in very simple games. On the positive side, we show that there are ways to assign taxes that can improve the performance of linear congestion games by forcing players to follow strategies where the total latency suffered is within a factor of 2 of the minimum possible; this result is shown to be tight. Furthermore, even in cases where in the absence of taxes the system behavior may be very poor, we show that the total disutility of players (latency plus taxes) is not much larger than the optimal total latency. Besides existential results, we show how to compute taxes in time polynomial in the size of the game by solving convex quadratic programs. Similar questions have been extensively studied in the model of non-atomic congestion games. To the best of our knowledge, this is the first study of the efficiency of taxes in atomic congestion games.
- Anshelevich, E., Dasgupta, A., Kleinberg, J. M., Tardos, E., Wexler, T., and Roughgarden, T. 2004. The price of stability for network design with fair cost allocation. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS'04). 295--304. Google Scholar
Digital Library
- Awerbuch, B., Azar, Y., and Epstein, A. 2005. The price of routing unsplittable flow. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC'05). 57--66. Google ScholarDigital Library
- Azar, Y., and Epstein, A. 2005a. Convex programming for scheduling unrelated parallel machines. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC'05). 331--337. Google ScholarDigital Library
- Azar, Y., and Epstein, A. 2005b. The hardness of network design for unsplittable flow with selfish users. In Proceedings of the 3rd Workshop on Approximation and Online Algorithms (WAOA'05). 41--54. Google ScholarDigital Library
- Azar, Y., Epstein, L., Richter, Y., and Woeginger, G. 2004. All-norm approximation algorithms. J. Algo. 52, 2, 120--133. Google ScholarDigital Library
- Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., and Moscardelli, L. 2006. Tight bounds for selfish and greedy load balancing. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP'06). Lecture Notes in Computer Science, vol. 4051, Springer, Part I. Google ScholarDigital Library
- Caragiannis, I., Kaklamanis, C., and Kanellopoulos, P. 2008. Improving the efficiency of load balancing games through taxes. In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE'08). Lecture Notes in Computer Science, vol. 5385, Springer. Google ScholarDigital Library
- Christodoulou, G., and Koutsoupias, E. 2005a. On the price of anarchy and stability of correlated equilibria of linear congestion games. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05). Lecture Notes in Computer Science, vol. 3669, Springer. Google ScholarDigital Library
- Christodoulou, G. and Koutsoupias, E. 2005b. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC'05). 67--73. Google ScholarDigital Library
- Chung, S. and Murty, K. 1981. Polynomially bounded ellipsoid algorithms for convex quadratic programming. In Nonlinear Programming, Vol. 4. Academic Press.Google Scholar
- Cole, R., Dodis, Y., and Roughgarden, T. 2003. Pricing network edges for heterogeneous selfish users. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC'03). 521--530. Google ScholarDigital Library
- Cole, R., Dodis, Y., and Roughgarden, T. 2006. How much can taxes help selfish routing? J. Comput. Syst. Sci. 72, 3, 444--467. Google ScholarDigital Library
- Czumaj, A. and Vöcking, B. 2007. Tight bounds for worst-case equilibria. ACM Trans. Algor. 3, 1. Google ScholarDigital Library
- Fleischer, L., Jain, K., and Mahdian, M. 2004. 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'04). 277--285. Google ScholarDigital Library
- Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2002. The structure and complexity of nash equilibria for a selfish routing game. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP'02). Lecture Notes in Computer Science, vol. 2380, Springer. Google ScholarDigital Library
- Fotakis, D., Kontogiannis, S., and Spirakis, P. 2005. Selfish unsplittable flows. Theoret. Comput. Sci. 340, 3, 514--538. Google ScholarDigital Library
- Fotakis, D., and Spirakis, P. 2007. Cost-balancing tolls for atomic network congestion games. In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE'07). Lecture Notes in Computer Science, vol. 4858, Springer. Google ScholarDigital Library
- Gairing, M., Lücking, T., Mavronicolas, M., and Monien, B. 2004. Computing nash equilibria for scheduling on restricted parallel links. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'04). 613--622. Google ScholarDigital Library
- Gairing, M., Monien, B., and Tiemann, K. 2006. Routing (un-) splittable flow in games with player-specific latency functions. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP'06). Lecture Notes in Computer Science, vol. 4051, Springer, Part I. Google ScholarDigital Library
- Karakostas, G., and Kolliopoulos, S. 2004. Edge pricing of multicommodity networks for heterogeneous selfish users. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS'04). 268--276. Google ScholarDigital Library
- Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2003. Approximate equilibria and ball fusion. Theory Comput. Syst. 36, 6, 683--693.Google ScholarCross Ref
- Koutsoupias, E., and Papadimitriou, C. 1999. Worst-case equilibria. In Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS'99). Lecture Notes in Computer Science, vol. 1563, Springer. Google ScholarDigital Library
- Lücking, T., Mavronicolas, M., Monien, B., and Rode, M. 2008. A new model for selfish routing. Theoret. Comput. Sci. 406, 2, 187--206. Google ScholarDigital Library
- Mavronicolas, M., and Spirakis, P. 2007. The price of selfish routing. Algorithmica 48, 1, 91--126. Google ScholarDigital Library
- Milchtaich, I. 1996. Congestion games with player-specific payoff functions. Games Eco. Behav. 13, 111--124.Google Scholar
- Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press. Google ScholarDigital Library
- Papadimitriou, C. 2001. Algorithms, games and the internet. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC'01). 749--753. Google ScholarDigital Library
- Rosenthal, R. 1973. A class of games possessing pure-strategy nash equilibria. International J. Game Theory 2, 65--67.Google ScholarCross Ref
- Roughgarden, T., and Tardos, E. 2002. How bad is selfish routing? J. ACM 49, 2, 236--259. Google ScholarDigital Library
- Suri, S., Tóth, T., and Zhou, Y. 2007. Selfish load balancing and atomic congestion games. Algorithmica 47, 1, 79--96. Google ScholarDigital Library
- Swamy, C. 2007. The effectiveness of stackelberg strategies and tolls for network congestion games. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). 1133--1142. Google ScholarDigital Library
Index Terms
- Taxes for linear atomic congestion games
Recommendations
Dynamic Taxes for Polynomial Congestion Games
Special Issue on EC'16We consider the efficiency of taxation in congestion games with polynomial latency functions along the line of research initiated by Caragiannis et al. [ACM Transactions on Algorithms, 2010], who focused on both pure and mixed Nash equilibria in games ...
Pure Nash equilibria in player-specific and weighted congestion games
Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there exist pure equilibria for both of these variants in ...
Altruism in Atomic Congestion Games
This article studies the effects of altruism, a phenomenon widely observed in practice, in the model of atomic congestion games. Altruistic behavior is modeled by a linear trade-off between selfish and social objectives. Our model can be embedded in the ...
Comments