Classical network-formation games (NFGs) are played on
directed graphs, and are used in network design and analysis. Edges
in the network are associated with costs and players have reachability
objectives, which they try to fulfill at a minimal cost. When several players
use the same edge, they share its cost. The theoretical and practical
aspects of NFGs have been extensively studied and are well understood.
All studies of NFGs, however, consider an explicit representation of the
network. In practice, networks are often built in a hierarchical manner.
Technically, some of the vertices in the network are boxes, associated with
nested sub-networks, where a sub-network may be “called” by several
boxes in the network. This makes hierarchical networks exponentially
more succinct than traditional “flat” networks.

We introduce hierarchical network formation games (HNFGs) and
study theoretical and practical aspects of the hierarchical setting. Different
applications call for different cost-sharing mechanisms, which define
how edge-formation costs are shared by their users. Indeed, in some applications,
cost sharing should refer to the flat expansion of the network
and in some it should take into account the hierarchical structure of the
network. We study properties of HNFGs like stability and equilibrium
inefficiency in the different mechanisms. We also study computational
aspects of HNFGs, where the principal question is whether their exponential
succinctness with respect to NFGs leads to an exponential increase
in the complexity of reasoning about them. This question is analogous
to research done in the formal-verification community about the ability
to model-check hierarchical systems in their succinct presentation. We
show that the picture is diverse and depends on the mechanism applied.