On Network Structure of Stable Strategies in Local Connection Games

Hikaru Iwazaki; Takenori Ujigawa; Shao-Chin Sung

doi:10.20965/jaciii.2012.p0420

single-jc.php

« previous

JACIII Vol.16 No.3 pp. 420-424

doi: 10.20965/jaciii.2012.p0420

(2012)

Paper:

Views over last 60 days: 209

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

Received:

October 15, 2011

Accepted:

December 31, 2011

Published:

May 20, 2012

Keywords:

network formation games, local connection games, stable strategy profiles, link cost, diameter

Abstract

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:

References

[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] V. Bala and S. Goyal, “Non-Cooperative Model of Network Formation,” In D. Acemoglu (Eds.), Econometrica, The Econometric Society, pp. 1181-1229, 2000.
[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] 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] 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.

[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.