# flowbased_network_creation_games__0bff044e.pdf

Flow-Based Network Creation Games

Hagen Echzell , Tobias Friedrich , Pascal Lenzner and Anna Melnichenko Hasso Plattner Institute, University of Potsdam, Germany

Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selﬁshly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like Vo IP. However, with today s abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufﬁcient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selﬁsh agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network ﬂow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is 1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.

1 Introduction Many of the networks we crucially rely on nowadays have evolved from small centrally designed networks into huge networks created and decentrally controlled by many selfish agents with possibly conﬂicting goals. For example, the structure of the Internet is essentially the outcome of a repeated strategic interaction by many selﬁsh economic agents [Papadimitriou, 2001; Tardos, 2004], e.g., Internet service providers (ISPs). Hence, such Internet-like networks can be analyzed by considering a strategic game which models the interaction of the involved agents. This insight has inspired researchers to propose game-theoretic models for

the decentralized formation of networks, most prominently the models in [Myerson, 2013; Jackson and Wolinsky, 1996; Bala and Goyal, 2000a; Fabrikant et al., 2003] and many variants of them. In these models selﬁsh agents select strategies to maximize their utility in the created network. Thus, the structure of the created network and corresponding agent utilities depend on the selﬁshly chosen strategies of all agents. To the best of our knowledge, the utility of the involved agents in all the existing models depends on the agents centrality or the size of their connected component and the cost spent for creating links. Striving for centrality, e.g., for low hop-distances to all other nodes in the created network, certainly plays an important role for the involved selﬁsh agents, e.g., ISPs, but it is not the only driving force. What has been completely neglected so far are bandwidth considerations. In this paper we take the ﬁrst steps into this largely unexplored area of game-theoretic network formation with bandwidth maximization. In particular, we consider budgetconstrained agents that strategically form links to other agents to maximize their ﬂow value towards all other nodes. This models agents that optimize the networks for data-intensive applications like online streaming instead of low-latency applications like Vo IP. Interestingly, by the Max Flow Min Cut Theorem [Ford and Fulkerson, 1956], ﬂow maximization corresponds to connectivity maximization which is tightly related to network robustness. While there have been works which consider robustness aspects as side constraints, also the aspect of maximizing the created network s robustness is, to the best of our knowledge, entirely unexplored. While classical network formation models with focus on centrality yield equilibrium networks that are sparse and have low diameter, our work shows that focusing on bandwidth/connectivity may explain why densely connected subnetworks, like k-core structures, and larger cycles appear in real-world networks: they are essential for its connectivity.

1.1 Model and Notation

We propose the Flow-Based Network Creation Game (ﬂow NCG), which is a variant of the well-known Network Creation Game [Fabrikant et al., 2003] where the agents create edges to maximize their ﬂow value as deﬁned by the classical Max-Flow Problem [Ford and Fulkerson, 1956]. Given a set of n selﬁsh agents which corresponds to the set of nodes V of a weighted directed network G = (V, E). Each agent

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

has a uniform budget of k N, with k < n, to establish connections to other agents. In the created graph G each edge has a capacity c : E(G) N. We deﬁne the degree of a node v in G as deg G(v) = P (x,v) E,x V c(x, v) + P (v,y) E,y V c(v, y), i.e., as the sum of the capacities of all incoming and outgoing edges. The edge set and capacities are deﬁned by the strategies of the agents. In particular, each agent strategically decides how to spend its budget, i.e., which subset of incident edges to buy and for each bought edge its capacity. Therefore, the strategy Sv of an agent v is a set of tuples (x, c(v, x)) V \{v} [k], where [k] = {1, . . . , k}. Here x denotes the node to which an edge is formed and c(v, x) the capacity of that edge bought by agent v. For nodes w V to which no edge is formed, we assume that c(v, w) = 0. A strategy Sv is feasible if the total capacity of all edges in Sv does not exceed the given budget k, i.e., P x V \{v} c(v, x) k. If (x, c(v, x)) Sv, we call v the owner of the edge (v, x) with capacity c(v, x). The vector of all agents strategies s = (Sv1, . . . , Svn) is denoted as a strategy proﬁle. Any strategy proﬁle s uniquely speciﬁes the weighted directed network G(s) = (V, E(s)) where (v, x) E(s) of capacity c(v, x) if and only if agent v buys the edge to x with non-zero capacity c(v, x). For sending ﬂow in the network G(s), we assume its undirected version F(s) = (V, EF (s)) where {v, x} EF (s) if (v, x) E(s) or (x, v) E(s) and the capacity c({v, x}) is deﬁned as c({v, x}) = c(v, x) + c(x, v). Thus, for sending ﬂow, any edge of G(s) can be used in both directions. See Figure 1 for an illustration of G(s) and its corresponding undirected version F(s). Note that throughout the paper

Figure 1: Graph G(s) and its undirected version F(s) for s = (Sv, Sx, Sy, Sz) with Sv = {(x, 1), (z, 1)}, Sx = {(v, 1), (z, 1)}, Sy = {(x, 1), (z, 1)}, Sz = {(y, 2)}. Agent z has degree 5 and can send a ﬂow of value 3, 3 and 4 to the agents v, x and y respectively.

we only work with G(s) and we will always assume its undirected version F(s) when computing ﬂow values. We call a directed weighted network G feasible if the sum over the weights of all incident outgoing edges for each node is at most k. Thus, we have a bijection between the set of feasible networks and the set of strategy proﬁles. Therefore, we will further omit s in G(s) if it is clear from the context and we will use G and s interchangeably if G = G(s). Let λG(s)(v, x) = P v1 V1,v2 V2,{v1,v2} EF (s) c({v1, v2}) be the capacity of a minimum v-x-cut (V1, V2) disconnecting node v from x in F(s) which we also call the local edge connectivity between x and v. The minimum over all pairwise local edge connectivities in G(s) is called the edge connectivity of G(s) and is denoted as λ(G(s)). A cut (V1, V2) in G(s), where V1 V2 = V and V1 V2 = , such that λ(G(s)) = P v1 V1,v2 V2,{v1,v2} EF (s) c({v1, v2}) is called a minimum cut (min-cut) of G(s). Note that cuts in G(s) are

always deﬁned on its undirected version F(s). By the Max Flow Min Cut Theorem [Ford and Fulkerson, 1956], the size of the min-v-x-cut equals the value of the max-ﬂow between nodes v and x. Hence, we use the local edge connectivity of v and x interchangeably with the value of maximum v-x-ﬂow. We deﬁne two versions of the ﬂow NCG. The ﬁrst is called the Average Flow NCG (avg-ﬂow NCG). For a given strategy proﬁle s, the utility function of an agent v is deﬁned as the average maximum ﬂow value to each other node in the network: u(v, s) = P i V \{v} λG(s)(v,i)

n 1 . The social utility of network

G(s) is the average agent utility, i.e., u(s) = P v V u(v,s)

n . The second variant is called the Minimum Flow NCG (minﬂow NCG). The utility of an agent in network G(s) is the size of the min-cut of the network λ(G(s)). Note that this value is the same for all agents in G(s). We deﬁne a tie-breaking between strategies for an agent which yield the same mincut of G(s): agents try to maximize the number of nodes with local edge connectivity exceeding λ(G(s)), i.e., to increase the number of highly robust connections. In particular, we deﬁne the agent s utility as the following vector: u(v, s) = (u1(v, s), u2(v, s)), where u1(v, s) = λ(G(s)) and u2(v, s) = |{i V \{v} : λG(s)(i, v) > λ(G(s))}|. We call the second component of the utility function u2(v, s) as the number of well-connected nodes. We assume that agents aim for maximizing their utility vector lexicographically. We deﬁne the social utility of a network in the min-ﬂow NCG as the edge connectivity of the network: u(s) = λ(G(s)). The social optimum (OPT) is a network G(s ) which maximizes the social utility u(s ) over all feasible strategy proﬁles. We say agent v reduces the capacity of the v-x edge by ℓ if it either decreases the capacity c(v, x) by ℓ(if c(v, x) > ℓ) or if it deletes the edge (v, x) (if c(v, x) = ℓ). Analogously, agent v increases the capacity of the v-x edge if it either increases the capacity c(v, x) by ℓ(if (x, c(v, x)) Sv) or if it buys the edge (v, x) with capacity ℓ. An improving move for agent vi is a strategy change from Svi to S vi such that u(vi, (s vi, s vi)) > u(vi, s), where (s vi, s vi) is a new strategy proﬁle which only differs from s in the strategy of agent vi. We say that agent v plays its best response Sv if there is no improving move for agent v. A strategy change towards a best response is called best response move. A sequence of best response moves which starts and ends with the same network is called a best response cycle. If every sequence of improving moves is ﬁnite, then the game has the ﬁnite improving property (FIP) or, equivalently, the game is a potential game [Monderer and Shapley, 1996]. We say that a network G(s) is in pure Nash equilibrium (NE) if all agents play a best response in G(s). We measure the loss of social utility due to the lack of a central authority and the agents selﬁshness with the Price of Anarchy (Po A) [Koutsoupias and Papadimitriou, 1999]. Let min NE(n, k)(max NE(n, k)) be the minimum (maximum) social utility of a NE with n agents with budget k, and let opt(n, k) be the corresponding utility of the social optimum. For given n and k the Po A is opt(n,k) min NE(n,k) and the Price of

Stability (Po S) is opt(n,k) max NE(n,k). The latter measures the minimum sacriﬁce in social utility for obtaining a NE network.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

1.2 Related Work

The NCG was proposed in [Fabrikant et al., 2003] and has been an object of intensive study for almost two decades. The model depends on an edge-price parameter α which deﬁnes the cost of any edge of the network and the agents objective function is to minimize their closeness centrality, i.e., their average hop-distance to all other nodes in the created network. A constant Po A was shown for almost all values of α, except for the range where α n, where only an upper bound of o(nε), for any ε > 0, is known [Demaine et al., 2012]. See [ Alvarez and Messegu e, 2019; Bil o and Lenzner, 2020] for the latest improvements on the Po A and a more detailed discussion. Moreover, [Kawald and Lenzner, 2013] proved that the NCG does not have the FIP. Many variants of the NCG have been proposed and analyzed but so far all of them consider agents which strive for centrality or only for creating a connected network. Related to our model are versions where agents can only swap edges [Alon et al., 2013; Mihal ak and Schlegel, 2012], bounded-budget versions [Laoutaris et al., ; Ehsani et al., 2015] and two versions which focus on robustness: in [Meirom et al., 2015] agents maintain two vertex-disjoint paths to any other node and in [Chauhan et al., 2016] agents consider their expected centrality with respect to a single random edge failure. Thus agents in these models enforce 2vertex-connectivity or 2-edge-connectivity in the created network which are much weaker robustness concepts compared to our approach. Another line of research are Network Formation Games [Bala and Goyal, 2000a] where agents only strive for being connected to all other nodes. Several variants with focus on robustness have been introduced: In [Bala and Goyal, 2000b] a model with probabilistic edge failures, in [Kliemann, 2011; Kliemann et al., 2017] adversarial models where a single edge is removed after the network is formed, in [Goyal et al., 2016; Friedrich et al., 2017] a version where a node is attacked with deterministic spread to neighboring nodes, and in [Chen et al., 2019] a model with probabilistic spread. To the best of our knowledge, no related model exists where agents try to maximize their connectivity. In the realm of classical optimization, maximizing the robustness of a network with a given budget is a frequently studied network augmentation problem, see, e.g., [Watanabe and Nakamura, 1987; Frank, 1994; Nagamochi and Ibaraki, 2008] for surveys. However, due to the centralized optimization view, these problems are very different from our model.

1.3 Our Contribution

By incorporating bandwidth considerations into the classical NCG we shed light on a largely unexplored area of research. In our Flow-Based NCG agents strategically create links under a budget constraint to maximize their average or minimum ﬂow value to all other agents. This is in stark contrast to existing models which focus on agents aiming for centrality or for maximizing the size of their connected component. For our novel modes, we provide an efﬁcient algorithm to compute a social optimum network and we uncover important structural properties of it. A major part of our research is a rigorous study of the structure and quality of the induced

equilibrium networks. We show that NE networks are guaranteed to be connected and that they contains a subgraph that is at least (k + 1)-edge-connected. Moreover, any NE in the min-ﬂow NCG is always (k + 1)-edge-connected. Most importantly, we prove that the social utility of all NE networks is close to optimum. More precisely, our Po A results for both models guarantee that the social utility of any NE is at least half the optimal utility, i.e., Po A 2, and this bound is tight for the min-ﬂow NCG and almost tight for the avg-ﬂow NCG. Besides this, we prove for both versions that the Po S = 1 and that the FIP does not hold. See Table 1 for an overview. Due to limited space, some proofs are sketched or omitted.

2 Social Optimum We analyze the structure of the OPT networks. In particular, we show a generic network construction with maximum social utility 2k for both game models.

Algorithm 1: Algorithm for computing the OPT

input : unweighted directed clique Kn =(V, E) output: social optimum network G

2 for i 1 to k do

3 ﬁnd a directed Hamiltonian cycle Cn in Kn;

4 add the cycle to the output graph G G Cn, i.e., increase capacity of each (u, v)-connection in G by 1 if (u, v) Cn;

Theorem 1. Algorithm 1 computes an optimal network with social utility 2k for the avg-ﬂow NCG and min-ﬂow NCG in polynomial time.

Proof. First, we prove a general upper bound on the social utility of OPT. Let G be an optimal network in the minﬂow NCG. The social utility of G equals the edge connectivity of G which is at most minv V deg G(v). The handshake lemma yields P v V deg G(v) = 2 P e E(G) c(e) 2nk, where the last inequality holds because every agent can build edges of the total capacity of at most k. Since the minimum degree is at most the average degree in the network, we get u(s) = λ(G(s)) minv V deg G(v) 2k. In the avg-ﬂow NCG, the social utility is u(s) = 1 n P v V u(v, s) where u(v, s) is the average local edge connectivity over all pairs (v, V \ {v}). The local edge connectivity of any pair of nodes v, w is at most min{deg G(v), deg G(w)}. Thus, u(s) 1

n P v V deg(v) 2k, again by the handshake lemma. Now we show that the social utility of the graph G produced by the algorithm matches the upper bound which implies that G is optimal. Since each node in G has an outdegree of k and no self-loops, G is a feasible network for both games. For any two nodes v, w V the minimum v-w-cut contains two edges of each Hamiltonian cycle added to G during the algorithm s run. Thus, the local edge connectivity of any pair of nodes equals 2k which implies u(G) = 2k in both games. It is easy to see that the algorithm runs in polynomial time since the Hamiltonian cycle can be constructed greedily.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Model u(OPT) Po S Po A FIP min-ﬂow NCG 2k (Thm. 1) 1 (Thm. 6) 2k k+1 (Thm. 9) no (Thm. 15)

avg-ﬂow NCG 2k (Thm. 1) 1 (Thm. 6) < 2 (Thm. 13) no (Thm. 15) 2k k+ k(k 1)

n 1 if k 0.5 + n 0.75 (Thm. 14)

2k k+1 if k > 0.5 + n 0.75 (Thm. 14)

Table 1: Overview of our results

Theorem 2. In the min-ﬂow NCG and the avg-ﬂow NCG OPT is a connected 2k-regular network.

3 Structural Properties of Equilibria In this section we prove structural properties of NE networks, which we will use later on to derive our Po A bounds. Theorem 3. In the min-ﬂow NCG and the avg-ﬂow NCG all agents use all of their k budget units in an NE network.

Proof. Consider a network G = G(s) which is in NE. Assume towards a contradiction that there is an agent v V which spends strictly less than k units of its budget in G(s). For the min-ﬂow NCG, we have, by deﬁnition, u(v, s) = (u1(v, s), u2(v, s)) = (λ(G), u2(v, s)). Let w V be an agent such that λG(v, w) = λ(G). Then agent v can improve its strategy by increasing the capacity of the edge (v, w). Indeed, after the strategy change (s to s = (s v, s v)) either the edge connectivity of the network increases, i.e., λ(G(s )) > λ(G(s)) or the edge connectivity does not change but u(v, s ) = (u1(v, s), u2(v, s )) (u1(v, s), u2(v, s) + 1) > u(v, s). In both cases agent v improves, which contradicts that G is in NE. For the avg-ﬂow NCG it is easy to see, that building an additional edge towards any agent w V \ {v} increases their local edge connectivity, while not decreasing the local edge connectivity between any pair of agents, and thus this results in a strategy s = (s v, s v) such that uv(s ) > uv(s). Thus, agent v can improve, which contradicts that G is in NE.

Theorem 4. In the min-ﬂow NCG and the avg-ﬂow NCG any equilibrium network is connected.

Proof. For both games assume towards a contradiction that there is a disconnected equilibrium network G. Note that λ(G) = 0. By Theorem 3 all agents use all of their budgets, thus, every vertex has an outgoing edge in G. As the number of nodes is ﬁnite, there must be a directed cycle in every weakly connected component of G. Thus, any agent v in such a cycle can remove an existing outgoing cycle-edge without disconnecting the weakly connected component and add the edge to any node of another component in G. In the min-ﬂow NCG, this move either increases the edgeconnectivity of the network, i.e., it increases u1(v, G), or it increases the number of well-connected agents, i.e., it increases u2(v, G) and u1(v, G) remains unchanged. Thus, agent v can improve which contradicts that G is in NE. For the avg-ﬂow NCG, consider two weakly connected components X, Y V in G such that |X| |Y |. Thus

there must be an agent v in X which can reduce the capacity of one connection in X by 1 and add an edge of capacity 1 to some other node in Y . This move changes only the local edge-connectivity between v and any other node by at most 1. Thus, its utility changes by at least |X| 1

n 1 > 0. Thus, agent v can improve which contradicts that G is in NE.

The next property will be about j-clusters, which are subset of nodes C V, |C| 2, from G such that the C-induced subgraph of G has edge connectivity of at least j.

Theorem 5. For the min-ﬂow NCG and the avg-ﬂow NCG, if G is in NE, there is a (k + 1)-cluster in G.

Proof. Consider a NE network G(s). We partition G(s), or more precisely its undirected version F(s), into components by the following method: As long as there is a cut (X, Y ) of size at most k, remove all edges of (X, Y ) from G. At each step of the algorithm either the algorithm terminates, i.e., there is a (k + 1)-cluster in G, or the number of connected components increases by at least 1 while the number of edges decreases by at most k. By Theorem 3 the sum of edge weights in the initial graph is nk. Hence, if a (k + 1)- cluster was not found, the algorithm produces a network containing n components and a set of edges of the total capacity of at least k. Since self-loops are not allowed, we have a contradiction. Thus, the process must ﬁnd a (k + 1)-cluster.

4 Price of Stability

Theorem 6. The Po S is 1 in the min-ﬂow NCG and the avgﬂow NCG.

Proof. Consider a directed cycle C where every edge has capacity k. We will show that C is a NE in both games. For the min-ﬂow NCG, consider a node, say v1, in C = G(s). Agent v1 owns one edge, w.l.o.g., (v1, v2) of capacity k. The only strategy change that v1 can perform is to reduce the capacity of the edge (v1, v2) and to spend the rest of the budget on new edges to other nodes. This move strictly decreases the degree of the node v2. Since the edge connectivity of any network is at most its minimum degree, which then is the degree of v2, this implies that the strategy change decreases v1 s utility. Hence, there is no improving move for agent v1, which, by symmetry, implies that every agent plays best response in C which proves that C is in NE. Analogously, in the avg-ﬂow NCG the same strategy change by any of the agents, say v1, decreases the degree of the respective neighbor v2. Thus, the local edge connectivity

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

of this pair of nodes decreases. At the same time, the local edge connectivity of v1 with other nodes does not change since it does not exceed the minimum degree of the pair, i.e., the degree of node v1. This implies a decrease of the average local edge connectivity for agent v1, i.e., the decrease of v1 s utility. Thus, all agents play best response and C is a NE. By Theorem 1 the social utility of OPT is 2k. We have proved the existence of a NE network with the same social utility for both models. Thus, Po S = 1 for both games.

5 Price of Anarchy

In this section we present our main results, which are a tight bound in the Po A for the min-ﬂow NCG and an almost tight Po A bound for the avg-ﬂow NCG. Moreover, whereas all previous results show the similarity of the min-ﬂow NCG and the avg-ﬂow NCG we will now highlight their differences. In particular, we show that NE networks in the min-ﬂow NCG may not be NE networks in the avg-ﬂow NCG and vice versa.

5.1 Po A of the Min-Flow NCG We start by providing a NE network for the min-ﬂow NCG with minimum social utility.

Theorem 7. For a given n and k such that k < n, there is a NE network G such that u(G) = k + 1 in the min-ﬂow NCG.

Proofsketch. We consider the following generic construction for a given number of agents n and budget k < n. Consider a set of nodes {v1, . . . , vn} = V (G) and a set of edges E(G) where for all 1 i < k each node vi is connected with a node vi+1 by an edge (vi, vi+1) with capacity c(vi, vi+1) = k (i 1) and by an edge (vi+1, vi) with capacity c(vi+1, vi) = i. Moreover, there is an edge (vk, vn) with capacity 1 and a set of sequential edges, for all k i n 1, (vi+1, vi) with capacity k. See Figure 2 for illustration of the construction. We claim that G is in NE in the min-ﬂow NCG. We omit the proof due to the space restrictions.

vn-1 k v1 v2 1

Figure 2: NE network in the min-ﬂow NCG. Note that this network is not a NE in the avg-ﬂow NCG. Indeed, agent v2 can delete the edge (v2, v1) and create the edge (v2, vn) with capacity 1.

The next result shows that any NE network in the minﬂow NCG is (k + 1)-edge-connected.

Theorem 8. The social utility of any NE network is at least k + 1 in the min-ﬂow NCG.

Proof. Assume towards a contradiction that there is a NE G = (V, E) such that it contains a cut (A, B) such that λ(G) = P e (A,B) c(e) k. By Theorem 5 there is an induced subgraph K = (C, E(K)) G such that C is a (k + 1)-cluster in G. W.l.o.g., let C A. Consider two

nodes v C and w B. Since k + 1 λ(K) deg K(v), there is a node x K which has an edge to v in K. We will show that agent x can signiﬁcantly improve on its strategy by reducing the capacity of the edge (x, v) by 1 and creating the edge (x, w) with capacity 1 (or increasing its capacity by 1 if it already exists). We denote the obtained networks as G = (V , E ) and K = (C, E ). Note that λG (x, v) λK (x, v) + 1 λK(x, v) 1 + 1 k + 1. If λ(G ) > λ(G), then agent x improved on its strategy since u1(x, G ) > u1(x, G). Thus, G is not a NE. If λ(G ) < λ(G), there is a cut (X, Y ), x X, v Y in G of size strictly less than λ(G) k. On the other hand, the size of the (X, Y )-cut is at least λG (x, v) k + 1 > λ(G). Hence, we have a contradiction. Finally, we consider the case λ(G ) = λ(G). We will show that u2(x, G ) > u2(x, G). First, note that for any node a V \ {x} such that λG(x, a) > λ(G), λ G(x, a) > λ(G ) holds. Indeed, in case λG (x, a) < λG(x, a), we have λG (x, a) = λG (x, v) k + 1 > λ(G) = λ(G ). In case λG (x, a) λG(x, a), and since λG(x, a) > λ(G), we have λG (x, a) > λ(G) = λ(G ). Therefore, after the strategy change u2(x, G ) u2(x, G) holds. Second, λG(x, w) = λ(G), since x A and w B, whereas λG (x, w) > λ(G ), i.e., u2(x, G ) > u2(x, G). Hence, u(x, G ) = (u1(x, G), u2(x, G )) > u(x, G), i.e., agent x does not play a best response in G. This contradicts the assumption that G is a NE.

Now we put the pieces together to derive our tight bound. Theorem 9. The Po A in the min-ﬂow NCG is 2k k+1.

Proof. By Theorem 1 and Theorem 8 we get that Po A 2k k+1. By Theorem 7 there is a NE network that meets the social utility lower bound, hence the Po A bound is tight.

5.2 Po A of the Avg-Flow NCG We start with providing constructions for two NE network with almost minimum social utility. Theorem 10. For n and k with 2 k < n, there is a NE network G such that u(G) = k+ k(k 1)

n 1 in the avg-ﬂow NCG.

Proofsketch. We construct the following network G = (V, E). We arrange k nodes in a circle such that each node has one edge with capacity k to the subsequent node. The remaining n k nodes each have a unit-weight edge to each node of the circle. See Figure 3 for an illustration of the construction. We omit the proof due to space constraints.

vk+2 vk+1 v1

Figure 3: NE network in the avg-ﬂow NCG. Note that this network is not a NE in the min-ﬂow NCG since it is not (k+1)-edge-connected, e.g., v1 can improve by reducing the capacity of the edge (v2, v3) by 1 and increasing the capacity of the edge (v2, vk+1) by 1.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Theorem 11. For a given n and k such that k < n, there is a NE network G such that u(G) = k + 1 in the avg-ﬂow NCG.

Proofsketch. Consider the following star-like network G = (V, E) with the set of nodes V = {c} {a1, . . . , ak 1} {b1, . . . , bn k}. Here c is a central node connected with all ai nodes by an edge with capacity 1. All ai nodes are connected with the central node by edges with capacity k. Each node bi, i = 1, . . . , n k 1 has an edge (bi, c) with capacity k 1, and only one node bn k has an edge (bn k, c) of capacity k. Also, there is an edge (c, b1) with capacity 1. Finally, all bi nodes are sequentially connected by edges (bi, bi+1) with capacity 1. See Figure 4 for illustration of the construction. The proof of the statement is rather technical, so we omit it due to the space constrains.

Figure 4: NE network in the avg-ﬂow NCG.

A similar technique as in the proof of Theorem 8 can be applied to prove that the edge connectivity of any NE network in the avg-ﬂow NCG is at least k. Theorem 12. For k 2, the edge connectivity of any NE network in the avg-ﬂow NCG is at least k.

Proofsketch. Assume G is a NE and λ(G) < k. Consider a min-cut (A, B) of size λ(G). By performing the same procedure as in the proof of Theorem 5 in each set A and B, we get two sets X A and Y B of a maximum size such that for each pair of nodes v1, v2 in the same set, λG(v1, v2) k. W.l.o.g., |Y | |X|. For some edge (v, w) in a k-cluster in X, agent v can reduce its capacity by 1 and create a new edge (v, y) with capacity 1 to y Y (or increase its capacity by 1 if it exists). The local edge connectivity decreases by at most 1 only between u and nodes in X, and increases by 1 between u and all nodes in Y . Thus, the utility changes by at least |X| 1

n 1 > 0, i.e., it is an improving move.

Theorem 13. For the avg-ﬂow NCG we have Po A< 2.

Proof. For k = 1 a trivial NE of social utility 2 is a directed cycle with all edge capacities equal 1. For general k 2, by Theorem 12, any NE is at least kedge-connected. On the other hand, by Theorem 5, any NE contains a (k + 1)-cluster of at least two nodes. Thus, at least two nodes have their utility of at least k+1+k(n 2)

n 1 > k and all other nodes have the utility of at least k. Hence the social utility is strictly grater than k(n 2)+2k

Now we provide an almost matching lower bound on the Po A. Theorem 14. For the avg-ﬂow NCG, we have Po A max n 2k k+k(k 1)/(n 1), 2k k+1 o .

Proof. By Theorem 10 and Theorem 11 the social utility of a worst-case equilibrium network is at most min{k + k(k 1)

n 1 , k + 1}. Therefore, for k 0.5 + n 0.75 the Po A

is at least 2k/ k + k(k 1)

n 1 = 2(n 1) n+k 2. Thus, for large n, the Po A tends to 2, i.e., the upper bound. With a high budget, i.e., for k > 0.5 + n 0.75, the Po A is at least 2k k+1.

6 Game Dynamics We analyze whether our games are guaranteed to converge to an NE under improving response dynamics. Unfortunately, this is not true for the min-ﬂow NCG and the avg-ﬂow NCG. Theorem 15. The min-ﬂow NCG and the avg-ﬂow NCG do not admit the FIP.

Proofsketch. We provide an improving response cycle (IRC) for each variant of the game depicted in Figure 5 and Figure 6. Note that the ﬁrst and the last networks are isomorphic in both sequences, which implies that we indeed have IRCs.

Figure 5: An IRC for the min-ﬂow NCG with k = 2. Since G and G

are isomorphic, the sequence of the improving moves recurs to G.

b b b c c c

Figure 6: An IRC for the avg-ﬂow NCG with k = 3. Since G and G

are isomorphic, the sequence of the improving moves recurs to G.

7 Conclusion We made the ﬁrst steps into the promising direction of investigating network formation games with bandwidth/connectivity considerations. For this, we proposed two versions: the min-ﬂow NCG where agents strive to maximize the connectivity of the entire network; and the avg-ﬂow NCG where agents try to maximize their average ﬂow value towards all other agents. For both versions our main focus was the analysis of equilibrium networks. In particular, we proved that NE networks contain a highly-connected component in the avg-ﬂow NCG, while in the min-ﬂow NCG the entire NE network must be highly-connected. This may explain the occurrence of k-core structures in many real-world networks. Our main results are (almost) tight bounds of less than 2 on the Po A which shows that NE networks are close to optimum and no external coordination is needed in our games. An important direction for future work is a generalization of the presented model to non-uniform budgets, non-integer edge capacities and a combination of bandwidth and centrality objectives for the agents.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

[Alon et al., 2013] Noga Alon, Erik D Demaine, Mohammad T Hajiaghayi, and Tom Leighton. Basic network creation games. SIAM Journal on Discrete Mathematics, 27(2):656 668, 2013. [ Alvarez and Messegu e, 2019] Carme Alvarez and Arnau Messegu e. On the price of anarchy for high-price links. In WINE 19, pages 316 329. Springer, 2019. [Bala and Goyal, 2000a] Venkatesh Bala and Sanjeev Goyal. A noncooperative model of network formation. Econometrica, 68(5):1181 1229, 2000. [Bala and Goyal, 2000b] Venkatesh Bala and Sanjeev Goyal. A strategic analysis of network reliability. Review of Economic Design, 5(3):205 228, 2000. [Bil o and Lenzner, 2020] Davide Bil o and Pascal Lenzner. On the tree conjecture for the network creation game. Theory Comput. Syst., 64(3):422 443, 2020. [Chauhan et al., 2016] Ankit Chauhan, Pascal Lenzner, Anna Melnichenko, and Martin M unn. On selﬁsh creation of robust networks. In SAGT 16, pages 141 152, 2016. [Chen et al., 2019] Yu Chen, Shahin Jabbari, Michael Kearns, Sanjeev Khanna, and Jamie Morgenstern. Network formation under random attack and probabilistic spread. ar Xiv preprint ar Xiv:1906.00241, 2019. [Demaine et al., 2012] Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The price of anarchy in network creation games. ACM Trans. on Algorithms (TALG), 8(2):13, 2012. [Ehsani et al., 2015] Shayan Ehsani, Saber Shokat Fadaee, Mohammad Amin Fazli, Abbas Mehrabian, Sina Sadeghian Sadeghabad, Mohammadali Safari, and Morteza Saghaﬁan. A bounded budget network creation game. ACM Trans. on Algorithms (TALG), 11(4):34, 2015. [Fabrikant et al., 2003] Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H Papadimitriou, and Scott Shenker. On a network creation game. In PODC 03, pages 347 351, 2003. [Ford and Fulkerson, 1956] Lester R. Ford and Delbert R. Fulkerson. Maximal ﬂow through a network. Canadian Journal of Mathematics, 8:399 404, 1956. [Frank, 1994] Andr as Frank. Connectivity augmentation problems in network design. Technical report, Univ. of Michigan, Ann Arbor, MI (United States), 1994. [Friedrich et al., 2017] Tobias Friedrich, Sven Ihde, Christoph Keßler, Pascal Lenzner, Stefan Neubert, and David Schumann. Efﬁcient best response computation for strategic network formation under attack. In SAGT 17, pages 199 211, 2017. [Goyal et al., 2016] Sanjeev Goyal, Shahin Jabbari, Michael Kearns, Sanjeev Khanna, and Jamie Morgenstern. Strategic network formation with attack and immunization. In WINE 16, pages 429 443. Springer, 2016.

[Jackson and Wolinsky, 1996] Matthew O Jackson and Asher Wolinsky. A strategic model of social and economic networks. Journal of economic theory, 71(1):44 74, 1996. [Kawald and Lenzner, 2013] Bernd Kawald and Pascal Lenzner. On dynamics in selﬁsh network creation. In SPAA 13, pages 83 92. ACM, 2013. [Kliemann et al., 2017] Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, and Anand Srivastav. Swap equilibria under link and vertex destruction. Games, 8(1):14, 2017. [Kliemann, 2011] Lasse Kliemann. The price of anarchy for network formation in an adversary model. Games, 2(3):302 332, 2011. [Koutsoupias and Papadimitriou, 1999] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In STACS 99, pages 404 413. Springer, 1999. [Laoutaris et al., ] Nikolaos Laoutaris, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, and Shang-Hua Teng. Bounded budget connection (BBC) games or how to make friends and inﬂuence people, on a budget. In PODC 08, pages 165 174. ACM. [Meirom et al., 2015] Eli A Meirom, Shie Mannor, and Ariel Orda. Formation games of reliable networks. In INFOCOM 15, pages 1760 1768. IEEE, 2015. [Mihal ak and Schlegel, 2012] Mat uˇs Mihal ak and Jan Christoph Schlegel. Asymmetric swap-equilibrium: A unifying equilibrium concept for network creation games. In MFCS 12, pages 693 704. 2012. [Monderer and Shapley, 1996] Dov Monderer and Lloyd S. Shapley. Potential games. Games and economic behavior, 14(1):124 143, 1996. [Myerson, 2013] Roger B Myerson. Game theory. Harvard university press, 2013. [Nagamochi and Ibaraki, 2008] Hiroshi Nagamochi and Toshihide Ibaraki. Algorithmic aspects of graph connectivity. Cambridge University Press, 2008. [Papadimitriou, 2001] Christos H. Papadimitriou. Algorithms, games, and the internet. In STOC 01, pages 749 753, 2001. [Tardos, 2004] Eva Tardos. Network games. In STOC 04, pages 341 342, 2004. [Watanabe and Nakamura, 1987] Toshimasa Watanabe and Akira Nakamura. Edge-connectivity augmentation problems. Journal of Computer and System Sciences, 35(1):96 144, 1987.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)