# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 2 The Model  
An all-optical network is modelled by an undirected graph \(G=(V,E)\), where nodes in \(V\) represent sites and undirected edges in \(E\) bidirectional optical fiber links between the sites. Given any two nodes \(x,y\in V\), a communication request between \(x\) and \(y\) is denoted as \(\{x,y\}\). A communication instance in \(G\) is a multiset of requests \(I\) (i.e., \(I\) can contain multiple requests between the same pair of nodes). A path system \(P\) for an instance \(I\) in \(G\) is a set of paths containing a distinguished simple connecting path in \(G\) for each request in \(I\). A solution \(\mathcal{R}(G,I)\) for an instance \(I\) in \(G\), \(\mathcal{R}\) for short, is a pair \((P_{\mathcal{R}},c_{\mathcal{R}})\) in which \(P_{\mathcal{R}}\) is a path system for \(I\) and \(c_{\mathcal{R}}:I\to W\) (with \(W=\mathbf{N}^{+}\) being the set of wavelengths) is a function associating a wavelength or color to each request in \(I\). Let \(p_{\mathcal{R}}(\{x,y\})\in P_{\mathcal{R}}\) denote the path connecting \(\{x,y\}\) in \(\mathcal{R}\) and \(|p_{\mathcal{R}}(\{x,y\})|\) be its length in terms of number of edges. A solution \(\mathcal{R}\) is feasible or is a routing for \(I\) in \(G\) if \(c_{\mathcal{R}}(\{x_{1},y_{1}\})\
eq c_{\mathcal{R}}(\{x_{2},y_{2}\})\) for any two requests \(\{x_{1},y_{1}\}\in I\) and \(\{x_{2},y_{2}\}\in I\) whose connecting paths \(p_{\mathcal{R}}(\{x_{1},y_{1}\})\) and \(p_{\mathcal{R}}(\{x_{2},y_{2}\})\) share an edge in \(G\), i.e., the associated colors are different. Let \(\omega_{\mathcal{R}}(G,I)\) be the number of colors used by the routing \(\mathcal{R}\) for \(I\) in \(G\) and \(\omega(G,I)=\min_{\mathcal{R}}\omega_{\mathcal{R}}(G,I)\) be the minimum number of colors used by any routing for \(I\). Analogously, let \(\pi_{\mathcal{R}}(G,I)=max_{e\in E}|\{p\in P_{\mathcal{R}}|e\in p\}|\) be the maximum load of an edge in \(G\) induced by the routing \(\mathcal{R}\) and \(\pi(G,I)=\min_{\mathcal{R}}\pi_{\mathcal{R}}(G,I)\) be the minimum maximum load of the routings for \(I\) in \(G\), also called load of \(I\) in \(G\). Clearly, since all the requests sharing an edge must have different colors, \(\omega_{\mathcal{R}}(G,I)\geq\pi_{\mathcal{R}}(G,I)\) for every \(\mathcal{R}\) and thus \(\omega(G,I)\geq\pi(G,I)\). Given that the optical spectrum is a scarce resource, in this paper, we aim at determining routings using a number of wavelengths close to the minimum one, i.e., \(\omega(G,I)\). In order to model our non-cooperative environment, we assume that each communication request \(\{x,y\}\in I\) is issued and handled by an agent \(\alpha\); for the sake of simplicity, we consider it as coincident with the request, that is \(\alpha=\{x,y\}\). Our goal is to assign payments (or costs) to the agents so that they are induced to choose in a non-cooperative way a good solution, i.e., a routing with a small number of colors. A payment function _price_ associates each possible routing and agent to a cost; in particular, \(price_{\mathcal{R}}(\alpha)\) is the cost that agent \(\alpha\in I\) has to pay to the network provider in order to obtain the asked service if the routing \(\mathcal{R}\) is adopted. In order to give our payment functions a higher generality, we assume the existence of a non-decreasing function \(f:W\to\mathbf{R}^{+}\) associating a cost to every color. Notice that \(f\) is non-decreasing because, in such a way, it is possible to implicitly model the increasing cost incurred by the network provider when it has implemented a routing using up to a given wavelength. A game \(\mathcal{G}=(G,I,price)\) among the \(|I|\) agents belonging to \(I\) on the network \(G\) induced by the payment function _price_ is defined as the set of agents' strategies \(P^{\alpha}\times W\), where \(P^{\alpha}\) is the set of connecting paths for \(\alpha\) and the utility function \(u(\alpha)=-price(\alpha)\).