# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 4 Minimal and Intermediate Payment Functions
We now show that the game induced by the function \(sum\text{-}col\) on the instance \(I=\{\underbrace{\{a,b\}}_{n\text{ times}}\}\) in the graph depicted in Figure 1 does not admit a Nash equilibrium. Let \(k\) be \(\lceil f(n)\rceil+1\). The routing \(\mathcal{R}^{*}=(P_{\mathcal{R}^{*}},c_{\mathcal{R}^{*}})\), where \(\forall\{a,b\}\in I\), \(|P_{\mathcal{R}^{*}}(\{a,b\})|=k\), i.e., each request is routed on a different chain of \(k\) edges, and \(c_{\mathcal{R}^{*}}(\{a,b\})=1\) is such that \(\omega_{\mathcal{R}^{*}}(G,I)=1\), thus \(w(G,I)\)=1. If we consider the routing \(\mathcal{R}=(p_{\mathcal{R}},c_{\mathcal{R}})\) where \(\forall\{a,b\}\in I\), \(|P_{\mathcal{R}^{*}}(\{a,b\})|=1\), then there exists a request using at least color \(n\). Since \(\mathcal{R}\) is an equilibrium, the thesis follows. Therefore, even if convergent, all the three minimal level functions yield the worst possible price of anarchy. Unfortunately, the following results show that, also, the remaining seven payment functions for the intermediate information level either are not convergent or yield the worst possible price of anarchy. Figure 1: In this graph, nodes \(a\) and \(b\) are connected through a single edge and \(n\) chains of \(k\) edges. **Theorem 5**. : _The payment function max-sum belongs to the class \(\Xi\)._  
Proof. : We show that _max-sum_ belongs to the subclass \(\Xi^{\prime\prime}\) of \(\Xi\). To this aim, it suffices to show that \(g(\sigma(e))=sum(e,\alpha)=\sum_{k\in r(e)}f(k)\) satisfies, for any sets of colors \(A\) and \(B\), the property \(A\setminus\{d\}\subseteq B\Rightarrow g(A)\leq g(B\cup\{d^{\prime}\})\) with \(d\in A\), \(d^{\prime}\geq d\) and \(d^{\prime}\
otin B\). Since \(A\setminus\{d\}\subseteq B\) and \(f\) is positive and non decreasing, we have \(g(B\cup\{d^{\prime}\})=f(d^{\prime})+\sum_{k\in B}f(k)\geq f(d)+\sum_{k\in A \setminus\{d\}}f(k)=g(A)\). **Theorem 6**. : _Nash equilibria are not guaranteed to exist for the games induced by the payment functions._  
1. _sum-max when the pricing function_ \(f\) _is unbounded;_
2. _max-avmax and sum-avmax when_ \(f\) _is such that_ \(\exists k:f(k)>2f(1)\)_;_
3. _max-avsum and sum-avsum when the_ \(f\) _is such that_ \(\exists k:f(k)>f(1)\)_, that is,_ \(f\) _is non-constant._  
The proof of Theorem 6 is deferred to the Appendix A. Finally, we have the following theorem concerning _sum-sum_. **Theorem 7**. : _The payment function sum-sum is not convergent when the pricing function \(f\) is such that \(\exists k:f(k)>f(1)+f(2)\)._  
Proof. : We show that, for the problem defined by the graph depicted in Figure 2 and by the instance \(I=\{\alpha=\{a,c\},\beta=\{d,c\}\}\), the Nash dynamics are cyclic for any pricing function \(f\), such that \(\exists k:f(k)>f(1)+f(2)\). The parameters \(n\), \(h\) and \(k\) depend on the pricing function \(f\) and must be suitably tuned as shown in the sequel of the proof. Let \(q\) be the edge \(\{a,b\}\), \(q^{\prime}\) be the path obtained from the union of the path of \(h\) edges and the edge \(\{d,b\}\), \(s\) be the edge \(\{b,c\}\), \(s^{\prime}\) be the path of \(k\) edges and \(r\) be the edge \(\{d,b\}\). The following conditions suffices to prove that the Nash dynamics are cyclic:  
\[(k+1)f(2)<2f(n)+f(n+1), \tag{3}\]  
\[2f(n)+f(1)<(k+1)f(2), \tag{4}\]  
\[(h+2)f(1)+f(2)<2f(n+1), \tag{5}\]  
Figure 2: In this graph, there exists a path consisting of \(h\) edges between the nodes \(a\) and \(d\), and there exist two paths, one consisting of a single edge and the other consisting of \(k\) edges between the nodes \(b\) and \(c\).