# On Nash Equilibria in Non-Cooperative All-Optical Networks +
## 4 Minimal and Intermediate Payment Functions  
Even though the results obtained in the case of complete information are fully satisfactory, they have been obtained under the assumption that each agent has full knowledge of the instance and the routing: this assumption is very strong and in real world networks might not be true either due to technological or privacy policies reasons. For this reason, in the sequel, we will focus on payment functions based on a more restricted level of information. Let us first define a set of payment functions that can be computed under a minimal or intermediate information level. Given a routing \(\mathcal{R}\), we first propose suitable cost functions defined on the edges that will be used as building blocks for the definition of the mentioned payment functions:  
* \(col(e,\alpha)=f(c(\alpha))\): the amount charged to \(\alpha\) on the edge \(e\) is the cost, according to \(f\), of the color he uses. * \(max(e,\alpha)=\max_{k\in\sigma_{\mathcal{R}}(e)}f(k)\): the amount charged to \(\alpha\) on the edge \(e\) is the cost of the highest color used along \(e\) (considering also the other agents). * \(sum(e,\alpha)=\sum_{k\in\sigma_{\mathcal{R}}(e)}f(k)\): the amount charged to \(\alpha\) on the edge \(e\) is the sum of the costs of all the colors used along \(e\). * \(avmax(e,\alpha)=\max_{k\in\sigma_{\mathcal{R}}(e)}\frac{f(k)}{|\sigma_{\mathcal{ R}}(e)|}\): the amount charged to \(\alpha\) on the edge \(e\) is the cost of the highest color used along \(e\), averaged or shared among all the agents traversing \(e\). * \(avsum(e,\alpha)=\sum_{k\in\sigma_{\mathcal{R}}(e)}\frac{f(k)}{|\sigma_{\mathcal{ R}}(e)|}\): the amount charged to \(\alpha\) on the edge \(e\) is the sum of the costs of all the colors used along \(e\), averaged on all the agents traversing \(e\). Starting from any edge cost function \(cost\), it is possible to define the following payment functions:  
* \(max\_cost(\alpha)=\max_{e\in p(\alpha)}cost(e,\alpha)\): the price asked to \(\alpha\) is the maximum cost, according to \(cost\), of an edge used by \(\alpha\). * \(sum\text{-}cost(\alpha)=\sum_{c\in p(a)}cost(e,\alpha)\): the price asked to \(\alpha\) is the sum of the costs of the edges used by \(\alpha\). The combination of the introduced edge cost functions with the above two strategies, that is, maximization or summation, gives rise to ten possible payment functions. In all cases, since the function \(f\) is non-decreasing, agents have an incentive to choose small colors so as to possibly minimize the overall number of used colors. Notice that all the ten introduced payment functions are computable under an intermediate information level. Moreover, \(max\text{-}col\), \(sum\text{-}col\) and \(max\text{-}max\) require only the minimal level, as \(max\text{-}col(\alpha)=\max_{c\in p(a)}col(e,\alpha)=f(c(\alpha))\), \(sum\text{-}col(\alpha)=\sum_{c\in p(a)}col(e,\alpha)=|p(\alpha)|\cdot f(c( \alpha))\) and \(max\text{-}max(\alpha)=\max_{c\in p(a)}\max_{k\in\sigma(e)}f(k)=\max_{k\in \sigma(p(a))}f(k)\). The following lemma shows how the families of functions defined in the previous section nicely characterize the class of games induced by them. Lemma 1: _The payment functions \(max\text{-}col\) and \(max\text{-}max\) belong to the class \(\Xi\)._  
Proof: It can be easily verified that, by definition, the payment function \(max\text{-}col\) belongs to \(\Xi^{\prime}\), while the payment function \(max\text{-}max\) belongs to \(\Xi^{\prime\prime}\). Moreover, a similar result holds for \(sum\text{-}col\). Theorem 4: _The payment function sum-col belongs to \(\Pi\), that is, it is convergent, but there exists a game \(\mathcal{G}=(G,I,sum\text{-}col)\) having a price of anarchy \(\rho=\frac{|I|}{\omega(G,I)}\)._  
Proof: The payment function \(sum\text{-}col\) belongs to \(\Pi\), since it clearly satisfies conditions (1) and (2).