Abstract
We introduce Colored Resource Allocation Games as a new model for selfish routing and wavelength assignment in multifiber all-optical networks. Colored Resource Allocation Games are a generalization of congestion and bottleneck games where players have their strategies in multiple copies (colors). We focus on two main subclasses of these games depending on the player cost: in Colored Congestion Games the player cost is the sum of latencies of the resources allocated to the player, while in Colored Bottleneck Games the player cost is the maximum of these latencies. We investigate the pure price of anarchy for three different social cost functions and prove tight bounds for each separate case. We first consider a social cost function which is particularly meaningful in the setting of multifiber all-optical networks, where it captures the objective of fiber cost minimization. Additionally, we consider the two usual social cost functions (maximum and average player cost) and obtain improved bounds that could not have been derived using earlier results for the standard models for congestion and bottleneck games.
This research has been co-financed by the European Union (European Social Fund–ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) — Research Funding Program: THALIS Investing in knowledge society through the European Social Fund.
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
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973)
Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14, 124–143 (1996)
Roughgarden, T.: Selfish routing and the price of anarchy. The MIT Press (2005)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Nomikos, C., Pagourtzis, A., Zachos, S.: Routing and path multicoloring. Inf. Process. Lett. 80(5), 249–256 (2001)
Nomikos, C., Pagourtzis, A., Potika, K., Zachos, S.: Routing and wavelength assignment in multifiber WDM networks with non-uniform fiber cost. Computer Networks 50(1), 1–14 (2006)
Andrews, M., Zhang, L.: Complexity of wavelength assignment in optical network optimization. In: INFOCOM. IEEE (2006)
Andrews, M., Zhang, L.: Minimizing maximum fiber requirement in optical networks. J. Comput. Syst. Sci. 72(1), 118–131 (2006)
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 (2005)
Li, G., Simha, R.: On the wavelength assignment problem in multifiber WDM star and ring networks. IEEE/ACM Trans. Netw. 9(1), 60–68 (2001)
Margara, L., Simon, J.: Wavelength assignment problem on all-optical networks with k fibres per link. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 768–779. Springer, Heidelberg (2000)
Bampas, E., Pagourtzis, A., Pierrakos, G., Potika, K.: On a noncooperative model for wavelength assignment in multifiber optical networks. IEEE/ACM Trans. Netw. 20(4), 1125–1137 (2012)
Busch, C., Magdon-Ismail, M.: Atomic routing games on maximum congestion. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol. 4041, pp. 79–91. Springer, Heidelberg (2006)
Nash, J.: Non-cooperative games. The Annals of Mathematics 54(2), 286–295 (1951)
Banner, R., Orda, A.: Bottleneck routing games in communication networks. In: INFOCOM. IEEE (2006)
Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: Mitzenmacher, M. (ed.) STOC, pp. 513–522. ACM (2009)
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 123–134. Springer, Heidelberg (2002)
Libman, L., Orda, A.: Atomic resource sharing in noncooperative networks. Telecommunication Systems 17(4), 385–409 (2001)
Kannan, R., Busch, C.: Bottleneck congestion games with logarithmic price of anarchy. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 222–233. Springer, Heidelberg (2010)
Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure Nash and strong equilibria in bottleneck congestion games. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 29–38. Springer, Heidelberg (2010)
Bilò, V., Moscardelli, L.: The price of anarchy in all-optical networks. In: Kralovic, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 13–22. Springer, Heidelberg (2004)
Bilò, V., Flammini, M., Moscardelli, L.: On Nash equilibria in non-cooperative all-optical networks. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 448–459. Springer, Heidelberg (2005)
Georgakopoulos, G.F., Kavvadias, D.J., Sioutis, L.G.: Nash equilibria in all-optical networks. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol. 3828, pp. 1033–1045. Springer, Heidelberg (2005)
Milis, I., Pagourtzis, A., Potika, K.: Selfish routing and path coloring in all-optical networks. In: Janssen, J., Prałat, P. (eds.) CAAN 2007. LNCS, vol. 4852, pp. 71–84. Springer, Heidelberg (2007)
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proceedings. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 295–304 (October 2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bampas, E., Pagourtzis, A., Pierrakos, G., Syrgkanis, V. (2013). Selfish Resource Allocation in Optical Networks. In: Spirakis, P.G., Serna, M. (eds) Algorithms and Complexity. CIAC 2013. Lecture Notes in Computer Science, vol 7878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38233-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-38233-8_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38232-1
Online ISBN: 978-3-642-38233-8
eBook Packages: Computer ScienceComputer Science (R0)