A unifying model of strategic network formation

Abstract

We provide a model that merges two basic models of strategic network formation and incorporates them as extreme cases: Jackson and Wolinsky’s connections model based on bilateral formation of links, and Bala and Goyal’s two-way flow model, where links can be unilaterally formed. In our model a link can be created unilaterally, but when it is only supported by one of the two players the flow through it suffers some friction or decay, but more than when it is supported by both players. When the friction in singly-supported links is maximal (i.e. there is no flow) we have Jackson and Wolinsky’s connections model, while when flow in singly-supported links is as good as in doubly-supported links we have Bala and Goyal’s two-way flow model. In this setting, a joint generalization of the results relative to efficiency and stability in both seminal papers is achieved, and the robustness in both models is tested with positive results.

1 Introduction

The importance of the role played by the network structures underlying social and economic phenomena is now widely recognized.¹ From a theoretical point of view, perhaps the most challenging issue is the formation of network structures. There are two main models of strategic network formation in economic literature: that of Jackson and Wolinsky (1996), where a link between two “players” (individuals, firms, towns, etc.) needs the support of both and forms only if both agree, and that of Bala and Goyal (2000a), where players can form links unilaterally. Jackson and Wolinsky’s model has two variants: the connections model and the coauthors model. Bala and Goyal’s model also has two versions: the one-way flow model, in which flow through a link runs toward a player only if he/she supports it, and the two-way flow model, in which flow runs in both directions through all links.

These seminal models have had a great impact on the literature, and are at the root of several extensions resulting from introducing different variations into one model or the other. This paper addresses a different goal: the unification of the two models by eliminating the dichotomy of unilateral versus bilateral formation of links. This is achieved by a model that bridges the gap between the two basic models of strategic network formation. More precisely, we provide a model which has Jackson and Wolinsky’s connections model and Bala and Goyal’s two-way flow model as extreme cases.² In the model introduced here a link can be created unilaterally and flow occurs in both directions with some degree of decay, the same in both directions. However, when a link is only supported by one of the two players (such a link is referred to as a “weak” link) the flow through it suffers a greater decay than when it is supported by both players (a “strong” link). That is, strong links work better than weak links, which may be a reasonable assumption in some contexts.³ $^{,}$ ⁴ When the decay in weak links is maximal (i.e. there is no flow) we have Jackson and Wolinsky’s connections model, where only strong links work, whereas when flow in weak links is as good as in strong links we have Bala and Goyal’s two-way flow model, where strong links are inefficient and unstable. In contrast to these two extreme cases, it seems reasonable to consider intermediate situations where both types of link work, but strong doubly-supported links work better than weak singly-supported ones. This joint generalization of both seminal models, besides providing a richer setting, allows for a study of the transition from one to the other, thus providing a “neighborhood” of each model which offers a point of view for testing the robustness of the results for each of the extreme cases.

We first provide a characterization of efficient architectures which smoothly extends the results relative to efficiency in the seminal papers (Prop. 1 in Jackson and Wolinsky 1996, and Prop. 5.5 in Bala and Goyal 2000a). As it turns out, in spite of the richer variety of feasible structures in this model, possibly combining weak and strong links (which complicates considerably the proofs), only the efficient structures in either model, i.e. the complete network of strong links, the complete network of weak links, the all-encompassing star of strong links or that of weak links, and the empty network, are efficient in this more general setting. No mixed structure is efficient for any value of the parameters.

As both a strictly noncooperative point of view and one allowing for pairwise agreements make sense in this joint generalization, we study the model in the crossfire of both approaches. Thus we study Nash, strict Nash and pairwise Nash stability. The notion of pairwise stability needs to be adapted for this more general model, where an individual’s potential actions include creating weak links or even making a preexisting weak link strong by making it double. The strongest natural adaptation of this notion consistent with this situation consists of refining Nash stability by also requiring stability w.r.t. pairwise coordination to form links.⁵ A study of stability from the two points of view of the efficient structures yields an incomplete characterization, which includes as particular cases the results obtained separately in either model (Prop. 2 in Jackson and Wolinsky 1996, and Prop. 5.3 in Bala and Goyal 2000a).

Thus, in both respects, i.e. efficiency and stability, transition from one model to the other turns out to be perfectly smooth, so that both models are robust and compatible from the point of view provided by this more general model.

The rest of the paper is organized as follows. Section 2 introduces notation and terminology. Section 3 presents a model that bridges the gap between the two seminal models. Section 4 addresses the question of efficiency for the intermediate model. In Sect. 5 Nash stable, Nash strictly stable and pairwise Nash stable structures are studied, and Sect. 6 summarizes the main conclusions and points out some lines of further research.

2 Preliminaries

A directed N-graph is a pair $(N,\Gamma )$, where $N=\{1,2,\ldots ,n\}$ is a finite set with $n\ge 3$ whose elements are called nodes, and $\Gamma$ is a subset of $N\times N$, whose elements are called links. A graph $\Gamma$ can be specified by a map $g:N\times N\rightarrow \{0,1\}{:}$

$$\begin{aligned} g(i,j):=\left\{ \begin{array}{l} 1,\quad \text { if }(i,j)\in \Gamma \\ 0,\quad \text { if }(i,j)\notin \Gamma . \end{array} \right. \end{aligned}$$

Then, we denote $g_{ij}:=g(i,j)$, and if $g_{ij}=1$ link (i, j) is referred to as “link ij in g”, and we write $ij\in g$. If $M\subseteq N$, $g\mid _{M\times M}$ specifies a subgraph which, abusing the notation, is denoted by $g\mid _{M}$. The empty graph is denoted by $g^{e}$ (i.e. $g_{ij}^{e}=0$, for all i, j). When both $g_{ij},g_{ji}\in g$, we say that i and j are connected by a strong link, while if only one of them is in g we say that they are connected by a weak link. If $g_{ij}=1$ in a graph g, $g-ij$ denotes the graph that results from replacing $g_{ij}=1$ by $g_{ij}=0$ in g; and if $g_{ij}=0$, $g+ij$ denotes the graph that results from replacing $g_{ij}=0$ by $g_{ij}=1$. Similarly, if $g_{ij}=g_{ji}=1$, $g-\overline{ij}=(g-ij)-ji$, and if $g_{ij}=g_{ji}=0$, $g+ \overline{ij}=(g+ij)+ji$. An isolated node in a graph g is a node that is not involved in any link, that is, a node i s.t. for all $j\ne i$ , $g_{ij}=g_{ji}=0$. A node is peripheral in a graph g if it is involved in a single link (weak or strong).

Given a graph g, a path of length k from j to i in g is a sequence of $k+1$ distinct nodes where j is the first, i the last one, and every two consecutive nodes are connected by a link. The distance between two nodes i, j, denoted by d(i, j; g), is the length of the shortest path connecting them. When there is no path connecting two nodes the distance between them is said to be $\infty$. A graph g is acyclic or contains no cycles if there are no two nodes connected by a link which are also connected by a path of length 2 or more. Given a graph g, and $K\subseteq N$, the subgraph $g\mid _{K}$ is said to be a weak (strong) component of g if for any two nodes $i,j\in K$ there is a path (of strong links) from j to i in g, and no subset of N strictly containing K meets this condition. When a component in either sense consists of a single node we say that it is a trivial component. The size of a component is the number of nodes from which it is formed. Based on these definitions we have two different notions of connectedness. We say that a graph g is weakly (strongly) connected if g is the unique weak (strong) component of g. Note that strong connectedness implies weak connectedness. A weak (strong) component $g\mid _{K}$ of a graph g is minimal if for all $i,j\in K$ s.t. $g_{ij}=1$, the number of weak (strong) components of g is smaller than the number of weak (strong) components of $g-ij$. When g is clear from the context, we refer to a component $g\mid _{K}$ as component K.

A graph is minimally weakly (strongly) connected if it is weakly (strongly) connected and minimal. In both cases, a minimally connected graph is a tree (of weak links in one case, of strong links in the other), but, in principle, any node in such trees can be seen as the root, i.e. a reference node from which there is a unique path connecting it with any other. Note that a weakly connected graph with no cycles is a tree in general formed by weak and strong links, and in general neither minimally weakly nor strongly connected.

The graph architectures explained hereafter play a role in what follows. A line is a graph consisting of a sequence of distinct nodes connected by links where no other links exist. A star (all-encompassing star) is a graph where one node is involved in links with some (all) other players, and no other links exist. A mixed star is a star formed by weak links and strong links. A wheel consists of a sequence of nodes connected by links in which the first and the last in that sequence are also linked, and no other links exist. A complete (weak-complete, strong-complete) graph is one where any two nodes are involved in a link (weak link, strong link).

3 The model

We consider situations where individuals may initiate or support links with other individuals under certain assumptions, thus creating a network formalized as a graph. We assume that at each node $i\in N$ there is an agent identified by label i and referred to as player ⁶ i. Each player i may invest in links with other players.⁷ A map $g_{i}:N\backslash \{i\}\rightarrow \{0,1\}$ describes the links in which player i invests. We write $g_{ij}:=g_{i}(j),$ and $g_{ij}=1$ ($g_{ij}=0$) means that i invests (does not invest) in a link with j. Thus, vector $g_{i}=(g_{ij})_{j\in N\backslash \{i\}}\in \{0,1\}^{N\backslash \{i\}}$ specifies the links in which i invests and is referred to as a strategy of player i. $G_{i}:=\{0,1\}^{N\backslash \{i\}}$ denotes the set of i’s strategies and $G_{N}=G_{1}\times G_{2}\times \cdots \times G_{n}$ the set of strategy profiles. A strategy profile $g\in G_{N}$ univocally determines a graph of links invested in. Given a strategy profile $g\in G_{N}$ and $i\in N$, $g_{-i}$ denotes the $N\backslash \{i\}$ strategy profile that results by eliminating $g_{i}$ in g, i.e. all links in which player i invests,⁸ and $(g_{-i},g_{i}^{\prime })$ , where $g_{i}^{\prime }\in G_{i}$, denotes the strategy profile that results from replacing $g_{i}$ by $g_{i}^{\prime }$ in g.

Let g be a strategy profile representing the links invested in by each player. The following is generally assumed:

• 1. Investment by player i in a link with any other player entails a cost $c>0$.

• 2. The player at node j has a particular type of information or other good⁹ of value v for any other player (w.l.o.g. we assume $v=1$).

• 3. The payoff of a player i is given by a function

  $$\begin{aligned} \Pi _{i}(g)=I_{i}(g^{*})-c_{i}(g), \end{aligned}$$

  (1)

where $I_{i}(g^{*})$ is the information received by i through the actual network $g^{*}$ under strategy profile g, and $c_{i}(g)=cn^{d}(i;g)$ the cost incurred by i, where $n^{d}(i;g)$ denotes the number of nodes in which i invests.

Under different assumptions, different models specify $g\mapsto g^{*}$ and $I_{i}$ differently. In all cases a game in strategic form is specified: $(G_{N},\{\Pi _{i}\}_{i\in N})$. In Jackson and Wolinsky (1996) only doubly supported links actually form, while in Bala and Goyal (2000a) links are created unilaterally.¹⁰ In both models the information flow through a link suffers some degree of decay, with $\delta$ ($0<\delta <1$) being the fraction of the value of information at one node that reaches another node through a link.¹¹ Thus, for the right instantiation of $g^{*}$, in both cases we have:

$$\begin{aligned} I_{i}(g^{*})=\sum _{j\in N(i;g)}\delta ^{d(i,j;g^{*})}. \end{aligned}$$

(2)

where N(i; g) denotes the set of nodes connected with i by a path.

In both Jackson and Wolinsky’s (1996) connections model and Bala and Goyal’s (2000a) two-way flow model with decay, the flow is assumed to be homogeneous (i.e. the same through all actual links). In order to bridge the gap between these two models, making a transition from one to the other possible, we introduce a very simple form of endogenous heterogeneity¹² relative to the level of decay. We consider a model where information flows through all links with some degree of decay, the same in both directions, but friction is smaller through strong links.

More precisely, let $\delta$ ($0\le \delta \le 1$) be the fraction of the value of information at one node that reaches another node through a strong link, and let $\alpha$ ($0\le \alpha \le \delta \le 1$) be the fraction of the value of information at one node that reaches another node through a weak link. For a graph g representing a strategy profile and a pair of nodes $i\ne j$, let $\mathcal {P}_{ij}(g)$ denote the set of paths in g from i to j. For $p\in \mathcal {P}_{ij}(g)$, let $\mathcal {\ell }(p)$ denote the length of p and $\omega (p)$ the number of weak links in p. Then i values information originating from j that arrives via p by

$$\begin{aligned} I_{ij}(p)=\delta ^{\mathcal {\ell }(p)-\omega (p)}\alpha ^{\omega (p)}. \end{aligned}$$

If information is routed via the best possible route from j to i, then i’s valuation of information originating from j is

$$\begin{aligned} I_{ij}(g)=\max _{p\in \mathcal {P}_{ij}(g)}I_{ij}(p) \end{aligned}$$

and i’s overall benefit from g (ignoring costs) is

$$\begin{aligned} I_{i}(g)=\sum _{j\in N(i;g)}I_{ij}(g). \end{aligned}$$

Thus (1) becomes (note that in this model the actual network and the strategy profile are the same, i.e. $g^{*}=g$)¹³:

$$\begin{aligned} \Pi _{i}(g)=I_{i}(g)-c_{i}(g)=\sum _{j\in N(i;g)}\max _{p\in \mathcal {P} _{ij}(g)}\delta ^{\mathcal {\ell }(p)-\omega (p)}\alpha ^{\omega (p)}-cn^{d}(i,g) \end{aligned}$$

(3)

Observe that:

$\bullet$ $0=\alpha<\delta <1$ yields Jackson and Wolinsky’s original connections model: information flows only through links in which both players invest.

$\bullet$ $0<\alpha =\delta <1$ yields Bala and Goyal’s two-way flow model with decay: information flows in both directions with the same decay through weak and strong links.

Thus, the intermediate situations, i.e. $0\le \alpha \le \delta <1$ yield a bridge-model between Jackson and Wolinsky’s original connections model ($\alpha =0$) and Bala and Goyal’s two-way flow connections model with decay ($\alpha =\delta$).

We first address the question of efficiency and then that of stability.

4 Efficiency

A network is said to be efficient for a particular configuration of values of the parameters if it maximizes the aggregate payoff, referred to as the value of the network. When the value of network g, denoted by $v\left( g\right)$, is greater than or equal to that of network $g^{\prime }$ we say that g dominates $g^{\prime }$. Both Jackson and Wolinsky (1996) and Bala and Goyal (2000a) provide a characterization of efficient networks in their settings. The statements are adapted to the terminology used here.

Jackson and Wolinsky (1996, Prop. 1): In Jackson and Wolinsky’s connections model, the only efficient networks are : 

• (i) The strong-complete graph if $c<\delta -\delta ^{2}$ (Region I in Fig. 1).

• (ii) All-encompassing stars of strong links if $\delta -\delta ^{2}<c<\delta +\left( n-2\right) \delta ^{2}/2$ (Region II in Fig. 1).

• (iii) The empty network if $\delta +\left( n-2\right) \delta ^{2}/2<c$ (Region III in Fig. 1).

Figure 1 shows the regions where these architectures are efficient. The cost, c, is represented on the vertical axis, and the fraction of the unit of information at one node that reaches another one through a link, $\delta$, on the horizontal axis. In order to keep the different regions of values of the parameters bounded, only the part of the picture for $c\le 1$ is represented in the figures, although no upper bound is imposed on c.

Fig. 1

Efficiency: $\alpha =0$ (Jackson and Wolinsky), $n=20$

Bala and Goyal (2000a, Prop. 5.5): In Bala and Goyal’s two-way flow model with decay, the only efficient networks are : 

• (i) The weak-complete graph if $c<2\left( \delta -\delta ^{2}\right)$ (Region I’ in Fig. 2).

• (ii) All-encompassing stars of weak links if $2\left( \delta -\delta ^{2}\right)<c<2\delta +\left( n-2\right) \delta ^{2}$(Region II’ in Fig. 2).

• (iii) The empty network if $2\delta +\left( n-2\right) \delta ^{2}<c$ (Region III’ in Fig. 2).

Fig. 2

Efficiency: $\alpha =\delta$ (Bala and Goyal), $n=20$

As we presently show, the only efficient architectures in our setting are, depending on the values of the parameters ($\alpha$, $\delta$, c and n ): the strong-complete, the weak-complete, the star of strong links, the star of weak links and the empty network. But in order to have a complete characterization, the region where each of them is efficient must be determined. This is established in Proposition 1, where only the region where the strong-complete network is efficient, and part of the region where the weak-complete network is efficient are directly established (the proof is in the Appendix). The rest is the result of several lemmas presented and proved in the Appendix, which in a patchwork-like way cover the whole region where the parameters vary. In spite of the complexity of this piecewise study, the strategy of the proof is easy to understand. The basic idea is, as in the seminal papers, to compare the value of an arbitrary component with that of certain “dominant” structures. Nevertheless, the possibility of weak and strong links makes this comparison more complicated. In different regions of values of the parameters, it is proved that a component of a network is dominated by a star with the same number of nodes (Lemmas 1, 2, 3 and 4). Then it is shown that a mixed star is dominated by a star with the same number of links (either all strong or all weak) (Lemma 5). To conclude the proof, a region containing the boundary between the regions where the star of strong links and the weak-complete graph are (later proved to be) efficient remains to be studied. This requires the use of different dominant structures, namely, two interesting sorts of “hybrid” structure (Fig. 12) between a star of strong links and a weak-complete network (Lemma 6). Finally, such hybrid structures are proved to be dominated in that region either by a weak-complete network or by a star of strong links with the same number of nodes (Lemma 7).

The following result, pulling together the partial results established in these lemmas, characterizes efficient architectures for the transitional model. The main conclusion is that the same structures which are efficient in the two seminal models (and only them) continue to be efficient in this richer model. The ‘competition’ of five different structures causes a relative complexity of the boundaries of the regions of values of the parameters where each of them ‘beats’ the others. In particular, a four-piece curve separates the regions where the efficient structures consist of strong links and that where they consist of weak links.

Fig. 3

Efficiency: $\alpha =0.2,$ $n=20$

Fig. 4

Efficiency: $\alpha =0.6,$ $n=20$

Fig. 5

Efficiency: $\alpha =0.2,$ $n=10$

Proposition 1

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$, then the unique efficient profile is:

• (i) The strong-complete graph if $c<\min \{\delta -\delta ^{2},2\left( \delta -\alpha \right) \}$ (Region I in Figs. 3, 4, 5).

• (ii) The weak-complete graph if

  $$\begin{aligned} 2\left( \delta -\alpha \right)<c<2\left( \alpha -\alpha ^{2}\right) \end{aligned}$$

  and $c\left( n-4\right) <2n\alpha -4\delta -2\left( n-2\right) \delta ^{2}$ (Region I’ in Figs. 3, 4 and 5).

• (iii) All-encompassing stars of strong links if

  $$\begin{aligned} \delta -\delta ^{2}<c<\min \{2\left( \delta -\alpha \right) +\left( n-2\right) \left( \delta ^{2}-\alpha ^{2}\right) ,\delta +\left( n-2\right) \delta ^{2}/2\}. \end{aligned}$$

  and $c\left( n-4\right) >2n\alpha -4\delta -2\left( n-2\right) \delta ^{2}$ (Region II in Figs. 3, 4 and 5).

• (iv) All-encompassing stars of weak links if

  $$\begin{aligned} \max \{2\left( \delta -\alpha \right) +\left( n-2\right) \left( \delta ^{2}-\alpha ^{2}\right) ,2\left( \alpha -\alpha ^{2}\right) \}<c<2\alpha +\left( n-2\right) \alpha ^{2} \end{aligned}$$

  (Region II’ in Figs. 3, 4 and 5).

• (v) The empty network if

  $$\begin{aligned} c>\max \{2\alpha +\left( n-2\right) \alpha ^{2},\delta +\left( n-2\right) \delta ^{2}/2\} \end{aligned}$$

  (Region III in Fig. 5).

Comments

• (i) Figures 3, 4 and 5 summarize Proposition 1. The images correspond to the cases $\alpha =0.2$ and $\alpha =0.6,$ with $n=20$ and $n=10$. Note that, as $0\le \alpha \le \delta <1$, only the part where $0.2\le \delta <1$ in Figs. 3 and 5 ($0.6\le \delta <1$ in Fig. 4) is meaningful. The strong-complete network is the only efficient graph in Region I: below the straight line $c=2\left( \delta -\alpha \right)$ and the parabola $c=\delta -\delta ^{2}$. The only efficient networks in Region I’ are weak-complete: above the line $c=2\left( \delta -\alpha \right)$, and below the horizontal line $c=2\left( \alpha -\alpha ^{2}\right)$ and the curve $c\left( n-4\right) =2n\alpha -4\delta -2\left( n-2\right) \delta ^{2}$ (a parabola). All-encompassing stars of strong links are the only efficient graphs in Region II: above the last parabola and $c=\delta -\delta ^{2}$, and below two parabolas: $c=2\left( \delta -\alpha \right) +\left( n-2\right) \left( \delta ^{2}-\alpha ^{2}\right)$ and $c=\delta +\left( n-2\right) \delta ^{2}/2$ (the part of the boundary corresponding to the latter is only visible in Fig. 5 since only the part of the pictures for $c\le 1$ is represented in the figures). All-encompassing stars of weak links are the only efficient graphs in Region II’: above the horizontal line $c=2\left( \alpha -\alpha ^{2}\right)$ and the parabola $c=2\left( \delta -\alpha \right) +\left( n-2\right) \left( \delta ^{2}-\alpha ^{2}\right)$, and below the horizontal line $c=2\alpha +\left( n-2\right) \alpha ^{2}$ (the part of the boundary corresponding to the latter is only visible in Fig. 5). Finally, in Region III the only efficient graph is the empty network: above $c=2\alpha +\left( n-2\right) \alpha ^{2}$ and $c=\delta +\left( n-2\right) \delta ^{2}/2$ (only visible in Fig. 5).

• (ii) All inequalities in Proposition 1 are strict to preserve uniqueness, but on the boundaries separating any two regions both structures are efficient.

• (iii) Observe that as $\alpha$ decreases towards 0 the image of these regions approaches the “map” in Fig. 1, corresponding to Prop. 1 in Jackson and Wolinsky (1996), namely Regions I and II in Figs. 3, 4 and 5 expand towards Regions I and II in Fig. 1, while regions where “weak” structures are efficient shrink and finally collapse when $\alpha =0$. In fact, Proposition 1 applied to case $\alpha =0$ yields Prop. 1 in Jackson and Wolinsky (1996). That is, setting $\alpha =0$ in (i), (iii) and (v) in Proposition 1, yields (i), (ii) and (iii) in Prop. 1 in Jackson and Wolinsky, respectively.

• (iv) As $\alpha$ “moves rightward”, ranging from 0 to 1, the vertical line $\delta =\alpha$ is Bala and Goyal’s two-way flow model, with $\delta =\alpha$ being the fraction of a unit of information at one node that reaches another one through a link. Thus, as this line sweeps the rectangle, the boundary points separating Regions I’, II’ and III on the vertical line $\delta =\alpha$, follow the curves $c=2\left( \alpha -\alpha ^{2}\right)$, and $c=2\alpha +(n-2)\alpha ^{2}$, which depict Fig. 2 exactly. In fact, Proposition 1 applied to case $\alpha =\delta$ yields Prop. 5.5 of Bala and Goyal (2000a). That is, setting $\alpha =\delta$ in (ii), (iv) and (v) in Proposition 1, yields (i), (ii) and (iii) in Prop. 5.5, respectively.

5 Stability

From a conceptual point of view, the first interesting issue raised by this “intermediate” model is how to adapt the different notions of stability used in each of the two benchmark models to this “mixed” situation. In Bala and Goyal’s purely noncooperative model Nash and strict Nash equilibrium are the natural stability notions. In Jackson and Wolinsky’s model, stability analysis is based on the notion of “pairwise” stability. In this transitional model a noncooperative approach based on Nash and strict Nash equilibrium makes sense, but adapting the pairwise stability notion (Jackson and Wolinsky 1996) is more delicate. The concept introduced by Jackson and Wolinsky, in a context where only strong links make sense and actually form, consists of two requirements: (i) no player gains by severing a link (“link deletion proofness”); and (ii) no two players who are not linked have an incentive to create a strong link (“link addition proofness”). Part (i) is the stability requirement for the only noncooperative dimension of Jackson and Wolinsky’s model, but in the current transitional model individual players have other options, given that weak links can be created unilaterally, and so can strong links by making double an existing weak link. A possibility here is to require stability w.r.t. both pairwise coordinated link-formation and all unilateral changes of strategy. This amounts to pairwise Nash stability, which refines Nash stability notion.¹⁴ A weaker notion of stability can be obtained by limiting the admissible unilateral moves.¹⁵ Nevertheless, all the stability results established here hold for the stronger notion of pairwise Nash stability due to the great degree of symmetry of all the efficient structures whose stability is studied.

Thus we consider the following three forms of stability.

Definition 1

A strategy profile g is:

• (i) A Nash equilibrium if $\Pi _{i}(g_{-i},g_{i}^{\prime })\le \Pi _{i}(g),$ for all i and all $g_{i}^{\prime }\in G_{i}.$

• (ii) A strict Nash equilibrium if $\Pi _{i}(g_{-i},g_{i}^{\prime })<\Pi _{i}(g),$ for all i and all $g_{i}^{\prime }\in G_{i}$ $(g_{i}^{\prime }\ne g_{i}).$

• (iii) Pairwise Nash stable if it is Nash stable and for all i, j $(i\ne j),$ if $g_{ij}=g_{ji}=0$ and $\Pi _{i}(g+\overline{ij})>\Pi _{i}(g),$ then $\Pi _{j}(g+\overline{ij})<\Pi _{j}(g)$.

We now study the stability of the efficient structures established in Proposition 1. Pairwise stable architectures are not characterized in Jackson and Wolinsky (1996), and nor are Nash stable networks in Bala and Goyal (2000a). The following results relative to pairwise stability in Jackson and Wolinsky’s connections model and to Nash and strict Nash architectures in Bala and Goyal’s two-way flow model with decay are proved in those seminal papers. Their statements are adapted to the terminology used here. In Jackson and Wolinsky’s model all links are strong, while in Bala and Goyal’s all links are weak, but who supports them may affect the stability of an architecture (the same occurs in our model). A center-sponsored (periphery-sponsored, mixed-sponsored) star is a star of weak links where the center supports all links (no link, some but not all links).

Jackson and Wolinsky (1996, Prop. 2): In Jackson and Wolinsky’s connections model:

• (i) A pairwise stable network has at most one nontrivial strong component.

• (ii) If $0<c<\delta -\delta ^{2}$ , then the unique pairwise stable network is the strong-complete graph (Region I in Fig. 6).

• (iii) If $\delta -\delta ^{2}<c<\delta$ , then an all-encompassing star of strong links is pairwise stable (Region II in Fig. 6), but not necessarily the unique pairwise stable graph (e.g. if $n=4$ and $\delta -\delta ^{3}<c<\delta$ a line of strong links is also stable, and if $c<\delta -\delta ^{3}$ , then a wheel of strong links is also pairwise stable).

• (iv) If $\delta <c$, then in a nonempty pairwise stable network no player is peripheral (Region III in Fig. 6).

Fig. 6

Pairwise stability: $\alpha =0$ (Jackson and Wolinsky)

Bala and Goyal (2000a, Prop. 5.3): In Bala and Goyal’s two-way flow model with decay : 

• (i) A strict Nash network is either weakly connected or empty.

• (ii) If $0<c<\delta -\delta ^{2}$ , then the unique strict Nash network is the weak-complete graph (Region I’ in Fig. 7).

• (iii) If $\delta -\delta ^{2}<c<\delta$ , then all-encompassing stars of weak links are strict Nash (Region II’ in Fig. 7).

• (iv) If $\delta<c<\delta +(n-2)\delta ^{2}$ , then all-encompassing periphery-sponsored stars, and only them among all-encompassing stars, are strict Nash (Region III’ in Fig. 7).

• (v) If $\delta <c$ , then the empty network is strict Nash (Region IV’ in Fig. 7).

Fig. 7

Strict Nash stability: $\alpha = \delta$ (Bala and Goyal), $n=20$

In contrast with the seminal models, in which each requires a different notion of stability, in the transitional model both a strictly noncooperative approach and one allowing for pairwise agreements make sense, so the question of stability is addressed from both points of view. As pairwise Nash stability refines Nash stability, we deal with the latter first. The following two propositions establish the transition between the preceding results. Proposition 2 deals with Nash stability and Proposition 3 with pairwise Nash stability.

The following proposition addresses Nash stability, establishing the range of values of the parameters for which each of the efficient structures characterized in Proposition 1 is a Nash network for the transitional model.

Proposition 2

If the payoff function is given by (3) with $0\le \alpha \le \delta <1,$ we have:

• (i) A Nash network is either weakly connected or all its components are strongly connected.

• (ii) If $0<c\le \min \{\delta -\delta ^{2},\delta -\alpha \}$ then the strong-complete network is Nash stable (strict Nash if the inequalities hold strictly) (Region I in Figs. 8, 9).

• (iii) If $\delta -\alpha \le c\le \alpha -\alpha ^{2}$ and $\delta \le 2\alpha /\left( 1+\alpha \right)$ then weak-complete networks are Nash (strict Nash if the inequalities hold strictly) (Region I’ in Figs. 8, 9).

• (iv) If $\alpha -\delta ^{2}\le c\le \delta -\alpha$, then all-encompassing stars of strong links are Nash stable (strict Nash if the inequalities hold strictly) (Region II in Figs. 8, 9).

• (v) If $c\ge \delta -\alpha$, and $\alpha -\alpha ^{2}\le c\le \alpha +(n-2)\alpha ^{2}$, then all-encompassing periphery-sponsored stars are Nash stable (strict Nash if the inequalities hold strictly) (Regions II’ and III’ in Figs. 8, 9).

• (vi) If $\max \{(\delta -\alpha )(1+(n-2)\alpha ),\alpha -\alpha ^{2}\}\le c\le \alpha$, then all-encompassing stars of weak links (periphery-sponsored, center-sponsored or mixed-sponsored) are Nash stable (strict Nash if the inequalities hold strictly) (Region II’ in Figs. 8, 9).

• (vii) If $c>\delta -\alpha$, then in a Nash stable network a peripheral player cannot be connected by a strong link. If $c>\alpha$, then in a Nash stable network a peripheral player cannot be sponsored by a weak link. If $c\ge \alpha$, then the empty network is Nash stable (strict Nash if the inequality holds strictly).

Fig. 8

Nash stability: $\alpha =0.2,$ $n=20$

Fig. 9

Nash stability: $\alpha =0.6,$ $n=20$

Comments

• (i) Figures 8 and 9 summarize Proposition 2 for $n=20,$ and $\alpha =0.2$ and $\alpha =0.6$, respectively. The strong-complete network is Nash stable in Region I: below the line $c=\delta -\alpha$ and the parabola $c=\delta -\delta ^{2}$. This region overlaps with the region where all-encompassing stars of strong links are Nash, namely Region II: below the line $c=\delta -\alpha$ and above the parabola $c=\alpha -\delta ^{2}$. The weak-complete networks are Nash in Region I’: above the line $c=\delta -\alpha$, and below $c=\alpha -\alpha ^{2}$, and to the left of the vertical line $\delta =2\alpha /\left( 1+\alpha \right)$. Periphery-sponsored stars are Nash in Regions II’ and III’: above lines $c=\delta -\alpha$ and $c=\alpha -\alpha ^{2}$, and below the horizontal line $c=\alpha +(n-2)\alpha ^{2}$ (only visible in Fig. 8). Finally, other stars of weak links, i.e. center-sponsored and mixed-sponsored stars, are Nash in a relatively small subset of this region, namely in Region II’: between the horizontal lines $c=\alpha$ and $c=\alpha -\alpha ^{2}$ and above $c=(\delta -\alpha )(1+(n-2)\alpha )$.

• (ii) As $\alpha$ “moves rightward”, ranging from 0 to 1,  the vertical line $\delta =\alpha$ is Bala and Goyal’s two-way flow model with $\delta =\alpha$ being the fraction of the unit of information at one node that reaches another one through a link. Thus, as this line sweeps the rectangle, the boundary points of Regions I’, II’ and III’ on the vertical line $\delta =\alpha$, follow the curves $c=\alpha$, $c=\alpha -\alpha ^{2}$, and $c=\alpha +(n-2)\alpha ^{2}$, which depict Fig. 7 exactly. In fact, Proposition 2 applied to case $\alpha =\delta$ yields Proposition 5.3 of Bala and Goyal (2000a). That is, setting $\alpha =\delta$ in (i), (iii), (v) and (vi) in Proposition 2, yields (i), (ii), (iii) and (iv) in Prop. 5.3, respectively.

• (iii) Above the line $c=\delta -\alpha ^{2}$ all Nash structures considered are formed exclusively by weak links, while below this line they consist of strong links only.

• (iv) The architectures studied in Proposition 2 are not the only ones which are Nash stable as the following example shows.

Example

If $n=4$, in addition to the structures whose Nash stability is established in Proposition 2, the following structures are also Nash stable: A wheel of strong links is Nash stable if $\alpha -\delta ^{2}\le c\le \delta -\alpha$; a line of strong links if $\alpha -\delta ^{3}\le c\le \delta -\alpha$; a wheel of weak links if $\delta -\alpha ^{2}<c<\alpha -\alpha ^{3}$ and $\delta <\alpha \left( 2+\alpha \right) /\left( 1+\alpha +\alpha ^{2}\right)$ (this last condition only applies if it is possible for a node to switch its support from one weak link to double another existing weak one); a line of weak links whose peripheral nodes are sponsored if $\max \{\alpha -\alpha ^{3},\delta +\delta \alpha +\delta \alpha ^{2}-\alpha -\alpha ^{2}-\alpha ^{3}\}\le c\le \alpha$. Moreover, for $n=4$ this provides a complete characterization of Nash stable structures, which at the same time shows the non-existence of Nash stable structures for certain values of the parameters.

The following proposition summarizes a similar study for pairwise Nash stability.

Proposition 3

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$, we have:

• (i) A pairwise Nash stable network has at most one non-trivial weak component (which is strong if $\alpha =0)$, and has at most one non-trivial strong component.

• (ii) If $0<c<\min \{\delta -\delta ^{2},\delta -\alpha \}$, then the strong-complete graph is the unique pairwise Nash stable network (Region I in Figs. 10, 11).

• (iii) If $\delta -\alpha<c<\alpha -\alpha ^{2}$ and $\delta <2\alpha /\left( 1+\alpha \right)$, then weak-complete graphs are the unique pairwise Nash stable networks (Region I’ in Figs. 10, 11).

• (iv) If $\delta -\delta ^{2}<c<\delta -\alpha$, then all-encompassing stars of strong links are pairwise Nash stable (Region II in Figs. 10, 11).

• (v) If $\delta -\alpha ^{2}<c<\alpha +(n-2)\alpha ^{2}$, then all-encompassing periphery-sponsored stars of weak links are pairwise Nash stable (Regions II’ and III’ in Figs. 10, 11).

• (vi) If $\max \{(\delta -\alpha )(1+(n-2)\alpha ),\delta -\alpha ^{2}\}<c<\alpha$, then all-encompassing stars of weak links (periphery-sponsored, center-sponsored or mixed-sponsored) are pairwise Nash stable (Region II’ in Figs. 10, 11).

• (vii) If $c>\delta -\alpha$, then in a pairwise Nash stable network a peripheral player cannot be connected by a strong link. If $c>\alpha$, then in a pairwise Nash stable network a peripheral player cannot be sponsored by a weak link. If $c>\delta$, then the empty network is pairwise Nash stable.

Fig. 10

Pairwise Nash stability: $\alpha =0.2,$ $n=20$

Comments

• (i) Figures 10 and 11 summarize Proposition 3 for $n=20$, and $\alpha =0.2$ and $\alpha =0.6$, respectively, depicting the regions where the different architectures are pairwise Nash stable. The strong-complete network is the only pairwise Nash stable architecture in Region I (the same region where they are Nash stable): below the line $c=\delta -\alpha$ and the parabola $c=\delta -\delta ^{2}$. The weak-complete networks are the only pairwise Nash stable architectures in Region I’: above the line $c=\delta -\alpha$, below $c=\alpha -\alpha ^{2}$, and to the left of the vertical line $\delta =2\alpha /\left( 1+\alpha \right)$. All-encompassing stars of strong links are pairwise Nash stable in Region II: below the line $c=\delta -\alpha$ and above the parabola $c=\delta -\delta ^{2}$. Periphery-sponsored stars are pairwise Nash stable in Regions II’ and III’: above the line $\delta =\delta -\alpha ^{2}$ and below the horizontal line $c=\alpha +(n-2)\alpha ^{2}$ (note that this last constraint is only visible in Fig. 10 because for $\alpha =0.6$ this upper bound is greater than 1). Other stars of weak links, i.e. center-sponsored and mixed-sponsored stars, are pairwise Nash stable in a relatively small subset of this region, namely in Region II’: below $c=\alpha$, above the lines $c=\delta -\alpha ^{2}$ and $c=(\delta -\alpha )(1+(n-2)\alpha )$.

• (ii) Observe that as $\alpha$ decreases towards 0 the image of these regions approaches the “map” of Fig. 6, corresponding to Prop. 2 of Jackson and Wolinsky (1996), namely Regions I and II in Figs. 10 and 11 expand approaching Regions I and II in Fig. 6, while regions where “weak” structures are pairwise Nash stable shrink and finally collapse when $\alpha =0$. In fact, Proposition 3 applied to case $\alpha =0$ yields Prop. 2 of Jackson and Wolinsky. That is, by setting $\alpha =0$ in (i), (ii), (iv) and (vii) in Proposition 3, yields (i), (ii), (iii) and (iv) in Prop. 2 of Jackson and Wolinsky (1996), respectively.

• (iii) A comparison with the results for Nash stability (Proposition 2) shows the following. The region where the strong-complete network is stable in either sense is the same, and the same goes for weak-complete networks (Regions I and I’ in Figs. 8, 9, 10 and 11). The reason is clear: in complete structures pairwise coordination does not actually provide new options in this model. However these regions are different for stars of strong links and stars of weak links (periphery-sponsored or not). In both cases the region where such structures are pairwise Nash stable is a subset of the region where they are Nash stable, due to the possibility of pairwise coordination to form new strong links, which destabilizes some Nash stable networks. But note that if attention is constrained to Bala and Goyal’s setting, i.e. to the line where $\alpha =\delta$, weak-complete networks, stars of weak links and periphery-sponsored stars of weak links are stable in either sense in the same regions.

• (iv) The architectures studied in Proposition 3 are not the only ones which are pairwise Nash stable as the following example shows.

Example

If $n=4$ the following structures are pairwise Nash stable: Any wheel of strong links if $\delta -\delta ^{2}<c<\delta -\alpha$ ; a line of strong links if $\delta -\delta ^{3}<c<\delta -\alpha$; any wheel of weak links if $\delta -\alpha ^{2}<c<\alpha -\alpha ^{3}$ and $\delta <\alpha \left( 2+\alpha \right) /\left( 1+\alpha +\alpha ^{2}\right)$ (this last condition only applies if it is possible for a node to switch its support from one weak link to making double another existing weak link); a line of weak links whose peripheral nodes are sponsored if $\delta +\delta \alpha -\alpha ^{2}-\alpha ^{3}<c<\alpha$ and $\delta <\alpha \left( 2+\alpha \right) /\left( 1+\alpha \right)$. For $n=4$ this is a complete characterization of pairwise Nash stable structures, which also shows the non-existence of pairwise Nash stable structures for certain values of the parameters.

(iv) Note that, as with Nash stability, above the line $c=\delta -\alpha ^{2}$ all pairwise Nash stable structures considered are formed exclusively by weak links, while below line $c=\delta -\alpha$ they consist of strong links. Therefore, as soon as $\alpha >0$ a gap opens between lines $c=\delta -\alpha$ and $c=\delta -\alpha ^{2}$. The following corollary, whose proof is in the Appendix, emerges relative to this gap:

Corollary 1

If the payoff function is given by (3) with $0\le \alpha \le \delta <1,$ $\delta -\alpha<c<\delta -\alpha ^{2}$, and $\alpha <c$, a non-empty pairwise Nash stable network necessarily contains cycles.

Fig. 11

Pairwise Nash stability: $\alpha =0.6,$ $n=20$

6 Concluding remarks

This paper introduces a model which bridges the gap between the two basic models of strategic network formation and incorporates them as extreme cases: Jackson and Wolinsky’s (1996) bilateral connections model and Bala and Goyal’s (2000a) unilateral connections two-way flow model. This richer hybrid model provides a common setting and makes it possible to transition from one to the other. The point of view provided by this continuum of models, bridging the gap between the two seminal models, shows the perfect compatibility and robustness of both in the sense that the transition from one to the other is smooth in all respects.

The efficient architectures are fully-characterized for all possible values of the parameters and the results relative to efficiency in both seminal papers extended. One noteworthy result is that only the structures which are efficient in the seminal models emerge as efficient in this transitional model.

The strictly noncooperative approach and the approach based on pairwise stability both make sense and are applied in this setting. Jackson and Wolinsky’s (1996) pairwise stability results for their connections model and the noncooperative stability results of Bala and Goyal (2000a) for their two-way flow model are extended to this more general model. However, as is the case for the seminal models, no characterization of stable structures has been obtained. Moreover, the question of existence of stable structures containing both strong and weak links remains open.

For none of the five efficient structures do the region where each one is efficient and the region where it is Nash or pairwise Nash stable coincide. Those with strong links (strong-complete and all-encompassing stars of strong links) are pairwise Nash stable only within a subset of the region where they are efficient. For instance, compare region II in Figs. 10 and 11, where all-encompassing stars of strong links are pairwise Nash stable, with the wider region II in Figs. 3 and 4, where they are efficient.¹⁶ As to efficient structures formed by weak links, the regions where they are efficient and those where they are Nash or pairwise Nash stable are different. In the case of non periphery-sponsored stars of weak links, the intersection of these regions is empty for certain values of the parameters.

The model introduced here can be extended in several directions. The assumption that the cost of a strong link exactly doubles that of a weak link is made in order to achieve the transition between the two seminal models by making coordination for the formation of strong links unnecessary. A more general model would assume the existence of links of different strengths, i.e. “conductivity”, and different costs. Other variations worth exploring would be studying the impact of “liberalizing” the cost sharing of strong links or limiting the number of links of different types that a node can support. In general, any extension of the benchmark models in the literature can also be tested in this mixed model. Also a similar transitional model between Jackson and Wolinsky’s (1996) connections model and Bala and Goyal’s (2000a) one-way flow model with decay, or between Bala and Goyal’s one-way flow and two-way flow models with decay remains to be explored.¹⁷

Finally, still within the model studied here, it would be interesting to settle the question of the existence of stable structures containing both weak and strong links. A shorter proof of Proposition 1 would also be desirable.

Appendix

Lemma 1

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$ and $c>\max \{\delta -\delta ^{2},2\left( \alpha -\delta ^{2}\right) \}$, then the maximal value of a weak component containing m nodes and $m-1$ or more strong links is only reached by a star with $m-1$ strong links.

Proof

Let K be a weak component containing m nodes and $k_{s}\ge m-1$ strong links and $k_{w}\ge 0$ weak links. Without loss of generality, it can be assumed that no link is superfluous. Then,

$$\begin{aligned} v(K)=k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +p(\alpha ,\delta ), \end{aligned}$$

where $p(\alpha ,\delta )$ is a polynomial on $\alpha$ and $\delta$ with integer positive coefficients (summing up to $\max \{m\left( m-1\right) -2\left( k_{s}+k_{w}\right) ,0\}$, i.e. twice the number of pairs of nodes non-directly connected) multiplying monomials of the form $\alpha ^{q}\delta ^{r}$ with $q+r\ge 2$. As $\alpha \le \delta$, the maximal value of this polynomial is obtained when $p(\alpha ,\delta )=(m\left( m-1\right) -2\left( k_{s}+k_{w}\right) )\delta ^{2}$, that is

$$\begin{aligned} v(K)\le k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +\left( m\left( m-1\right) -2\left( k_{s}+k_{w}\right) \right) \delta ^{2}, \end{aligned}$$

while the value of a star of $m-1$ strong links with m nodes is

$$\begin{aligned} v(S_{m-1,0})=\left( m-1\right) \left( 2\delta -2c\right) +\left( m-1\right) \left( m-2\right) \delta ^{2}. \end{aligned}$$

Thus, the difference is

$$\begin{aligned} v(S_{m-1,0})-v(K)\ge \left( m-1-k_{s}\right) \left( 2\delta -2c-2\delta ^{2}\right) +k_{w}\left( 2\delta ^{2}-2\alpha +c\right) \ge 0, \end{aligned}$$

given that $m-1-k_{s}\le 0$, $2\delta -2c-2\delta ^{2}<0$ and $2\delta ^{2}-2\alpha +c>0$. Moreover, it is 0 only for $k_{s}=m-1$ and $k_{w}=0$. Finally, a component with $k_{s}=m-1$ and $k_{w}=0$ is necessarily minimally strongly connected, and the maximal value of a minimally strongly connected component is only reached by stars of strong links. $\square$

In what follows a mixed star consisting of $k_{s}$ strong links and $k_{w}$ weak links is denoted by $S_{k_{s},k_{w}}$.

Lemma 2

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$ and $c>2\alpha$, then a weak component containing m nodes and fewer than $m-1$ strong links is dominated by a mixed star with the same number of strong links.

Proof

Let K be a weak component containing m nodes and $k_{s}<m-1$ strong links and $k_{w}\ge m-1-k_{s}>0$ weak links. Without loss of generality, it can be assumed that no link is superfluous. Thus, reasoning as in the preceding lemma, we have:

$$\begin{aligned} v(K)\le k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +k_{s}\left( k_{s}-1\right) \delta ^{2} \\ +k_{s}\left( m-1-k_{s}\right) 2\alpha \delta +\left( m-1-k_{s}\right) \left( m-2-k_{s}\right) \alpha ^{2}, \end{aligned}$$

while the value of a star with $k_{s}$ strong links and $m-1-k_{s}$ weak links is

$$\begin{aligned} v\left( S_{k_{s},m-1-k_{s}}\right) =k_{s}\left( 2\delta -2c\right) +\left( m-1-k_{s}\right) \left( 2\alpha -c\right) \\ +k_{s}\left( k_{s}-1\right) \delta ^{2}+k_{s}\left( m-1-k_{s}\right) 2\alpha \delta +\left( m-1-k_{s}\right) \left( m-2-k_{s}\right) \alpha ^{2}. \end{aligned}$$

Thus, the difference is

$$\begin{aligned} v\left( S_{k_{s},m-1-k_{s}}\right) -v(K)=\left( c-2\alpha \right) \left( k_{s}+k_{w}-\left( m-1\right) \right) \ge 0, \end{aligned}$$

given that $k_{s}+k_{w}\ge m-1$ and $c>2\alpha$. And it is 0 only for $k_{s}+k_{w}=m-1$. Finally, the maximal value of a component with $m-1$ links is only reached by stars. $\square$

The next lemma establishes the same result for $2\left( \alpha -\alpha ^{2}\right)<c<2\alpha$.

Lemma 3

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$ and $2\left( \alpha -\alpha ^{2}\right)<c<2\alpha$, then a weak component containing m nodes and fewer than $m-1$ strong links is dominated by a mixed star with the same number of strong links.

Proof

Let K be a weak component containing m nodes, $k_{s}<m-1$ strong links and $k_{w}\ge m-1-k_{s}>0$ weak links. Without loss of generality, it can be assumed that no link is superfluous. The maximal value of the component here requires a more detailed discussion than in the case $c>2\alpha$ addressed in the preceding lemma. Thus we have

$$\begin{aligned} v(K)\le k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +A\delta ^{2}+B\alpha \delta +C\alpha ^{2}, \end{aligned}$$

where

$$\begin{aligned} A=\min \{k_{s}(k_{s}-1),m(m-1)-2k_{s}-2k_{w}\}. \end{aligned}$$

Two cases must be considered depending on which of these numbers is smaller:

1st case: $A=m(m-1)-2k_{s}-2k_{w}.$ In this case $B=C=0$, and we have

$$\begin{aligned} v(K)\le k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +(m(m-1)-2k_{s}-2k_{w})\delta ^{2}, \end{aligned}$$

while the value of a star with $k_{s}$ strong links and $m-1-k_{s}$ weak links is

$$\begin{aligned} v\left( S_{k_{s},m-1-k_{s}}\right)= & {} k_{s}\left( 2\delta -2c\right) +\left( m-1-k_{s}\right) \left( 2\alpha -c\right) \\&+k_{s}\left( k_{s}-1\right) \delta ^{2}+k_{s}\left( m-1-k_{s}\right) 2\alpha \delta \\&+\left( m-1-k_{s}\right) \left( m-2-k_{s}\right) \alpha ^{2}. \end{aligned}$$

Thus, the difference is

$$\begin{aligned}&v\left( S_{k_{s},m-1-k_{s}}\right) \\&\quad -v(K) \ge \left( m-1-k_{s}-k_{w}\right) \left( 2\alpha -c\right) \\&\quad +(k_{s}(k_{s}-1)-m(m-1)+2k_{s}+2k_{w})\delta ^{2} \\&\quad +k_{s}\left( m-1-k_{s}\right) 2\alpha \delta +\left( m-1-k_{s}\right) \left( m-2-k_{s}\right) \alpha ^{2} \\&=a\left( 2\alpha -c\right) +b\delta ^{2}+d\alpha \delta +e\alpha ^{2}, \end{aligned}$$

where a, b, d and e denote the coefficients in the last expression. Note that $a\le 0$, while b, d and e are $\ge 0$. As $2\alpha -c<2\alpha ^{2},$ by replacing $2\alpha -c$ by $2\alpha ^{2}$ in the last expression and taking into account that $\alpha \le \delta$ we have

$$\begin{aligned} v\left( S_{k_{s},m-1-k_{s}}\right) -v(K)\ge a2\alpha ^{2}+b\delta ^{2}+d\alpha \delta +e\alpha ^{2} \\ \ge a2\alpha ^{2}+b\alpha ^{2}+d\alpha ^{2}+e\alpha ^{2}=(2a+b+d+e)\alpha ^{2} \end{aligned}$$

Therefore, if $2a+b+d+e\ge 0$ the proof is concluded in the 1st case, and summing up these coefficients we have $2a+b+d+e=0.$

2nd case: $A=k_{s}(k_{s}-1).$ In this case $k_{s}(k_{s}-1)/2$ is the maximal number of non-directly linked pairs that can receive $\delta ^{2}$ from each other. Now

$$\begin{aligned} B=\min \{2k_{s}(m-1-k_{s}),m(m-1)-2k_{s}-2k_{w}-k_{s}(k_{s}-1)\}. \end{aligned}$$

Thus, we again have two cases:

Case 2.1: $B=m(m-1)-2k_{s}-2k_{w}-k_{s}(k_{s}-1).$ In this case $C=0$, and

$$\begin{aligned} v(K)\le & {} k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +k_{s}(k_{s}-1)\delta ^{2} \\&+(m(m-1)-2k_{s}-2k_{w}-k_{s}(k_{s}-1))\alpha \delta . \end{aligned}$$

Thus, subtracting this value from that of a star with $k_{s}$ strong links and $m-1-k_{s}$ weak links the difference is

$$\begin{aligned}&v\left( S_{k_{s},m-1-k_{s}}\right) -v(K)\ge \left( m-1-k_{s}-k_{w}\right) \left( 2\alpha -c\right) \\&\quad +(2k_{s}(m-1-k_{s})-(m(m-1)-2k_{s}-2k_{w}-k_{s}(k_{s}-1))\alpha \delta \\&\quad +\left( m-1-k_{s}\right) \left( m-2-k_{s}\right) \alpha ^{2}=a\left( 2\alpha -c\right) +b\alpha \delta +d\alpha ^{2}, \end{aligned}$$

and proceeding just as in the first case we similarly conclude that $v\left( S_{k_{s},m-1-k_{s}}\right) -v(K)\ge 0.$

Case 2.2: $B=2k_{s}(m-1-k_{s}).$ In this case

$$\begin{aligned} C=m(m-1)-2k_{s}-2k_{w}-k_{s}(k_{s}-1)-2k_{s}(m-1-k_{s}),\text { and} \end{aligned}$$

$$\begin{aligned} v\left( S_{k_{s},m-1-k_{s}}\right) -v(K)\ge \left( m-1-k_{s}-k_{w}\right) \left( 2\alpha -c\right) \\ +(k_{s}+k_{w}-\left( m-1\right) )2\alpha ^{2}=a\left( 2\alpha -c\right) +b\alpha ^{2}, \end{aligned}$$

and proceeding again as before we conclude that $v\left( S_{k_{s},m-1-k_{s}}\right) -v(K)\ge 0.$ $\square$

Lemma 4

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$, and $c<2\left( \delta -\alpha \right)$, then: (i) in a non-empty efficient network all links are strong; (ii) if in addition $c>\delta -\delta ^{2}$, then a weak component is dominated by a star of strong links.

Proof

(i) Let g be a nonempty efficient network, and assume $ij\in g$ and $ji\notin g$, then the contribution of i’s (j’s) unit of value to j’s (i’s) payoff is $\alpha$, otherwise ij would be superfluous, but then, as $c<2\left( \delta -\alpha \right)$, by making ij double the sum of the payoffs of i and j would increase, and no other player’s payoff would decrease, which contradicts g’s efficiency.

(ii) Let K be a weak component with no superfluous links. By (i), all its links must be strong. But then by Lemma 1 it is dominated by a star of strong links (note that $c>2\left( \alpha -\delta ^{2}\right)$ follows easily from $c<2\left( \delta -\alpha \right)$ and $c>\delta -\delta ^{2}$, and Lemma 1 can be applied). $\square$

Lemmas 1, 2, 3 and 4 establish that, for different configurations of values of the parameters, any component is dominated by a star, possibly mixed. The following lemma shows that mixed stars are always dominated by stars containing only one type of link.

Lemma 5

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$, a star containing both strong and weak links is strictly dominated either by a star with the same number of links all of which are strong or by a star with the same number of links all of which are weak.

Proof

Let $S_{k_{s},k_{w}}$ be a star connecting m nodes with $k_{s}>0$ strong links and $k_{w}=m-1-k_{s}>0$ weak links. Its value is given by

$$\begin{aligned} v\left( S_{k_{s},k_{w}}\right) =k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +k_{s}\left( k_{s}-1\right) \delta ^{2}+2k_{s}k_{w}\alpha \delta +k_{w}\left( k_{w}-1\right) \alpha ^{2}. \end{aligned}$$

By making double a weak link, $S_{k_{s}+1,k_{w}-1}$ results, and

$$\begin{aligned} v\left( S_{k_{s}+1,k_{w}-1}\right)= & {} \left( k_{s}+1\right) \left( 2\delta -2c\right) +\left( k_{w}-1\right) \left( 2\alpha -c\right) \\&+\left( k_{s}+1\right) k_{s}\delta ^{2}+2\left( k_{s}+1\right) \left( k_{w}-1\right) \alpha \delta +\left( k_{w}-1\right) \left( k_{w}-2\right) \alpha ^{2}. \end{aligned}$$

Thus, as $k_{w}=m-1-k_{s}$, $v\left( S_{k_{s}+1,k_{w}-1}\right) -v\left( S_{k_{s},k_{w}}\right) =$

$$\begin{aligned} \left( 2\delta -2c\right) -\left( 2\alpha -c\right) +2\left( m-2\right) \alpha \left( \delta -\alpha \right) +2k_{s}\left( \delta -\alpha \right) ^{2}. \end{aligned}$$

(4)

Note that if this number is $>0$, the greater $k_{s}$ is the greater this number will be, and consequently the value of a star of strong links connecting m nodes is greater than that of $S_{k_{s},k_{w}}$.

By making a double link weak, $S_{k_{s}-1,k_{w}+1}$ results, and

$$\begin{aligned} v\left( S_{k_{s}-1,k_{w}+1}\right)= & {} \left( k_{s}-1\right) \left( 2\delta -2c\right) +\left( k_{w}+1\right) \left( 2\alpha -c\right) \\&+\left( k_{s}-1\right) \left( k_{s}-2\right) \delta ^{2}+2\left( k_{s}-1\right) \left( k_{w}+1\right) \alpha \delta +\left( k_{w}+1\right) k_{w}\alpha ^{2}. \end{aligned}$$

Thus, as $k_{w}=m-1-k_{s}$, $v\left( S_{k_{s}-1,k_{w}+1}\right) -v\left( S_{k_{s},k_{w}}\right) =$

$$\begin{aligned} -\left( 2\delta -2c\right) +\left( 2\alpha -c\right) +2\left( \delta ^{2}-m\alpha \delta +\left( m-1\right) \alpha ^{2}\right) -2k_{s}\left( \delta -\alpha \right) ^{2}. \end{aligned}$$

(5)

If this number is $>0$, the smaller $k_{s}$ is the greater this number will be and consequently the value of a star of weak links is greater than that of $S_{k_{s},k_{w}}$.

It only remains to show that the value necessarily increases by either making a weak link double or making a strong one weak, that is, either (4) or (5) is greater than 0. Write $X=\left( 2\delta -2c\right) -\left( 2\alpha -c\right)$, $Y=2\left( m-2\right) \alpha \left( \delta -\alpha \right) +2k_{s}\left( \delta -\alpha \right) ^{2}$ and $Y^{\prime }=2\left( \delta ^{2}-m\alpha \delta +\left( m-1\right) \alpha ^{2}\right) -2k_{s}\left( \delta -\alpha \right) ^{2}$. Thus we prove that necessarily either

$$\begin{aligned} v\left( S_{k_{s}+1,k_{w}-1}\right) -v\left( S_{k_{s},k_{w}}\right) =X+Y>0\quad \text {or}\quad V\left( S_{k_{s}-1,k_{w}+1}\right) -v\left( S_{k_{s},k_{w}}\right) =-X+Y^{\prime }>0. \end{aligned}$$

Assume $X+Y\le 0$, i.e. $X\le -Y$, then we prove that $-X+Y^{\prime }>0$, i.e. $X<Y^{\prime }$. For this it suffices to show that $-Y<Y^{\prime }$, i.e. $Y+Y^{\prime }>0.$ In fact we have $Y+Y^{\prime }=2\left( \delta -\alpha \right) ^{2}>0$. $\square$

Above $c=\delta -\delta ^{2}$ and $c=2\left( \alpha -\delta ^{2}\right)$ the preceding lemmas show the domination of stars, either of weak links or of strong links, for all the configurations of values of the parameters except the region considered in the next two lemmas, where two sorts of “hybrid” structure, somewhere between stars of strong links and weak-complete (see Fig. 12),¹⁸ serve as a term of comparison.

Fig. 12

“Hybrid” structures

Lemma 6

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$ and

$$\begin{aligned} \max \{2\left( \delta -\alpha \right) ,2\left( \alpha -\delta ^{2}\right) \}<c<2\left( \alpha -\alpha ^{2}\right) \text {,} \end{aligned}$$

then a weak component containing m nodes and fewer than $m-1$ strong links is dominated by a network consisting of a star with the same number of strong links and: (i) if $c>2\left( \alpha -\alpha \delta \right)$, with the rest of the nodes along with the center of the star forming a complete subnetwork of weak links; (ii) if $c<2\left( \alpha -\alpha \delta \right)$, any other pairs, except those of peripheral nodes of the star, are connected by weak links; (iii) in particular, in both cases, if the component contains no strong links it is dominated by the weak-complete graph.

Proof

(i):

Let K be a weak component, containing m nodes, $k_{s}<m-1$ strong links and $k_{w}\ge m-1-k_{s}>0$ weak links. Without loss of generality, it can be assumed that no link is superfluous. Thus we have

$$\begin{aligned} v(K)\le k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +A\delta ^{2}+B\alpha \delta , \end{aligned}$$

where

$$\begin{aligned} A=\min \{k_{s}(k_{s}-1),m(m-1)-2k_{s}-2k_{w}\}. \end{aligned}$$

Let $g_{k_{s}}^{*}$ be a m-node network consisting of a star with $k_{s}$ strong links and the rest of the nodes along with the center of the star forming a complete subnetwork of weak links (see Fig. 12a). Then

$$\begin{aligned} v(g_{k_{s}}^{*})=k_{s}\left( 2\delta -2c\right) +k_{w}^{\prime }\left( 2\alpha -c\right) +A^{\prime }\delta ^{2}+B^{\prime }\alpha \delta , \end{aligned}$$

(6)

where

$$\begin{aligned} k_{w}^{\prime }=(m-k_{s})(m-k_{s}-1)/2\text {,\quad }A^{\prime }=k_{s}(k_{s}-1)\text {\quad and\quad }B^{\prime }=2k_{s}(m-k_{s}-1). \end{aligned}$$

(7)

Now, depending on the value of A, we have two cases: 1st case: $A=m(m-1)-2k_{s}-2k_{w}.$ In this case $B=0$ and $A\le A^{\prime }$. Then we have

$$\begin{aligned} v(g_{k_{s}}^{*})-v(K)\ge (k_{w}^{\prime }-k_{w})\left( 2\alpha -c\right) +(A^{\prime }-A)\delta ^{2}+B^{\prime }\alpha \delta . \end{aligned}$$

As $k_{w}^{\prime }+A^{\prime }/2+B^{\prime }/2=k_{w}+A/2$ and $A\le A^{\prime }$, $k_{w}^{\prime }\le k_{w}$. And as $2\alpha -c<2\alpha \delta$ and $k_{w}^{\prime }-k_{w}+B^{\prime }/2=A/2-A^{\prime }/2$, and $2\alpha \delta <2\delta ^{2}$ we have:

$$\begin{aligned} v(g_{k_{s}}^{*})-v(K)\ge (A^{\prime }-A)\delta ^{2}+(k_{w}^{\prime }-k_{w}+B^{\prime }/2)2\alpha \delta \\ \ge (k_{w}^{\prime }-k_{w}+B^{\prime }/2+A^{\prime }/2-A/2)2\alpha \delta =0. \end{aligned}$$

2nd case: $A=k_{s}(k_{s}-1).$ Then

$$\begin{aligned} B=\min \{2k_{s}(m-1-k_{s}),m(m-1)-2k_{s}-2k_{w}-k_{s}(k_{s}-1)\}. \end{aligned}$$

In both cases $B^{\prime }\ge B\ge 0$, and $k_{w}\ge k_{w}^{\prime }\ge 0$, with $k_{w}^{\prime }+B^{\prime }/2=k_{w}+B/2$. And as $c<2\left( \alpha -\alpha \delta \right)$, we have

$$\begin{aligned} v(g_{k_{s}}^{*})-v(K)\ge & {} (k_{w}^{\prime }-k_{w})\left( 2\alpha -c\right) +(B^{\prime }-B)2\alpha \delta \\\ge & {} (k_{w}^{\prime }-k_{w})(2\alpha -c-2\alpha \delta )\ge 0. \end{aligned}$$

(ii):

Let K be a weak component as in (i). Let $g_{k_{s}}^{**}$ be a m-node network consisting of a star with $k_{s}$ strong links and any other pairs of nodes, except those of peripheral nodes of the star, connected by weak links (see Fig. 12b). Thus

$$\begin{aligned} v(g_{k_{s}}^{**})=k_{s}\left( 2\delta -2c\right) +k_{w}^{\prime }\left( 2\alpha -c\right) +A^{\prime }\delta ^{2}, \end{aligned}$$

(8)

where

$$\begin{aligned} A^{\prime }=k_{s}(k_{s}-1)\text {\quad and\quad }k_{w}^{\prime }=m(m-1)/2-k_{s}-k_{s}(k_{s}-1)/2. \end{aligned}$$

(9)

Two cases must be considered depending on the value of A: 1st case: $A=m(m-1)-2k_{s}-2k_{w}.$ In this case $B=0$ and $A\le A^{\prime }$. Thus we have

$$\begin{aligned} v(K)\le k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +A\delta ^{2}, \end{aligned}$$

and consequently

$$\begin{aligned} v(g_{k_{s}}^{**})-v(K)\ge (k_{w}^{\prime }-k_{w})\left( 2\alpha -c\right) +(A^{\prime }-A)\delta ^{2}. \end{aligned}$$

As $k_{w}^{\prime }+A^{\prime }/2=k_{w}+A/2$, that is, $k_{w}^{\prime }-k_{w}=A/2-A^{\prime }/2\le 0$, and we have

$$\begin{aligned} v(g_{k_{s}}^{**})-v(K)\ge (k_{w}^{\prime }-k_{w})(2\alpha -c-2\delta ^{2})\ge 0. \end{aligned}$$

2nd case: $A=k_{s}(k_{s}-1).$ Thus

$$\begin{aligned} B=\min \{2k_{s}(m-1-k_{s}),m(m-1)-2k_{s}-2k_{w}-k_{s}(k_{s}-1)\}. \end{aligned}$$

In this case $B\ge 0$, and as $k_{w}+B/2=k_{w}^{\prime }$ and $c<2\left( \alpha -\alpha \delta \right)$, i.e. $2\alpha \delta <2\alpha -c$, we have:

$$\begin{aligned} v(K)\le & {} k_{s}\left( 2\delta -2c\right) +k_{w}\left( 2\alpha -c\right) +k_{s}(k_{s}-1)\delta ^{2}+B\alpha \delta \\\le & {} k_{s}\left( 2\delta -2c\right) +(k_{w}+B/2)\left( 2\alpha -c\right) +k_{s}(k_{s}-1)\delta ^{2}. \end{aligned}$$

Thus

$$\begin{aligned} v(g_{k_{s}}^{**})-v(K)\ge (k_{w}^{\prime }-(k_{w}+B/2))(2\alpha -c)=0. \end{aligned}$$

(iii):

Just note that in both cases, (i) and (ii), the component is assumed to have fewer than $m-1$ strong links, which includes the case of no strong links. But note that the structure proved to dominate the component, i.e. $g_{0}^{*}$ or $g_{0}^{**}$, is then a weak-complete network. $\square$

Lemma 7

If the payoff function is given by (3) with $0\le \alpha \le \delta <1$ and

$$\begin{aligned} \max \{2\left( \delta -\alpha \right) ,2\left( \alpha -\delta ^{2}\right) \}<c<2\left( \alpha -\alpha ^{2}\right) \text {,} \end{aligned}$$

then a weak component of a network is dominated either by a weak-complete subnetwork or by a star of strong links with the same number of nodes.

Proof

In view of the preceding lemma, in this region a component with no strong links is dominated by a weak-complete network with the same number of nodes. If a component with m nodes contains at least $m-1$ strong links, Lemma 1 establishes that it is dominated by a star with $m-1$ strong links. If it contains some strong links, but fewer than $m-1$, Lemma 6 shows that it is dominated by one of two types of structure with the same number $k_{s}$ of strong links, either $g_{k_{s}}^{*}$ or $g_{k_{s}}^{**}$. We now prove that such structures are dominated either by a weak-complete subnetwork or by star of strong links with the same number of nodes. Consider first the case when $c>2\left( \alpha -\alpha \delta \right)$. In this case, the dominant structure is $g_{k_{s}}^{*}$. Thus $v(g_{k_{s}}^{*})$ is given by (6), with (7). Thus, comparing this value with that of $v(g_{k_{s}+1}^{*})$ and $v(g_{k_{s}-1}^{*})$, we have

$$\begin{aligned} v(g_{k_{s}+1}^{*})-v(g_{k_{s}}^{*})= & {} X+\left( 2\alpha -c\right) -4\alpha \delta , \\ v(g_{k_{s}-1}^{*})-v(g_{k_{s}}^{*})= & {} -X+2\delta ^{2}, \end{aligned}$$

where $X=2\delta -2c-(m-k_{s})\left( 2\alpha -c\right) +k_{s}2\delta ^{2}+(m-2k_{s})2\alpha \delta .$ We prove that one of these differences is necessarily positive. Assume $-X+2\delta ^{2}\le 0,$ that is, $X\ge 2\delta ^{2}.$ Thus

$$\begin{aligned} v(g_{k_{s}+1}^{*})-v(g_{k_{s}}^{*})\ge 2\delta ^{2}+2\alpha -c-4\alpha \delta , \end{aligned}$$

which is $>0$ if $c<2\delta ^{2}+2\alpha -4\alpha \delta$. To see that this is so, note that $\alpha <\delta$, thus $(\alpha -\delta )^{2}>0$, i.e. $\alpha ^{2}+\delta ^{2}-2\alpha \delta >0.$ Then, as $c<2\alpha -2\alpha ^{2}$

$$\begin{aligned} c<2\alpha -2\alpha ^{2}<2\alpha -2(2\alpha \delta -\delta ^{2})<2\delta ^{2}+2\alpha -4\alpha \delta . \end{aligned}$$

Therefore one of the two differences must be positive. In other words $g_{k_{s}}^{*}$ is dominated either by $g_{k_{s}-1}^{*}$ or by $g_{k_{s}+1}^{*}$. This entails that $g_{k_{s}}^{*}$ is dominated by one of the extreme cases: $g_{0}^{*}$ or $g_{m}^{*}$, i.e. a m -node weak-complete network or star of strong links. $\square$

Proof of Proposition 1:

(i):

As $c<\delta$, an efficient network is non-empty, and, as $c<2\left( \delta -\alpha \right)$, by Lemma 4(i), in a non-empty efficient network all links are strong. Let g then be a network where all links are strong and assume nodes i and j are not connected. As $c<\delta -\delta ^{2}$, i.e. $\delta ^{2}<\delta -c$, both i and j improve their payoffs if the strong link $\overline{ij}$ forms, and the other players’ payoffs do not decrease. Therefore, the unique efficient network is the strong-complete one.

(ii):

Consider first the subregion where $c<2\left( \alpha -\delta ^{2}\right)$. Let g be a network where two nodes, i and j, are not directly connected. Thus i $\left( j\right)$ receives at most $\delta ^{2}$ from j’s $\left( i\text {'s}\right)$ unit of value. As $2\delta ^{2}<2\alpha -c$, the sum of the payoffs of i and j increases if a weak link between them forms, and the other players’ payoffs do not decrease. Thus, if $c<2\left( \alpha -\delta ^{2}\right)$ an efficient network must be complete. Note that $\alpha$ must be greater than $\delta ^{2}$. Now as $2\left( \delta -\alpha \right) <c$, if a strong link $\overline{ij}$ in a complete network is replaced by a weak link, then the sum of the payoffs of i and j increases, and the other players’ payoffs do not decrease. Therefore, if $2\left( \delta -\alpha \right)<c<2\left( \alpha -\delta ^{2}\right)$ then the unique efficient profile is the weak-complete graph. The rest of the region remains to be examined, i.e. where $c\ge 2\left( \alpha -\delta ^{2}\right)$. But this is a subset of the range of values of the parameters considered in Lemmas 6 and 7, where any component is dominated either by a weak-complete subnetwork or by a star of strong links with the same number of nodes. As $c<2\left( \alpha -\alpha ^{2}\right) <2\alpha$, an efficient network must be connected, therefore any network is dominated either by a weak-complete network or by an all-encompassing star of strong links. Finally, it can be checked immediately that the former dominates the latter if and only if $c\left( n-4\right) \le 2n\alpha -4\delta -2\left( n-2\right) \delta ^{2}$, strictly if the inequality is strict, while both structures are equally efficient in case of equality.

(iii):

By Lemma 1, any component with at least $m-1$ strong links is dominated by a star of strong links. It remains to be checked that this is also the case if it has fewer than $m-1$ strong links. As seen in Lemma 4, in this region, when $c<2\left( \delta -\alpha \right)$, a weak component is dominated by a star of strong links, therefore the statement is proven in this case. Now consider the case $c\ge 2\left( \delta -\alpha \right)$. If $c>2\alpha$, Lemma 2 ensures that any component is dominated by a mixed star with the same number of strong links, and by Lemma 3 the same holds if $2\left( \alpha -\alpha ^{2}\right)<c<2\alpha .$ By Lemma 5 mixed stars are dominated either by stars of weak links or by stars of strong links, so this conclusion applies to the subset of the region under consideration where $c>2\left( \alpha -\alpha ^{2}\right)$. The subset where $2\left( \delta -\alpha \right) \le c<2\left( \alpha -\alpha ^{2}\right)$ remains to be discussed, where Lemmas 6 and 7 apply and ensure that any component is dominated either by a weak-complete subnetwork or by a star of strong links with the same number of nodes. If $c<2\alpha$, an efficient network must be connected, therefore in this region any network is dominated either by a weak-complete network or by an all-encompassing star of strong links. But the latter is dominated by the former if and only if $c\left( n-4\right) \le 2n\alpha -4\delta -2\left( n-2\right) \delta ^{2}$, strictly if the inequality is strict, while both structures are equally efficient in case of equality. Now if $c\ge 2\alpha$, Lemmas 2 and 5, ensure that any component of an efficient network must be a star of either weak links or strong links. As the value of a component of an efficient network must be non-negative, it is immediate to check that the value of a star with $m_{1}+m_{2}$ nodes is greater than the sum of the values of two stars with $m_{1}$ and $m_{2}$ nodes each. In short, it is proved that throughout the region a component is dominated by a star of strong or of weak links. It then follows immediately that the former dominates the latter if and only if $c\le 2\left( \delta -\alpha \right) +\left( n-2\right) \left( \delta ^{2}-\alpha ^{2}\right)$, strictly if the inequality is strict, while both structures are equally efficient in case of equality. Thus, in the whole region the only non-empty efficient network is the all-encompassing star of strong links. Finally, the all-encompassing star of strong links yields a non-negative value if and only if $c<\delta +\left( n-2\right) \delta ^{2}/2$.

(iv):

By the same argument used in $\left( iii\right)$, Lemmas 1–5 ensure that in this region any network is dominated by an all-encompassing star of weak links or by one of strong links. As stated before, the former dominates the latter if and only if $c\ge 2\left( \delta -\alpha \right) +\left( n-2\right) \left( \delta ^{2}-\alpha ^{2}\right)$, strictly if the inequality is strict, while both structures are equally efficient in case of equality. Thus, in the whole region the only efficient non-empty network is the all-encompassing star of weak links. Finally, the all-encompassing star of weak links yields non-negative value if and only if $c<2\alpha +\left( n-2\right) \alpha ^{2}$.

(v):

This follows from the discussion in $\left( iii\right)$ and $\left( iv\right)$. $\square$

Proof of Proposition 2:

• (i) Let g be a Nash network. Assume g has more than one non-trivial weak component. If any of them is not strongly connected it contains at least one weak link, say ij, i.e. $ij\in g$ and $ji\notin g$, but then any node in a different weak component will benefit by creating a weak link with j, which contradicts that g is a Nash network.

• (ii) Let g be the strong-complete network. A player i has no incentive to withdraw support for a double link $\overline{ij}$ (or a set of them), if and only if $\delta -c$ is greater than or equal to $\alpha$ and to $\delta ^{2}$. In other words, if $\delta -c\ge \max \{\alpha ,\delta ^{2}\}$, which is equivalent to $c\le \min \{\delta -\delta ^{2},\delta -\alpha \}$. Now assume these conditions hold strictly, then the network described is strict Nash.

• (iii) Let g be a weak-complete network. For a weak link $ij\in g$, player i has no incentive to withdraw support for it if and only if $\alpha -c\ge \alpha ^{2}$. On the other hand, j has no incentive to double this link if and only if $\alpha \ge \delta -c$. Thus we have two necessary conditions for pairwise Nash stability: $\delta -\alpha \le c\le \alpha -\alpha ^{2}$. Finally, i has no incentive to switch its support from ij to another, say ik, thus making double the existing weak link ki, if and only if $2\alpha \ge \delta +\alpha \delta ,$ i.e. $\delta \le 2\alpha /\left( 1+\alpha \right) .$ Now assume all these conditions hold strictly. Then, as $c<\alpha -\alpha ^{2}<\alpha ,$ either of the two players in any pair not connected by a link would benefit by creating a weak link. Thus g must be complete, and as $c>\delta -\alpha$ no strong link can exist. Therefore g is weak-complete. Thus, if all these conditions hold (strictly) g is a Nash (strict Nash) network.

• (iv) Let g be an all-encompassing star of strong links. The center has no incentive to withdraw support for a link (or a set of them) if $\delta -c\ge \alpha$. No peripheral node is interested in forming a weak link with another (or a set of them) if $c\ge \alpha -\delta ^{2}$. If these conditions hold strictly, then g is strict Nash.

• (v) Let g be an all-encompassing periphery-sponsored star. No peripheral node has an incentive to sever its link if $\alpha +(n-2)\alpha ^{2}-c\ge 0$ . If $c\ge \delta -\alpha$, the center has no incentive to double a link (or a set of them). If $c\ge \alpha -\alpha ^{2}$ no peripheral node has an incentive to form a weak link with another (or a set of them). Therefore, if all three conditions hold (strictly) g is a Nash (strict Nash) network. In (vi) we show that for other stars to be Nash $c\le \alpha$ is required.

• (vi) Let g be an all-encompassing star. If it is center-sponsored or a mixed-sponsored star, the center has no incentive to sever a link (or a set of them) if $c\le \alpha$ (which does not apply if the star is periphery-sponsored) and no peripheral node whose link is supported by the center has an incentive to double it if $\alpha +(n-2)\alpha ^{2}\ge \delta +(n-2)\delta \alpha -c$, i.e. if $c\ge (\delta -\alpha )(1+(n-2)\alpha )$. Finally, no peripheral node is interested in forming a weak link with another (or a set of them) if $c\ge \alpha -\alpha ^{2}$. If these conditions hold strictly, then g is strict Nash.

• (vii) This is straightforward. $\square$

Proof of Proposition 3:

• (i) Let g be a pairwise Nash stable network. Assume g has more than one non-trivial weak component. Let $ij\in g$ and $kl\in g$ be two links in different weak components. If both are strong, i.e. $\overline{ij}\in g$ and $\overline{kl}\in g$, it easily follows that both j and k benefit by creating a strong link $\overline{jk}$. If $\alpha >0$ and one of them, say ij, is weak, i.e. $ji\notin g$, then k will benefit by creating a weak link with j. In both cases there is a contradiction with pairwise stability.

• (ii) By Proposition 2(ii), the strong-complete network is strict Nash under these conditions. Now assume this condition holds strictly: any two players not connected by a link must then benefit by forming a strong link, and any player benefits by making a weak link supported by another player double, so only the strong-complete network is pairwise Nash stable.

• (iii) By Proposition 2(iii), under these conditions a weak-complete network is a Nash network. Now assume all these conditions hold strictly. Then, as $c<\alpha -\alpha ^{2}<\alpha ,$ either of the two players in any pair not connected by a link would benefit by creating a weak link. Thus g must be complete, and as $c>\delta -\alpha$ no strong link can exist. Therefore g is weak-complete. Finally, $\delta <2\alpha /\left( 1+\alpha \right)$ guarantees that weak-complete networks alone are pairwise Nash stable. Note that, as it occurs with the strong-complete, pairwise coordination does not provide actual new options.

• (iv) By Proposition 2(iv), under these conditions an all-encompassing star of strong links is a Nash network. In such a star no two peripheral nodes are interested in forming a strong link if $c\ge \delta -\delta ^{2}$, which is stronger than $c\ge \alpha -\delta ^{2}$ and consequently pairwise Nash stability strictly refines Nash stability for these structures.

• (v) By Proposition 2(v), under these conditions an all-encompassing periphery-sponsored star is a Nash network. And no pair of peripheral nodes are interested in forming a strong link if $\alpha +(n-2)\alpha ^{2}-c\ge \delta +\alpha +(n-3)\alpha ^{2}-2c\ge 0$, that is, if $c\ge \delta -\alpha ^{2}$. Therefore, g is pairwise Nash stable if and only if $\delta -\alpha ^{2}\le c\le \alpha +(n-2)\alpha ^{2}$.

• (vi) By Proposition 2(vi), under these conditions an all-encompassing star of weak links is a Nash network. Note that $\delta -\alpha ^{2}\le c\le \alpha$ implies $\delta -\alpha ^{2}\le c\le \alpha +(n-2)\alpha ^{2}$, therefore, as proven in (v), an all-encompassing periphery-sponsored star is pairwise Nash stable. Now let g be an all-encompassing center-sponsored or mixed-sponsored star of weak links. Then, no pair of peripheral nodes are interested in forming a strong link (in this respect the situation is entirely similar to (v)) if $c\ge \delta -\alpha ^{2}$.

• (vii) This is straightforward. $\square$

Proof of Corollary 1:

Assume g is a pairwise Nash stable network. By Proposition 2(i), g is weakly connected. If $\delta -\alpha <c$, no peripheral player can be connected by a strong link, nor sponsored by a weak link if $\alpha <c$. Therefore a peripheral node can only be connected by a weak link supported by itself. But only one such peripheral node can exist, because if there were more, as $c<\delta -\alpha ^{2}$, it would then be profitable for any pair of them to form a strong link. Consequently, under these conditions g cannot be a weakly connected graph with no cycles. $\square$