Flow-Based Network Creation Games

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 conflicting goals. For example, the structure of the Internet is essentially the outcome of a repeated strategic interaction by many selfish 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 selfish 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 selfishly 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 selfish 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 first 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 flow 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 VoIP. Interestingly, by the Max Flow Min Cut Theorem [Ford and Fulkerson, 1956], flow 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 (flowNCG), which is a variant of the well-known Network Creation Game [Fabrikant et al., 2003] where the agents create edges to maximize their flow value as defined by the classical Max-Flow Problem [Ford and Fulkerson, 1956]. Given a set of n selfish agents which corresponds to the set of nodes V of a weighted directed network G = (V,E). Each agent 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 define the degree of a node v in G as degG(v) = ∑(x,v)∈E,x∈V c(x, v) + ∑(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 defined 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., ∑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 profile. Any strategy profile s uniquely specifies 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 flow 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 defined as c({v, x}) = c(v, x) + c(x, v). Thus, for sending flow, 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

we only work with G(s) and we will always assume its undirected version F (s) when computing flow 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 profiles. 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) = ∑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)) = ∑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 defined 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-flow between nodes v and x. Hence, we use the local edge connectivity of v and x interchangeably with the value of maximum v-x-flow.

We define two versions of the flowNCG. The first is called the Average Flow NCG (avg-flowNCG). For a given strategy profile s, the utility function of an agent v is defined as the average maximum flow value to each other node in the network: u(v, s) = ∑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) = ∑v∈V u(v,s) n .

The second variant is called the Minimum Flow NCG (minflowNCG). 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 define 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 define 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 define the social utility of a network in the min-flowNCG 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 profiles.

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 profile 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 finite, then the game has the finite 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' selfishness with the Price of Anarchy (PoA) [Koutsoupias and Papadimitriou, 1999]. Let minNE(n, k)(maxNE(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 PoA is opt(n,k) minNE(n,k) and the Price of Stability (PoS) is opt(n,k) maxNE(n,k) . The latter measures the minimum sacrifice in social utility for obtaining a NE network.

1.2 RelatedWork

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 defines 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 PoA 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 PoA 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 flow 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 efficient 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-flowNCG 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 PoA results for both models guarantee that the social utility of any NE is at least half the optimal utility, i.e., PoA ≤ 2, and this bound is tight for the min-flowNCG and almost tight for the avg-flowNCG. Besides this, we prove for both versions that the PoS = 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.

input : unweighted directed clique Kn=(V,E) output: social optimum network G 1 G← (V, ∅); 2 for i ← 1 to k do 3 find 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-flowNCG and min-flowNCG 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 minflowNCG. The social utility of G equals the edge connectivity of G which is at most minv∈V degG(v). The handshake lemma yields ∑v∈V degG(v) = 2 ∑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 degG(v) ≤ 2k.

In the avg-flowNCG, the social utility is u(s) = 1n ∑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{degG(v), degG(w)}. Thus, u(s) ≤ 1n ∑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.

Theorem2. In the min-flowNCG and the avg-flowNCGOPT 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 PoA bounds.

Theorem 3. In the min-flowNCG and the avg-flowNCG 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-flowNCG, we have, by definition, 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-flowNCG 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-flowNCG and the avg-flowNCG 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 finite, 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-flowNCG, 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-flowNCG, 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 + |Y | 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-flowNCG and the avg-flowNCG, 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 find a (k + 1)-cluster.

4 Price of Stability

Theorem 6. The PoS is 1 in the min-flowNCG and the avgflowNCG.

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-flowNCG, 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-flowNCG the same strategy change by any of the agents, say v1, decreases the degree of the respective neighbor v2. Thus, the local edge connectivity 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, PoS = 1 for both games.

5 Price of Anarchy

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

5.1 PoA of the Min-FlowNCG

We start by providing a NE network for the min-flowNCG 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-flowNCG.

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-flowNCG. We omit the proof due to the space restrictions.

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

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

Proof. Assume towards a contradiction that there is a NE G = (V,E) such that it contains a cut (A,B) such that λ(G) = ∑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) ≤ degK(v), there is a node x ∈ K which has an edge to v in K.

We will show that agent x can significantly 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 PoA in the min-flowNCG is 2k k+1 .

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

5.2 PoA of the Avg-FlowNCG

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-flowNCG.

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.

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-flowNCG.

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.

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-flowNCG is at least k.

Theorem 12. For k ≥ 2, the edge connectivity of any NE network in the avg-flowNCG 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 + |Y | n-1 > 0, i.e., it is an improving move.

Theorem 13. For the avg-flowNCG we have PoA< 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 n = k.

Now we provide an almost matching lower bound on the PoA. Theorem 14. For the avg-flowNCG, we have PoA ≥ max{ 2k k+k(k-1)/(n-1) , 2k k+1 }.

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 PoA is at least 2k/ (k + k(k-1) n-1 ) = 2(n-1) n+k-2 . Thus, for large n, the PoA tends to 2, i.e., the upper bound. With a high budget, i.e., for k > 0.5+ √n-0.75, the PoA 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-flowNCG and the avg-flowNCG.

Theorem 15. The min-flowNCG and the avg-flowNCG 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 first and the last networks are isomorphic in both sequences, which implies that we indeed have IRCs.

Figure 5: An IRC for the min-flowNCG with k = 2. Since G and G′ are isomorphic, the sequence of the improving moves recurs to G.

7 Conclusion

We made the first steps into the promising direction of investigating network formation games with bandwidth/connectivity considerations. For this, we proposed two versions: the min-flowNCG where agents strive to maximize the connectivity of the entire network; and the avg-flowNCG where agents try to maximize their average flow 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-flowNCG, while in the min-flowNCG 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 PoA 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.