# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 2 The Model
A routing \(\mathcal{R}\) is a (pure) Nash equilibrium if, and only if, for any agent \(\alpha\) and routing \(\mathcal{R}^{\prime}\) differing from \(\mathcal{R}\) only for the path and/or the color associated to \(\alpha\), it holds that \(price_{\mathcal{R}}(\alpha)\leq price_{\mathcal{R}^{\prime}}(\alpha)\). Denoted as \(\mathcal{N}\), the set of the routings at Nash equilibrium, the price of anarchy of the game \(\mathcal{G}\) is defined as the worst case ratio \(\rho=sup_{\mathcal{R}\in\mathcal{N}}\frac{\omega_{\mathcal{R}}(G,I)}{\omega(G,I)}\) among all the possible games \(\mathcal{G}\). The evolution of the game \(\mathcal{G}\) is a sequence of moves \((\alpha,p_{old},color_{old},p_{news},color_{new})\) starting from an arbitrary routing, where \(\alpha\) is an agent and \((p_{old},color_{old})\in P^{\alpha}\times W\) and \((p_{new},color_{new})\in P^{\alpha}\times W\) are the old and the new strategies of \(\alpha\), respectively. The Nash dynamics of the game \(\mathcal{G}\) are the directed graph \((\Phi,M)\), where \(\Phi\) is the set of possible routings for \(G\) and \(I\) and there exists an arc \((\mathcal{R}_{1},\mathcal{R}_{2})\in M\) if there exists a selfish move from \(\mathcal{R}_{1}\) to \(\mathcal{R}_{2}\), i.e., there exists an agent \(\alpha\) such that \(price_{\mathcal{R}_{2}}(\alpha)<price_{\mathcal{R}_{1}}(\alpha)\). If the Nash dynamics are acyclic for every \(G\) and \(I\), the game \(\mathcal{G}\) is said to be convergent. Analogously, any payment function _price_ inducing only convergent games is said to be convergent. We say that game \(\mathcal{G}\) converges to routing \(\mathcal{R}\) whenever \(\mathcal{G}\) is convergent and admits the unique pure Nash equilibrium \(\mathcal{R}\). It is worth noting that, even if the Nash dynamics are cyclic, the game might admit a Nash equilibrium. Table 1 summarizes all the notations defined above. For ease of notation, when clear from the context, in the following, we will drop the index \(\mathcal{R}\) from the notation, thus, for instance, writing \(price(\alpha)\), \(p(\alpha)\), \(c(\alpha)\), \(\sigma(e)\) and \(\sigma(p)\) in place of \(price_{\mathcal{R}}(\alpha)\), \(p_{\mathcal{R}}(\alpha)\), \(c_{\mathcal{R}}(\alpha)\), \(\sigma_{\mathcal{R}}(e)\) and \(\sigma_{\mathcal{R}}(p)\). Before concluding the section, we finally observe that the payment function \(price_{\mathcal{R}}\), in a strongly distributed non-cooperative environment, has to be computed by each single agent requiring the communication service. However, the level of global information they have can be limited by technological constraints, as well as privacy policies carried out by the service provider or simply enforced by the law. Therefore, in general, \(price_{\mathcal{R}}\) is not computed, starting from the instance \(I\) and the routing \(\mathcal{R}\), but on a more restricted set of information induced by them. To this aim, we introduce the concepts of states and levels of information. The edge state (resp. path state) of the network \(G\) induced by a routing \(\mathcal{R}\) for \(I\) is a function \(\sigma_{\mathcal{R}}:E\to 2^{W}\) (resp. \(\vartheta_{\mathcal{R}}:\mathcal{P}\to 2^{W}\), where \(\mathcal{P}\) is the set of all the simple paths in \(G\)) associating to every edge \(e\in E\) (resp. path \(p\in\mathcal{P}\)) the set of the wavelengths used along \(e\) (resp. \(p\)). It is then possible to distinguish among three basic levels of information:  
* Minimal. Each agent \(\alpha=\{x,y\}\) knows the available wavelengths along any given path connecting \(x\) to \(y\), that is, the function \(price_{\mathcal{R}}\) can be computed, even knowing only the restriction of the path state \(\vartheta_{\mathcal{R}}(\alpha)\) on the set of the paths from \(x\) to \(y\). * Intermediate. Each agent information knows the wavelengths available along any given edge, that is, the function \(price_{\mathcal{R}}\) can be computed, even knowing only the edge state \(\sigma_{\mathcal{R}}\). * Complete.