The increasing connectivity between critical infrastructures creates a network of networks in which the interdependencies between the networks play an important role in understanding the emerging functions and performances. To this end, this paper aims to establish a game-theoretic framework to capture the interactions between two system designers who aim to maximize individual network utilities. In particular, we use the game model to investigate the decentralized interdependent network for maximizing the algebraic connectivity of the global network. We develop an alternating play algorithm, and show its convergence to a Nash equilibrium network after a finite number of iterations. We corroborate our results through case studies of power and communication networks, and compare the Nash equilibrium solutions with their constrained team solution counterparts. The experimental results provide design guidelines and insights to increase the efficiency of the interdependent network formation games.