JACIII Vol.16 No.3 pp. 420-424
doi: 10.20965/jaciii.2012.p0420


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

October 15, 2011
December 31, 2011
May 20, 2012
network formation games, local connection games, stable strategy profiles, link cost, diameter

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.

Cite this article as:
H. Iwazaki, T. Ujigawa, and S. Sung, “On Network Structure of Stable Strategies in Local Connection Games,” J. Adv. Comput. Intell. Intell. Inform., Vol.16, No.3, pp. 420-424, 2012.
Data files:
  1. [1] 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.
  2. [2] V. Bala and S. Goyal, “Non-Cooperative Model of Network Formation,” In D. Acemoglu (Eds.), Econometrica, The Econometric Society, pp. 1181-1229, 2000.
  3. [3] 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.
  4. [4] 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.
  5. [5] 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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on Aug. 21, 2019