On Nash Equilibria in Non-Cooperative All-Optical Networks
| Autor: | Vittorio Bilò, Michele Flammini, Luca Moscardelli |
|---|---|
| Přispěvatelé: | Bilo', Vittorio, Flammini, M, Moscardelli, L., Bilò, Vittorio, Flammini, M. |
| Jazyk: | angličtina |
| Rok vydání: | 2005 |
| Předmět: |
Mathematical optimization
Computer Science::Computer Science and Game Theory lcsh:T55.4-60.8 Computer science optical networks 0102 computer and information sciences 02 engineering and technology selfish routing Network topology 01 natural sciences lcsh:QA75.5-76.95 Theoretical Computer Science symbols.namesake WDM Complete information 0202 electrical engineering electronic engineering information engineering Price of anarchy lcsh:Industrial engineering. Management engineering Price of stability Numerical Analysis price of anarchy TheoryofComputation_GENERAL algorithmic game theory 020206 networking & telecommunications Function (mathematics) Algorithmic game theory Nash equilibria Optical networks Price of anarchy Pricing of optical network services Selfish routing WDM Computational Mathematics nash equilibria Computational Theory and Mathematics 010201 computation theory & mathematics Nash equilibrium Best response pricing of optical network services symbols lcsh:Electronic computers. Computer science Algorithmic game theory Routing (electronic design automation) Epsilon-equilibrium Constant (mathematics) Congestion game |
| Zdroj: | STACS 2005 ISBN: 9783540249986 STACS Algorithms, Vol 14, Iss 15, p 15 (2021) Scopus-Elsevier Algorithms Volume 14 Issue 1 |
| Popis: | In this paper we investigate the problem in which an all-optical network provider must determine suitable payment functions for non-cooperative agents wishing to communicate so as to induce routings in Nash equilibrium using a low number of wavelengths. We assume three different information levels specifying the local knowledge that agents may exploit to compute their payments. While under complete information of all the agents and their routing strategies we show that functions can be determined that perform how centralized algorithms preserving their time complexity, knowing only the used wavelengths along connecting paths (minimal level) or along the edges (intermediate level) the most reasonable functions either do not admit equilibria or equilibria with a different color assigned to each agent, that is with the worst possible ratio between the Nash versus optimum performance, also called price of anarchy. However, by suitably restricting the network topology, a price of anarchy 25.72 has been obtained for chains and 51.44 for rings under the minimal level, and further reduced respectively to 3 and 6 under the intermediate level, up to additive factors converging to 0 as the load increases. Finally, again under the minimal level, a price of anarchy logarithmic in the number of agents has been determined also for trees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|