Selfish Network Creation with Non-uniform Edge Cost

Abstract

Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games.

We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.

1 Introduction

Complex networks from the Internet to various (online) social networks have a huge impact on our lives and it is thus an important research challenge to understand these networks and the forces that shape them. The emergence of the Internet was one of the driving forces behind the rise of Algorithmic Game Theory [26] and it has also kindled the interdisciplinary field of Network Science [6], which is devoted to analyzing and understanding real-world networks. Game-theoretic models for network creation lie in the intersection of both research directions and yield interesting insights into the structure and evolution of complex networks. In these models, agents are associated to nodes of a network and choose their neighbors selfishly to minimize their cost. Many such models have been proposed, most prominently the models of Jackson and Wolinsky [16], Bala and Goyal [5] and Fabrikant et al. [14], but almost all of them treat edges equally, that is, they assume a fixed price for establishing any edge which is considered as a parameter of these games. This yields very simple models but has severe influence on the obtained equilibria and their properties.

We take a radical departure from this assumption by proposing and analyzing a variant of the Network Creation Game [14] in which the edges have non-uniform cost which solely depends on the structure of the network. In particular, the cost of an edge between agent u and v which is bought by agent u is proportional to v’s degree in the network, i.e. edge costs are proportional to the degree of the other endpoint involved in the edge. Thus, we introduce individual prices for edges and at the same time we obtain a simple model which is parameter-free.

Our model is inspired by social networks in which the nodes usually have very different levels of popularity which is proportional to their degree. In such networks connecting to a celebrity usually is expensive. Hence, we assume that establishing a link to a popular high degree node has higher cost than connecting to an unimportant low degree node. Moreover, in social networks links are formed mostly locally, e.g. between agents with a common neighbor, and it rarely happens that links are removed, on the contrary, such networks tend to get denser over time [20]. This motivates two other extensions of our model which consider locality and edge additions only.

1.1 Model and Notation

Throughout the paper we will consider unweighted undirected networks $G = (V,E)$, where V is the set of nodes and E is the set of edges of G. Since edges are unweighted, the distance $d_G(u,v)$ between two nodes u, v in G is the number of edges on a shortest path between u and v. For a given node u in a network G let $N_k(u)$ be the set of nodes which are at distance at most k from node u in G and let $B_k(u)$ be the set of nodes which are at exactly distance k from node u (the distance-k ball around u). We denote the diameter of a network G by D(G), the degree of node u in G, which is the number of edges incident to u, by $deg_G(u)$. We will omit the reference to G whenever it is clear from the context.

We investigate a natural variant of the well-known Network Creation Game (NCG) by Fabrikant et al. [14] which we call the degree price network creation game (degNCG). In a NCG the selfish agents correspond to nodes in a network and the strategies of all agents determine which edges are present. In particular, the strategy $S_u$ of an agent u is any subset of V, where $v \in S_u$ corresponds to agent u owning the undirected edge $\{u,v\}$. For $v \in S_u$ we will say that agent u buys the edge $\{u,v\}$. Any strategy vector $\mathbf {s}$ which specifies a strategy for each agent then induces the network $G(\mathbf {s})$, where

$$G(\mathbf {s}) = \left( V, \bigcup _{u\in V} \bigcup _{v \in S_u} \{u,v\}\right) .$$

Here we assume that $G(\mathbf {s})$ does not contain multi-edges, which implies that every edge has exactly one owner. Since edge-ownership is costly (see below) this assumption trivially holds in any equilibrium network. Moreover, any network G together with an ownership function, which assigns a unique owner for every edge, determines the corresponding strategy vector. Hence, we use strategy vectors and networks interchangeably and we assume that the owner of every edge is known. In our illustrations we indicate edge ownership by directing the edges away from their owner. We will draw undirected edges if the ownership does not matter.

The cost function of agent u in network $G(\mathbf {s})$ consists of the sum of edge costs for all edges owned by agent u and the distance cost, which is defined as the sum of the distances to all other nodes in the network if it is connected and $\infty$ otherwise. The main novel feature which distinguishes the degNCG from the NCG is that each edge has an individual price which is proportional to the degree of the endpoint which is not the owner. That is, if agent u buys the edge $\{u,v\}$ then u’s cost for this edge is proportional to node v’s degree. For simplicity we will mostly consider the case where the price of edge $\{u,v\}$ for agent u is exactly v’s degree without counting edge $\{u,v\}$. Thus the cost of agent u in network $G(\mathbf {s})$ is

$$cost_u(G(\mathbf {s})) = \sum _{v \in S_u}(\deg _{G(\mathbf {s})}(v)-1) + dist_{G(\mathbf {s})}(u).$$

Note that in contrast to the NCG our variant of the model does not depend on any parameter and the rather unrealistic assumption that all edges have the same price is replaced with the assumption that buying edges to well-connected nodes is more expensive than connecting to low degree nodes.

Given any network $G(\mathbf {s})$, where agent u has chosen strategy $S_u$. We say that $S_u$ is a best response strategy of agent u, if $S_u$ minimizes agent u’s cost, given that the strategies of all other agents are fixed. We say that a network $G(\mathbf {s})$ is in pure Nash equilibrium (NE), if no agent can strictly decrease her cost by unilaterally replacing her current strategy with some other strategy. That is, a network $G(\mathbf {s})$ is in NE if all agents play a best response strategy.

Observe that in the degNCG we assume that agents can buy edges to every node in the network. Especially in modeling large social networks, this assumption seems unrealistic. To address this, we also consider a restricted version of the model which includes locality, i.e. where only edges to nodes in distance at most k, for some fixed $k\ge 2$, may be bought. We call this version the k-local degNCG (degkNCG) and its pure Nash equilibria are called k-local NE (kNE). We will mostly consider the case strongest version where $k=2$.

We measure the quality of a network $G(\mathbf {s})$ by its social cost, which is simply the sum over all agents’ costs, i.e. $cost(G(\mathbf {s})) = \sum _{u\in V}cost_u(G(\mathbf {s}))$. Let ${worst }_n$ and ${best }_n$ denote the social cost of a (k)NE network on n nodes which has the highest and lowest social cost, respectively. Moreover, let ${opt }_n$ be the minimum social cost of any network on n nodes. We measure the deterioration due to selfishness by the Price of Anarchy (PoA) which is the maximum over all n of the ratio $\frac{{worst}_n}{{opt}_n}$. Moreover, the more optimistic Price of Stability (PoS) is the maximum over all n of the ratio $\frac{{best}_n}{{opt}_n}$.

The use case of modeling social networks indicates another interesting version of the degNCG, which we call the degree price add-only game (degAOG) and its k-local version degkAOG. In these games, agents can only add edges to the network whereas removing edges is impossible. This mirrors social networks where an edge means that both agents know each other.

1.2 Related Work

Our model is a variant of the well-known Network Creation Game (NCG) proposed by Fabrikant et al. [14]. The main difference to our model is that in [14] it is assumed that every edge has price $\alpha >0$, where $\alpha$ is some fixed parameter of the game. This parameter heavily influences the game, e.g. the structure of the equilibrium networks changes from a clique for very low $\alpha$ to trees for high $\alpha$. For different regimes of $\alpha$ different proof techniques yield a constant PoA [1, 13,14,15, 21, 23] but it is still open whether the PoA is constant for all $\alpha$. In particular, constant upper bounds on the PoA are known for $\alpha < n^{1-\varepsilon }$, for any fixed $\varepsilon >\frac{1}{\log n}$ [13], and if $\alpha > 65n$ [21]. The best general upper bound is $2^{\mathcal {O}\sqrt{\log n}}$ [13]. The dynamics of the NCG have been studied in [17] where it was shown that there cannot exist a generalized ordinal potential function for the NCG. Also the complexity of computing a best response has been studied and its NP-hardness was shown in [14]. If agents resort to simple strategy changes then computing a best response can trivially be done in polynomial time and the obtained equilibria approximate Nash equilibria well [19].

Removing the parameter $\alpha$ by restricting the agents to edge swaps was proposed and analyzed in [2, 24]. The obtained results are similar, e.g. the best known upper bound on the PoA is $2^{\mathcal {O}\sqrt{\log n}}$, there cannot exist a potential function [18] and computing a best response is NP-hard. However, allowing only swaps leads to the unnatural effects that the number of edges cannot change and that the sequential version heavily depends on the initial network.

Several versions for augmenting the NCG with locality have been proposed and analyzed recently. It was shown that the PoA may deteriorate heavily if agents only know their local neighborhood or only a shortest path tree of the network [7, 8]. In contrast, a global view with a restriction to only local edge-purchases yields only a moderate increase of the PoA [11].

The idea of having nodes with different popularity was also discussed in the so called celebrity games [3, 4]. There, nodes have a given popularity and agents buy fixed-price edges to get highly popular nodes within some given distance bound. Hence, this model differs heavily from our model.

To the best of our knowledge, there are only two related papers which analyze a variant of the NCG with non-uniform edge price. In [12] agents can buy edges of different quality which corresponds to their length and the edge price depends on the edge quality. Distances are then measured in the induced weighted network. Closer to our model is [22] where heterogeneous agents, important and unimportant ones, are considered and both classes of agents have different edge costs. Here, links are formed with bilateral agreement [10, 16] and important nodes have a higher weight, which increases their attractiveness.

1.3 Our Contribution

We introduce and analyze the first parameter-free variants of Network Creation Games [14] which incorporate non-uniform edge cost. In almost all known versions the outcomes of the games and their analysis heavily depend on the edge cost parameter $\alpha$. We depart from this by assuming that the cost of an edge solely depends on structural properties of the network, in particular, on the degree of the endpoint to which the edge is bought. Essentially, our models incorporate that the cost of an edge is proportional to the popularity of the node to which it connects. This appears to be a realistic feature, e.g. for modeling social networks.

On the first glance, introducing non-uniform edge cost seems to be detrimental to the analysis of the model. However, in contrast to this, we give a simple proof that the PoA of the degNCG is actually constant. To the best of our knowledge, our model is the first version of the NCG for which this strong statement could be established. A constant PoA is widely conjectured for the original NCG [14] but its proof is despite serious efforts of the community still an open question. Besides this strongest possible bound on the PoA, which we also generalize to arbitrary linear functions of a node’s degree and to the 4-local version, we prove a PoA upper bound of $\mathcal {O}(\sqrt{n})$ for the deg2NCG, where agents are restricted to act within their 2-neighborhood and we show for this version that computing a best response strategy is NP-hard. Moreover, we investigate the dynamic properties of the deg(2)NCG and prove that improving response dynamics may not converge to an equilibrium, that is, there cannot exist a generalized ordinal potential function.

We contrast these negative convergence results by analyzing a version where agents can only add edges, i.e. the deg(2)AOG, where convergence of the sequential version is trivially guaranteed, and by analyzing the speed of convergence for different agent activation schemes. The restriction to only edge additions has severe impact on the PoA, yielding a $\varTheta (n)$ bound, but we show that the impact on the social cost is low, if round-robin dynamics starting from a path are considered, where agents buy their best possible single edge in each step.

Due to space constraints, all omitted details can be found in [9].

2 Hardness

In this section we investigate the computational hardness of computing a cost minimizing strategy, i.e. a best response, in the deg2NCG and in the deg2AOG.

Theorem 1

Computing the best response in the deg2NCG and the deg2AOG is NP-hard.

3 Analysis of Equilibria

We start with the most fundamental statement about equilibria which is their existence. We use the center sponsored spanning star $S_n$, see Fig. 1(a), for the proof and provide some other examples of NE and 2NE networks in Fig. 1.

Theorem 2

The star $S_n$ is a (k)NE for the deg(k)NCG and the deg(k)AOG for any k.

Fig. 1.

Examples of NE and 2NE networks

3.1 Bounding the Diameter of Equilibrium Networks

We investigate the diameter of (2)NE networks. Analogously to the original NCG [14], bounding the diameter plays an important role in bounding the PoA.

Theorem 3

Consider variants of the degAOG and the degNCG where the price of any edge $\{u,v\}$ bought by agent u is any linear function of v’s degree in G, that is, $price_u(\{u,v\})=\beta \cdot ~deg_{G(s)}(v)+\gamma$, where $\beta , \gamma \in \mathbb {R}$. Then the diameter of any NE network in the degAOG and the degNCG is constant.

Proof

We consider a NE network $G = (V,E)$ and assume that the diameter D of G is at least 4. Then there exist nodes $a,b \in V$, such that $d_G(a,b)=D$. Therefore, the distance cost of a agent a in G is at least $D+|B_1(b)|(D-1)+|N_2(a)|$. Thus, if agent a buys the edge $\{a,b\}$ then this improves agent a’s distance cost by at least $D-1+|B_1(b)|(D-3)$. Since the network G is in NE, the distance cost improvement must be less than agent u’s cost for buying the edge $\{a,b\}$:

$$\begin{aligned} D-1+|B_1(b)|(D-3)&\le \beta \cdot deg_{G}(b)+\gamma \\ \iff D-1+(D-3)\cdot deg_{G}(b)&\le \beta \cdot deg_{G}(b)+\gamma . \end{aligned}$$

Solving for D under the assumption $deg_G(b) \ge 1$ yields

$$D \le \frac{(\beta +3)deg_G(b)+\gamma +1}{deg_G(b)+1} < \beta +3 + \frac{\gamma +1}{deg_G(b)+1} \in \mathcal {O}(1).$$

   $\square$

Using $\beta =1$ and $\gamma = -1$ yields the edge price for our version of the degNCG and the degAOG. This, and the NE example in Fig. 1(b) yields the following:

Corollary 1

The diameter of any NE network in the degAOG and the degNCG is at most 3 and this upper bound is tight.

Since in the proof of Theorem 3 in the case of $\beta = 1$ and $\gamma = -1$ buying an edge to a node in distance 4 suffices, we get the following statement.

Corollary 2

Any 4NE network has diameter at most 3.

Note that the examples in Fig. 1(c) and (d) show that the diameter in the 2-local version, i.e. in the deg2NCG and the deg2AOG, can exceed 3. We prove a higher upper bound on the diameter for the 2-local versions.

Theorem 4

The diameter of any 2NE network is in $\mathcal {O}(\sqrt{n})$.

Proof

Consider a 2NE network $G=(V,E)$ with $|V|=n$ and let D denote its diameter. Consider two nodes $a,b\in V$ such that $d_G(a,b)=D$ and a shortest-path tree $T_a=(V,E_a)$ which is rooted at node a (see Fig. 2).

Fig. 2.

The shortest-path tree $T_a$. Dashed lines denote edges of G which are not in the tree, i.e. the non-tree edges.

The height of $T_a$ is D and there must be a subtree $T_c$ which contains node b and which has node c as root, where c is chosen such that $d_G(a,c)=2$ and c belongs to the path from a to b in $T_a$. Since the height of $T_c$ is $D-2$ it follows that the number of nodes in $T_c$ must be at least $D-1$. Let $|T_x|$ denote the number of nodes in the subtree of $T_a$ rooted at node x. Hence, we have $|T_c| \ge D-1$.

Note that if agent a buys any edge $\{a,x\}$ in network G then this improves a’s distance cost by at least $|T_x|$. Since G is in 2NE, we know that buying the edge $\{a,c\}$ is not an improving move for agent a which implies that $|T_c|$ is at most the cost of the edge $\{a,c\}$ which is equal to $deg_G(c)$. Since $|T_c|\ge D-1$ it follows that $deg_G(c)\ge D-1$.

Let $L_i$ denote the set of nodes which are in distance i from the root a in the tree $T_a$. For example $L_0=\{a\}, c\in L_2$ and $b\in L_D$. Thus, we have $D-1\le deg_G(c)\le |L_1|+(|L_2|-1)+|L_3|$.

Analogously, since G is in 2NE, we have that no agent $v_i$ in layer $L_i$ on the $c-b$ path in $T_a$ can decrease her cost by buying an edge to a node in layer $L_{i+2}$ which is a neighbor of a neighbor in $T_a$. With analogue reasoning as above we get $D-(i-1)\le deg_G(v_i)\le |L_{i-1}|+(|L_i|-1)+|L_{i+1}|$.

Note that not only agents from lower layers cannot improve by buying edges towards nodes in upper layers but also agents from upper layers cannot improve by buying edges towards nodes in lower layers. Thus we have

$$D-(i-1)\le deg_G(v_i)\le |L_{i-1}|+(|L_i|-1)+|L_{i+1}|$$

and

$$D-(i-1)\le deg_G(v_{D-i})\le |L_{D-i-1}|+(|L_{D-i}|-1)+|L_{D-i+1}|$$

for any $2\le i \le \left\lfloor \frac{D}{2}\right\rfloor -1$. Summing up all inequalities yields:

$$2\sum _{i=2}^{\left\lfloor \frac{D}{2}\right\rfloor -1}\big (D-(i-1)\big )\le 3\left( \sum _{i=1}^{D}{|L_i|}-(D-1)\right) .$$

For the left side we have

$$\frac{3D^2}{4}-4D-3 < \left( \left\lfloor \frac{D}{2}\right\rfloor -2\right) \left( 2D+1 - \left\lfloor \frac{D}{2}\right\rfloor \right) = 2\sum _{i=2}^{\left\lfloor \frac{D}{2}\right\rfloor -1}\big (D-(i-1)\big )$$

and the right side gives $3\left( \sum _{i=1}^{D}{|L_i|}-(D-1)\right) \le 3n-3D+3$, which yields

$$\frac{3D^2}{4}-4D-3< 3n-3D+3 \Rightarrow D < \frac{2}{3}\left( 1+\sqrt{9n+19}\right) \in \mathcal {O}(\sqrt{n}).$$

   $\square$

3.2 Price of Stability

For analyzing the Price of Stability, we have to investigate the network which has the minimum possible social cost.

Lemma 1

The center sponsored spanning star $S_n$ is an optimal solution of the deg(k)NCG and the deg(k)AOG for any k.

We have shown in the proof of Theorem 2 that the center sponsored spanning star $S_n$ is in (k)NE for any k. With Lemma 1 this yields the following for $k\ge 2$.

Corollary 3

The Price of Stability of the deg(k)NCG and the deg(k)AOG is 1.

3.3 Price of Anarchy

For investigating the quality of the equilibria of our games, we first adapt an important lemma by Fabrikant et al. [14] to our setting.

Lemma 2

If a (k)NE network G in the deg(k)NCG has diameter D, then its social cost is at most $\mathcal {O}(D)$ times the minimum possible social cost.

From Corollaries 1 and 2 we know that the diameter of any NE in the degNCG and any 4NE in the deg4NCG is at most 3. Also, from the Lemma 2 we know that the social cost of any NE network G is at most $\mathcal {O}(D(G))$ times the minimum possible social cost. This implies the following statement.

Theorem 5

The Price of Anarchy of the degNCG and the deg4NCG is in $\mathcal {O}(1)$.

A straightforward adaptation of Lemma 2 together with Theorem 3 yields:

Corollary 4

The Price of Anarchy of variants of the degNCG where the price of any edge $\{u,v\}$ bought by agent u is linear in v’s degree in G, is constant.

Using Theorem 4 and Lemma 2 yields the following statement.

Corollary 5

The Price of Anarchy of the deg2NCG is in $\mathcal {O}(\sqrt{n})$.

We conclude with analyzing the PoA in the deg(k)AOG. The upper bound is trivially in $\mathcal {O}(n)$, the matching lower bound holds, since a clique is in (k)NE for the deg(k)AOG for any k.

Observation 6

The Price of Anarchy of deg(k)AOG is in $\varTheta (n)$ for any k.

4 Dynamics

In this section we consider the dynamic properties of the sequential version of the deg(k)NCG and the deg(k)AOG. The sequential version corresponds to an iterative process, called improving response dynamics (IRD), which starts with some initial strategy vector $\mathbf {s}$ and its corresponding initial network $G(\mathbf {s})$ and then agents are activated one at a time according to some activation scheme, e.g. a random or adversarially chosen move order or round-robin activation, and active agents are allowed to myopically update their current strategy. They will do so only if the new strategy yields strictly less cost than their current strategy. For the deg(2)AOG we will also consider the best single edge dynamics, which is a special case of the improving response dynamics, in which active agents buy the best possible single edge, if this strictly decreases their current cost.

The most important dynamic property of a game is the finite improvement property (FIP) [25], which states that any sequence of improving moves must be finite. The seminal paper [25] established that having the FIP is equivalent to being a generalized ordinal potential game. Thus, games having the FIP are guaranteed to converge to an equilibrium under improving move dynamics.

4.1 Dynamics in the deg(k)NCG

We investigate the convergence properties of the deg(k)NCG and prove that the deg(k)NCG may not converge under improving move dynamics.

Theorem 7

The deg(k)NCG does not have the FIP for any k, which implies that these games cannot have a generalized ordinal potential function.

Proof

(Sketch). See Fig. 3 for an improving response cycle.

Fig. 3.

Example of an improving response cycle for the deg(k)NCG.

Remark 1

The presented improving response cycle in Fig. 3 is not a best response cycle for the deg(k)NCG since in network $G_3$ agent j has a strictly better local move: Buying the edge to agent h and swapping her edge from i to e.

4.2 Dynamics in the Add-Only Model

We consider dynamics in the deg(k)AOG. First of all, since agents can only add edges, the deg(k)AOG trivially has the FIP, i.e. it is an ordinal potential game with the number of bought edges serving as a generalized ordinal potential function.

Since convergence is guaranteed, we focus on investigating the speed of convergence and the quality of the obtained networks. For the latter, Observation 6 yields a devastating result. However, we contrast this for the deg2AOG by proving that if round-robin best single edge dynamics starting on a path as initial network are used, then the social cost is actually close to the best possible achievable social cost.

Theorem 8

Let $P_n = \{v_1 \cdots v_n\}$ be the path of length n, with $v_1$ and $v_n$ as leaf nodes, as a initial graph for the deg(k)AOG:

• 1. If in any step the active agent is chosen uniformly at random then IRD in the deg(k)AOG converge in $\mathcal {O}(n^3)$ steps in expectation.

• 2. If in any step the active agent and her improving response is chosen adversarially then IRD in the deg(k)AOG converge in $\varTheta (n^2)$ steps.

• 3. If round-robin best single edge dynamics are used in the deg2AOG, the process converges in at most $\mathcal {O}(n \log n)$ steps to a network with diameter $\mathcal {O}(1)$.

We contrast the upper bounds by showing that convergence in $\mathcal {O}(n)$ many improving responses is possible.

Theorem 9

Let $P_n$ be the initial network then there exists a sequence of improving responses which takes

• 1. $n-2+\frac{n-7}{3}$ steps to obtain a NE network in the degAOG;

• 2. $n-1$ steps to obtain a 2NE network in the deg2AOG.

Finally, we investigate the quality of the (2)NE networks which can be obtained by improving move dynamics starting from the path $P_n$. For this, we introduce a measure which is similar to the Price of Anarchy. Let $G_0$ be any initial connected network and let $Z(G_0)$ be the set of networks which can be obtained via improving response dynamics in the deg(2)AOG. Let $Best(G_0) \in Z(G_0)$ be the reachable network with minimum social cost among all networks in $Z(G_0)$. We can now measure the quality of any network $G \in Z(G_0)$ by investigating the ratio $\rho (G,G_0) = \frac{cost(G)}{cost(Best(G_0))}$.

Theorem 10

• 1. Let G be any network in $Z(G_0)$ then $\rho (G,G_0) \in \mathcal {O}(n).$

• 2. There is a network $G \in Z(P_n)$ for the deg(2)AOG with $\rho (G,P_n) \in \varTheta (n)$.

• 3. Let $G^*$ be the network obtained by the round-robin best single edge dynamics in the deg2AOG, then we have $\rho (G^*,P_n) \in \mathcal {O}(\log n)$.

5 Conclusion

We have introduced natural variants of the well-known NCG by Fabrikant et al. [14], which have the distinctive features that they are parameter-free and at the same time incorporate non-uniform edge costs. Besides proving that computing a best response is NP-hard and that improving response dynamics may never converge to an equilibrium, we have also established that the degNCG has a constant Price of Anarchy. This strong statement holds whenever the edge price is any linear function of the degree of the non-owner endpoint of the edge or if agents are allowed to buy edges to nodes in their 4-neighborhood. For the version which includes stronger locality, i.e. the deg2NCG, we have shown that the PoA is in $\mathcal {O}(\sqrt{n})$ and, as a contrast, for the add-only version the PoA is in $\varTheta (n)$. We also demonstrate how to circumvent the latter negative result by using suitable activation schemes on a sparse initial network.

Studying the bilateral version of our model, where both endpoints of the edge have to agree and pay proportionally to the degree of the other endpoint for establishing an edge, is an obvious future research direction. For this version, we have already established that most of our proofs can be easily adapted, which implies that our results, with minor modifications, still hold. Another interesting extension would be to consider an edge price function which depends on the degree of both involved nodes. This could be set up such that edges between nodes of similar degree are cheap and edges become expensive when the degree of both nodes differs greatly.