Efficiency and stability in the connections model with heterogeneous node

This paper studies the connections model (Jackson and Wolinsky, 1996) when nodes may have different values. It is shown that efficiency is reached by a strongly hierarchical structure that we call strong NSG-networks: Nested Split Graph networks where the hierarchy or ranking of nodes inherent in any such network is consistent with the rank of nodes according to their value, perhaps leaving some of the nodes with the lowest values disconnected. A simple algorithm is provided for calculating these efficient networks. We also introduce a natural extension of pairwise stability assuming that players are allowed to agree on how the cost of each link is split and prove that stability in this sense for connected strong NSG-networks entails efficiency.