Abstract
We investigate the effectiveness of Stackelberg strategies for atomic congestion games with unsplittable demands. In our setting, only a fraction of the players are selfish, while the rest are willing to follow a predetermined strategy. A Stackelberg strategy assigns the coordinated players to appropriately selected strategies trying to minimize the performance degradation due to the selfish players. We consider two orthogonal cases, namely linear congestion games with arbitrary strategies and congestion games on parallel links with arbitrary non-negative and non-decreasing latency functions. We restrict our attention to pure Nash equilibria and derive strong upper and lower bounds on the Price of Anarchy under different Stackelberg strategies.
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
Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact Price of Anarchy for Polynomial Congestion Games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 218–229. Springer, Heidelberg (2006)
Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: STOC 2005, pp. 57–66 (2005)
Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: STOC 2005, pp. 67–73 (2005)
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish Routing in Capacitated Networks. Mathematics of Operations Research 29(4), 961–976 (2004)
Correa, J.R., Stier-Moses, N.E.: Stackelberg Routing in Atomic Network Games. Technical Report DRO-2007-03, Columbia Bussiness School (2007)
Czumaj, A.: Selfish Routing on the Internet. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, Boca Raton, USA (2004)
Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: Nash Equilibria in Discrete Routing Games with Convex Latency Functions. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 645–657. Springer, Heidelberg (2004)
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)
Kaporis, A.C., Spirakis, P.G.: The Price of Optimum in Stackelberg Games on Arbitrary Single Commodity Networks and Latency Functions. In: SPAA 2006, pp. 19–28 (2006)
Karakostas, G., Kolliopoulos, S.: Stackelberg Strategies for Selfish Routing in General Multicommodity Networks. Technical Report AdvOL 2006/08, McMaster University (2006)
Korilis, Y.A., Lazar, A.A., Orda, A.: Achieving Network Optima Using Stackelberg Routing Strategies. IEEE/ACM Transactions on Networking 5(1), 161–173 (1997)
Koutsoupias, E., Papadimitriou, C.: Worst-case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Kumar, V.S.A., Marathe, M.V.: Improved Results for Stackelberg Strategies. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 776–787. Springer, Heidelberg (2002)
Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: A New Model for Selfish Routing. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 547–558. Springer, Heidelberg (2004)
Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65–67 (1973)
Roughgarden, T.: The Price of Anarchy is Independent of the Network Topology. Journal of Computer and System Sciences 67(2), 341–364 (2003)
Roughgarden, T.: Stackelberg Scheduling Strategies. SIAM Journal on Computing 33(2), 332–350 (2004)
Sharma, Y., Williamson, D.P.: Stackelberg Thresholds in Network Routing Games. In: EC 2007 (to appear, 2007)
Swamy, C.: The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games. In: SODA 2007 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fotakis, D. (2007). Stackelberg Strategies for Atomic Congestion Games. In: Arge, L., Hoffmann, M., Welzl, E. (eds) Algorithms – ESA 2007. ESA 2007. Lecture Notes in Computer Science, vol 4698. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75520-3_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-75520-3_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75519-7
Online ISBN: 978-3-540-75520-3
eBook Packages: Computer ScienceComputer Science (R0)