## 4 Application to Parametric Network Games
### Basics of Network Games  
We begin with a recapitulation of foundational Graph Theory concepts. We define a graph \(g\) as a pair of sets \((V,E)\), where \(V\) represents the set of nodes, while \(E\) represents the set of arcs composed of pairs of nodes \((v,w)\). Arcs sharing identical terminal nodes are categorized as parallel arcs, while arcs in the form of \((v,v)\) are designated as loops. For the context at hand, we exclusively consider simple graphs, which are characterized by the absence of both parallel arcs and loops. Within our framework, the players are represented by the \(n\) nodes of the graph. Furthermore, we operate within the framework of undirected graphs, wherein arcs \((v,w)\) and \((w,v)\) are considered equivalent. Two nodes \(v\) and \(w\) are adjacent if they are connected by the arc \((v,w)\). The information regarding the adjacency of nodes can be stored in the form of the adjacency matrix \(G\), where the elements \(g_{ij}\) assume a value of \(1\) when \((v_{i},v_{j})\) is an arc and \(0\) otherwise. Notice that matrix \(G\) is symmetric and with diagonal elements equal to \(0\). For a specific node \(v\), the nodes that share a direct link with it through arcs are referred to as the neighbors of \(v\). These neighbors are collated within the set \(N_{v}(g)\). The cardinality of \(N_{v}(g)\) is the degree of \(v\). A walk is defined as a sequence \(v_{0},e_{1},v_{1},e_{2},\ldots,v_{k}\) comprising both graph nodes \(v_{i}\) and graph edges \(e_{i}\), for any \(1\leq i\leq k\), where the arc \(e_{i}\) has endpoints \(v_{i-1}\) and \(v_{i}\). Notice that within a walk, the possibility of revisiting a node or traversing an arc multiple times is permitted. The length of a walk is equal to the number of its arcs. The indirect connections between any two nodes within the graph are described through the utilization of the powers of the adjacency matrix \(G\). Indeed, it can be proved that the element \(g_{ij}^{[k]}\) of \(G^{k}\) provides the number of walks of length \(k\) between the nodes \(v_{i}\) and \(v_{j}\). We now recall some concepts of Game Theory, which will then be adapted to our specific framework. A strategic game (in normal form) is a model of interaction among decision makers, which are usually called players. Each player has to make a choice among various possible actions, but the outcome of her choice also depends on the choice made by the other players. The elements of the game are:  
* A set of \(n\) players;
* A set \(A_{i}\), for each player \(i\in\{1,\ldots,n\}\), called the strategy (or action) set of player \(i\); each element \((x_{1},x_{2},\ldots,x_{n})\in A:=A_{1}\times A_{2}\times\ldots\times A_{n}\) is called a strategy profile;
* For each player \(i\in\{1,\ldots,n\}\), a set of preferences, according to which they can order the various profiles;
* For each player \(i\in\{1,\ldots,n\}\), a utility (or payoff) function, \(u_{i}:A\to\mathbb{R}\), which represents their preferences such that to higher values there correspond better outcomes. Let us notice that the utility function of player \(i\) does not merely depend on \(x_{i}\), but on the whole strategy profile \(x=(x_{1},x_{2},\ldots,x_{n})\); that is, the interaction with the other players cannot be neglected in their decision processes. In the case of more than two players, it is important to distinguish the action of player \(i\) from the action of all the other players. To this end, we will use the notation \(x_{-i}\) to denote the subvector \((x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n})\), and write \(x=(x_{i},x_{-i})=(x_{1},\ldots,x_{n})\). Since each player \(i\) wishes to maximize their utility, and only controls her action variable \(x_{i}\), a useful solution concept is that of Nash equilibrium of the game.