  We study the strategic formation of multi-layer networks, where each layer
represents a different type of relationship between the nodes in the network
and is designed to maximize some utility that depends on the topology of that
layer and those of the other layers. We start by generalizing distance-based
network formation to the two-layer setting, where edges are constructed in one
layer (with fixed cost per edge) to minimize distances between nodes that are
neighbors in another layer. We show that designing an optimal network in this
setting is NP-hard. Despite the underlying complexity of the problem, we
characterize certain properties of the optimal networks. We then formulate a
multi-layer network formation game where each layer corresponds to a player
that is optimally choosing its edge set in response to the edge sets of the
other players. We consider utility functions that view the different layers as
strategic substitutes. By applying our results about optimal networks, we show
that players with low edge costs drive players with high edge costs out of the
game, and that hub-and-spoke networks that are commonly observed in
transportation systems arise as Nash equilibria in this game.
