Temporal Network Creation Games

Davide Bilò, Sarel Cohen, Tobias Friedrich, Hans Gawendowicz, Nicolas Klodt, Pascal Lenzner, George Skretas

TL;DR

This paper introduces the first game-theoretic model for the creation of temporal networks, where agents strategically build connections over time to ensure reachability. They demonstrate that while equilibria exist, computing them is computationally hard, and analyze the efficiency loss due to selfish behavior, showing it's logarithmic in the number of agents.

What Problem Does This Paper Address?

Many real-world networks, like social networks or infrastructure, are not static. They evolve over time, with connections appearing and disappearing. Furthermore, these networks often emerge from the interactions of many individual, "selfish" agents (e.g., users, companies) who act to maximize their own benefit.

Traditional research on networks has largely focused on either static networks or temporal networks, but not on how temporal networks are formed by strategic agents. This paper bridges this gap by combining game theory (specifically, network formation games) with temporal graph theory. The core problem is to understand how selfish agents would collectively build a temporal network that ensures everyone can reach everyone else, and how efficient (or inefficient) this decentralized process is compared to a centrally planned optimal network.

Methods

The authors introduce the Temporal Reachability Network Creation Game (TRNCG). In this game:

  • Host Graph: A complete temporal graph is given, defining the available edges and their time labels.
  • Agents: Each node in the host graph is a strategic agent.
  • Strategies: Agents choose which edges to "buy" (create) from the host graph. Buying an edge has a cost.
  • Objective: Agents aim to ensure they can reach all other nodes via temporal paths (paths where edge labels strictly increase).
  • Cost Function: An agent's cost is the number of edges they buy plus a large penalty for each node they cannot reach.
  • Equilibria: The paper analyzes two types of equilibria:
  • Pure Nash Equilibrium (NE): A state where no agent can unilaterally improve their situation by changing their strategy.
  • Greedy Equilibrium (GE): A state where no agent can improve their situation with a single edge addition or deletion.

The authors then investigate:

  • Computational Complexity: They prove that finding a best response strategy for an agent and determining if a given state is a Nash Equilibrium are NP-hard problems, even for simple cases.
  • Existence of Equilibria: They show that equilibria are guaranteed to exist for temporal graphs with a lifetime of 2.
  • Quality of Equilibria (Price of Anarchy - PoA): They analyze how much worse the total cost of an equilibrium network is compared to the optimal network. They derive bounds on the PoA for both NE and GE, showing they are close to each other (differing by a logarithmic factor).

Datasets

Not discussed in the paper. The paper focuses on theoretical models and constructions rather than empirical evaluation on real-world datasets.

Key Insights and Ideas

  • Temporal Networks are Harder: Adding the temporal dimension significantly increases the computational complexity of network formation games, making best response computations and equilibrium checking NP-hard, unlike their static counterparts.
  • Equilibria are Guaranteed (for simple cases): Despite the complexity, equilibria are shown to exist for temporal graphs with a lifetime of 2, suggesting that stable states can be reached.
  • Selfishness Costs Logarithmically: The decentralized, selfish creation of temporal networks leads to an inefficiency (Price of Anarchy) that grows only logarithmically with the number of agents. This is a relatively good outcome, suggesting that selfish behavior doesn't lead to drastically suboptimal networks in this temporal setting.
  • Greedy vs. Optimal: Greedy equilibria (achieved by simple, step-by-step improvements) are shown to be close in quality to Nash equilibria, making them a more tractable concept for analysis.

Key Results

  • NP-hardness: Computing a best response strategy for an agent is NP-hard. Deciding if a strategy profile is a Nash Equilibrium is NP-hard for temporal host graphs with lifetime $t > 3$.
  • Existence: For complete temporal host graphs with lifetime $t=2$, a Pure Nash Equilibrium is guaranteed to exist.
  • Price of Anarchy (PoA):
    • The PoA for Greedy Equilibria is bounded by $O(\log n)$.
  • The PoA for Nash Equilibria is also bounded by $O(\log n)$.
  • A lower bound for the PoA is $\Omega(\log n)$, showing that the logarithmic bound is tight.
  • For a fixed maximum lifetime $t_{max}$, the PoA for GE is at most $t_{max}$.

Limitations and Future Work

  • Restricted Setting: The current model assumes a complete temporal host graph and unit costs for edges. Future work could explore non-complete host graphs, non-uniform edge costs, and directed edges.
  • Existence for $t > 2$: While equilibria are guaranteed for $t=2$, proving their existence for $t > 3$ remains an open and challenging problem.
  • Agent Objectives: Agents currently aim for reachability. Future work could explore objectives like minimizing travel time or maximizing robustness.
  • Dynamic Updates: The paper focuses on the initial creation. Investigating how agents adapt their strategies over time in response to network changes is a natural extension.
  • Cooperation: Exploring models where agents can cooperate instead of acting purely selfishly is another promising direction.

Summary updated

Abstract

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.
BibTeX
@inproceedings{bilo2023temporal,
  author = {Davide Bilò and Sarel Cohen and Tobias Friedrich and Hans Gawendowicz and Nicolas Klodt and Pascal Lenzner and George Skretas},
  title = {{Temporal Network Creation Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/279},
}
Figure