# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 3 Preliminaries  
In the first part of this section, we prove that, under complete information, any centralized algorithm \(\mathcal{A}\) for the all-optical routing problem can be suitably used in a non-cooperative environment for achieving a price of anarchy either equal to \(1\) or \(k\), according to whether \(\mathcal{A}\) is optimal or \(k\)-approximating, respectively. Theorem 3.1: _Given any routing \(\tilde{\mathcal{R}}\) for a game \(\mathcal{G}\), there exists a payment function letting \(\mathcal{G}\) converge to \(\tilde{\mathcal{R}}\) in at most \(3|I|\) steps._  
Proof: Given any routing \(\mathcal{R}\), the payment function is defined as follows. \[price_{\mathcal{R}}(\alpha)=\left\{ \begin{array}{ll}0&\text{if }p_{\mathcal{R}}( \alpha)=p_{\tilde{\mathcal{R}}}(\alpha)\wedge c_{\mathcal{R}}(\alpha)=c_{ \tilde{\mathcal{R}}}(\alpha),\\ 2&\text{if }(p_{\mathcal{R}}(\alpha)\
eq p_{\tilde{\mathcal{R}}}(\alpha)\lor c _{\mathcal{R}}(\alpha)\
eq c_{\tilde{\mathcal{R}}}(\alpha))\wedge c_{ \mathcal{R}}(\alpha)\leq\omega_{\tilde{\mathcal{R}}}(G,I),\\ 1&\text{if }(p_{\mathcal{R}}(\alpha)\
eq p_{\tilde{\mathcal{R}}}(\alpha)\lor c _{\mathcal{R}}(\alpha)\
eq c_{\tilde{\mathcal{R}}}(\alpha))\wedge c_{ \mathcal{R}}(\alpha)>\omega_{\tilde{\mathcal{R}}}(G,I).\end{array} \right.\]
* Convergence. Since the payment function is such that any move of an agent does not affect the cost of any other agent and has a codomain of cardinality \(3\), any agent can perform at most \(3\) moves during the game, thus the game converges in at most \(3|I|\) moves. * Uniqueness. We now show that the only Nash equilibrium for \(\mathcal{G}\) is \(\tilde{\mathcal{R}}\). Suppose, by contradiction, that in the routing \(\mathcal{R}\) at Nash equilibrium, there exists an agent \(\alpha\) such that \(price_{\mathcal{R}}(\alpha)=2\). Agent \(\alpha\) can clearly perform a move by switching to a color \(c_{\mathcal{R}}(\alpha)>\omega_{\tilde{\mathcal{R}}}(G,I)\), so as to pay a cost equal to \(1\), and this contradicts the hypothesis that \(\mathcal{R}\) is a Nash equilibrium. Analogously, suppose that in the routing \(\mathcal{R}\) at Nash equilibrium there exists at least one agent \(\alpha\) such that \(price_{\mathcal{R}}(\alpha)=1\). In \(\mathcal{R}\), \(\alpha\) is thus assigned the color \(c_{\mathcal{R}}(\alpha)>\omega_{\mathcal{R}}(G,I)\). Having already proven that \(\alpha\) cannot pay a cost equal to \(2\), we have that no agent in the routing \(\mathcal{R}\) is assigned a color \(c_{\mathcal{R}}(\alpha)\leq\omega_{\tilde{\mathcal{R}}}(G,I)\) unless \(R(\alpha)=\tilde{R}(\alpha)\wedge c_{\mathcal{R}}(\alpha)=c_{\tilde{\mathcal{R }}}(\alpha)\), that is, unless he is using the same path and the same color of \(\tilde{\mathcal{R}}\). Thus, agent \(\alpha\) can perform a move by choosing the same path and color of \(\tilde{\mathcal{R}}\), so as to pay \(0\), and this contradicts the hypothesis that \(\mathcal{R}\) is a Nash equilibrium. We have shown that in a routing \(\mathcal{R}\) at Nash equilibrium \(price_{\mathcal{R}}(\alpha)=0\)\(\forall\alpha\in I\); by the definition of \(price_{\mathcal{R}}\), each agent uses the same path and color of the routing \(\tilde{\mathcal{R}}\), thus \(\mathcal{R}=\tilde{\mathcal{R}}\). Corollary 3.1: _Let \(\mathcal{A}\) be any \(k\)-approximation algorithm for the all-optical routing problem (\(k=1\) if \(\mathcal{A}\) is optimal). Then, there exists a payment function yielding a game \(\mathcal{G}\), converging in at most \(3|I|\) steps and having a price of anarchy equal to \(k\). Moreover, the time complexity of the computation of the function is at most the same as \(\mathcal{A}\)._  
Proof: The claim is an immediate consequence of Theorem 3.1: by letting \(\tilde{\mathcal{R}}\) be the routing returned by algorithm \(\mathcal{A}\), the price of anarchy of \(\mathcal{G}\) is simply the approximation ratio of \(\mathcal{A}\), and finally, each agent, in order to compute the payment function, has to find the same path and color computed by the algorithm \(\mathcal{A}\).