# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 3 Preliminaries
In the sequel, we will focus on the minimal and intermediate information levels. Before proceeding with the presentation of our results, let us first introduce two families of payment functions that provide a useful characterization of a class of convergent games with the worst possible price of anarchy. Given a generic move \(\mu\) performed by an agent \(\alpha\) from \(\mathcal{R}_{old}\) to \(\mathcal{R}_{new}\), let \(A\) be the set of agents sharing at least one edge with \(\alpha\) in \(\mathcal{R}_{old}\) and no edges with \(\alpha\) in \(\mathcal{R}_{new}\) and \(B\) be the set of agents sharing at least one edge with \(\alpha\) in \(\mathcal{R}_{new}\). We denote with \(\Pi\) the set of payment functions, satisfying the following conditions:  
\[\forall\beta\in A,\mathit{price}_{\mathcal{R}_{new}}(\beta)\leq\mathit{price }_{\mathcal{R}_{old}}(\beta) \tag{1}\]  
\[\forall\beta\in B,\mathit{price}_{\mathcal{R}_{new}}(\beta)>\mathit{price}_{ \mathcal{R}_{old}}(\beta)\Rightarrow\mathit{price}_{\mathcal{R}_{new}}(\beta) \leq\mathit{price}_{\mathcal{R}_{new}}(\alpha) \tag{2}\]  
Roughly speaking, condition (1) means that all the players sharing at least an edge with \(\alpha\) before her move and no edge after such a move does not increase their costs. Condition (2) means that given a generic player \(\beta\) sharing at least an edge with \(\alpha\) after \(\mu\) and increasing their cost after such a move, the cost of \(\beta\) after \(\mu\) is at most the cost of \(\alpha\) after \(mu\). Such conditions will be useful for proving the convergence to equilibrium. Theorem 2.2: _All the payment functions belonging to \(\Pi\) are convergent._  
Proof: Let \(\Psi_{old}\) be the sequence of costs \(\mathit{price}_{\mathcal{R}_{old}}(\beta)\)\(\forall\beta\in I\) ordered in a non-decreasing way and let \(\Psi_{new}\) be the sequence of costs \(\mathit{price}_{\mathcal{R}_{new}}(\beta)\)\(\forall\beta\in I\) ordered in the same way, that is, the new sequence of costs yielded by the execution of a move \(\mu\) performed by the agent \(\alpha\). By the definition of the class \(\Pi\), \(\mu\) can increase the cost of any other agent to reach, at most, the value \(\mathit{price}_{\mathcal{R}_{new}}(\alpha)\). Since it holds \(\mathit{price}_{\mathcal{R}_{new}}(\alpha)\leq\mathit{price}_{\mathcal{R}_{old }}(\alpha)\), we obtain that the sequence \(\Psi_{new}\) is lexicographically smaller than \(\Psi_{old}\). Notice that such a lexicographic order induces a total order among the nodes of the Nash dynamics. The sequence \(\Psi_{0}=<0,0,0,\ldots>\) is the bottom of the lexicographic ordering, hence the thesis. As can be easily seen, the number of steps needed to converge to an equilibrium may not be polynomial in the dimensions of the instance. We now define a subclass of \(\Pi\) of payment functions inducing games \(\mathcal{G}\), having a price of anarchy \(\rho=\frac{|I|}{\omega(\mathcal{G},I)}\), which is clearly the worst possible, since any feasible solution for the problem uses at most \(|I|\) colors, while \(\omega(G,I)\) is the optimal solution. We denote as \(\Xi=\Xi^{\prime}\cup\Xi^{\prime\prime}\) the class of payment functions satisfying at least one of the following conditions:  
* _Subclass_\(\Xi^{\prime}\): \(\forall\alpha\in I,\mathit{price}(\alpha)\) depends only on the color \(c(\alpha)\) and \(c_{\mathcal{R}}(\alpha)\geq c_{\mathcal{R}^{\prime}}(\alpha)\Rightarrow\mathit{ price}_{\mathcal{R}}(\alpha)\geq\mathit{price}_{\mathcal{R}^{\prime}}(\alpha)\) for any \(\mathcal{R}\) and \(\mathcal{R}^{\prime}\); that is, the cost for each agent depends only on its own color in the routing and any other agent \(\alpha\) never gets a benefit in performing a move \((\alpha,p_{old},\mathit{color}_{old},p_{new},\mathit{color}_{new})\) where \(\mathit{color}_{new}\geq\mathit{color}_{old}\).