Next Article in Journal
New Directions in Behavioral Game Theory: Introduction to the Special Issue
Next Article in Special Issue
A Survey on Nonstrategic Models of Opinion Dynamics
Previous Article in Journal
Communication, Expectations, and Trust: An Experiment with Three Media
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Note on Connectivity and Stability in Dynamic Network Formation

Department of Economics, Kyung Hee University, 1 Hoegidong, Dongdaenumku, Seoul 130-701, Korea
*
Author to whom correspondence should be addressed.
Submission received: 15 September 2020 / Revised: 2 October 2020 / Accepted: 12 October 2020 / Published: 29 October 2020
(This article belongs to the Special Issue Social and Economic Networks)

Abstract

:
We consider the dynamic network formation problem under the requirement that the whole network be connected and remain connected after q nodes are destroyed. We propose the concept of dynamic C q -stability and characterize dynamic C q -stable networks for any q 0 . Comparison with the outcome in the static model is also discussed.
JEL Classification:
C72

1. Introduction

The value of a social network relies crucially on its connectivity and resilience, which can be defined by the ability to maintain connectivity even after unexpected trembles due to external shocks. In a prior paper [1], we considered the problem of forming a network under the requirement that the whole network be connected and remain connected after eliminating q nodes, and introduced the concept of the C q -stability of a network in a static setting. The C q -stability is, roughly speaking, to require connectivity in addition to pairwise stability defined by Jackson and Wolinsky [2] even after any at most q nodes are deleted. In the paper, we characterized the C 1 -stable networks without characterizing general C q -stable networks.
In this paper, we extend the network formation problem and the concept of C q -stability to a dynamic setting. In a dynamic model in which one player is spawned at each period, we characterize the dynamic C q -stable network for q 0 and compare the outcome with that in the static model of Jun and Kim [1]. Our concept of dynamic C q -stability will be also called intraperiod-farsighted stability, since it is defined based on our assumption that players are forward looking only within each period.
There are some papers on the resilience of a network. To the best of our knowledge, Jun and Kim [1] is the first paper to acknowledge the possibility of node destruction in the literature on (social or economic) network formation. After Jun and Kim [1], there have been some studies that added an attacker as an active player. In particular, Goyal and Vigier [3] considered a contest game between a network designer and an attacker. The designer first chooses a network and allocates defense resources across nodes, and then an adversary allocates attack resources to nodes. If the adversary’s attack on a node succeeds, he captures the node and any unprotected nodes connected with the nodes via contagion. Then, the designer cannot control the nodes anymore. The objective of the designer is to maximize the total value from the whole network. In Dziubiński and Goyal [4], there is no contagion but the model is quite similar. Unlike Jun and Kim [1], however, both are centralized network design problems rather than decentralized network formation problems. Moreover, information decay is assumed in neither model. Thus, in Goyal and Vigier [3], a network generates the same value insofar as it is connected. That is, how it is connected does not matter. In Dziubiński and Goyal [4] that considers the linking costs explicitly, it is not important, either, how a network is connected and, as a result, how much it can reduce communication delays, because information decay is not assumed. Hoyer and De Jaegher [5] also considers a centralized network design problem with linking costs and without information decay. They analyze both cases of node deletion and link deletion. Exceptionally, Haller and Hoyer [6] is a decentralized network formation model just like Jun and Kim [1], but it assumes no information decay, either. It uses the solution concept of Nash stability, whereas Jun and Kim [1] proposes a new solution concept of C q -stability which shares the spirit of pairwise stability but is stronger than that. It is well known that Nash stability and pairwise stability do not have any inclusion relation. On one hand, Nash stability could be stronger than pairwise stability because it requires a network to be robust against unilateral deviations involving more than two players (for example, cutting a link and at the same time linking with the third player) and only a pair’s deviation, but, on the other hand, pairwise stability could be stronger because it requires a network to be robust against any bilateral deviations of a pair of players to form a link and a unilateral deviation.
Our dynamic model of network formation is also similar to a sequential version of a network creation game which was introduced by Fabrikant et al. [7]. Both take the delay cost into account but Fabrikant et al. [7] used Nash stability as a solution concept, unlike our paper. Leme et al. [8] proposed subgame perfection as the solution concept in a model in which players arrive sequentially, just as we used the concept of intraperiod-farsighted stability to capture dynamic consistency, but neither of Fabrikant et al. [7] and Leme et al. [8] considered the possibility of attacks.
In Section 2, we introduce some preliminary definitions in graph theory. In Section 3, we set up a dynamic model of network formation. Section 4 provides an analysis for the dynamic model without faults and with faults. Concluding remarks follow in Section 5. All the proofs are provided in Appendix A.

2. Preliminaries

Let N = { 1 , 2 , , n } be the set of nodes representing agents with n 1 . Interactions among agents are formally represented by a graph (or network) g.1
If agents i and j are linked to each other in graph g, we denote it by i j g . We also denote by g + i j the graph obtained from adding the link i j to g and by g i j the graph obtained from deleting the link i j from g. A path between i 1 and i n in g is a set of distinct nodes { i 1 , i 2 , , i n } N such that i 1 i 2 , i 2 i 3 , , i n 1 i n g . We will use more intuitive notation for a path as i 1 i 2 i n 1 i n interchangeably.
A graph g is said to be connected if there is a path in g between any pair of agents i and j in N. Additionally, g is said to be q-connected if g is still connected even after q nodes are deleted.2 We will denote the set of all connected graphs by C and the set of all q-connected graphs by C q . Then, it is obvious that graph g is q-connected whenever it is q -connected for q < q , that is, C q C q if q < q for all q = 0 , 1 , , n where C 0 C .
If g is not connected, it is possible that only a proper subset of N have links in g. We will denote the subset by S ( g ) and define it by S ( g ) = { i , j N i j g } .

3. Dynamic Model of Network Formation

We consider communication networks. If i j g , both of agent i and agent j incur the cost c ( 0 , ) of connecting the direct link. If agent i and j are directly linked, they can exchange information without delay (i.e., in one unit of time length). If agent i is indirectly linked to j, i.e., there is a path { i , i 1 , , i k , j } between i and j in g, a delay occurs in receiving information from each other. The delay cost can be represented by the distance between them in g which is defined by the number of links in the shortest path between i and j in g and denoted by d ( i , j ; g ) . If there is no path between i and j for some i , j N , we define d ( i , j ; g ) = .
The total cost that each agent i incurs in graph g is the sum of the delay cost and the connecting cost, which is given by
w i ( g ) = T i ( g ) + C i ( g ) ,
where T i ( g ) j i d ( i , j ; g ) and C i ( g ) j ; i j g c . We will call T i ( g ) and C i ( g ) agent i’s delay status and connecting status respectively. Note that w i ( g ) = for any i N if g C , while w i ( g ) < for any i N if g C . Note that if an agent adds a link, it has a tradeoff between increasing his total linking cost and reducing the total delay cost which is the benefit of adding a link.
We consider the following model of dynamic network evolution. In each period t, player t is born. Thus, in the first period, the population consists of only one agent. In the t-th period, player t joins the population consisting of t 1 players. The stage game of the t-th period proceeds as follows: First, player 1 decides whether to propose connecting a link with the newcomer, player t.3 After the decision of player t whether to accept the proposal, player 2 decides whether to propose a link with player t and so on until player t 1 makes a decision. Players are forward-looking only within a period. In other words, players make backward inductions in a stage game of each period. When they make a decision at period t, they do not take into account the possibility of repeating this procedure against player t + 1 , t + 2 , . Once a link is formed, the connecting cost c is sunk, meaning that no agent considers the option of severing an already formed link because a player could not recover c by doing so. On the other hand, the communication costs are not sunk. Communications occur in every period. Thus, the delay costs are incurred in each period. For example, if g t + 1 = g t + t ( t + 1 ) , player t incurs delay costs T t ( g t ) at both period t and period t + 1 and further incurs the additional delay cost of one for communication with a new entrant t + 1 at period t + 1 .

4. Analysis

In this section, we analyze the dynamic model with the constraint that the network is required to be connected.4 We consider both the case of no fault and the case of faults.

4.1. No Fault Case

First, we consider the case that there is no possibility that any node will be destroyed. Note that the network at each period t must be subgame perfect due to the prescribed sequential nature of a stage game. By a subgame perfect network, we mean a network that is realized in a subgame perfect equilibrium in the t-th stage game. Thus, under the requirement that a network be connected, i.e., g C , a dynamically C -stable network at period t is defined by g t C such that (i) g t is a subgame perfect network and (ii) w k ( g t ) w k ( g t 1 ) , k S ( Δ g ) where Δ g = g t g t 1 . If g t is a dynamically C -stable network at period t for all t, we call { g t } t = 1 dynamically C -stable. We will use dynamic C -stability as our main solution concept. Additionally, note that a sequence of C -stable networks at period t is strictly increasing in the sense that g t g t for any t , t t > t , because the assumption that the cost of linking in a period becomes sunk in the next period thereafter eliminates the possibility that an existing link is severed. This concept of C -stability is based on pairwise stability by Jackson and Wolinsky [2] that requires a new link to be formed by mutual consent of the linking agents.5
It is worthwhile to mention the relations of our concept to other concepts in literature. Our definition of dynamic C -stability is distinguished from that of Watts [9] and Jackson and Watts [10] who assume that players are myopic. In our definition, players are farsighted in the sense that they make linking decisions by comparing g t 1 with g t that will be completed at the end of period t. In other words, player i does not compare g t 1 with g t 1 + i t because he is farsighted enough to expect other links to follow in period t. However, they are not perfectly farsighted in the sense that they do not compare g t 1 with g t + 1 , g t + 2 and ⋯. Thus, we call our definition of dynamic stability intraperiod-farsighted stability to distinguish it from farsighted stability by Chwe [11] and Page et al. [12].
To characterize dynamic C -stable networks, we need several lemmas. Lemma 1 tells us whether two extreme players (the most senior player and the most junior player) in a line network have an incentive to link between them.
Lemma 1.
For any given t, define I t ( a t , b t ] by
I t = t 1 t 3 4 , t 1 2 4 for odd t 3 t 2 2 4 , t t 2 4 for even t 4
Then, (i) a t + 1 = b t , (ii) I t I t = for t t , and (iii) t = 3 I t = R + .
This lemma says that { I t } is a partition of R + that consists of a monotonically increasing sequence of intervals. The interval I t is essential to characterizing the stable network, because a t and b t have the interpretations as the benefits from node 1 linking with node t 1 and node t, respectively. Intuitively, if c I t , node 1 will have no incentive to link with node t 1 at period t 1 because c > a t but he will have an incentive to link with node t at period t because c < b t , assuming that g t 1 is a line.
To understand the intuition, let Δ T k be the benefit of node k from linking with the new node t at period t. Then, the benefit is the difference in his delay status. Assuming that g t 1 is a line, the incentive of node 1 to link with node t is exactly identical to the incentive of node t 1 to link with node t. Hence, 1 t g t implies ( t 1 ) t g t .6 Thus, b t = Δ T 1 = T 1 ( g ¯ t ) T 1 ( g ¯ t + 1 t ) where g ¯ t = g t 1 + ( t 1 ) t . If t = 2 l + 1 is odd,
Δ T 1 = j = 1 t 1 j j = 1 l 2 j = t ( t 1 ) 2 l ( l + 1 ) = t ( t 1 ) 2 t 1 2 t + 1 2 ( l = t 1 2 ) = ( t 1 ) 2 4 ,
and if t = 2 l is even,
Δ T 1 = j = 1 t 1 j j = 1 l 1 2 j + l = t ( t 1 ) 2 [ l ( l 1 ) + l ] = t ( t 1 ) 2 t 2 4 ( l = t 2 ) = t ( t 2 ) 4 .
Similarly, a t can be computed by replacing t by t 1 in (1) and (2).
It is intuitively clear that node 1 has more incentive to link with the entrant as the length of the line network is longer. Thus, Lemma 2 follows.
Lemma 2.
Assume that g t 1 is a line; i.e., g t 1 = { 12 , 23 , , ( t 2 ) ( t 1 ) } . Then, Δ T k is strictly decreasing in k, for k = 1 , , t 2 .
This lemma implies that if node 1 has no incentive to link with node t, neither does node k for k = 2 , , t 2 . The following lemma is helpful for understanding the incentive of node t 1 to link with node t.
Lemma 3.
Assume that g t 1 is a line. Then, 1 t g t implies ( t 1 ) t g t .
This lemma implies that the incentive of node t 1 to link with the entrant t in a line network g t 1 is congruent with the incentive of node 1.
Lemma 4.
For given t, if c k = 3 t 1 I k , i.e., c > a t , g t 1 is a line.
The main insight behind this lemma is that the most senior player enjoys the first mover advantage. He can save the connecting cost by taking advantage of juniors who must link with the newcomers. We can call this the deferral principle.7 The first mover (senior) advantage is mainly due to the requirement that the network must be connected.
To illustrate C -stable networks, consider t = 4 . It is clear that g 2 = { 12 } , since g 2 C . At t = 3 , node 1 would not link with node 3 if c > 1 , because he knows that if he does not, node 2 must link to node 3. Accordingly, g 3 = { 12 , 23 } for any c > 1 . This is contrasted with the case that c < 1 in which node 1 will link to the new node 3 even if he knows that a direct link between node 2 and node 3 will follow his linking with node 3 because the benefit of reducing a delay by the direct link with node 3 exceeds the linking cost ( c < 1 ). At t = 4 , node 3 must link with the new node 4 (i.e., 34 g 4 ) if 4 i g 4 for all i = 1 , 2 . If 24 g 4 , node 3 will not link with node 4 (i.e., 34 g 4 ), as far as c > 1 . If 14 g 4 , 34 g 4 if 1 < c < 2 because the linking cost c is smaller than the benefit of reducing delay which is 2. If c > 2 , 14 g 4 would lead to 34 g 4 and 24 g 4 . Therefore, node 1 would prefer not to link to node 4, because in that case, node 3 must link with node 4 and this is better for node 1. Thus, 14 g 4 if and only if 1 < c < 2 . The resulting stable network at t = 4 is a circle if 1 < c < 2 and a line if c > 2 . This argument can be generalized for t > 4 by the following proposition.
Proposition 1.
If c < 1 , the complete graph is the only dynamically C -stable network. For any c > 1 , there exists a finite time t ¯ ( c ) such that, for all t < t ¯ ( c ) , g t is a line, and g t is a circle if t = t ¯ ( c ) . In particular, t ¯ ( c ) is determined by t such that c I t ¯ ( c ) , and t ¯ ( c ) is strictly increasing in c.
In Appendix B, we will provide an algorithm which we call optimal deferral algorithm to find the C -stable network for any t.
By varying c instead of varying t and fixing c, Proposition 1 can be interpreted as follows.
Corollary 1.
Suppose that c I t ¯ for some t ¯ . Then, g t is a circle if t = t ¯ ( c I t ), and g t is a line if c k = 3 t I k .
We can compare the result in this dynamic model of network formation with that of a static model that was obtained in Jun and Kim [1]. First, the complete network is uniquely C -stable if c < 1 in both the dynamic model and the static model. Second, the line network is statically C -stable if c > k ( k 2 ) 4 for even k and ( k 1 ) 2 4 for odd k. Proposition 1 shows that the line network is dynamically C -stable in the same range of c. Third, the circle network is dynamically C -stable if c I k . Let I ¯ k be the range of c in which a circle is C -stable in a static model. Then, we have
I ¯ k = ( k 1 ) ( k 3 ) 8 , ( k 1 ) 2 4 if   k   is   odd k 2 4 k + 8 8 , k ( k 2 ) 4 if   k = 4 l ( k 2 ) 2 8 , k ( k 2 ) 4 if   k = 4 l 2 ,
by Proposition 1 of Jun and Kim [1]. Since I k I ¯ k for all k ( 4 ) , the dynamic C -stability of a circle implies static C -stability, but not vice versa.

4.2. Fault Case

Now, we consider the possibility that q ( 1 ) nodes are destroyed due to exogenous shocks, for example, an enemy’s attack.8 Thus, in this section, besides connectivity, we impose a further requirement that a graph remains connected even after the deletion of any at most q nodes and their direct links. Then a graph g t C q at period t is dynamically C q -stable if and only if (i) g t is subgame perfect and (ii) w k ( g t ) w k ( g t 1 ) , k S ( Δ g ) .
Proposition 2.
If c < 1 , the complete graph is the only C q -stable network. For any q 1 , if t q + 2 , the unique dynamically C q -stable network is the complete graph. If t > q + 2 , it must be a graph such that there are q + 2 centers called hubs forming a complete subnetwork among them and the rest of the nodes have ( q + 1 ) links to the centers.
Without the possibility of node extinction, hubs would not be necessary for stability, but hubs are essential for stability in the presence of a possibility of attacks on nodes, and furthermore, more hubs are necessary in the presence of attacks on more nodes (larger q).
It is easy to see that a dynamically C q -stable network is, in general, not C q -stable in a static model. Dynamic C q -stability requires q + 2 centers that form a clique.9 If a pair of centers delete the link between them, it is profitable if c > 1 , because the delay cost per each node increases by one and c > 1 . Therefore, if c > 1 , no dynamically C q -stable network is C q -stable in a static model. This disparity mainly comes from our assumption that c is sunk. Once a link is formed in a previous period, it is never severed in our dynamic model, even if it may become redundant by subsequently formed links. Thus, the resulting dynamically C q -stable network may not be C q -stable in a static sense because such a link may not be formed in a static model. To elaborate, note that all nodes must have at least q + 1 degrees in a q-connected network (see Lemma 2 of Jun and Kim [1]). In our dynamic model, q + 2 centers form q + 1 links with all the other center nodes and then the ( q + 3 ) -th node form links with q + 1 center nodes. Let i 1 be the remaining center node; i.e., i 1 ( q + 3 ) g q + 3 . Similarly, if ( q + 4 ) -th node forms links with center nodes except node i 2 ( i 1 ) , it is dynamically C q -stable. It is, however, not statically C q -stable, because two other center nodes i 3 , i 4 for i 3 , i 4 i 1 , i 2 could benefit from severing their direct link if c > 1 , while the remaining graph is still q-connected, although severing the link is not permissible in the dynamic model in which the linking cost is sunk.
Clearly, there is a coordination problem,10 because no player would want to be a hub if hubs are more likely to be attacked.11 In our dynamic model, however, such a coordination problem is easily resolved by seniority. The most senior players must form the hubs to maintain q-connectivity. In this sense, the possibility of external attacks gives seniors a disadvantage to becoming a hub.

5. Conclusions

In this paper, we characterized the C -stable network and the C q -stable network in a dynamic model in which players enter the population sequentially. We believe that it is worthwhile to examine how robust our characterization is to variations of the model. We look forward to more enriched models in this direction.

Author Contributions

Formal analysis, T.J. and J.-Y.K.; writing–original draft preparation, J.-Y.K.; writing–review and editing, J.-Y.K. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Proofs

Proof of Lemma 1.
(i) If t is odd, a t + 1 = ( t 1 ) 2 4 = b t . If t is even, a t + 1 = ( t + 1 1 ) ( t + 1 3 ) 4 = t ( t 2 ) 4 = b t . (ii) and (iii) are clear from (i). □
Proof of Lemma 2.
We have
Δ T k = T k ( g ¯ t ) T k ( g ¯ t + k t ) = T 1 ( g ¯ t k + 1 ) T 1 ( g ¯ t k + 1 + 1 ( t k + 1 ) ) ,
by relabeling k , , t to 1 , , t k + 1 , where g ¯ t = g t 1 + ( t 1 ) t = { 12 , 23 , , ( t 1 ) t } , for any k = 2 , 3 , , t 1 . Since g ¯ t + 1 t is a circle with t nodes for any t, this is strictly increasing in t k + 1 (circle size), so it is strictly decreasing in k. □
Proof of Lemma 3.
Consider the incentive of node 1 to link with node t. If he does not link, neither does node k ( t 2 ) by Lemma 2. Thus, node t 1 must link with node t since g t C . In this case, g t is a line such that g t = { 12 , 23 , , ( t 1 ) t } , and node 1 becomes the extreme node of the line network. On the other hand, if node 1 links with node t, node t 1 will link with node t, too, because node t 1 would otherwise become an extreme node of a line network g t = { t 1 , 12 , , ( t 2 ) ( t 1 ) } . Therefore, if node 1 prefers a circle to a line (with himself being an extreme node of the line), node t 1 also prefers a circle to a line in which he is one of the extreme nodes. This implies that node t 1 prefers to link with node t, whenever node 1 prefers to link with node t. □
Proof of Lemma 4.
Since c > a t , we have c > a k for any k = 3 , , t 1 by Lemma 1. This implies that node 1 has no incentive to link with the entrant k for k = 3 , , t 1 . Then, by Lemma 2, node j has no incentive to link with the entrant t 1 for any j = 3 , , t 3 , either. Thus, connectivity requires node t 2 to link with node t 1 . (I.e., node t 2 has an incentive to link with node t 1 , considering w i ( g ) = if g is not connected). This implies that the resulting network g t 1 is a line. □
Proof of Proposition 1.
It is trivial that the complete graph is the only dynamically C -stable network if c < 1 . For c > 1 , suppose c I t ¯ ( c ) ( a t ¯ , b t ¯ ) . Then, it is clear from Lemma 1 that a t < c , t < t ¯ ( c ) .
(i) We will show that for any t < t ¯ ( c ) , no node k ( < t 1 ) has an incentive to form a link with a new entrant t. By Lemma 4, g t 1 is a line. Now, since c > a t , node 1 has no incentive to link with node t. Then, by Lemma 2, node k for k = 2 , , t 2 will not link with node t, implying that node t 1 must link with node t due to the requirement of connectivity. Therefore, g t is a line for any t < t ¯ ( c ) .
(ii) We will show that g t ¯ ( c ) is a circle. Since c I t ¯ ( c ) , c < b t . This implies that node 1 has an incentive to link with node t. Note that node 2 has no incentive to link with node t, because T 2 ( g ¯ t ) T 2 ( g ¯ t + 2 t ) = T 1 ( g ¯ t 1 ) T 1 ( g ¯ t 1 + 1 ( t 1 ) ) = a t 1 < c . Moreover, by Lemma 4, no node k = 3 , , t 2 has an incentive to link with node t. The incentive of node t 1 to link with node t is identical with node 1’s incentive. Additionally, the incentive of node t to connect two links instead of one link is exactly identical with the incentives of node 1 and node t 1 . Thus, ( t 1 ) t g t . Therefore, g t is a circle.
(iii) Since both b t increases in t and lim t b t = , for any c < , there exists t ¯ ( c ) < such that c I t ¯ ( c ) ; i.e., g t ¯ is a circle and g t is a line for any t < t ¯ . □
Proof of Proposition 2.
(i) It is trivial that the complete graph is the only C q -stable network if c < 1 .
(ii) It is clear that g t is a complete graph for any t q . (If i j g t , deleting ( t 2 ) nodes except i and j would make it disconnected. Thus, g t C q .)
(iii) We can show that g t is a complete graph for t = q + 1 , q + 2 . If t 0 t g t for t = q + 1 or q + 2 and for some t 0 q , deleting all other nodes than node t 0 and node t would make the graph disconnected.
(iv) If t > q + 2 , we will first show that g t C q . Let T = { 1 , 2 , , t } , H = { 1 , 2 , , q + 2 } and J = { q + 3 , , t } . We may call i H an insider and j J an outsider. Let S be any subset of T with | S | = q . We will denote the graph obtained by deleting all the nodes in S from g t by g t ( T \ S ) . Now, if S H , two nodes will remain in hub H. Let the nodes be i and i . Then, i i g t ( T \ S ) because i i g t ( T ) and i , i S . Since any outsider j has ( q + 1 ) links with insiders, i j g t ( T ) or i j g t . If i j g t ( T ) and i j g t ( T ) for any j , j J , it implies that i j , i j g t ( T ) , so there is a path between j and j , j i i j in g t ( T S ) . If i j , i j g t ( T ) for the same i, there is a path between j and j , j i j in g t ( T S ) . If j S or j , j S , it is trivial that g t C q .
(v) It remains to show that g t is C q -stable. First, any outsider j J would not connect more than q + 1 nodes with insiders from the assumption that c > 1 , since additional link will reduce delay cost by one. Second, any outsider could not have less than q + 1 nodes with insiders. If i j , i j g t ( T ) for some j J , choose S = H \ { i , i } . Then, there is no path between i and j in g t ( T \ S ) , i.e., g t C q . Therefore, in a C q -stable network, any outsider j J must have exactly q + 1 links with nodes in H. □

Appendix B. Optimal Deferral Algorithm

Lemma A1.
For given t, if c I t , a necessary condition for g t to be C -stable is that d ( i , j ; g t ) < t 1 for all i , j t .
Proof. 
Suppose that d ( i , j ; g t ) k ( t 1 ) for some i , j t . Let the shortest path between them be { i 0 , i 1 , i 2 , , i k } with i 0 i and i k j . We can relabel i 0 , , i k by 1 , 2 , · , k + 1 . Since c I t = ( a t , b t ] and t k + 1 , we have c < a k + 1 by Lemma 1. This implies that one extreme node 1 (or node i) has an incentive to link with the other extreme node k + 1 (or node j) directly or indirectly via a more junior node. Thus, it must be that d ( i , j ; g t ) < k . This is a contradiction. □
Optimal Deferral Algorithm:
If c I t for some t, g t is a circle, while g k is a line for any k t 1 by Proposition 1. Now, the following steps will generate g l for any l > t .
  • Step 1:
In period l, link players l and l 1 and let g l 0 = g l 1 + l ( l 1 ) . Define S 1 l = { i < l 1 d ( i , l ; g l 0 ) t 1 } . If S 1 l = , define g l = g l 0 . If S 1 l , let i 1 * = sup S 1 l and define g l = g l 0 + i 1 * l .
  • Step 2:
For j 1 , let S j + 1 l = { i S j l \ { i 1 * } d ( i , l ; g l j ) t 1 } . If S j + 1 l = , g l = g l j . If S j + 1 l , let i j + 1 * = sup S j + 1 l and define g l j + 1 = g l j + i j + 1 * l .
  • Step 3:
Repeat step 1 and step 2 until S j * l = . Define g l = g l j * .
We will sketch the proof of why the network that is obtained by the optimal deferring algorithm is dynamic C -stable.
Start from period t such that g t is a circle, i.e., c I t . In step 1, for l = t + 1 , S 1 t + 1 is the set of nodes i such that the (shortest) distance from t + 1 in g t + 1 0 is not less than t 1 . If S 1 t + 1 = , i.e., d ( i , t + 1 ; g t + 1 0 ) < t 1 for all i t , g t + 1 need not have other link than t ( t + 1 ) , because c I t . So, g t + 1 = g t + t ( t + 1 ) is C -stable. If S 1 t + 1 , the nodes i S 1 t + 1 needs an additional link to maintain d ( i , t + 1 ) < t 1 by Lemma 4. By the senior advantage, the most junior, i.e., i 1 * = sup S 1 t + 1 takes the role of linking with t + 1 . We denote the resulting network by g t + 1 1 = g t + 1 0 + i 1 * ( t + 1 ) .
Now, it is still possible that d ( i , t + 1 ; g t + 1 1 ) t 1 for some i. It is the reason why we need step 2. In step 2, define S 2 t + 1 = S 1 t + 1 \ { i 1 * } by the set of nodes i in S 1 t + 1 \ { i 1 * } such that the shortest distance from t + 1 in g t + 1 1 is not less than t 1 . If S 2 t + 1 , take i 2 * = sup S 2 t + 1 again by the senior advantage and link i 2 * to t + 1 . We define the resulting network by g t + 1 2 = g t + 1 1 + i 2 * ( t + 1 ) .
We repeat this process for any j > 2 and for any l > t + 1 , until S j l = . If we define j * by j such that S j l = , it is clear that g l = g l j * is C -stable.

References

  1. Jun, T.; Kim, J.-Y. Connectivity, Stability and Efficiency in a Network as Information Flow. Math. Soc. Sci. 2007, 53, 314–331. [Google Scholar] [CrossRef]
  2. Jackson, M.; Wolinsky, A. A Strategic Model of Social and Economic Networks. J. Econ. Theory 1996, 71, 44–74. [Google Scholar] [CrossRef]
  3. Goyal, S.; Vigier, A. Attack, defence, and contagion in networks. Rev. Econ. Stud. 2014, 81, 1518–1542. [Google Scholar] [CrossRef]
  4. Dziubiźski, M.; Goyal, S. Network design and defence. Games Econ. Behav. 2013, 79, 30–43. [Google Scholar] [CrossRef] [Green Version]
  5. Hoyer, B.; De Jaegher, K. Strategic Network Disruption and Defense. J. Pub. Econ. Theory 2016, 18, 802–830. [Google Scholar] [CrossRef] [Green Version]
  6. Haller, H.; Hoyer, B. The common enemy effect under strategic network formation and disruption. J. Econ. Behav. Org. 2019, 162, 146–163. [Google Scholar] [CrossRef]
  7. Fabrikant, A.; Luthra, A.; Maneva, E.N.; Papadimitriou, C.H.; Shenker, S. On a network creation game. In Proceedings of the twenty-second annual symposium on Principles of distributed computing (PODC), Boston, MA, USA, 13–16 July 2003; pp. 347–351. [Google Scholar] [CrossRef]
  8. Leme, R.P.; Syrgkanis, V.; Tardos, É. The curse of simultaneity. In Proceedings of the 3rd Innovations in Theoretical Computer Science ConferenceJanuary (ITCS), Cambridge, MA, USA, 8–10 January 2012; pp. 60–67. [Google Scholar] [CrossRef]
  9. Watts, A. A Dynamic Model of Network Formation. Games Econ. Behav. 2001, 34, 331–341. [Google Scholar] [CrossRef] [Green Version]
  10. Jackson, M.; Watts, A. The Evolution of Social and Economic Networks. J. Econ. Theory 2002, 106, 265–295. [Google Scholar] [CrossRef] [Green Version]
  11. Chwe, M. Farsighted Coalitional Stability. J. Econ. Theory 1994, 63, 299–325. [Google Scholar] [CrossRef]
  12. Page, F., Jr.; Wooders, M.; Kamat, S. Network and Farsighted Stability. J. Econ. Theory 2005, 120, 257–269. [Google Scholar] [CrossRef] [Green Version]
1
In this paper, we use the terms “graph” and “network” interchangeably.
2
By deletion of a node, we mean that all the incident links to the node are deleted together.
3
Since he is the most senior in the society, he is entitled to move first.
4
Requiring connectivity is reasonable, especially when pieces of information possessed by each agent are complementary.
5
Severing an existing link unilaterally does not occur in C -stable networks due to the assumption of sunk linking costs.
6
For a formal proof, see Lemma 3.
7
The insight of the deferral principle is similar to the principle of last clear chance in law. In tort law, if several legal parties are jointly responsible for an accident but a second mover could have avoided the accident, the second mover tends to be placed in a disadvantageous position by the contributory negligence rule. It is referred to as the doctrine of last clear chance. In our model, all the players are jointly responsible for network disconnection. In this case, the last mover bears the burden of connecting with the entrant.
8
In the static model of Jun and Kim [1] in which the number of players is fixed, it is natural to adopt the interpretation that nodes naturally die with some exogenous probability, but in this dynamic model, it is less natural because an exogenously fixed probability of death must imply that q increases as the population size grows. Thus, in this paper, we adopt the interpretation of node destruction as a result of an enemy’s attack. An exogenous q in this dynamic model can be justified by the implicit assumption that the enemy’s ability to attack is limited only to q nodes.
9
A clique is defined by a maximal complete subgraph of a given graph.
10
Even without possibility of attacks, a coordination problem occurs in a static network formation model. See Jun and Kim [1].
11
Since we do not assume a strategic enemy, there is no reason for a hub node to be more likely to be attacked in our model.
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Jun, T.; Kim, J.-Y. A Note on Connectivity and Stability in Dynamic Network Formation. Games 2020, 11, 49. https://0-doi-org.brum.beds.ac.uk/10.3390/g11040049

AMA Style

Jun T, Kim J-Y. A Note on Connectivity and Stability in Dynamic Network Formation. Games. 2020; 11(4):49. https://0-doi-org.brum.beds.ac.uk/10.3390/g11040049

Chicago/Turabian Style

Jun, Tackseung, and Jeong-Yoo Kim. 2020. "A Note on Connectivity and Stability in Dynamic Network Formation" Games 11, no. 4: 49. https://0-doi-org.brum.beds.ac.uk/10.3390/g11040049

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop