×

zbMATH — the first resource for mathematics

On Stackelberg strategies in affine congestion games. (English) Zbl 1404.91045
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 132-145 (2015).
Summary: We investigate the efficiency of some Stackelberg strategies in congestion games with affine latency functions. A Stackelberg strategy is an algorithm that chooses a subset of players and assigns them a prescribed strategy with the purpose of mitigating the detrimental effect that the selfish behavior of the remaining uncoordinated players may cause to the overall performance of the system. The efficiency of a Stackelberg strategy is measured in terms of the price of anarchy of the pure Nash equilibria they induce. Three Stackelberg strategies, namely largest latency first, cover and scale, were already considered in the literature and non-tight upper and lower bounds on their price of anarchy were given. We reconsider these strategies and provide the exact bound on the price of anarchy of both largest latency first and cover and a better upper bound on the price of anarchy of scale.
For the entire collection see [Zbl 1326.68026].

MSC:
91A43 Games involving graphs
91A65 Hierarchical games (including Stackelberg games)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211–1233 (2011) · Zbl 1231.91008 · doi:10.1137/090748986
[2] Awerbuch, B., Azar, Y., Epstein, L.: The price of routing unsplittable flow. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 57–66. ACM Press (2005) · Zbl 1192.90099
[3] Bhawalkar, K., Gairing, M., Roughgarden, T.: Weighted congestion games: price of anarchy, universal worst-case examples, and tightness. ACM Trans. Econ. Comput. 2(4), 14 (2014) · Zbl 1287.91026 · doi:10.1145/2629666
[4] Bilò, V.: A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 215–228. Springer, Heidelberg (2013) · Zbl 1390.91017 · doi:10.1007/978-3-642-38016-7_18
[5] Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606–637 (2011) · Zbl 1237.91049 · doi:10.1007/s00453-010-9427-8
[6] Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 67–73. ACM Press (2005) · Zbl 1192.91039 · doi:10.1145/1060590.1060600
[7] Correa, J.R., Stier Moses, N.E.: Stackelberg routing in atomic network games. Technical report DRO-2007-03, Columbia Business School (2007)
[8] Fotakis, D.: Stackelberg strategies for atomic congestion games. Theor. Comput. Syst. 47(1), 218–249 (2010) · Zbl 1203.91035 · doi:10.1007/s00224-008-9152-8
[9] Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: Nash equilibria in discrete routing games with convex latency functions. J. Comput. Syst. Sci. 74(7), 1199–1225 (2008) · Zbl 1152.91324 · doi:10.1016/j.jcss.2008.07.001
[10] Karakostas, G., Kolliopoulos, S.: Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica 53(1), 132–153 (2009) · Zbl 1175.90067 · doi:10.1007/s00453-007-9018-5
[11] Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999) · Zbl 1099.91501 · doi:10.1007/3-540-49116-3_38
[12] Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: A new model for selfish routing. Theoret. Comput. Sci. 406(3), 187–206 (2008) · Zbl 1154.91011 · doi:10.1016/j.tcs.2008.06.045
[13] Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[14] Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33(2), 332–350 (2004) · Zbl 1080.90046 · doi:10.1137/S0097539701397059
[15] Roughgarden, T.: Intrinsic robustness of the price of anarchy. Commun. ACM 55(7), 116–123 (2012) · doi:10.1145/2209249.2209274
[16] Suri, S., Tóth, C.D., Zhou, Y.: Selfish load balancing and atomic congestion games. Algorithmica 47(1), 79–96 (2007) · Zbl 1107.68026 · doi:10.1007/s00453-006-1211-4
[17] Swamy, C.: The effectiveness of Stackelberg strategies and tolls for network congestion games. ACM Trans. Algorithms 8(4), 36 (2012) · Zbl 1295.91021 · doi:10.1145/2344422.2344426
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.