Hans Gawendowicz

Hans Gawendowicz, Nicolas Klodt, Aleksandrs Morgensterns et al.

A crucial aspect of research is understanding how real-world networks, such as transportation and information networks, are formed. A prominent model for such networks was introduced by \cite{fabrikant_network_2003} and extended by \cite{bilo_temporal_2023}, incorporating temporal graphs to better represent real-world networks. In this model, there is a given host graph with $n$ agents (represented by nodes) and time labels on the edges. Each agent can establish connections by purchasing edges. This makes the edges present at the time steps given by the time labels of the host graph. The goal of each agent is to reach as many other agents as possible while minimizing the number of edges bought. However, this model makes the simplifying assumption that each edge comes with predetermined time steps. We address this deficiency by extending the model of Bilo et al. \cite{bilo_temporal_2023} to allow agents to purchase edges and to decide when they appear. To capture a variety of real-world applications, we study two reachability models and several cost functions based on the label an agent assigns to an edge. For these settings, we provide proofs of existence of Nash equilibria, as well as lower and upper bounds on the Price of Anarchy and Price of Stability.

Davide Bilò, Sarel Cohen, Tobias Friedrich et al.

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.