  We analyze a network formation game in a strategic setting where payoffs of
individuals depend only on their immediate neighbourhood. We call these payoffs
as localized payoffs. In this game, the payoff of each individual captures (1)
the gain from immediate neighbors, (2) the bridging benefits, and (3) the cost
to form links. This implies that the payoff of each individual can be computed
using only its single-hop neighbourhood information. Based on this simple model
of network formation, our study explores the structure of networks that form,
satisfying one or both of the properties, namely, pairwise stability and
efficiency. We analytically prove the pairwise stability of several interesting
network structures, notably, the complete bi-partite network, complete
equi-k-partite network, complete network and cycle network, under various
configurations of the model. We validate and extend these results through
extensive simulations. 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-bi-partite network) is 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, which is the ratio of the sum of payoffs of the
players in an optimal pairwise stable network to that of an efficient network.
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 of the parameters, we obtain a lower bound of 0.5 on the price
of stability. 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.
