Topologies of stable strategic networks with localized payoffs

Abstract

There are numerous types of networks in the real-world which involve strategic actors: supply chain networks, logistics networks, company networks, and social networks. In this investigation, we explore the topologies of decentralized networks that will be formed by strategic actors who interact with one another. In particular, we analyze a network formation game in a strategic setting where payoffs of individuals depend only on their immediate neighbourhood. These localized payoffs incorporate the social capital emanating from bridging positions that nodes hold in the network. Using this novel and appealing 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 applying classical results from extremal graph theory and discover that the Turán graph (or the complete equi-bipartite network) emerges as the unique efficient network under many configurations of parameters. We examine the tradeoffs between topologies of pairwise stable networks and efficient networks using the notion of price of stability. We identify several parameter configurations where the price of stability is 1 (or at least lower bounded by 0.5) in the proposed model. This leads to another key insight of this paper: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized payoffs. 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 test-bed. © 2013 IEEE.