# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 4 Minimal and Intermediate Payment Functions
\[2f(n+1)<(h+2)f(1)+f(n). \tag{6}\]  
Consider the initial routing \(\mathcal{R}_{0}=(R_{0},c_{0})\), displayed in Table 2.  
At this first step, \(\beta\) plays the move \((\beta,\{r,s\},n,\{r,s^{\prime}\},2)\) because of condition (3), thus leading to the routing \(\mathcal{R}_{1}=(R_{1},c_{1})\), displayed in Table 3.  
Now, \(\alpha\) plays the move \((\alpha,\{q,s\},n+1,\{q^{\prime},s\},1)\) because of condition (5), thus leading to the routing \(\mathcal{R}_{2}=(R_{2},c_{2})\), displayed in Table 4.  
Finally, \(\alpha\) plays the move \((\alpha,\{q^{\prime},s\},1,\{q,s\},n+1)\) because of condition (6), thus leading the game back to the initial routing \(\mathcal{R}_{0}\) (displayed in Table 2). In order to complete the proof, we have to show how to satisfy the conditions (3)-(6) and how to tune the parameters \(n\), \(k\) and \(h\). The four conditions are satisfied by choosing \(k\) and \(h\), such that  
\[0<\frac{2f(n)+f(1)-f(2)}{f(2)}<k<\frac{2f(n)+f(n+1)-f(2)}{f(2)}\]  
and  
\[(k+1)f(2)<2f(n)+f(n+1), \tag{3}\]0  
Choosing \(n:\,f(n)>f(1)+f(2)\) assures that \(h\) and \(k\) always exist and are integers. **5. Results for Specific Topologies**  
In Section 4, we have shown that the price of anarchy for general topologies under the intermediate and minimal levels of information can be very high. For this reason, always considering the intermediate and minimal levels of information, in this section, we consider networks having specific topologies, like chains (i.e., sites are connected along a line), and rings (i.e., cycles of sites) and trees. Let us first consider the minimal information level. Any strictly increasing payment function computable under this level, like \(price(\alpha)=c(\alpha)\), induces games in which a routing \(\mathcal{R}\) at Nash equilibrium can be seen as a solution of the classical first-fit algorithm for the all-optical routing problem that assigns to each request the smallest available color. In particular, this solution is the one returned by first-fit when requests are considered in non-decreasing order of color in \(\mathcal{R}\). Therefore, the induced price of anarchy is bounded by the approximation ratio of first-fit. Concerning the above-mentioned topologies, for any instance \(I\), first-fit uses a number of colors that are at most \(8\pi(G,I)\) in chains [24] and at most \(\mathcal{O}((\log|I|)\pi(G,I))\) in trees [25]. Recalling that \(\omega(G,I)\geq\pi(G,I)\), the following theorem holds. Theorem 4.1: _The payment function \(price(\alpha)=c(\alpha)\) induces games with a price of anarchy \(8\) in chains and \(\rho=\mathcal{O}(\log|I|)\) in trees, both converging in \(\omega_{\mathcal{R}}(G,I)^{2}\) steps from any initial routing._  
For rings, it is possible to use the result of [24] by routing requests on the chain obtained deleting an edge \(e\in E\) of the ring. In fact, denoted as \(P\), the path system containing all such connecting paths, for any routing \(\mathcal{R}\) with \(P_{\mathcal{R}}=P\), it results in \(\pi_{\mathcal{R}}(G,I)\leq 2\pi(G,I)\). In other words, this at most doubles the induced load. The following payment function forces Nash equilibria using the set of paths \(P\):  
\[price(\alpha)=\left\{ \begin{array}{ll}1&\text{if }e\in p(\alpha)\\ 1-\frac{1}{c(\alpha)}&\text{otherwise}\end{array} \right.\]  
Since the payment function belongs to \(\Pi\) and, when restricted to the routings \(\mathcal{R}\) with \(P_{\mathcal{R}}=P\), is strictly increasing, it follows that each agent has an incentive in choosing the smallest available color. By recalling that, in this case, the load at most doubles with respect to the chain topology, the following theorem holds. Theorem 4.2: _In ring networks, the above payment function induces games with price of anarchy \(16\) and converging in \(\omega_{\mathcal{R}}(G,I)^{2}\) steps from any initial routing \(\mathcal{R}\)._  
In the remaining part of the section, we show how, raising the level of information to the intermediate one, it is possible to further reduce the price of anarchy for chains and rings.