Temporal Network Creation Games

1 Introduction

Networks are omnipresent in everyday life. They range from abstract constructs, such as (online) social networks, to essential infrastructure, such as transportation networks and power grids. Given their ubiquity and importance, rigorous research has been conducted to better understand real-world networks. Researchers strive to evaluate the behavior of networks, their structural properties and the processes that drive their formation. Over the years, the research community has realized that more varied and complex models are required to capture the intricacies that govern a network's attributes. Two such intricacies are:

• (i) many networks are dynamic in nature, i.e. the nodes and/or the connections of the nodes change over time;
• (ii) the formation of many networks is driven by many individual and selfish agents without central coordination.

Due to the complexity that each of these settings introduces, researchers so far considered only one of the above assumptions that many real-world networks naturally exhibit.

However, in many real-world settings both (i) and (ii) apply. For example, consider the problem of scheduling meetings in a large institution where employees are interested in disseminating information to all their colleagues. For this, they can schedule meetings with others at different time slots depending on their availability. Meetings with multiple individuals at the same time slot enables the spread of information to all participants. Naturally, the goal is to minimize the number of meetings needed to inform everyone.

Our goal is for this paper to be the inaugural effort in combining dynamic networks with a game-theoretic analysis in order to better capture the formation of real-world networks.

1.1 Our Approach

We initiate the study of dynamic networks from a gametheoretic perspective by combining one of the earliest and very influential strategic network formation models for static networks, the non-cooperative network formation model by Bala and Goyal [2000], with the seminal temporal graph model of Kempe et al. [2002].

In the network formation model by Bala and Goyal [2000], the agents are nodes of a network and they strategically create costly incident links to maximize the number of nodes they can reach either directly or via a sequence of hops in the network. The temporal graph model of Kempe et al. [2002] assumes that an edge-labeled graph is given, where the labels indicate the time step where the respective edge is available. By combining the features of these two models, we assume that a temporal graph serves as the host graph for our network formation game. Agents correspond to its nodes and can create costly incident edges having the time labels specified by the host graph. Most importantly, instead of using standard reachability defined as the existence of a path between two nodes, we employ the concept of temporal reachability, where some node u can reach a node v if a temporal path, i.e., a path with monotonically increasing edge labels, exists.

As a first step in this line of research, we consider a restricted version, where the underlying temporal host graph is a clique, all edges have unit cost, and the objective of each agent is to create as few edges as possible to ensure the existence of a temporal path from itself to every other node of the graph. Although being the simplest variant of our framework, this setting has the striking feature that equilibrium states of our game correspond to temporal spanners of the underlying temporal host graph. Thus, our model captures the decentralized creation of a temporal spanner by selfish agents. To the best of our knowledge, so far only centralized approaches exist for this prominent algorithmic problem.

We emphasize that our framework can be generalized to much more complex settings. In particular, and similarly to (recent variants of) the well-studied Network Creation Game by Fabrikant et al. [2003], more than temporal reachability could be studied in future work. For example, the existence of short temporal paths, additional robustness guarantees, and more complicated edge cost functions.

1.2 Our Contribution

We explore the formation of temporal spanners by strategic agents via studying the Temporal Reachability Network Creation Game, whose equilibrium networks must be temporal spanners. Besides this being the first decentralized approach for computing temporal spanners, the entailed equilibria must be stable with respect to local changes of the involved nodes.

Although we show that computing a best response strategy is NP-hard even if the host graph has a lifetime t = 2, we nonetheless show for this case that equilibria exist and that they can be computed efficiently. The existence of equilibria remains a challenging open problem for t ≥ 3. However, we show that in this case, deciding if a given strategy profile is an equilibrium is NP-hard. This is remarkable, as similar questions are still open for most other game-theoretic network creation models. Also, in contrast to the classical Network Formation Game on static graphs [Bala and Goyal, 2000], this shows that incorporating temporal graphs yields a computationally much harder model.

As our main contribution, we provide non-trivial structural properties of equilibrium networks and we exploit them to prove bounds on the Price of Anarchy (PoA), i.e., on the quality of the obtained temporal spanners. Low bounds on the PoA imply that these equilibrium spanners are close to optimal. Regarding this, we give an upper bound of O(√n) on the PoA and provide a lower bound of Ω(log n).

Moreover, driven by the hardness of computing a best response strategy, we also investigate Greedy Equilibria (GE), that rely on very simple strategy changes. We connect them to Nash Equilibria by showing that the PoA with regard to Greedy Equilibria is at most a O(logn) factor larger than the PoA with regard to Nash Equilibria. This shows that not much is lost by focusing on GEs.

All omitted details can be found in [Bil`o et al., 2023].

1.3 RelatedWork

The formation of networks by strategic agents has been studied intensively within the last decades. One of the earliest models is also closest to our work. In the Network Formation Game by Bala and Goyal [2000] selfish agents buy incident edges and their utility is a function that increases with the number of agents they can reach and it decreases with the number of edges bought. Most relevant for us is the version where undirected edges are formed. For this the authors prove that equilibria always exist and that they are either stars or empty graphs. Moreover, improving response dynamics quickly converge to such states. Also, for this model computing a best response strategy and deciding if a given state is in equilibrium can be done efficiently.

The network formation game was extended to a setting with attacks on the formed network [Goyal et al., 2016]. There, the objective is post-attack reachability. This variant is more complex, but best response strategies can still be computed efficiently [Friedrich et al., 2017]. Recently, a variant with probabilistic attack was studied [Chen et al., 2019]. Also related are Topology Control Game [Eidenbenz et al., 2006], where the agents are points in the plane and edge costs are proportional to the Euclidean distance among the endpoints. Similar in spirit is the model by Guly´as et al. [2015], but there the agents are points in hyperbolic space using greedy routing. Also models exist where the agents aim for creating a robust network, i.e., communication in the network should rely on more than a single path [Meirom et al., 2015; Chauhan et al., 2016; Echzell et al., 2020].

Besides network formation games with reachability objective, even more model variants exist, where shortest path distances play a prominent role. Starting with the Network Creation Game [Fabrikant et al., 2003], that is based on the even older Connections Game [Jackson and Wolinsky, 1996], researchers have focused on utility functions that depend on the distances of the respective agent to the other agents in the formed network. For this, variants exist that involve cooperation [Corbo and Parkes, 2005; Andelman et al., 2009], locality [Bil`o et al., 2016; Cord-Landwehr and Lenzner, 2015], non-uniform edge prices [Chauhan et al., 2017; Bil`o et al., 2019], and most recently, social networks [Bil`o et al., 2021; Friedrich et al., 2022; Bullinger et al., 2022].

For most of these variants, computing a best response strategy is NP-hard, improving response dynamics are not guaranteed to converge, and the hardness of deciding equilibria is open. Moreover, for the original Network Creation Game [Fabrikant et al., 2003] equilibria always exist and the Price of Anarchy (PoA) is known to be constant for almost the full parameter range of the model. Similar results hold for the other models, with some notable exceptions, e.g., the geometric version has a high PoA [Bil`o et al., 2019].

To the best of our knowledge, no game-theoretic network formation model involving temporal graphs has been studied. However, starting from the work by Kempe et al. [2002], a lot of research has been devoted to algorithmic problems on temporal graphs, in particular to temporal spanners. Relevant for us, it has been shown that temporal cliques admit sparse temporal spanners [Casteigts et al., 2021] and also sparse spanners with low stretch are possible [Bil`o et al., 2022]. In con-

(v1, v3), (v1, v4) and buying (v1, v2) is an improving move.

trast, on non-complete temporal graphs spanners can be very dense [Axiotis and Fotakis, 2016]. The same holds true if strict temporal paths are considered, i.e., if the labels on the edges of a path must strictly increase [Kempe et al., 2002]. Closely related to the reachability problem, [Klobas et al., 2022] study the problem of finding the minimum number of labels required to achieve temporal connectivity in a graph.

Spanners on static graphs are a classical topic, see [Ahmed et al., 2020] for a recent survey. For spanners in geometric settings, see [Narasimhan and Smid, 2007].

1.4 Model and Notation

Before stating our game-theoretic model, we will first introduce temporal graphs and temporal spanners.

Temporal Graphs and Spanners

A temporal graph G = (VG,EG, λG) is an undirected labeled graph, where λG : EG → N, assigns a label to each edge. The edge labels of G model at which point in time an edge is available. For simplicity, we assume that all labels are consecutive starting with 1. Formally, ⋃e∈EG λG(e) = {1, 2, . . . , t}, for some t ∈ N, where t is called the lifetime. Note that, for simplicity, we assume that every edge has a single time label, i.e., every edge is available only at a particular single time step. All results in this paper also hold if we extend the model to allow multiple labels per edge. As long as the graph G is clear from context, we might omit the subscripts and write V, E, and λ instead of VG, EG, and λG.

A (simple) temporal path in G is a (simple) path in G with monotonically increasing edge labels. Formally, it is a sequence of (distinct) nodes v1, . . . , vi ∈ VG, that forms a (simple) path in G, i.e., for 1 ≤ j ≤ i - 1 we have ej = {vj, vj+1} ∈ EG, where for all 1 ≤ j ≤ i - 2 we have λG(ej) ≤ λG(ej+1). Note, that the labels do not have to increase strictly since we assume zero edge traversal time.

For two nodes u, v ∈ VG, we say that u can reach v in the temporal graph G if and only if there is a temporal path from u to v in G. We define RG(u) as the set of nodes that u can reach in G. Note that u ∈ RG(u), since every node can trivially reach itself via a temporal path of length 0. If every node can reach every other node, we say that G is temporally connected. With this we define a temporal spanner of G as any temporally connected subgraph G′ of G with VG′ = VG and EG′ ⊆ EG. If no edge can be removed from G′ while keeping the temporal spanner property, we call G′ a minimal temporal spanner of G. If G′ has at most as many edges as any other temporal spanner of G, we call G′ a minimum temporal spanner of G.

The Temporal Reachability Network Creation Game

Now we define our game-theoretic network creation model, called the Temporal Reachability Network Creation Game (TRNCG). Let H = (VH, EH, λH) be a given complete temporal graph that serves as the host graph of our game. We assume that every node v ∈ VH corresponds to a strategic agent and let |VH| = n denote the number of agents.

We assume that agents play strategies, where a strategy Sv of some agent v is defined as Sv ⊆ VH \{v}, i.e., the strategy specifies to which other agents agent v wants to create an edge. The strategies of all agents together form the strategy profile s = ⋃v∈VH {(v, Sv)}.

A strategy profile s defines the created directed temporal graph G(s) = (VG(s), EG(s), λG(s)), with

where λG(s) is the labeling λH restricted to the edge set EG(s), with λG(s)((u, v)) = λG(s)((v, u)) = λH({u, v}). Thus, G(s) is a directed subgraph of the complete host graph H that contains the union of all edges that are created by the agents, i.e., for every edge in G(s) there is exactly one agent that wants to create it. We use directed edges to encode the owner of the edge, where edges are always directed away from their owner. For reachability, these edge directions will be ignored.

Agents choose their respective strategy to minimize their individual cost, where the cost of agent v in the created directed temporal graph G(s) is defined as

where K > 1 is a large constant and G↔ (s) is the undirected version of G(s), i.e., VG↔ (s) = VG(s) and EG↔ (s) = {{u, v} | u ∈ Sv ∨ v ∈ Su} with λG↔ (s)({u, v}) = λH({u, v}), for all edges {u, v} ∈ EG↔ (s). Thus, in the created temporal graph G(s), agent v incurs a cost of one unit for each edge it creates and a penalty of K for each agent it cannot reach via a temporal path that ignores edge directions. Hence, agents aim to create as few edges as possible while still maintaining undirected temporal reachability.

Let s-v = s \ (v, Sv) denote the set of strategies of all agents other than agent v. Now consider that v changes its strategy Sv to S′v . The resulting strategy profile is s-v ∪ {(v, S′v )} which we will abbreviate as s-v ∪ S′v . We say that agent v's strategy change from Sv to S′v is an improving move, if it yields strictly less cost for agent v, i.e., if cH(v, s-v ∪ S′v ) < cH(v, s). If we additionally restrict the strategy change to a single addition or deletion 1 , we call it a greedy improving move. For an example, see Figure 1. If there is no improving move or greedy improving move of v for s, we call Sv a best response or greedy best response, respectively.

Given this definition, we can now define our solution concepts. For a given host graph H we say that the strategy profile s is in Pure Nash Equilbrium (NE) [Nash, 1950], if no agent has an improving move. We say s is in Greedy Equilibrium (GE) [Lenzner, 2012] if no agent has a greedy improving move. Note, that every greedy improving move is also an improving move and therefore every NE is also in GE.

Since we have a bijection between s and G(s), we will use the strategy profile s and its corresponding created graph G(s) interchangeably and we will say that G(s) is in NE (or GE). Note that for any graph G(s) in NE or GE, it follows that for every edge (u, v) ∈ EG(s) we have (v, u) /∈ EG(s). This is true, since otherwise one of the agents could omit the other from its strategy without removing the edge from G↔ (s) and thereby decrease its cost.

Given a temporal host graph H and a strategy profile s, we want to compare different created graphs in terms of their social cost. Here, the social cost of some created graph G(s) is defined as

Note that the social cost of G(s) equals |EG(s)| if G↔ (s) is a temporal spanner. If for some host graph H the strategy profile s∗H minimizes the social cost, we call s∗H a social optimum for H and, by extension, the corresponding graph G(s∗H ) a social optimum subgraph of H, often denoted as OPT. Since K is large, the set of social optimum subgraphs and the set of minimum temporal spanners for H coincide.

To investigate the efficiency loss from letting agents act selfishly towards minimizing their costs, we define the Price of Anarchy (PoA) [Koutsoupias and Papadimitriou, 1999]. The PoA is the worst ratio between the social cost of any stable state and the social cost of the corresponding social optimum on the same host graph. Towards a formal definition, let NEH denote the set of strategy profiles that are in NE for a given host graph H. Moreover, let Hn,tmax denote the set of all possible complete temporal host graphs with n nodes and a lifetime of at most tmax. Then, the PoA, with respect to NE, is formally defined as

The PoA w.r.t. GE is defined analogously. We write PoANE(n) instead of PoANE (n, (n2 )) when we consider host graphs with arbitrary lifetime.

Lastly, we define an important property of the game dynamics: We say that the TRNCG has the finite improvement property if any sequence of improving moves must be finite.

1 Formally, for x ∈ Sv and y ∈ VH \Sv, we have S′v = Sv \{x} or S′v = Sv ∪ {y}. Note, that typically in the literature, greedy improving moves also allow swaps, i.e. S′v = (Sv \ {x}) ∪ {y}. However, due to our model definition we can ignore swaps because if swapping x for y is improving, simply adding y is also improving.

2 Computational Complexity

In this section, we prove that computing best responses and checking strategy profiles whether they are in NE is NP-hard. This is a significant difference to network formation games with reachability objective where computing best responses is computationally easy [Bala and Goyal, 2000]. This means that adding the temporal component to the model makes it considerably harder.

Theorem 1. Given a tuple (H, s, x) consisting of a complete temporal host graph H with lifetime t ≥ 2, a strategy profile s, and a node x ∈ VH, computing a best response for x is NP-hard.

Theorem 2. Deciding whether a pair (H, s) consisting of a complete temporal host graph H with lifetime t ≥ 3 and a strategy profile s is a NE is NP-hard.

Proof. Given a universe U := {u1, . . . , uk} of k elements and a set of m sets M := {M1, . . . , Mm} ⊆ P(U), deciding whether a given set cover C ⊆ M for U is a minimum set cover is NP-hard. We give a polynomial time reduction that, given an instance (U,M, C), constructs a tuple (H, s) consisting of a temporal host graph H and a strategy profile s. We show that C is a minimum set cover if and only if s is a NE for H. Instead of defining s directly, we define G := G(s). More precisely, the host graph H is defined as follows

The set of edges of G(s) is defined as follows

Intuitively, we construct a node for each set in M and each element in U and connect each set with all its elements via a monotonically increasing path of length 2. See Figure 2 for an example of the construction. The other edges are chosen so that G is a temporal spanner and all nodes except for x play best response. This can easily be checked for every node. Hence, to check whether s is a NE, we only need to check whether x plays best response.

Let C ′ ⊆Mbe a minimum set cover for U and Sbx a best response of x for s.

Consider S′x := C ′ , meaning that x builds all the edges {x,Mi} for Mi ∈ C ′ . We see that x can now reach every node in G(s-x ∪ S′x ). Therefore, when C is not a minimum set cover and therefore |C ′ | < |C| it follows that |S′x | < |Sx| which implies that s is not a NE.

Since Sbx is a best response, x can reach every node in G(s-x ∪ Sbx ). Suppose, x buys an edge to one of the nodes uj or vij. Instead, x can buy an edge to a node Mi, such that uj ∈ Mi, without breaking reachability. Therefore, there is a best response Sbx ′ ⊆M. Note that x still reaches all nodes u ∈ U in G(s-x ∪ Sbx ′ ) and u can only be reached by x if there is M ∈ M such that x builds an edge to M. This means that C ′′ := Sbx ′ is a set cover. Therefore, if s is not a NE, it follows |Sbx | < |Sx| which implies that |C ′′ | < |C|, so C is not a minimum set cover.

It is obvious that this construction is computable in polynomial time which concludes the proof.

While NE is a very natural solution concept, the fact that it is computationally hard to compute best responses raises the question of whether it can realistically model the selfishness of the agents. Therefore, we will also consider GE because greedy best responses are computable in polynomial time.

Proposition 3. Given a tuple (H, s, x) consisting of a temporal host graph H, a strategy profile s, and a node x ∈ VH, a greedy best response for x is computable in polynomial time.

3 Existence and Properties of Equilibria

We discuss under what circumstances equilibria exist and what properties they have. We start by showing that equilibrium existence cannot be proven via potential functions.

Theorem 4. The TRNCG is not a potential game.

Note that all the strategy changes in the improving response cycle are greedy best responses, too. This means that it is not a potential game even with regard to GE.

Next, we show that equilibria always exist when the lifetime is t = 2 and that we can find one in polynomial time.

This contrasts the result from Theorem 1 which showed that, even for t = 2, computing best responses is NP-hard.

Theorem 5. Let H be a complete temporal host graph with t = 2. Then there is a strategy profile s in NE for H.

Proof. We show this by proving that H contains a spanning tree T whose edges all have the same label. Note that any strategy profile s such that G↔ (s) = T is a NE.

Let Hi denote the subgraph of H on VH that contains all edges of H of label i. We show that at least one between H1 and H2 is connected, thus proving the existence of T .

The claim trivially follows if H1 is connected. So, assume that H1 is not connected, i.e., there is a cut (X, Y ) that is traversed by none of the edges in H1. All the edges that traverse the cut (X, Y ) are in H2. Hence, H2 is connected.

In the following, we prove that stable graphs cannot contain too many edges. We first bound the number of edges for graphs with a small lifetime t.

Theorem 6. Let H be a complete temporal host graph containing n > 2 nodes and lifetime t > 1. Then any GE contains at most t(n - 2) edges.

Proof. Let s be a strategy profile and G := G(s) a GE. If there are at least n edges with some label l, some of them form a cycle. Removing one edge from the cycle does not change reachability among pairs of nodes. Therefore, each label can appear at most n - 1 times. Furthermore, if there are n-1 edges and no cycles with the same label in G, those edges would form a spanning tree of G that guarantees reachability among pairs of nodes. Then, no other edge would be needed. Therefore, if G contains at least two labels, each label appears at most (n - 2) times. Combined with only t labels existing, G contains at most t(n - 2) edges.

Next, we prove an upper bound on the number of edges in an equilibrium state independent of t. We start by introducing the concept of necessary edges which we then use to characterize a structure that cannot appear in an equilibrium.

Definition 7 (necessary edge). Let H be a complete temporal host graph with n agents, s a strategy profile and G := G(s). For each edge e = (u, v) ∈ G that u buys, we define

We say that e is necessary for u to reach the agents in AG(e).

Note, that if G is a GE, AG(e) ̸= ∅ for all e ∈ EG.

Using this definition, we characterize a structure that cannot appear in any strategy profile.

Lemma 8. Let H be a complete temporal host graph, s be a strategy profile, and G := G(s). There cannot be nodes z, u1, u2, x, y ∈ V and distinct edges e1x, e1y, e2x, e2y ∈ EG such that for i ∈ {1, 2} and j ∈ {x, y}

1. {z, ui} ∈ EG↔ \ {eij};
2. eij is bought by ui;
3. j ∈ AG(eij);

(See Figure 3.)

Proof. Towards a contradiction, suppose there are nodes z, u1, u2, x, y ∈ V and edges e1x, e1y, e2x, e2y ∈ EG as defined above. W.l.o.g. λ({z, u1}) ≤ λ({z, u2}) and λ(e1x) ≤ λ(e1y). Any temporal path from u2 to x starts with e2x (since x ∈ AG(e2x)) and has to use e1x. Otherwise, u1 could reach x by using {z, u1}, {z, u2} and then the path from u2 to x without needing e1x which contradicts x ∈ AG(e1x). The same holds for y instead of x.

Therefore, there is a temporal path P from u2 to u1, which starts with e2x and arrives at u1 no later than λ(e1x) ≤ λ(e1y). This means that u2 does not need e2y to reach y since it can use P to get to u1 and travel to y from there. This contradicts y ∈ AG(e2y).

The forbidden structure from Figure 3 implies that graphs with at least √6n 32 +n edges must contain unnecessary edges, giving us a bound on the number of edges in an equilibrium.

Theorem 9. Let H be a complete temporal host graph with |VH| = n agents and s be a strategy profile. If G := G(s) contains at least √6n 32 + n edges, then G is not a GE.

Proof. Towards a contradiction, suppose that G is a GE and |EG| ≥ √6n 32 + n. As shown in the full version [Bil`o et al., 2023], there is a node z ∈ VG and a set M ⊂ VG such that

1. |M| = ⌈ 1 3 √6n⌉;
2. (u, z) ∈ EG, for every u ∈M;
3. Each u ∈M has a set Eu ⊆ EG of at least 23 √6n outgoing edges (u, v) with z ̸= v and λG((u, z)) ≤ λ((u, v)). See Figure 4 for an illustration.

For each edge e ∈ Eu, let ae ∈ AG(e) be a representative of AG(e). Note that AG(e) ̸= ∅ because G is a GE, so those representatives always exist. For each u ∈ M, we define

Intuitively, Du contains nodes that z can reach by going over u and that u needs to buy an edge for.

We see that the forbidden structure from Lemma 8 appears if there are two nodes u, v ∈ M such that |Du ∩ Dv| ≥ 2. We can therefore assume |Du ∩ Dv| ≤ 1 for all u, v ∈ M. Also, for e, e′ ∈ Eu we have AG(e) ∩ AG(e′ ) = ∅ since there cannot be two edges that are necessary for u to reach the same node. From this, we get |Du| ≥ |Eu| ≥ 23 √6n.

Using the inclusion-exclusion principle, we get

This is a contradiction since G has only n nodes.

4 Quality of Equilibria

Finally, we characterize the quality of equilibra by analyzing the Price of Anarchy (PoA). We show that the PoA with regard to NE and GE are within a log(n)-factor of each other, meaning that any bound on the easier to analyze Greedy Equilibria also yields a bound for Nash Equilibria. We the proceed to give several upper and lower bounds.

For analyzing the PoA, we start by upper bounding the cost of the social optimum. The following result follows from [Casteigts et al., 2021].

Theorem 10. Let H be a complete temporal host graph with |VH| = n agents and OPT be a social optimum for H. Then SCH(OPT) = |EOPT| ∈ O(n log(n)).

Whether we consider NE or GE has an impact on the PoA. However, we show that these two PoA's differ only by at most a factor of O(log(n)).

Proof. Let H be a complete temporal host graph with n vertices and lifetime t. Moreover, let s be a strategy profile in GE and let s∗H the social optimum for H such that PoAGE(n) = SCH(s) SCH(s∗H ) . We construct a new temporal host graph H′ by relabeling all edges not in G(s) to t + 1.

First, we argue that s is in NE with respect to H′ . Consider a strategy change for a node u that removes k edges and adds l edges. Since s is stable against edge removal, removing those k edges will lead to at least k nodes no longer being reachable from u. Additionally, agent u can use the l added edges only to reach the other endpoints of the edges since all edges not in G(s) have a higher label in H′ than all the edges in G(s). Therefore, for agent u to reach everyone after the strategy change, we need k ≤ l which means that the strategy change is not an improving move.

We also have SCH(s) = SCH′ (s) and SCH(s∗H ) ≥ n - 1. Let s∗H′ be a social optimum for H′ . By Theorem 10

we have SCH′(s∗H′) ∈ O(n log(n)), from which we get SCH(s∗H ) ∈ Ω ( SCH′ (s∗H′ ) log(n) ) and therefore

When considering the PoA with respect to a fixed maximum lifetime tmax instead of a fixed n, we get an upper bound for the PoA of tmax.

Theorem 12. For fixed maximum lifetime tmax, we have PoAGE(n, tmax) ≤ tmax - tmax n-1 . For tmax = 2, we have PoAGE(n, 2) = PoANE(n, 2) = 2 - 2 n-1 .

Proof sketch. The upper bound on PoAGE(n, tmax) follows directly from Theorem 6 by lower bounding the social cost of the optimum with n - 1.

For the tight lower bound when tmax = 2 which also holds for PoANE(n, 2), we construct the graph from Figure 5.

We show that the PoA scales at least logarithmically with n by giving a class of host graphs that have equilibria which are by a logarithmic factor worse than the social optimum.

Proof. Let n ≥ 8 be a power of 2. Kempe et al. [2002] proved how to label a log(n)-dimensional hypercube with labels in {1, . . . , log(n)} so as the resulting temporal graph is a minimal temporal spanner. The idea of our proof is to define the host graph H on n nodes so that it contains the log(n)- dimensional hypercube which is a NE regardless of the strategy profile that generates it, and a spanning tree formed by edges having the same label 1 + log(n).

Formally, the nodes are bitstrings of length log(n). The complete host graph H is defined as follows

The strategy profile s induces a graph G := G↔ (s) with

EG↔ := {{u, v} | v and u differ in exactly one bit}.

Figure 5 shows an illustration of G for n = 8.

Since n ≥ 8, H contains a spanning tree OPT whose edges are all labelled with log(n) + 1. Since OPT is a temporal spanner, it is a social optimum with SCH(OPT) = n - 1.

G is a hypercube graph containing n2 log(n) edges and therefore SCH(G) = n2 log(n). If G is a NE, we get the desired bound

Finally, we argue that G is a NE. First, we observe that there is exactly one temporal path from every node u to every other node v. When considering the bit strings of these two nodes, the path flips all of the bits that are different in u and v in ascending order. By definition of H, all of those edges exist and are labeled in ascending order.

Secondly, note that all edges {u, v} ∈ EG↔ are needed by both of their end points to reach each other. By definition of EG, the bitstrings of u and v differ only in one position p. When removing the edge {u, v}, a temporal path starting from u has to flip another bit than p. In a temporal path on G, this bit can never be flipped back, so v cannot be reached. We also observe that buying other edges outside of EG cannot replace any edge in EG.

Hence, G is a temporal spanner and no agent can improve their strategy, which makes s a NE.

An upper bound for the PoA follows from Theorem 9.

Proof. This follows from Theorem 9 and by lower bounding the social cost of the optimum with n - 1.

5 Conclusion and Outlook

In this paper, we combine game-theoretic network creation with temporal graphs. To this end, we defined and analyzed the Temporal Reachability Network Creation Game.

Even though we consider a restricted setting with unit cost on each edge and a complete host graph, we show NPhardness for computing best responses and for deciding NE, showing that adding temporal aspects to the model makes it much harder. As our main contribution, we show non-trivial structural properties of equilibria and use them to derive several upper and lower bounds on the Price of Anarchy.

Since the upper bound of O(√n) on the PoA only uses one local property, we believe that the PoA is closer to our lower bound of Ω(log(n)). Another important open question is settling the existence of equilibria for all complete temporal host graphs. We conjecture that equilibria exist, but, based on our efforts, even proving this for lifetime t = 3 is challenging.

We laid the groundwork for future research in this field. There are many natural extensions of our model. As far as agent strategy is concerned, the agents might want to minimize the distance to all others or, due to the time attribute introduced by our model, the agents may want to minimize their arrival time at the other agents. Also structural properties of the host graph could be altered. For enhanced realism, the edges could be directed, have non-uniform buying costs, and/or non-instant traversal times. The rules of the game can also be adjusted, for example by allowing cooperation.