Computer Science – Social and Information Networks
Scientific paper
2011-12-30
Computer Science
Social and Information Networks
Scientific paper
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.
Narahari Yadati
Narasimha Srinath
Narayanam Ramasuri
Subramanian C. A.
Vallam Rohith Dwarakanath
No associations
LandOfFree
Topologies and Price of Stability of Complex Strategic Networks with Localized Payoffs : Analytical and Simulation Studies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Topologies and Price of Stability of Complex Strategic Networks with Localized Payoffs : Analytical and Simulation Studies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topologies and Price of Stability of Complex Strategic Networks with Localized Payoffs : Analytical and Simulation Studies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-334766