  Most networks are not static objects, but instead they change over time. This
observation has sparked rigorous research on temporal graphs within the last
years. In temporal graphs, we have a fixed set of nodes and the connections
between them are only available at certain time steps. This gives rise to a
plethora of algorithmic problems on such graphs, most prominently the problem
of finding temporal spanners, i.e., the computation of subgraphs that guarantee
all pairs reachability via temporal paths. To the best of our knowledge, only
centralized approaches for the solution of this problem are known. However,
many real-world networks are not shaped by a central designer but instead they
emerge and evolve by the interaction of many strategic agents. This observation
is the driving force of the recent intensive research on game-theoretic network
formation models.
  In this work we bring together these two recent research directions: temporal
graphs and game-theoretic network formation. As a first step into this new
realm, we focus on a simplified setting where a complete temporal host graph is
given and the agents, corresponding to its nodes, selfishly create incident
edges to ensure that they can reach all other nodes via temporal paths in the
created network. This yields temporal spanners as equilibria of our game. We
prove results on the convergence to and the existence of equilibrium networks,
on the complexity of finding best agent strategies, and on the quality of the
equilibria. By taking these first important steps, we uncover challenging open
problems that call for an in-depth exploration of the creation of temporal
graphs by strategic agents.
