## 4 Price of Anarchy  
Models \(\mathcal{M}_{1}\), \(\mathcal{M}_{2}\) and \(\mathcal{M}_{3}\) are equivalent with respect to the PoA, as shown by the following two Theorems. Theorem 4.3: _The PoA for SumNCG in \(\mathcal{M}_{1}\), \(\mathcal{M}_{2}\), and \(\mathcal{M}_{3}\) is \(\Theta(\min\{1+\alpha,n\})\) for every \(\alpha\)._  
Proof: Notice that each network that is compatible with the view of \(u\) in model \(\mathcal{M}_{2}\) (resp. \(\mathcal{M}_{3}\)) must also be compatible with the view of \(u\) in \(\mathcal{M}_{1}\) (resp. \(\mathcal{M}_{2}\)). This shows that the PoA can only decrease when we consider \(\mathcal{M}_{1}\), \(\mathcal{M}_{2}\), and \(\mathcal{M}_{3}\) in this order. We will prove the claim by showing that \(O(\min\{1+\alpha,n\})\) is an upper bound for \(\mathcal{M}_{1}\) and \(\Omega(\min\{1+\alpha,n\})\) a lower bound in \(\mathcal{M}_{3}\). We start by proving our lower bound in \(\mathcal{M}_{3}\). To this aim, consider the complete graph and notice that it is an equilibrium since the only SPT rooted in each vertex (player) is a star, and no edge can be removed. The corresponding social cost is \(\Omega(\alpha n^{2}+n^{2})\), while the cost of an optimal network is upper bounded by that of a star, i.e., \(O(\alpha n+n^{2})\). It follows that the PoA must be \(\Omega(\min\{n,1+\alpha\})\). We now turn our attention to the upper bound in \(\mathcal{M}_{1}\). We start by showing that the diameter of an equilibrium graph \(G\) can be at most \(O(1+\sqrt{\alpha})\). Let \(u\) and \(v\) be two players such that the eccentricity \(D\) of \(u\) in \(G\) is equal to \(d(u,v)\geq 4\) (we can assume that such a pair exists as otherwise the diameter of \(G\) would be at most \(3\)). If player \(u\) were to buy the edge \((u,v)\), he/she would decrease her distances towards at least \(\frac{D}{4}\) vertices, namely, those on the shortest path between \(u\) and \(v\), by at least \(\frac{3}{4}D-\frac{1}{4}D-1=\frac{1}{4}D-1\). This would decrease her usage cost by at least \(\Omega(D^{2})\). Notice that this reasoning is compatible with the local view of \(u\) in model \(\mathcal{M}_{1}\), since \(u\) only needs to know \(d(u,v)\) (while no knowledge of the internal vertices of \(\pi\) is necessary). As the edge \((u,v)\) is not in \(G\), we can infer that \(\alpha=\Omega(D^{2})\), which implies \(D=O(1+\sqrt{\alpha})\). The PoA can then be upper bounded as follows,  
\[O\left(\frac{\alpha n^{2}+n^{2}(1+\sqrt{\alpha})}{\alpha n+n^{2}}\right)=O( \min\{n,1+\alpha\}).\qed\]  
**Theorem 10**. : _The PoA for MaxNCG in \(\mathcal{M}_{1}\), \(\mathcal{M}_{2}\), and \(\mathcal{M}_{3}\) is \(\Theta(n)\) for \(\alpha=\Omega(1)\), and \(\Theta(1+\alpha n)\) if \(\alpha=O(1)\)._  
Proof. : By similar arguments as the ones used in the proof of Theorem 9, we only need to show an upper bound to the PoA in model \(\mathcal{M}_{1}\) and a lower bound to the PoA in model \(\mathcal{M}_{3}\). Once again, we can consider a complete graph \(H\) to obtain our lower bound. The same discussion in the proof of Theorem 9 also applies to MaxNCG, and shows that \(H\) is an equilibrium network in \(\mathcal{M}_{1}\). The social cost of \(H\) is \(\Omega(\alpha n^{2}+n)\), while that of a star is \(O(\alpha n+n)\). As a consequence, we obtain a lower bound on the PoA of \(\Omega\left(\frac{\alpha n^{2}+n}{\alpha n+n}\right)\), which reduces to \(\Omega(n)\) for \(\alpha=\Omega(1)\), and to \(\Omega(1+\alpha n)\) for \(\alpha=O(1)\). To prove our upper bound on \(\mathcal{M}_{3}\) we show that, in any equilibrium graph \(G\), the diameter of \(G\) must be at most \(O(1+\alpha n)\). Let \(u\) be a player having eccentricity \(D\geq 4\) in \(G\), define \(X\) as the set of vertices at distance \(\lfloor D/2\rfloor\) from \(u\) in \(G\). If \(u\) were to buy all edges in \(\{u\}\times X\), his/her eccentricity would decrease by \(\Omega(D)\). As \(G\) is an equilibrium, we know that the building cost must exceed \(\Omega(D)\), in formulas: \(\alpha n\geq\alpha\cdot|X|=\Omega(D)\), i.e., \(D=O(1+\alpha n)\).