Strategic Network Formation with Localized Pay-offs

In this investigation, we analyze a network formation game in a strategic setting where pay-offs of individuals depend only on their immediate neighbourhood. These localized pay-offs incorporate the social capital emanating from bridging positions that nodes hold in the network. Using this simple and novel model of network formation, our study explores the structure of networks that form, satisfying pairwise stability or efficiency or both. We derive sufficient conditions for the pairwise stability of several interesting network structures. We characterize topologies of efficient networks by drawing upon classical results from extremal graph theory and discover that the Turan graph (or the complete equi-bipartite network) emerges as the unique efficient network under many configurations of parameters. We examine the trade-offs between topologies of pairwise stable networks and efficient networks using the notion of price of stability. Interestingly, we find that price of stability is equal to 1 for almost all configurations of parameters in the proposed model; and for the rest of the configurations, we obtain a lower bound of 0.5. This leads to another key insight of this article: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized pay-offs. We study the dynamics of the proposed model by designing a simple myopic best response updating rule and implementing it on a customized network formation testbed.