# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 4 Minimal and Intermediate Payment Functions
: Let us consider any evolution of the game starting from any given configuration and let us show that it converges to a Nash equilibrium in a finite number of agent moves. At any intermediate configuration, let us partition \(I\) into two sets \(A\) and \(B\), such that \(A\) contains all the agents that, in the sequel of the game, will never perform a move to a higher shelf. We show that, after a finite number of moves, a new agent will enter in \(A\), so that in a finite number of steps, it will finally result \(A=I\). This proves the convergence of the game, since starting from such final configuration, the agents cannot perform an infinite number of moves without raising their shelf. First of all, we note that, since by construction, the number of wavelengths in each shelf is infinite, each agent \(\alpha\) can always perform a move leading him in a feasible shelf \(i\), that is, such that \(i\geq l(\alpha,\mathcal{R})\). Moreover, the moves leading \(\alpha\) on a shortest path and in a feasible shelf are the only ones which can make \(\alpha\)'s cost strictly smaller than \(\lfloor\frac{n}{2}\rfloor\). Finally, an agent routing a shortest path and lying in a feasible shelf, maintaining his connection path, decreases his cost if he moves to a lower feasible shelf or to a smaller color of its shelf. Consider a move of agent \(\alpha_{1}\) to a shelf \(i_{1}\). The proof proceeds by cases: after the move  
1. \(\alpha_{1}\) will never perform a move increasing his shelf. In this case, \(\alpha_{1}\) is entered in \(A\). 2. At a certain point of the game, \(\alpha_{1}\) performs a move increasing his shelf. This is due to another agent \(\alpha_{2}\) who has performed a move to a shelf \(i_{2}\leq i_{1}\). However, it cannot be \(i_{2}=i_{1}\), as \(\alpha_{2}\) increases \(\alpha_{1}\)'s load to \(i_{1}+1\) and would have the same load \(i_{1}+1\) in shelf \(i_{1}\) (i.e., \(i_{1}\) is not feasible for \(\alpha_{2}\)), thus not decreasing his cost. We can then continue applying the same analysis to \(\alpha_{2}\). Since the number of shelves in which agents can move is bounded by \(\pi(G,I)\), we must finally arrive to an agent \(\alpha_{j}\) with \(j\leq\pi(G,I)\) for which the first case holds. As already observed, any routing \(\mathcal{R}\) at Nash equilibrium corresponds to the output of [PERSON]'s algorithm without using colors in \(W_{2}\) when the agents arrive in non decreasing order of color in \(\mathcal{R}\). Thus, the maximum used color in \(\mathcal{R}\) is at most the third one of shelf \(\pi(G,I)\) if \(\pi(G,I)>1\), while it is equal to the first one of shelf 1 otherwise. This shows that the maximum used color is at most \(3\pi_{\mathcal{R}}(G,I)+\lfloor\log_{2}3\pi_{\mathcal{R}}(G,I)\rfloor+3\). Since \(\mathcal{R}\) uses shortest paths, \(\pi_{\mathcal{R}}(G,I)\leq 2\pi_{\mathcal{R}}(G,I)\) and the resulting price of anarchy is \(\rho=6+\mathcal{O}(\frac{\log(\pi_{\mathcal{R}}(G,I))}{\pi_{\mathcal{R}}(G,I)})\). Clearly, a similar function  
\[price^{\prime}=\min\left\{n,1+2n\max\{0,load(\alpha,\mathcal{R})-sh(c(\alpha)) \}-\frac{1}{2+sh(c(\alpha))-\frac{1}{2\zeta(\alpha)}}\right\}\]  
can be used also in chains, for which connection paths are unique and thus no doubling of the load occurs. Theorem 4.1: _In chain networks, the game induced by the above payment functions converges and has a price of anarchy \(\rho=3+\mathcal{O}(\frac{\log(\pi(G,I))}{\pi(G,I)})\)._