# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 4 Minimal and Intermediate Payment Functions
We first focus on ring topologies, as the corresponding results can be directly extended to chains. Our purpose is to force the agents to simulate the behavior of the online algorithm proposed by [PERSON] [26]. In such an algorithm, the path system \(P\) is fixed and the optical spectrum is divided in shelves, numbered consecutively starting from \(1\). The color assigned to an arriving agent \(\alpha\) is the lowest available one in the minimal shelf \(i\), such that the load induced on the edges of \(\alpha\) by all the agents up to shelf \(i\) is at most \(i\). More precisely, denoted as \(sh(w)\), the shelf of a given wavelength \(w\), the load \(l(\alpha,\mathcal{R})\) of an agent \(\alpha\) according to a routing \(\mathcal{R}\) is  
\[l(\alpha,\mathcal{R})=\max_{e\in p(\alpha)}|\{w|w\in\sigma(e)\wedge sh(w)\leq sh (c(\alpha))\}|.\]  
Clearly, any routing \(\mathcal{R}\) such that \(P_{\mathcal{R}}=P\) has the same load \(\pi_{\mathcal{R}}(G,I)\) and in the routing \(\mathcal{R}\) returned by the algorithm, at most \(\pi_{\mathcal{R}}(G,I)\) shelves are used to allocate all the agents. Moreover, as shown in [26], during all the executions of the algorithm, the first shelf contains only one color and the other ones no more than three colors, thus yielding \(\omega_{\mathcal{R}}(G,I)\leq 3\cdot\pi_{\mathcal{R}}(G,I)-2\) colors, that is, at most \(3\) times above the optimum. In devising a payment function that mimics [PERSON]'s algorithm, it is necessary to cope with several problems. First of all, it is necessary to fix a path system with a low induced load. This is obtained by giving agents an incentive to use shortest paths, as in any routing \(\mathcal{R}\) satisfying such a property \(\pi_{\mathcal{R}}(G,I)\leq 2\pi(G,I)\), that is, the induced load is at most doubled. Moreover, the convergence of the game is an issue, since the move of an agent might compromise the minimality of the payments of the agents in his shelf and in the above ones. Finally, in order for an agent to always find a proper shelf during the evolution of the game, we have to allow an unlimited number of colors to be contained in each shelf. Since, however, Nash equilibria will use only one wavelength of the first shelf and at most three in the other ones, we have to choose the function \(sh\) associating colors to shelves trying to minimize, for each \(i\), the maximum third color of all the shelves up to \(i\). To this aim, we partition the set of wavelengths \(W\) in two subsets \(W_{1}\) and \(W_{2}\), in which \(W_{2}=\{2^{i}|i=0,1,2,\ldots\}\) is the set of the slack wavelengths. Each shelf has an infinite number of wavelengths and the first one of shelf \(1\) and the first three ones of all the other shelves correspond consecutively to small colors in \(W_{1}\), while the other ones to slack colors in \(W_{2}\), assigned to the different shelves according to a dove-tail technique in such a way that, for every \(i\geq 1\) and \(j>3\), there exists a finite wavelength \(w\in W_{2}\) that corresponds to the \(j\)-th color of shelf \(i\). As can be easily checked, while the first color of shelf \(1\) is \(3\), the third color of each shelf \(i>1\) is at most \(3i+\lfloor\log_{2}3i\rfloor+3\). Assuming that the function \(sh\) realizes the above mapping of colors and that \(n\) is the number of nodes in the ring, the payment function _price_ charges to agent \(\alpha\)  
\[\min\left\{\Big{\lfloor}\frac{n}{2}\Big{\rfloor},\big{\lvert}p(\alpha)\big{ }\big{\rvert}+n\max\{0,l(\alpha,\mathcal{R})-sh(c(\alpha))\}-\frac{1}{2+sh(c( \alpha))-\frac{1}{2c(\alpha)}}\right\}.\]  
Intuitively, a routing \(\mathcal{R}\) is at Nash equilibrium if, and only if, each request uses a shortest path and the color that [PERSON]'s algorithm assigns to him when agents arrive in non-decreasing order of color in \(\mathcal{R}\), clearly not using colors in \(W_{2}\). In ring networks, the game induced by the above payment function converges and has a price of anarchy \(\rho=6+\mathcal{O}\big{(}\frac{\log(\pi(G,I))}{\pi(G,I)}\big{)}\). Proof.