assume a complete information scenario, where all agents have knowledge of the entropic vector $\overrightarrow{{\bf H}}$, the strategy space ${\bf G}$ and the utilities of all agents ${\bf u}$.

Stability concept and network efficiency
----------------------------------------

The link formation game is formulated as a non-cooperative simultaneous move game and we focus on the Nash Equilibrium (NE) as the solution concept. The NE is defined as follows $$u_{i}({\bf g}_{i}^{*},{\bf g}_{-i}^{*})\geq u_{i}({\bf g}_{i},{\bf g}_{-i}^{*}),\forall{\bf g}_{i}\in\{0,1\}^{N-1},\forall i\in\mathcal{N},\label{eq6}$$ where ${\bf g}_{i}^{*}$ is the NE strategy of agent $i$, and ${\bf g}_{-i}^{*}$ is the NE strategy profile of all users other than $i$. A strict NE is obtained by making the inequality in (\[eq6\]) strict. The game can have multiple NE defined as ${\bf G^{*}}=\{{\bf g}^{*}|\,\,\forall u_{i}({\bf g}_{i}^{*},{\bf g}_{-i}^{*})\geq u_{i}({\bf g}_{i},{\bf g}_{-i}^{*}),\forall{\bf g}_{i}\in\{0,1\}^{N-1}\}$. In the following Theorem, we show that there exists at least one network satisfying the NE conditions, i.e. ${\bf G^{*}}\neq\phi$.

[*(The Existence of Nash Equilibrium)*]{} A pure strategy NE always exists for $\mathcal{G}^{N}=\langle\mathcal{N},{\bf G},{\bf u},\overrightarrow{{\bf H}}\rangle$.

See Appendix A.

The social welfare of the network formation game is defined as the sum of agents’ individual utilities. For a strategy profile ${\bf g}$, the social welfare is defined as $$U({\bf g}){\vcentcolon=}\sum_{i\in\mathcal{N}}u_{i}({\bf g}).\label{eq7}$$ A strategy 