### The Standard Model for NCGs  
A first NCG model that received considerable attention in the algorithmic game theory area is due to [PERSON] et al. [1]. In this model, which we will call SumNCG in the sequel, each player \(u\) pays \(\alpha\) for each link she activates as his/her _building cost_, and the _sum_ of all distances from \(u\) to all other vertices in the resulting network as her _usage cost_. More formally, if \(V\) is a set of \(n\) agents, the set of the possible strategies of player \(u\in V\) is \(2^{V\setminus\{u\}}\) (Given a set \(X,2^{X}\) denotes the power set of \(X\)). Given a strategy \(\sigma_{u}\) for each agent \(u\in V\), we will call the vector \(\sigma=(\sigma_{u})_{u\in V}\) a _strategy profile_, and we will denote by \(G(\sigma)\) the resulting network, i.e., a graph containing a vertex for each player in \(V\), and such that its edge set \(E(\sigma)\) contains an edge \((u,v)\) if and only if \(u\in\sigma_{v}\) or \(v\in\sigma_{u}\). To easy the notation, we will sometimes use \(G\) instead of \(G(\sigma)\) if no ambiguity arises. Moreover, we will say that \(u\in V\)_owns_ the edges in \(\{u\}\times\sigma_{u}\) (Notice that, according to the above definition, an edge can be owned by both its endpoints). The goal of each agent \(u\in V\) is that of minimizing her cost \(C_{u}(\sigma)\) in the resulting strategy profile \(\sigma\), which is defined as  
\[C_{u}(\sigma)=\alpha\cdot|\sigma_{u}|+\sum_{v\in V}d_{G(\sigma)}(u,v), \tag{1}\]  
where \(d_{G(\sigma)}(u,v)\) is the distance between player \(u\) and player \(v\) in \(G(\sigma)\). Quite naturally, we define the _social cost_ of \(\sigma\) as the sum of the costs \(C_{u}(\sigma)\) incurred by all players \(u\in V\). Notice that in the above description, we are _implicitly_ assuming that each player \(u\) has a complete knowledge of the current network \(G(\sigma)\). This means that \(u\) can evaluate both his/her current cost \(C_{u}(\sigma)\), and the cost \(C_{u}(\sigma_{-u},\sigma_{u}^{\prime})\) that he/she would incur if he/she were to change her strategy from \(\sigma_{u}\) to \(\sigma_{u}^{\prime}\), as he/she is aware that--following her change--the current network will transit to \(G(-u,\sigma_{u}^{\prime})\) (The notation \((\sigma_{-u},\sigma_{u}^{\prime})\) denotes the vector obtained from \(\sigma\) by replacing component \(\sigma_{u}\) with \(\sigma_{u}^{\prime}\)). Therefore, a (pure strategy) _Nash Equilibrium_ (NE) for the game is a strategy profile \(\tilde{\sigma}\) where, for every player \(u\) and every strategy \(\sigma_{u}\), we have that \(C_{u}(\tilde{\sigma})\leq C_{u}(\tilde{\sigma}_{-u},\sigma_{u})\). A vast body of literature deals with the problem of characterizing the space of NE in order to bound the _Price of Anarchy_ (PoA) as a function of the parameter \(\alpha\). Here, the PoA is defined as the ratio between the social cost of the worst NE (i.e., any NE \(\sigma\) maximizing its social cost \(\sum_{u}C_{u}(\sigma)\)), and the social cost of an _optimal_ strategy profile (i.e., a strategy profile \(\sigma^{*}\) minimizing its social cost \(\sum_{u}C_{u}(\sigma^{*})\)) [2; 3; 4; 5; 6; 7; 8]. Intuitively, the PoA provides an upper bound on the loss of efficiency (measured in terms of the social cost) between the stable networks that can be reached as a result of the uncoordinated selfish behavior of the agents and that of any optimal (but not necessarily stable) network that minimizes the social cost. Large values of the PoA show that the distributed network formation process might converge to costly networks when compared to a \"centralized\" design. Conversely, small values of the PoA show that even if the network arises from a combination of selfish strategies, its quality will not be significantly worse than the best possible design.