On Network Structure of Stable Strategies in Local Connection Games
Hikaru Iwazaki, Takenori Ujigawa, and Shao-Chin Sung
Aoyama Gakuin University, 5-10-1 Fuchinobe, Chuo-ku, Sagamihara-shi, Kanagawa 252-5258, Japan
We are concerned with a model of network formation games, called local connection games, in which networks are formed based on players’ strategies. Each player may decide to build links to other players by paying a certain cost fixed in advance, and a strategy of each player is a selection of links to be built. Each player determines and/or changes her or his strategy depending on cost for building links and cost of contacting all other players on the entire network, which influence the structure of the entire network. One of the main interests on the study of local connection games is to characterize all the stable strategy profiles. In this paper, we analyze the influences on network structure of stable strategy profiles caused by the cost for building links. For the unit cost case, we provide, in terms of network structure, a necessary and sufficient condition for strategy profiles to be stable. Moreover, we investigate the relationship between integral cost cases and non-integral cost cases as well.
-  S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, and L. Roditty, “On Nash Equilibria for a Network Creation Game,” In Proc. of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, Miami, Florida, pp. 89-98, 2006.
-  V. Bala and S. Goyal, “Non-Cooperative Model of Network Formation,” In D. Acemoglu (Eds.), Econometrica, The Econometric Society, pp. 1181-1229, 2000.
-  J. Corbo and D. Parkes, “The price of selfish behavior in bilateral network formation,” In Proc. of the 24th Annual ACM Symposium on Principles of Distributed Computing, pp. 99-107, Las Vegas, Nevada, 2005.
-  A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker, “On a Network Creation Game,” In Proc. of Twenty-Second ACM Symposium on Principles of Distributed Computing, pp. 247-351, Boston, Massachusetts, 2003.
-  E. Tardos and T. Wexler, “Network Formation Games and the Potential Function Method,” In N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, pp. 487-516, 2007.