# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## Appendix A Proof of Theorem 6  
Proof. : Claim 1. We show that the game induced by the function \(sum\)-\(max\) on the instance \(I=\{\{a,c_{i}\},\underbrace{\{b,d_{i}\}}_{m\text{ times}}|i\in\{1,2,\ldots,n,n+1\}\}\) in the graph depicted in Figure 11, does not admit a Nash equilibrium if \(f\) is unbounded. In such a graph, there exist two paths between the nodes \(a\) and \(b\), one consisting of a unique edge and the other one having \(h\) edges. Similarly, there exist two paths between any pair of nodes \(b\) and \(c_{i}\) having one and \(k\) edges, respectively. The parameters \(m,n,h\) and \(k\) depend on \(f\) and must be carefully tuned, as shown in the sequel. We now give a set of conditions which is sufficient to prove the non-existence of a Nash equilibrium. First of all, we have three technical conditions:  
\[n>m>1, \tag{1}\]  
\[f(n+1)>f(n), \tag{2}\]  
\[f(m+1)>f(m). \tag{3}\]  
Clearly, in any Nash equilibrium, the agents \(\{b,d_{i}\}\) can use at most the color \(m+1\) (or a color \(x\) such that \(f(x)=f(m+1)\)), if the edge \(\{b,c_{i}\}\) is used by an agent \(\{a,c_{i}\}\) with a color at most \(m\), and can use at most color \(m\) otherwise. Because of technical condition (2) and by imposing the following conditions,  
\[2f(n)<(h+k)f(1), \tag{4}\]  
\[2f(n)<hf(1)+f(m+1), \tag{5}\]  
\[(k+1)f(m)<2f(n+1), \tag{6}\]  
\[(k+1)f(m)<(h+k)f(1), \tag{7}\]  
\[(k+1)f(m)<hf(1)+f(m+1), \tag{8}\]  
This is not an equilibrium, since by condition (A15), \(\beta_{\bar{j}}\) can move to the chain of \(k\) edges. * The agent \(\alpha\) uses the edge \(\{a,b\}\) with a color at least equal to \(n+1\) and all the agents \(\beta\) use the chain of \(k\) edges. This is not an equilibrium since by condition (A13), \(\alpha\) can move to the chain of \(h\) edges. We conclude the proof by showing how the imposed conditions can be always satisfied. We first note that some conditions are implied by other ones: \((A14)\wedge(A1)\wedge(A3)\Rightarrow(A12)\) since \(2f(n+1)<hf(1)+f(m+1)<hf(m+1)+f(m+1)=(h+1)f(m+1)\); \((A14)\Rightarrow(A5)\) since \(2f(n)\leq 2f(n+1)<hf(1)+f(m+1)\); \((A9)\wedge(A14)\Rightarrow(A10)\) since \(2f(n+1)<hf(1)+f(m+1)<hf(1)+kf(1)=(h+k)f(1)\); \((A10)\Rightarrow(A4)\) since \(2f(n)\leq 2f(n+1)<(h+k)f(1)\); \((A9)\wedge(A1)\wedge(A3)\Rightarrow(A11)\) since \(k>\frac{f(m+1)}{f(1)}>1\Rightarrow 2f(n+1)<(1+k)f(n+1)\); \((A15)\Rightarrow(A6)\) since \((k+1)f(m)=kf(m)+f(n+1)+f(n+1)=2f(n+1)\); \((A6)\wedge(A10)\Rightarrow(A7)\) since \((k+1)f(m)<2f(n+1)<(h+k)f(1)\); \((A6)\wedge(A14)\Rightarrow(A7)\) since \((k+1)f(m)<2f(n+1)<hf(1)+f(m+1)\). From the remaining conditions (A9), (A13), (A14) and (A15) we obtain \[\frac{2f(n+1)-f(m+1)}{f(1)}<h<\frac{2f(n+1)-f(1)}{f(1)}\] and \[\frac{2f(m+1)-f(1)}{f(1)}<k<\frac{f(n+1)}{f(m)}.\] The existence of \(h\) and \(k\) integers is guaranteed by \(f(m+1)>2f(1)\) and \(f(n+1)>\frac{2f(m)f(m+1)}{f(1)}\), which make the width of the above intervals greater than 1. Finally, in order to meet all the conditions including the initial technical ones, it is sufficient to choose \[m\text{ such that}\left\{ \begin{array}{l}f(m+1)>2f(1),\\ f(m+1)>f(m),\\ m>1.\end{array} \right.\] and \[n\text{ such that}\left\{ \begin{array}{l}f(n+1)>\frac{2f(m)f(m+1)}{f(1)},\\ f(n+1)>f(n),\\ n>m.\end{array} \right.\] Since \(f\) is unbounded, all the constraints are satisfiable. Claim 2. We show that, for the problem defined by the graph depicted in Figure A2 and by the instance \[I=\{\{a,c_{i}\},\{b,c_{i}\}|i\in\{1,2,\ldots,n\}\}\] no Nash equilibrium exists for any pricing function \(f\), such that \(\exists k:f(k)>2f(1)\). The parameter \(n\) depends on \(f\) and must be suitably tuned. We set \(n\) as the smallest integer for which \(f(n)>2f(1)\). In any routing, there must exist an agent \(\{a,c_{i}\}\) using a color at least equal to \(n\). Let \(\alpha=\{a,c_{i}\}\) be one of these agents and \(\beta=\{b,c_{i}\}\). Clearly, in any routing at Nash equilibrium, \(\beta\) must use a color strictly less than \(n\). We prove the claim by considering all the possible routings.