{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:44:58Z","timestamp":1760233498320,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,1,9]],"date-time":"2021-01-09T00:00:00Z","timestamp":1610150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 2008 research project COGENT (COmputational and GamE-theoretic aspects of uncoordinated NeTworks)"],"award-info":[{"award-number":["PRIN 2008 research project COGENT (COmputational and GamE-theoretic aspects of uncoordinated NeTworks)"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider the problem of determining a routing in all-optical networks, in which some couples of nodes want to communicate. In particular, we study this problem from the point of view of a network provider that has to design suitable payment functions for non-cooperative agents, corresponding to the couples of nodes wishing to communicate. The network provider aims at inducing stable routings (i.e., routings corresponding to Nash equilibria) using a low number of wavelengths. We consider three different kinds of local knowledge that agents may exploit to compute their payments, leading to three corresponding information levels. Under complete information, the network provider can design a payment function, inducing the agents to reach a Nash equilibrium mirroring any desired routing. If the price to an agent is computed only as a function of the wavelengths used along connecting paths (minimal level) or edges (intermediate level), the most reasonable functions either do not admit Nash equilibria or admit very inefficient ones, i.e., with the largest possible price of anarchy. However, by suitably restricting the network topology, a constant price of anarchy for chains and rings and a logarithmic one for trees can be obtained under the minimal and intermediate levels, respectively.<\/jats:p>","DOI":"10.3390\/a14010015","type":"journal-article","created":{"date-parts":[[2021,1,10]],"date-time":"2021-01-10T19:55:56Z","timestamp":1610308556000},"page":"15","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Nash Equilibria in Non-Cooperative All-Optical Networks"],"prefix":"10.3390","volume":"14","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica e Fisica \u201cEnnio De Giorgi\u201d, University of Salento, Provinciale Lecce-Arnesano, P.O. Box 193, 73100 Lecce, Italy"}]},{"given":"Michele","family":"Flammini","sequence":"additional","affiliation":[{"name":"GSSI Institute, Viale Francesco Crispi 7, 67100 L\u2019Aquila, Italy"}]},{"given":"Luca","family":"Moscardelli","sequence":"additional","affiliation":[{"name":"Dipartimento di Economia, University of Chieti-Pescara, Viale Pindaro 42, 65125 Pescara, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1109\/49.57798","article-title":"Dense wavelength division multiplexing networks: Principles and applications","volume":"8","author":"Brackett","year":"1990","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_2","unstructured":"Beauquier, B., Bermond, J.C., Gargano, L., Hell, P., Perennes, S., and Vaccaro, U. (1997, January 1). Graph Problems Arising from Wavelength-Routing in All- Optical Networks. Proceedings of the 2nd Workshop on Optics and Computer Science (Part of IPPS\u201997), Geneva, Switzerland."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gargano, L., and Vaccaro, U. (2000). Routing in All\u2013Optical Networks: Algorithmic and Graph\u2013Theoretic Problems. Numbers, Information and Complexity, Kluwer Academic.","DOI":"10.1007\/978-1-4757-6048-4_45"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., and Shenker, S. (2003, January 13\u201316). On a network creation game. Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), Boston, MA, USA.","DOI":"10.1145\/872035.872088"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., and Talwar, K. (2004, January 13\u201315). The complexity of pure equilibria. Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, USA.","DOI":"10.1145\/1007352.1007445"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3305","DOI":"10.1016\/j.tcs.2008.01.004","article-title":"The structure and complexity of Nash equilibria for a selfish routing game","volume":"410","author":"Fotakis","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/game.1996.0027","article-title":"Congestion games with player-specific payoff functions","volume":"13","author":"Milchtaich","year":"1996","journal-title":"Games Econ. Behav."},{"key":"ref_8","unstructured":"Owen, G. (1995). Game Theory, Academic Press. [3rd ed.]."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., and Yannakakis, M. (1994, January 23\u201325). On complexity as bounded rationality. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (STOC), Montreal, QC, Canada.","DOI":"10.1145\/195058.195445"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01737559","article-title":"A class of games possessing pure-strategy Nash equilibria","volume":"2","author":"Rosenthal","year":"1973","journal-title":"Int. J. Game Theory"},{"key":"ref_11","unstructured":"Vetta, A. (2002, January 16\u201319). Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Vancouver, BC, Canada."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., and Papadimitriou, C. (1999, January 4\u20136). Worst-case equilibria. Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Trier, Germany.","DOI":"10.1007\/3-540-49116-3_38"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., and Spirakis, P. (2001, January 6\u20138). The price of selfish routing. Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC), Crete, Greece.","DOI":"10.1145\/380752.380846"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/506147.506153","article-title":"How bad is selfish routing?","volume":"49","author":"Roughgarden","year":"2002","journal-title":"J. ACM"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V.V. (2007). Algorithmic Game Theory, Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"4332","DOI":"10.1016\/j.disc.2009.01.011","article-title":"Nash equilibria in all-optical networks","volume":"309","author":"Georgakopoulos","year":"2009","journal-title":"Discret. Math."},{"key":"ref_17","unstructured":"Mertikopoulos, P., Moustakas, A.L., and Tzanakaki, A. (2016). Boltzmann meets Nash: Energy-efficient routing in optical networks under uncertainty. arXiv."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Pavel, L. (2012). Game Theory for Control of Optical Networks, Birkh\u00e4user.","DOI":"10.1007\/978-0-8176-8322-1"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1109\/TNET.2010.2068309","article-title":"On the complexity of the regenerator placement problem in optical networks","volume":"19","author":"Flammini","year":"2011","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"3553","DOI":"10.1016\/j.tcs.2010.05.011","article-title":"Minimizing total busy time in parallel scheduling with application to optical networks","volume":"411","author":"Flammini","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"7109","DOI":"10.1016\/j.tcs.2011.09.023","article-title":"Optimizing regenerator cost in traffic grooming","volume":"412","author":"Flammini","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/s00453-012-9693-8","article-title":"On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming","volume":"68","author":"Flammini","year":"2014","journal-title":"Algorithmica"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1721","DOI":"10.1016\/j.comnet.2008.02.009","article-title":"Selfishness, collusion and power of local search for the ADMs minimization problem","volume":"52","author":"Flammini","year":"2008","journal-title":"Comput. Netw."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"35:1","DOI":"10.1145\/1978782.1978790","article-title":"Max-Coloring and Online Coloring with Bandwidths on Interval Graphs","volume":"7","author":"Pemmaraju","year":"2011","journal-title":"ACM Trans. Algorithms"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0304-3975(99)00025-0","article-title":"On-line Routing in All-Optical Networks","volume":"221","author":"Bartal","year":"1999","journal-title":"Theor. Comput. Sci. Spec. Issue"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1051\/ita\/1995290504231","article-title":"Optimal On-Line Coloring of Circular Arc Graphs","volume":"29","author":"Slusarek","year":"1995","journal-title":"Inform. Theorique Appl."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:08:56Z","timestamp":1760159336000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,9]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010015"],"URL":"https:\/\/doi.org\/10.3390\/a14010015","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,1,9]]}}}