Price of Stability in Survivable Network Design

Date Added: Jul 2009
Format: PDF

This paper studies the survivable version of the game theoretic network formation model known as the Connection Game, originally introduced in. In this model, players attempt to connect to a common source node in a network by purchasing edges, and sharing their costs with other players. This paper introduce the survivable version of this game, where each player desires 2 edge-disjoint connections between her pair of nodes instead of just a single connecting path, and analyze the quality of exact and approximate Nash equilibria. This version is significantly different from the original Connection Game and has more complications than the existing literature on arbitrary cost-sharing games since the authors consider the formation of networks that involve many cycles.