Network Creation Games with Traceroute-Based Strategies ^†

Abstract

Network creation games have been extensively used as mathematical models to capture the key aspects of the decentralized process that leads to the formation of interconnected communication networks by selfish agents. In these games, each user of the network is identified by a node and selects which link to activate by strategically balancing his/her building cost with his/her usage cost (which is a function of the distances towards the other player in the network to be built). In these games, a widespread assumption is that players have a common and complete information about the evolving network topology. This is only realistic for small-scale networks as, when the network size grows, it quickly becomes impractical for the single users to gather such a global and fine-grained knowledge of the network in which they are embedded. In this work, we weaken this assumption, by only allowing players to have a partial view of the network. To this aim, we borrow three popular traceroute-based knowledge models used in network discovery: (i) distance vector, (ii) shortest-path tree view, and (iii) layered view. We settle many of the classical game theoretic questions in all of the above models. More precisely, we introduce a suitable (and unifying) equilibrium concept which we then use to study the convergence of improving and best response dynamics, the computational complexity of computing a best response, and to provide matching upper and lower bounds to the price of anarchy.

1. Introduction

The construction of large communication networks involves the interaction of many independent and selfish agents with competing interests and, in such a decentralized setting, the problem of understanding the formation process of a network arises naturally. More formally, we model the agents (i.e., players) as a set of n vertices in a graph, each controlled by a player that wants to connect itself to all of the other participants of the network. This can happen either directly, by the unilateral and costly activation of a corresponding logical or physical communication channel (i.e., a link), or indirectly by routing messages over (a subset of the) existing (bidirectional) links that were activated by other agents. Quite naturally, players prefer low-latency communication paths over longer paths and will therefore always route messages along a shortest path. It is then clear how tension stems from the desire of a player for efficient communication, and his/her interest in minimizing the number of activated links. The study of such a trade-off between a player’s building cost (which is proportional to the number of links she decides to activate) and her usage cost (some function that depends on the distance between the player and the remaining agents in the resulting network) results in the corresponding study of a communication network creation game, also known as network connection game (simply NCG in the following).

1.1. The Standard Model for NCGs

A first NCG model that received considerable attention in the algorithmic game theory area is due to Fabrikant et al. [1]. In this model, which we will call SumNCG in the sequel, each player u pays $\alpha$ for each link she activates as his/her building cost, and the sum of all distances from u to all other vertices in the resulting network as her usage cost. More formally, if V is a set of n agents, the set of the possible strategies of player $u\in V$ is $2^{V\backslash \left\{u\right\}}$ (Given a set X, $2^X$ denotes the power set of X). Given a strategy ${\sigma }_u$ for each agent $u\in V$, we will call the vector $\sigma ={\left({\sigma }_u\right)}_{u\in V}$ a strategy profile, and we will denote by $G\left(\sigma \right)$ the resulting network, i.e., a graph containing a vertex for each player in V, and such that its edge set $E\left(\sigma \right)$ contains an edge $(u,v)$ if and only if $u\in {\sigma }_v$ or $v\in {\sigma }_u$. To easy the notation, we will sometimes use G instead of $G\left(\sigma \right)$ if no ambiguity arises. Moreover, we will say that $u\in V$ owns the edges in $\left\{u\right\}\times {\sigma }_u$ (Notice that, according to the above definition, an edge can be owned by both its endpoints). The goal of each agent $u\in V$ is that of minimizing her cost cost $C_u\left(\sigma \right)$ in the resulting strategy profile $\sigma$, which is defined as

$$C_u\left(\sigma \right)=\alpha ·\left|{\sigma }_u\right|+\sum _{v\in V}{d}_{G\left(\sigma \right)}(u,v),$$

(1)

where $d_{G\left(\sigma \right)}(u,v)$ is the distance between player u and player v in $G\left(\sigma \right)$. Quite naturally, we define the social cost of $\sigma$ as the sum of the costs $C_u\left(\sigma \right)$ incurred by all players $u\in V$.

Notice that in the above description, we are implicitly assuming that each player u has a complete knowledge of the current network $G\left(\sigma \right)$. This means that u can evaluate both his/her current cost $C_u\left(\sigma \right)$, and the cost $C_u({\sigma }_{-u},{\sigma }_u^{\prime })$ that he/she would incur if he/she were to change her strategy from ${\sigma }_u$ to ${\sigma }_u^{\prime }$, as he/she is aware that—following her change—the current network will transit to $G({\sigma }_{-u},{\sigma }_u^{\prime })$ (The notation $({\sigma }_{-u},{\sigma }_u^{\prime })$ denotes the vector obtained from $\sigma$ by replacing component ${\sigma }_u$ with ${\sigma }_u^{\prime }$). Therefore, a (pure strategy) Nash Equilibrium (NE) for the game is a strategy profile $\overline{\sigma }$ where, for every player u and every strategy ${\sigma }_u$, we have that $C_u\left(\overline{\sigma }\right)\le C_u({\overline{\sigma }}_{-u},{\sigma }_u)$. A vast body of literature deals with the problem of characterizing the space of NE in order to bound the Price of Anarchy (PoA) as a function of the parameter $\alpha$. Here, the PoA is defined as the ratio between the social cost of the worst NE (i.e., any NE $\sigma$ maximizing its social cost ${\sum }_u{C}_u\left(\sigma \right)$), and the social cost of an optimal strategy profile (i.e., a strategy profile ${\sigma }^{*}$ minimizing its social cost ${\sum }_u{C}_u\left({\sigma }^{*}\right)$) [2,3,4,5,6,7,8]. Intuitively, the PoA provides an upper bound on the loss of efficiency (measured in terms of the social cost) between the stable networks that can be reached as a result of the uncoordinated selfish behavior of the agents and that of any optimal (but not necessarily stable) network that minimizes the social cost. Large values of the PoA show that the distributed network formation process might converge to costly networks when compared to a “centralized” design. Conversely, small values of the PoA show that even if the network arises from a combination of selfish strategies, its quality will not be significantly worse than the best possible design. It follows from the best-known results that the PoA of SumNCG is constant whenever $\alpha \ge n^{1-\epsilon }$, for any $\epsilon \ge 1/logn$ (see in [3,4]) or when $\alpha \le (1+{\epsilon }^{\prime })n$ for any constant ${\epsilon }^{\prime }\ge 0$ (see in [6]). For the remaining (small) range of values of $\alpha$, the PoA is upper bounded by $2^{O\left(\sqrt{logn}\right)}$ [7].

In [7], the authors introduced a variant of SumNCG named MaxNCG. In MaxNCG, the usage cost of a player u is his/her eccentricity in the current network $G\left(\sigma \right)$, so that u’s cost function becomes

$$C_u\left(\sigma \right)=\alpha ·\left|{\sigma }_u\right|+max\{d_{G\left(\sigma \right)}(u,v):v\in V\}.$$

(2)

MaxNCG was further considered in [3], where it was shown that the PoA of the game is constant whenever $\alpha \le 129$ or $\alpha =O(1/\sqrt{n})$.

1.2. Other Models for NCGs

Several variants of these two basic models have been defined, with the goal of better characterizing specific aspects of the network formation process. These variants range from limiting the modifications that players are allowed to perform on their current strategies (see in [9,10,11]), to budgeting either the number of edges a player can activate or her eccentricity (see in [12,13,14]), and finally to considering generalized versions of the basic models on edge-weighted graphs (see in [15,16]). Generally speaking, all the aforementioned models exhibit a substantial asymptotic increase in their PoAs compared to that of corresponding basic models introduced above.

Observe that all these models, except for those given in [10,11], share a severe restriction with the basic model, namely, the NP-hardness for a player to select a best-response strategy. Besides that, they also all assume that players have a common and complete information about the ongoing network. While this is feasible for small-size instances of the game, this becomes unrealistic for large-size networks. This is rather problematic, given the growing size of the inputs in the practice. Moreover, quite paradoxically, the full-knowledge assumption is not simplifying at all: it makes it computationally unfeasible for a player to select a best-response strategy, as said before, or even to check whether she is actually in a NE! To address these delicate issues, a new model which limits a player’s full knowledge of the network structure up to a given radius k from herself has been introduced in [17]. In such a setting, players do not even know the size n of the network (in distributed computing terminology, the system is uniform). The authors provided a comprehensive set of upper and lower bounds to the Price of Anarchy (PoA) for the entire range of values of k, which have been confirmed by a further experimental evaluation in [18]. Critically, these bounds to the PoA refer to a new suitable equilibrium concept that accounts for the limited knowledge of the players. More precisely, as a player has a partial (defective) view of the network, before changing her strategy she has to evaluate whether such a choice is convenient in every realizable network which is compatible with her current view. Then, let ${\sigma }_u$ be the strategy played by player u, and define ${\Sigma |}_{{\sigma }_u}$ to be the set of strategy profiles $\sigma =({\sigma }_{-u},{\sigma }_u)$ of the players such that the network $G\left(\sigma \right)$ is realizable according to player u’s view. Let

$$\Delta ({\sigma }_u,{\sigma }_u^{\prime })=\underset{{\sigma \in \Sigma |}_{{\sigma }_u}}{max}\{C_u({\sigma }_{-u},{\sigma }_u^{\prime })-C_u\left(\sigma \right)\}$$

(3)

denote the worst possible cost difference u would have in switching from ${\sigma }_u$ to ${\sigma }_u^{\prime }$. This means that if $\Delta ({\sigma }_u,{\sigma }_u^{\prime })>0$, then there is some strategy profile $\sigma$ compatible with u’s current view for which switching from $\sigma$ to $({\sigma }_{-u},{\sigma }_u^{\prime })$ would increase u’s cost. Conversely, if $\Delta ({\sigma }_u,{\sigma }_u^{\prime })<0$, player u can safely change her strategy from ${\sigma }_u$ to ${\sigma }_u^{\prime }$ as this will decrease her cost by at least $|\Delta ({\sigma }_u,{\sigma }_u^{\prime }\left)\right|>0$ in all of the conceivable networks $G\left(\sigma \right)$ that are compatible with u’s view. Then, the Local Knowledge Equilibrium (LKE) is defined as a strategy profile $\overline{\sigma }$ such that for every player u and every strategy ${\sigma }_u$, we have $\Delta ({\overline{\sigma }}_u,{\sigma }_u)\ge 0$. Notice that our equilibrium concept is actually weaker than the classical NE concept as we have that every NE is also a LKE.

1.3. Our New Local-View Models for NCGs

In this work, we continue the study of NCGs in which players have only a partial information about the current network. Along this direction, we focus on the most prominent local-knowledge models used in the area of network discovery (see in [19,20]) in which the structure of a large unknown network need to be fully identified using a small number of queries on the network’s vertices (where the considered local-knowledge model determines which information are returned by a query). In details, we study the following traceroute-based view models, which all find motivations in the practice of probing the topology of a network by tracing the route of packets (According to the spirit of the game, we assume that in all the models, the players initially sit on a connected network):

(${\mathcal{M}}_1$)

Distance vector: in addition to his/her incident edges, each player u knows only the distances in $G\left(\sigma \right)$ between u and all the agents (this is the minimal knowledge needed by a player in order to compute her current cost).

(${\mathcal{M}}_2$)

Shortest-Path Tree (SPT) view: each player u knows the edges of some SPT of $G\left(\sigma \right)$ rooted at u.

(${\mathcal{M}}_3$)

Layered view: each player u knows the set of edges belonging to at least one SPT of $G\left(\sigma \right)$ rooted at u.

Observe that, in all the above games, each player only has a defective (partial) view of the current network, and therefore the LKE fits perfectly as solution concept. However, unlike the models in [18], our players are always able to compute their current cost $C_u\left(\sigma \right)$ as they are aware of their distances towards all the other vertices in the network (i.e., $C_u\left(\sigma \right)$ is constant for all ${\sigma \in \Sigma |}_{{\sigma }_u}$). For all our models, we study the iterated version of the game and we analyze whether improving and best-response dynamics always converge to a LKE. In these dynamics, we will also assume that the players not only myopic but also oblivious, i.e., they only compute their responses as a function of their current view, without using any information about their previous views. In addition, we study how the computational difficulty of computing a best response strategy changes according to the partial-knowledge model at hand. Finally, we provide matching upper and lower bounds to the PoA in all of the studied models. See

Table 1. Summary of our results (and open problems). In the first column, convergence (and divergence) are reported w.r.t. either improving or best-response dynamics (improving response dynamics (IRD) and best response dynamics (BRD), resp.). In the second column, we report the time complexity of selecting a best-response strategy.

	Convergence	Best-Response Complexity	PoA
${\mathcal{M}}_1$	Sum: Yes (∀ improving response dynamics (IRD)) Max: Yes (∀ IRD)	Sum: Open Max: Polynomial	Sum: $\Theta (min\{1+\alpha ,n\left\}\right)$ Max: $\Theta \left(n\right)$ if $\alpha =\Omega \left(1\right)$     $\Theta (1+\alpha n)$ if $\alpha =O\left(1\right)$
${\mathcal{M}}_2$	Sum: No (∃ best response dynamics (BRD) cycle) Max: No (∃ BRD cycle)	Sum: Polynomial Max: Polynomial	Sum: $\Theta (min\{1+\alpha ,n\left\}\right)$ Max: $\Theta \left(n\right)$ if $\alpha =\Omega \left(1\right)$     $\Theta (1+\alpha n)$ if $\alpha =O\left(1\right)$
${\mathcal{M}}_3$	Sum: No (∃ BRD cycle) Max: No (∃ BRD cycle)	Sum: NP-hard Max: NP-hard	Sum: $\Theta (min\{1+\alpha ,n\left\}\right)$ Max: $\Theta \left(n\right)$ if $\alpha =\Omega \left(1\right)$     $\Theta (1+\alpha n)$ if $\frac{1}{n-1}\le \alpha =O\left(1\right)$

for a summary of our results.

The paper is organized as follows. In Section 2, we focus on convergence issues, while in Section 3 we analyze the computational complexity of finding a best-response. Finally, in Section 4 we study the PoA. All the sections are structured in subsections, according to the various view models. A preliminary version of this work appeared in [21].

2. Convergence

2.1. Model ${\mathcal{M}}_1$

We start by observing that in ${\mathcal{M}}_1$ a player u can only infer the existence of the edges $(x,y)$ for which $d_G(u,y)=d_G(u,x)+1$ and no other vertex $x^{\prime }\ne x$ satisfies $d_G(u,x)=d_G(u,x^{\prime })$ (this captures all the edges incident to u as the special case $x=u$).

As a consequence, whenever u has at least two neighbors, swapping (i.e., replacing an owned edge with another one) any of his/her edges will never be an improving response as (in u’s view) this might cause the resulting network to become disconnected. We summarize this property in the next Lemma.

Lemma 1.

In bothSumNCGandMaxNCGin ${\mathcal{M}}_1$, any player u that has an improving response involving edge swaps must have degree 1 (and u must own its sole incident edge).

Theorem 1.

In ${\mathcal{M}}_1$, any improving response dynamics forSumNCGmust converge to an equilibrium.

Proof. 

Consider any strategy profile in which no edge is owned by both endpoints, which can be safely assumed as this can only happen in the starting network.

Notice that, in such a configuration, no edge can be removed by any player (as otherwise the network could become disconnected in the player’s view). As the maximum number of edges is upper bounded by $O\left(n^2\right)$, it suffices to show that any dynamics in which only swap moves are allowed must converge.

Consider a network G and player u that changes her strategy from ${\sigma }_u$ to ${\sigma }_u^{\prime }$ (with $|{\sigma }_u|=|{\sigma }_u^{\prime }|$) in order to improve her (worst-case) cost. As the cost of player u in the resulting network $G^{\prime }$ must be lower than her corresponding cost in G, and since the building cost of u is unchanged, we know that the usage cost of u decreases when moving from G to $G^{\prime }$.

In the rest of the proof we will argue that the function $\Phi \left(G\right)={\sum }_{x\in V}{\sum }_{v\in V}{d}_G(x,v)$ is a potential function for this game, i.e., the value of $\Phi$ decreases whenever any improving response is played. The claim will immediately follow by noticing that $\Phi$ has a finite domain. As the degree of u in G is 1, as shown by Lemma 1, we can write

$$\begin{array}{c}\Phi \left(G\right)-\Phi \left(G^{\prime }\right)=\sum _{x\in V}\sum _{v\in V}{d}_G(x,v)-\sum _{x\in V}\sum _{v\in V}{d}_{G^{\prime }}(x,v)\hfill \\ =\sum _{x\in V\backslash \left\{u\right\}}\sum _{v\in V\backslash \left\{u\right\}}{d}_G(x,v)+2\sum _{v\in V}{d}_G(u,v)-\sum _{x\in V\backslash \left\{u\right\}}\sum _{v\in V\backslash \left\{u\right\}}{d}_{G^{\prime }}(x,v)-2\sum _{v\in V}{d}_{G^{\prime }}(u,v)\\ \hfill =2\left(\sum _{v\in V}{d}_G(u,v)-\sum _{v\in V}{d}_{G^{\prime }}(u,v)\right)>0.\end{array}$$

where the fact that u has degree 1 in both G and $G^{\prime }$ implies that $d_G(x,v)=d_{G^{\prime }}(x,v)$ for every $x,v\in V\backslash \left\{u\right\}$. □

A similar result can be shown for MaxNCG in model ${\mathcal{M}}_1$:

Theorem 2.

In ${\mathcal{M}}_1$, any improving response dynamics forMaxNCGmust converge to an equilibrium.

Proof. 

Similarly to the proof of Theorem 1, it will suffice to prove that every dynamics involving only swap moves converges to an equilibrium. We will show that this holds true using similar argument to those in [22]. Consider a graph G corresponding to some profile of strategies and look at the n-dimensional vector ${\epsilon }_G$ in which the i-th entry is the eccentricity of the i-th vertex of G. Now, consider the sorted version of ${\epsilon }_G$ in which entries appear in non-increasing order. We will assume that comparisons among n-dimensional vectors be performed in lexicographic order and we will consider the function that maps each strategy profile the corresponding sorted vector ${\epsilon }_G$. We will prove that the value of such a function can only decrease following an improving response.

As show in Lemma 1, all players that are able to change their strategy to an improving response must have degree 1 in the current network G. Consider a player u changing her strategy to an improving response and let $G^{\prime }$ be the resulting network and denote by ${\epsilon }_H\left(x\right)$ the eccentricity of vertex $x\in V\left(H\right)$ in H. As the number edges of edges owned by u cannot decrease, we must have ${\epsilon }_G\left(u\right)>{\epsilon }_{G^{\prime }}\left(u\right)$.

We now prove that if the eccentricity a player $x\ne u$ increases between G and $G^{\prime }$ (as a consequence of u’s strategy change), then ${\epsilon }_{G^{\prime }}\left(x\right)<{\epsilon }_{G^{\prime }}\left(u\right)$. Consider a vertex x such that ${\epsilon }_G\left(x\right)<{\epsilon }_{G^{\prime }}\left(x\right)$ and notice that, as u has degree 1 in both G and $G^{\prime }$, it must hold that ${\epsilon }_{G^{\prime }}\left(x\right)=d_{G^{\prime }}(x,u)\le {\epsilon }_{G^{\prime }}\left(u\right)$, which concludes the proof. □

2.2. Models ${\mathcal{M}}_2$ and ${\mathcal{M}}_3$

Here, we show that, by contrast to model ${\mathcal{M}}_1$, a best-response dynamics is not guaranteed to converge in models in ${\mathcal{M}}_2$ and ${\mathcal{M}}_3$, i.e., best responses cycles can arise. Even thought we are dealing with undirected graphs (i.e., each edge can be traversed in both directions no matter which of its endpoints is the buyer), we will draw some edges as arrows directed away from the buyer in order to stress edge ownership. The next vertex to change her strategy to a best response is shown in dark gray and the set of edges that belong to her current view are depicted using bold lines/arrows.

We start by considering ${\mathcal{M}}_2$:

Theorem 3.

Best-response cycles are possible in bothSumNCGandMaxNCGin ${\mathcal{M}}_2$.

Proof. 

As far as MaxNCG is concerned, a best-response cycle for $\alpha \ge 6$ is depicted in Figure 1. The current player in graphs $\left(a\right)$ to $\left(d\right)$ always replaces his/her current strategy with an best response decreasing her cost. The graph in Figure 1d is isomorphic to that in Figure 1a, where the roles of the vertices labeled a and b are swapped. By mirroring the previous best-responses moves, the configuration in graph $\left(a\right)$ will be reached again, thus completing the cycle for MaxNCG.

Figure 2 shows a best-response cycle for SumNCG when $\alpha \ge 6$, which concludes the proof. □

We also have similar results in model ${\mathcal{M}}_3$.

Theorem 4.

Best-response cycles are possible in bothSumNCGandMaxNCGin ${\mathcal{M}}_3$.

Proof. 

A best-response cycle for SumNCG in ${\mathcal{M}}_3$ when $\alpha =15$ is shown in Figure 3. Graphs $\left(a\right)$ and $\left(d\right)$ are isomorphic and, in particular, the roles of vertices a and c are exchanged.

Figure 4 shows a best-response cycle for MaxNCG when $\alpha =2-ϵ$, for a sufficiently small value of $ϵ>0$. □

3. Complexity of Computing a Best Response

We now consider the computational complexity of the problem of computing a best response strategy in our models. For ${\mathcal{M}}_1$ we will show that it is possible to compute a best response strategy for MaxNCG in polynomial time. The corresponding problem form SumNCG remains open, although we conjecture that a polynomial-time algorithm exists for this game as well.

Concerning ${\mathcal{M}}_2$, we prove that a best response strategy can be efficiently computed for SumNCG as well as MaxNCG. If we consider ${\mathcal{M}}_3$ instead, then the problem becomes NP-hard for both games.

3.1. Model ${\mathcal{M}}_1$

In this section, we design a polynomial-time dynamic programming algorithm that computes a best response of a player for MaxNCG in ${\mathcal{M}}_1$. Fix a strategy profile $\sigma$ and a player u, and let ℓ be the eccentricity of u in $G\left(\sigma \right)$. We will use $\mathcal{G}$ to refer to the set of all graphs that are compatible with u’s view in $\sigma$. Furthermore, we will use the set ${\mathcal{G}}^{\prime }$ consisting of all graphs that can be obtained by removing the edges incident to u from some graph in $\mathcal{G}$. For $i=0,\dots ,\ell$, let $L_i$ be the set of vertices at distance exactly i from u in $G\left(\sigma \right)$. Finally, for $X,Y\subseteq V$ and a graph G having V as its vertex set, we define $d_G(X,Y)={max}_{y\in Y}{min}_{x\in X}{d}_G(x,y)$ and $\delta (X,Y)={max}_{G\in {\mathcal{G}}^{\prime }}{d}_G(X,Y)$. With a slight abuse of notation we will write $\delta (X,y)$ in place of $\delta (X,\{y\left\}\right)$ whenever $y\in V$.

Our dynamic programming algorithm will exploit the structural properties of best-response strategies in the worst-case graph that are summarized in the following lemmata.

Lemma 2.

Let $\varnothing ⊊L_i^{\prime }⊊L_i$ and $y\in L_j$, with $i,j>0$. If there exists an index $0<t\le min\{i,j\}$ such that $|L_t|=1$, then let h be the maximum such index t; otherwise, let $h=\perp$. Then,

$$\delta (L_i^{\prime },y)=\left\{\begin{array}{cc}j+i-2h\hfill & ifh\ne \perp ;\hfill \\ +\infty \hfill & ifh=\perp .\hfill \end{array}\right.$$

Proof. 

We start by considering the case $h\ne \perp$. Let the sole vertex in $L_h$ be z. It is not hard to see that $\delta (L_i^{\prime },y)\le j+i-2h$ as any $G\in {\mathcal{G}}^{\prime }$ must contain (i) some path of length $i-h$ from z to each of the vertices in $L_i$, and (ii) a path from z to y having a length of $j-h$. Consider now any tree $T\in \mathcal{G}$ in which the lowest common ancestor between y and each vertex in $L_i^{\prime }$ is z (notice that it is always possible to find such a tree T). For every $x\in L_i^{\prime }$ we have $d_T(x,y)=j+i-2h$, implying $\delta (x,y)\ge d_T(x,y)=i+i-2h$.

We now turn our attention to the case $h=\perp$. Pick any graph $G\in {\mathcal{G}}^{\prime }$ such that (i) G is disconnected, (ii) all the vertices in $L_i$ belong to the same connected component $\mathcal{C}$ of G, and (iii) y is not among the vertices in $\mathcal{C}$ (again, it is always possible to find that such a graph G). Then, $\delta (L_i^{\prime },y)=\infty$. □

Lemma 3.

Let $y\in L_j$, with $j>0$. If there exists an index $0<t\le j$ such that $|L_t|=1$, then let h be the maximum such index; otherwise, let $h=\perp$. Then, the following holds $\forall i=1,\dots ,\ell$,

$$\delta (L_i,y)=\left\{\begin{array}{cc}j-i\hfill & ifi\le j;\hfill \\ j+i-2h\hfill & ifh\ne \perp andi>j;\hfill \\ +\infty \hfill & ifh=\perp andi>j;\hfill \end{array}\right.$$

Proof. 

The case $h=\perp$ and $i>j$ has already been handled in the proof of Lemma 2, we therefore focus on the two remaining cases.

When $i\le j$, we have that $d_G(L_i,y)=j-i$ for all graphs $G\in \mathcal{G}$, thus $\delta (L_i,y)=j-i$. When $i>j$ and $h\ne \perp$, we can consider any tree $T\in \mathcal{G}$ in which the lowest common ancestor between $x\in L_i$ and y is the solve vertex z in $L_h$. Then we have $d_T(x,y)=j+i-2h$ for every $x\in L_i$, which implies that $\delta (x,y)=j+i-2h$. □

Define $S=\{v\in L_1:u\in {\sigma }_v\}$ as the set of players v that have bought the edge $(v,u)$ towards u in the strategy profile $\sigma$. We can show the following.

Lemma 4.

There exists a best-response strategy ${\sigma }_u^{*}$ for u such that, for every $i=2,\dots ,\ell$, either $L_i\cap {\sigma }_u^{*}=\varnothing$ or $L_i\subseteq {\sigma }_u^{*}$. Moreover, at least one of the following two conditions holds: $|L_1|=1$ or $L_1\subseteq ({\sigma }_u^{*}\cup S)$.

Proof. 

We start by noticing that when $|L_1|\ge 2$ and $L_1\subseteq ({\sigma }_u^{*}\cup S)$ we can find a network $G\in \mathcal{G}$ that becomes disconnected when player u changes her strategy from $\sigma$ to ${\sigma }^{*}$. This implies that ${\sigma }_u^{*}$ cannot be a best response for u and proves the second part of our claim.

Given a possible strategy ${\sigma }_u^{\prime }$ for u, define $f\left({\sigma }_u^{\prime }\right)=\left|\{i\in \{2,\dots ,\ell \}s.t.{\sigma }_u^{\prime }\cap L_i\ne \varnothing \mathrm{and}{L}_i\subseteq {\sigma }_u^{\prime }\}\right|$. In other words, $f\left({\sigma }_u^{\prime }\right)$ is the number of levels $L_i$ with $i\ge 2$ for which u is buying some but not all edges towards the vertices in $L_i$, according to strategy ${\sigma }_u^{\prime }$.

We prove that if ${\sigma }_u^{\prime }$ is a strategy for which $f\left({\sigma }_u^{\prime }\right)>0$, then there exists another strategy ${\sigma }_u^{″}$ for u such that $f\left({\sigma }_u^{″}\right)<f\left({\sigma }_u^{\prime }\right)$ and $\Delta ({\sigma }_u,{\sigma }_u^{\prime })\ge \Delta ({\sigma }_u,{\sigma }_u^{″})$. As $f\left({\sigma }_u^{\prime }\right)>0$ we are always able to find an index i for which neither $L_i\cap {\sigma }_u^{\prime }=\varnothing$ nor $L_i\subseteq {\sigma }_u^{\prime }$. Define $L_i^{\prime }=L_i\cap {\sigma }_u^{\prime }$ and let $j\in \{1,2,\dots ,i-1\}$ be the maximum index for which $|L_j|=1$, if any. If such an index exists, we let ${\sigma }_u^{″}=({\sigma }_u^{\prime }\backslash L_i^{\prime })\cup L_j$; otherwise (if j does not exist), we let ${\sigma }_u^{″}={\sigma }_u^{\prime }\backslash L_i^{\prime }$. By our choice of ${\sigma }_u^{″}$, we must have both $f\left({\sigma }_u^{″}\right)<f\left({\sigma }_u^{\prime }\right)$ and $|{\sigma }_u^{″}|\le |{\sigma }_u^{\prime }|$. Moreover, invoking Lemmas 2 and 3, we obtain $\delta (L_j,V)\le \delta (L_i^{\prime },V)$. It follows that $\delta ({\sigma }_u^{″},V)\le \delta ({\sigma }_u^{\prime },V)$ and hence, for every $G\in \mathcal{G}$:

$$C_u(({\sigma }_{-u},{\sigma }_u^{″}),G)=\alpha ·|{\sigma }_u^{″}|+\delta ({\sigma }_u^{″},V)\le \alpha ·\left|{\sigma }_u^{\prime }\right|+\delta ({\sigma }_u^{\prime },V)=C_u(({\sigma }_{-u},{\sigma }_u^{\prime }),G),$$

thus showing that $\Delta ({\sigma }_u,{\sigma }_u^{\prime })\ge \Delta ({\sigma }_u,{\sigma }_u^{″})$. □

We can now design a polynomial-time algorithm to compute a best-response in ${\mathcal{M}}_1$:

Theorem 5.

In ${\mathcal{M}}_1$ the best response of a player can be computed in polynomial time forMaxNCG.

Proof. 

We will design a dynamic programming algorithm that computes a best-response strategy satisfying the conditions of Lemma 4.

For $i=0,\dots ,\ell$ and $\eta =0,\dots ,n-2$, we denote by $A[i,\eta ]$ the minimum criminality of a set of vertices X such that $L_i\subseteq X$ and $\delta \left(X,{\bigcup }_{h=1,\dots ,i}{L}_h\right)\le \eta -2$. The idea is that $A[i,\eta ]$ will be (proportional to) the minimum building cost needed to ensure that the distance between u and all the vertices in ${\bigcup }_{h=1,\dots ,i}{L}_h$ will not exceed $\eta +1$ with the restriction that u can only buy edges towards sets of vertices X for which $L_i\subseteq X\subseteq {\bigcup }_{h=1,\dots ,i}{L}_h$.

For technical simplicity (and with a small abuse of notation) we will consider $L_0$ to be the empty set. Moreover, we define $g(i,\eta )$ as the smallest index for which $0\le g(i,\eta )\le i$ and $\delta (L_{g(i,\eta )}\cup L_i,{\bigcup }_{h=g(i,\eta ),\dots ,i}{L}_h)\le \eta$. According to the above discussion, the cost of a best-response strategy will be equal to:

$$1+\underset{\eta =0,\dots ,n-2}{min}\{\eta +\alpha ·\underset{max\{1,g(\ell ,\eta \left)\right\}\le j\le \ell }{min}A[j,\eta ]\}.$$

For every $\eta =0,\dots ,n-1$, we have $A[0,\eta ]=0$ and $A[1,\eta ]=|{\sigma }_u\cap L_1|$ as each edge $(u,v)$ between u and $v\in L_1\backslash {\sigma }_u$ is bought by v. Moreover, for $i=1,\dots ,\ell$ and $\eta =0,\dots ,n-2$, we can efficiently compute $A[i,\eta ]$ using the following identity,

$$A[i,\eta ]=|L_i|+\underset{g(i,\eta )\le j<i}{min}A[j,\eta ].$$

After the cost of a best-response strategy ${\sigma }_u^{*}$ for u has been found, one can easily find the strategy ${\sigma }_u^{*}$ itself by retracing the dynamic-programming choices backwards. □

3.2. Model ${\mathcal{M}}_2$

In model ${\mathcal{M}}_2$, we are able to design polynomial-time algorithms to compute a best-response strategy for a player for both SumNCG and MaxNCG, as the following theorem shows.

Theorem 6.

In ${\mathcal{M}}_2$, the best response of a player can be computed in polynomial time for bothSumNCGandMaxNCG.

Proof. 

Let $\sigma$ be a strategy profile, where ${\sigma }_u$ denotes the current strategy of some player u, and let $T\left(u\right)$ be the shortest-path tree (rooted in u) corresponding to u’s view of the network $G\left(\sigma \right)$. We now design a dynamic programming algorithm computing a best response ${\sigma }_u^x$ for u (in polynomial-time). For SumNCG and MaxNCG, our algorithm will respectively solve a variant of the k-median and the k-center problem on trees. The input of the k-median (resp., k-center) problem is a graph H, and the goal is that of finding a set S of exactly k vertices in H in order to minimize the sum of distances (resp. the maximum distances) between each node in H and the closest node in S (Actually, the k-median problem asks to minimize the average distance between the vertices of H and the closest vertex in S. However, it is easy to see that this is equivalent to minimizing the sum of the above distances).

By deleting u from $T\left(u\right)$ we are left with a some forest F. Let $T_1,\dots ,T_h$ be the trees in F and let $r_i$ be the root of $T_i$. Let $z=|{\sigma }_u|$. We can assume (w.l.o.g.) that the trees $T_i$ with $i\le z$ (for some value of z) are those for which u owns the edge $(u,r_i)$ and that all edges $(u,r_j)$ for $j>z$ are owned by $r_j$.

For $i\le z$ and $0\le k<n$, we let $A[i,k]$ be the cost of an optimal solution the instance of the k-median (resp. k-center) problem in which $H=T_i$. Similarly, for $z<i\le h$ and $0\le k<n$, we let $A[i,k]$ be the cost of an optimal solution to the instance of a constrained version of the k-median (resp. k-center) problem in which $H=T$ and we additionally require the solution to contain vertex $r_i$. Whenever there is no feasible solution to the above instances (e.g., when $k\ge \left|V\right(T_i\left)\right|$) we let $A[i,k]=+\infty$. It is well known both the k-median and the k-center problem can be solved in polynomial time when the input graph H is a trees (and it is easy to see that this is still true for their constrained variants).

We now consider the first i trees and, for each value of j, we compute the minimum aggregate cost $B[i,j]$ that can be obtained by solving i (possibly constrained) instances of k-median (resp. k-center) on the trees $T_1,\dots ,T_i$ while selecting exactly j vertices across all such instances. More formally, for the k-median problem, we define

$$B[i,j]=\underset{\begin{array}{c}{j}_1,j_2,\dots ,j_i\in \mathbb{N}\\ j_1+j_2+\dots +j_i=j\end{array}}{min}\sum _{\ell =1}^{i}A[\ell ,j_{\ell }],$$

while, for the k-center problem we define

$$B[i,j]=\underset{\begin{array}{c}{j}_1,j_2,\dots ,j_i\in \mathbb{N}\\ j_1+j_2+\dots +j_i=j\end{array}}{min}max\left\{A[\ell ,j_{\ell }]:1\le \ell \le i\right\}.$$

Notice that, by definition, $B[1,j]=A[1,j]$ for both problems. For $i>1$, we can efficiently compute $B[i,j]$ using the following recursive formulas. For the k-median problem we have

$$B[i,j]=\underset{1\le t\le j-i+1}{min}\left\{A[i,t]+B[i-1,j-t]\right\},$$

while, for the k-center problem,

$$B[i,j]=\underset{1\le t\le j-i+1}{min}max\left\{A[i,t],B[i-1,j-t]\right\}.$$

To find the cost of u’s best response ${\sigma }_u^{*}$ in SumNCG, we observe that $n-1+B[h,j]$ is exactly the smallest usage cost incurred by u if she decides to buy exactly $j-(h-z)$ edges (as $h-z$ edges are already owned by the vertices $r_i$ with $z+1\le i\le h$). We therefore know that, in SumNCG,

$$C_u(({\sigma }_{-u},{\sigma }_u^{*}),G)=n-1+\underset{h-z\le j<n}{min}\left\{B[h,j]+\alpha (j-h+z)\right\}.$$

Similarly, $1+B[h,j]$ is the smallest usage cost for u when he/she constructs exactly $j-(h-z)$ edges in MaxNCG, therefore

$$C_u(({\sigma }_{-u},{\sigma }_u^{*}),G)=1+\underset{h-z\le j<n}{min}\left\{B[h,j]+\alpha (j-h+z)\right\}.$$

In both cases, the number of edges $|{\sigma }_u^{*}|$ that u buys in a best response is $arg{min}_{h-z\le j<n}\left\{B[h,j]+\alpha (j-h+z)\right\}$. Retracing the dynamic programming choices backwards, it is possible to compute (in polynomial time) the optimal number $j_i^{*}$ of edges to be bought towards the vertices in each tree $T_i$. The actual edges to activate in SumNCG (resp. MaxNCG) can be found by inspecting the optimal solutions for the (possibly constrained) k-median (reps. k-center) instances associated with each $A[i,j_i^{*}]$. □

3.3. Model ${\mathcal{M}}_3$

As far as model ${\mathcal{M}}_3$ is concerned, the problem of computing a best response is NP-hard for both SumNCG and MaxNCG, as shown by the following results:

Theorem 7.

Computing a best response for a player in ${\mathcal{M}}_3$ forSumNCGis NP-hard.

Proof. 

We probe the claim by providing a polynomial-time reduction from the (decision version of) the Minimum Dominating Set problem (MDSP) on bipartite graphs to the problem of computing a best response in ${\mathcal{M}}_3$, similarly to that used in [1].

An instance of MDSP is a pair $\langle G,k\rangle$ where G is a graph and k is a positive integer. The problem is that of deciding whether there exists a subset D of vertices of H such that (i) each vertex $v\in V^{\prime }$ is either in D or is adjacent to a vertex in D, and (ii) $\left|D\right|\le k$. It is well-known that MDSP is hard even when H is bipartite [23].

Let $\langle H,k\rangle$ be an instance of MDSP where $H=(U^{\prime }\cup V^{\prime },E^{\prime })$ is a bipartite graph. Fix any value of $\alpha \in (1,2)$ and let G be the graph obtained from H by adding an additional vertex (player) u along with all the edges in $\left\{u\right\}\times U^{\prime }$. Consider any strategy profile $\sigma$ such that $G\left(\sigma \right)=G$ and all edges incident to u are bought solely by u. Notice that each edge $e\in E^{\prime }$ belongs to at least one shortest path from u in G and therefore the view of u coincides with G itself.

Let ${\sigma }_u^{*}$ be a best response strategy for u and notice that the eccentricity of u in $G({\sigma }_{-u},{\sigma }_u^{*})$ must be at most 2. Indeed, if a vertex v was at a distance of at least 3 from u in $G({\sigma }_{-u},{\sigma }_u^{*})$, then u could improve her cost by playing ${\sigma }_u^{*}\cup \left\{u\right\}$ instead of ${\sigma }_u^{*}$ (thus decreasing the distance to v by at least 2 while increasing her building cost by $\alpha <2$). It follows that ${\sigma }_u^{*}$ must be a dominating set of H.

We now argue that ${\sigma }_u^{*}$ must be a minimum dominating set of H. Indeed, given any strategy ${\sigma }_u^{\prime }$ of player u for which the eccentricity of u in $G({\sigma }_{-u},{\sigma }_u)$ is at most 2, we have that

$$\begin{array}{cc}\hfill C_u({\sigma }_{-u},{\sigma }_u^{\prime })& =\alpha |{\sigma }_u^{\prime }|+\sum _{v\in V^{\prime }}{d}_{G\left(({\sigma }_{-u},{\sigma }_u^{\prime })\right)}(u,v)\hfill \\ \hfill & =\alpha |{\sigma }_u^{\prime }|+\sum _{v\in {\sigma }_u^{\prime }}{d}_{G\left(({\sigma }_{-u},{\sigma }_u^{\prime })\right)}(u,v)+\sum _{v\in V^{\prime }\backslash {\sigma }_u^{\prime }}{d}_{G\left(({\sigma }_{-u},{\sigma }_u^{\prime })\right)}(u,v)\hfill \\ \hfill & =\alpha |{\sigma }_u^{\prime }|+|{\sigma }_u^{\prime }|+2(|V^{\prime }|-|{\sigma }_u^{\prime }\left|\right)=(\alpha -1)|{\sigma }_u^{\prime }|+2|V^{\prime }|,\hfill \end{array}$$

which is minimized when $|{\sigma }_u^{\prime }|$ is minimized.

The above discussion implies that H admits a dominating set D with $\left|D\right|\le k$ vertices if $|{\sigma }^{*}|\le k$ and concludes the proof. □

Theorem 8.

Computing a best response for a player in ${\mathcal{M}}_3$ forMaxNCGis NP-hard.

Proof. 

As in the proof of Theorem 7, we prove the claim through a reduction (similar to than in [3]), from the Minimum Dominating Set problem (MDSP) on bipartite graphs [23]. Given an instance $\langle H,k\rangle$ of (the decision version) of MDSP on bipartite graphs, we further assume w.l.o.g. that $H=(U^{\prime }\cup V^{\prime },E^{\prime })$ admits a dominating set $D^{*}$ of size smaller than $\frac{|U^{\prime }\cup V^{\prime }|}{2}$ (If this is not the case, then it suffices to consider the graph $\overline{H}$ obtained from the disjoint union of H with a star on $|U^{\prime }\cup V^{\prime }|+2$ vertices centered in some vertex v. $H^{\prime }$ has $2|U^{\prime }\cup V^{\prime }|+2$ vertices and admits a minimum dominating set of cardinality at most $|U^{\prime }\cup V^{\prime }|+1$. Moreover, $D\subseteq U^{\prime }\cup V^{\prime }$ is a dominating set for H iff $D\cup \left\{v\right\}$ is a dominating set of $\overline{H}$).

Pick $\alpha =\frac{2}{|U^{\prime }\cup V^{\prime }|}$ and let G be the graph obtained from H by adding an additional vertex (player) u along with all the edges in $\left\{u\right\}\times U^{\prime }$. Consider any strategy profile $\sigma$ such that $G\left(\sigma \right)=G$ and all edges incident to u are bought solely by u, so that the view of u coincides with G itself.

Let ${\sigma }_u^{*}$ be a best response strategy for u and let $\mathcal{E}$ be the eccentricity of u in $G({\sigma }_{-u},{\sigma }_u^{*})$. Clearly, ${\sigma }^{*}\ne \varnothing$. If $\mathcal{E}>2$, then u could buy an edge towards every vertex in G increasing her building cost by at most $\alpha |(U^{\prime }\cup V^{\prime })\backslash {\sigma }^{*}|<2$ and reducing her usage cost by $\mathcal{E}-1\ge 2$. If $\mathcal{E}=1$, then $|{\sigma }^{*}|=|U^{\prime }\cup V^{\prime }|$ and u could delete all the edges towards vertices that are not in $D^{*}$, thus saving at least $\alpha \frac{|U^{\prime }\cup V^{\prime }|}{2}=2$ on his/her building cost, while increasing the usage cost by 1. We can therefore conclude that $\mathcal{E}=2$, i.e., ${\sigma }^{*}$ must be a dominating set of H.

As each dominating sets D of H is also a strategy for u such that u has cost $\alpha \left|D\right|+2$ in $G({\sigma }_{-u},D)$, we have that H admits a dominating set D with $\left|D\right|\le k$ vertices iff $|{\sigma }^{*}|\le k$. □

4. Price of Anarchy

Models ${\mathcal{M}}_1$, ${\mathcal{M}}_2$ and ${\mathcal{M}}_3$ are equivalent with respect to the PoA, as shown by the following two Theorems.

Theorem 9.

The PoA forSumNCGin ${\mathcal{M}}_1$, ${\mathcal{M}}_2$, and ${\mathcal{M}}_3$ is $\Theta (min\{1+\alpha ,n\left\}\right)$ for every α.

Proof. 

Notice that each network that is compatible with the view of u in model ${\mathcal{M}}_2$ (resp. ${\mathcal{M}}_3$) must also be compatible with the view of u in ${\mathcal{M}}_1$ (resp. ${\mathcal{M}}_2$). This shows that the PoA can only decrease when we consider ${\mathcal{M}}_1$, ${\mathcal{M}}_2$, and ${\mathcal{M}}_3$ in this order. We will prove the claim by showing that $O(min\{1+\alpha ,n\left\}\right)$ is an upper bound for ${\mathcal{M}}_1$ and $\Omega (min\{1+\alpha ,n\left\}\right)$ a lower bound in ${\mathcal{M}}_3$.

We start by proving our lower bound in ${\mathcal{M}}_3$. To this aim, consider the complete graph and notice that it is an equilibrium since the only SPT rooted in each vertex (player) is a star, and no edge can be removed. The corresponding social cost is $\Omega (\alpha n^2+n^2)$, while the cost of an optimal network is upper bounded by that of a star, i.e., $O(\alpha n+n^2)$. It follows that the PoA must be $\Omega (min\{n,1+\alpha \left\}\right)$.

We now turn our attention to the upper bound in ${\mathcal{M}}_1$. We start by showing that the diameter of an equilibrium graph G can be at most $O(1+\sqrt{\alpha })$. Let u and v be two players such that the eccentricity D of u in G is equal to $d(u,v)\ge 4$ (we can assume that such a pair exists as otherwise the diameter of G would be at most 3). If player u were to buy the edge $(u,v)$, he/she would decrease her distances towards at least $\frac{D}{4}$ vertices, namely, those on the shortest path between u and v, by at least $\frac{3}{4}D-\frac{1}{4}D-1=\frac{1}{2}D-1$. This would decrease her usage cost by at least $\Omega \left(D^2\right)$. Notice that this reasoning is compatible with the local view of u in model ${\mathcal{M}}_1$, since u only needs to know $d(u,v)$ (while no knowledge of the internal vertices of $\pi$ is necessary). As the edge $(u,v)$ is not in G, we can infer that $\alpha =\Omega \left(D^2\right)$, which implies $D=O(1+\sqrt{\alpha })$.

The PoA can then be upper bounded as follows,

$$O\left(\frac{\alpha n^2+n^2(1+\sqrt{\alpha })}{\alpha n+n^2}\right)=O(min\{n,1+\alpha \}).$$

□

Theorem 10.

The PoA forMaxNCGin ${\mathcal{M}}_1$, ${\mathcal{M}}_2$, and ${\mathcal{M}}_3$ is $\Theta \left(n\right)$ for $\alpha =\Omega \left(1\right)$, and $\Theta (1+\alpha n)$ if $\alpha =O\left(1\right)$.

Proof. 

By similar arguments as the ones used in the proof of Theorem 9, we only need to show an upper bound to the PoA in model ${\mathcal{M}}_1$ and a lower bound to the PoA in model ${\mathcal{M}}_3$.

Once again, we can consider a complete graph H to obtain our lower bound. The same discussion in the proof of Theorem 9 also applies to MaxNCG, and shows that H is an equilibrium network in ${\mathcal{M}}_1$. The social cost of H is $\Omega (\alpha n^2+n)$, while that of a star is $O(\alpha n+n)$. As a consequence, we obtain a lower bound on the PoA of $\Omega \left(\frac{\alpha n^2+n}{\alpha n+n}\right)$, which reduces to $\Omega \left(n\right)$ for $\alpha =\Omega \left(1\right)$, and to $\Omega (1+\alpha n)$ for $\alpha =O\left(1\right)$.

To prove our upper bound on ${\mathcal{M}}_3$ we show that, in any equilibrium graph G, the diameter of G must be at most $O(1+\alpha n)$. Let u be a player having eccentricity $D\ge 4$ in G, define X as the set of vertices at distance $\lfloor D/2\rfloor$ from u in G. If u were to buy all edges in $\left\{u\right\}\times X$, his/her eccentricity would decrease by $\Omega \left(D\right)$. As G is an equilibrium, we know that the building cost must exceed $\Omega \left(D\right)$, in formulas: $\alpha n\ge \alpha ·\left|X\right|=\Omega \left(D\right)$, i.e., $D=O(1+\alpha n)$. This shows that the social cost of G must be at most $O(\alpha n^2+n+n^2)$ and we can upper bound the PoA as $\frac{O(\alpha n^2+n+n^2)}{\Omega (\alpha n+n)}$, which yields the sought bounds when instantiated with $\alpha =\Omega \left(1\right)$ and $\alpha =O\left(1\right)$. □