A Note on Partner Heterogeneity and Strict Nash Networks

Banchongsan Charoensook

Keimyung University, Daegu, South Korea.

DOI: 10.4236/tel.[phone]                

Abstract

This note extends the studies on the impacts of partner heterogeneity in two-way flow Strict Nash network of (Billand et al., 2011) by allowing for the existence of small information decay. I show that the incorporation of small information decay does not change the results of this aforementioned paper: every Strict Nash network is a minimally connected Bi or branching network. Since the studies on the roles of partner heterogeneity by this aforementioned paper are limited to the assumption that link formation is unilateral, I also propose another extension that studies the roles of partner heterogeneity in a more general model of network formation proposed by (Olaizola and Valenciano, 2015), which allows link formation to be both unilateral and bilateral. I show that the inclusion of partner heterogeneity breaks away a major result in this aforementioned paper: Nash network no longer consists of at most one nontrivial strongly full subnetwork.

Keywords

Network Formation, Nash Network, Two-Way Flow Network, Agent Heterogeneity, Efficient Network

1. Introduction

Social networks influence social and economic activities because they diffuse information related to these activities. Examples include employment through referral networks for jobs (Granovetter, 2018) and purchasing decision through interpersonal network where product information is exchanged (Katz et al., 2017). This has motivated the literature of network formation, which predicts the patterns of networks that are formed given that agents create links with one another in order to share information and other resources. A large branch of this network formation model is the two-way flow model of noncooperative network formation pioneered by (Bala and Goyal, 2000). As mentioned in (Galeotti et al., 2006), this model can be interpreted in the context of telephone calls, where a link sender unilaterally pays for the link establishment cost in order to acquire nonrival information (e.g., information related to price and quality of consumer products) owned by another agent called link receiver. Once the link is established the agent who receives the link can also acquire the information of the agent who initiates the phone call, hence the term “two-way flow”. This model is the basis that allows several researchers to study how factors such as agent heterogeneity and information decay impact the decisions of agents to form link with one another as well as the resulted shapes of equilibrium networks. For example, Billand et al. (2011) assume partner heterogeneity. That is, link formation cost and value of information are determined by the identity of link receiver¹. This form of heterogeneity has become a small branch of literature of its own, encompassing analyses pertaining to equilibrium characterization (Billand et al., 2011), existence of the equilibrium networks (Billand et al., 2012) as well as efficiency (Unlu, 2018).

In this note, I advance this branch of literature in the studies of partner heterogeneity in two-way flow model of network formation by proposing an extended model that allows for existence of small information decay as in (De Jaegher and Kamphorst, 2015). My contributions are twofold. First, it helps understand how the coexistence of partner heterogeneity and information decay impact the shapes of equilibrium networks. Typically, in the literature these two factors are studied in isolation of one another as it helps understand how the equilibrium networks are impacted by each of these factors. This raises the question of how the coexistence of both factors would impact the equilibrium networks. To my knowledge this note is the first work that seeks to answer this question by providing a detailed equilibrium characterization. Quite surprisingly, the addition of small decay assumption to the partner heterogeneity model of (Billand et al., 2011) does not change the external shapes of the equilibrium networks. However, the identities of agents located in the networks may change. In Example 1, I show that an agent who attracts other agents to form links with does not need to be an agent that incurs the lowest link formation cost as in (Billand et al., 2011). Rather, the agent who is chosen as a partner for link formation is the agent that provides an optimal tradeoff between the link formation cost borne by the link sender and the relatively low degree to which information decays, which varies according to the locations of agent in the network.

Another contribution of this note is seen in Example 2 in Discussion section, which extends the present unilateral model with partner heterogeneity by allowing for link formation to be established either unilaterally or bilaterally. My intention here is to study the roles of partner heterogeneity in a more general setting. Inspired by an innovative work of (Olaizola and Valenciano, 2015), a link that is formed unilaterally (weak link) suffers from a small decay while a link that is formed bilaterally suffers no decay (strong link). Thus, my Example 2 becomes an extension of (Olaizola and Valenciano, 2015) by incorporating partner heterogeneity. I show that an important property of Nash network in the model of (Olaizola and Valenciano, 2015), which is such that every Nash network that is minimally connected has at most one non-empty full subgraph consisting of strong links, is violated once partner heterogeneity replaces agent homogeneity. Indeed, to my knowledge this note is the first work that explores the roles of agent heterogeneity in such a general model of network formation².

This note proceeds as follows. First, I introduce the models and the definitions of Strict Nash networks and Nash networks in the next section. In the Main Result section, I provide a characterization of Strict Nash networks. Subsequently Discussion section shows an example related to (Olaizola and Valenciano, 2015) mentioned above. The last section concludes.

2. The Model

Since this note is an extension of (Billand et al., 2011), most notations will follow this aforementioned paper.

Individual’s strategy: $N=\left\{1,\cdots ,n\right\}$ is the set of all agents. Let $i\mathrm{,}j\in N$ , $i\ne j$ . $g_{i,j}=1$ if i forms a link with j or accesses j and $g_{i,j}=0$ otherwise. A collection of such decision of i is a strategy of i, which is $g_i=\left\{g_{i,j}:j\in N,j\ne i\right\}$ . Since link formation is unilateral, a strategy profile $g=\left\{g_i:i\in N\right\}$ is, equivalently, a network.

Structure of information: Let ${\bar{g}}_{i,j}=1$ if $g_{i,j}=1$ or $g_{j,i}=1$ or both, and ${\bar{g}}_{i,j}=0$ otherwise. We say that an undirected link between i and j exists if ${\bar{g}}_{i,j}=1$ . Of course, $\bar{g}=\left\{{\bar{g}}_{i,j}:i,j\in N,i\ne j\right\}$ is called an undirected network.

Value of Information and link formation cost: $V_{ij}$ represents the value of information that i receives from j if information is transmitted perfectly. A value structure is $\mathcal{V}={\left\{V_{ij}\right\}}_{ij\in N\times N}$ . If $V_{ij}=V_j$ for every $i\in N$ then $\mathcal{V}$ is said to satisfy partner heterogeneity (in information value). Similarly, $c_{ij}$ is cost that i bears if he forms a link with j and $\mathcal{C}={\left\{c_{ij}\right\}}_{ij\in N\times N,i\ne j}$ is the cost structure. If $V_{ij}=V_j$ for every $i\in N$ $\mathcal{C}$ is said to satisfy partner heterogeneity (in link formation cost). Throughout this paper, we assume that $\mathcal{V}$ and $\mathcal{C}$ satisfy partner heterogeneity.

Information transmission and decay: A chain between k and j— ${\bar{P}}_{i\mathrm{,}j}$ —is defined as a sequence of agents $j_0\mathrm{,}{j}_1\mathrm{,}\cdots \mathrm{,}{j}_m$ such that $j_0=j,j_m=k$ and ${\bar{g}}_{j_l,j_{l+1}}=1$ for $l=0,\cdots ,m-1$ . A path from k to j— $P_{i\mathrm{,}j}$ —is defined likewise except that $g_{j_l,j_{l+1}}=1$ instead of ${\bar{g}}_{j_l,j_{l+1}}=1$ . If a chain between i and j exists, we sat that i observes j and vice versa. In g, let $N_i\left(g\right)$ be the set of agents that i observes including i himself³. In the paper of (Billand et al., 2011) information transmission is perfect so that if there is a chain between i and j then i receives $V_{ij}$ and j receives $V_{ji}$ . This note extends this aforementioned paper by assuming that information transmission is not perfect. This imperfect transmission is represented by the decay factor $\sigma \in \left(\mathrm{0,1}\right]$ . Consider two ij-chains, ${\bar{P}}^1{}_{i\mathrm{,}j}$ and ${\bar{P}}^2{}_{i\mathrm{,}j}$ . ${\bar{P}}^1{}_{i\mathrm{,}j}$ is said to be shorter than ${\bar{P}}^2{}_{i\mathrm{,}j}$ if $\left|{\bar{P}}^1{}_{i,j}\left(g\right)\right|<\left|{\bar{P}}^2{}_{i,j}\left(g\right)\right|$ . The distance between i and j, $d\left(i\mathrm{,}j\mathrm{<mo>\; ;\; </mo>}g\right)$ , is defined as the amount of links in the shortest ij-chain. Similar to (De Jaegher and Kamphorst, 2015) an ex-post information value that i receives from j is ${\sigma }^{d\left(i\mathrm{,}j\mathrm{<mo>\; ;\; </mo>}g\right)}{V}_{ij}$ .

Small Decay Assumption: Since an ex-post information value that i receives from j is ${\sigma }^{d\left(i\mathrm{,}j\mathrm{<mo>\; ;\; </mo>}g\right)}{V}_{ij}$ , by reducing the distance ${\sigma }^{d\left(i\mathrm{,}j\mathrm{<mo>\; ;\; </mo>}g\right)}$ an agent i can improve the benefits that he receives from j. To reduce the distance, i can do so by forming a link with an agent that would create a new ij-chain that is shorter than the preexisting ones. However, if information decay is sufficiently low, i.e., $\sigma$ is sufficiently close to 1, then such an incentive disappears since the benefits from so doing cannot cover the cost c borned by i. This assumption is assumed throughout the paper of (De Jaegher and Kamphorst, 2015) and will be used throughout this note.

Network properties: A network $g^{\prime }$ is a subnetwork of g if $g^{\prime }\subset g$ . Let $N\left(g^{\prime }\right)$ denotes the set of all agents in $g^{\prime }$ . Let $g-ij$ be defined as g with the modification that $g_{ij}=0$ and $g-\bar{i}j$ be defined as g with the modification that $g_{ij}=g_{ji}=0$ . A network is minimal if there is at most one chain between any pair of agents. A network is connected if there is at least one chain between any pair of agents. A component of a network is a maximal connected subnetwork. A component is empty if it contains only one agent. In a network g, the information that i receives is $I_i\left(g\right)={\displaystyle {\sum }_{j\in N\left(g\right)\backslash \left\{i\right\}}}{\sigma }^{d\left(i,j;g^{\prime }\right)}{V}_{i,j}$ . Suppose that g is minimally connected. Given that $g_{ij}=1$ let $A_{ij}\left(g\right)$ be a subnetwork consisting of links of all agents that i is able to obtain information by accessing j. Let $j^{\prime }\mathrm{,}{k}^{\prime }\in N\left(A_{ij}\right)$ , $j^{\prime }$ is said to be better-informed than $k^{\prime }$ if $I_{j^{\prime }}\left(A_{ij}\right)\ge I_{k^{\prime }}\left(A_{ij}\right)$ . $j^{\prime }$ is best-informed in $A_{ij}$ if $I_{j^{\prime }}\left(A_{ij}\right)\ge I_{k^{\prime }}\left(A_{ij}\right)$ for every $k^{\prime }\in N\left(A_{ij}\right)$ ⁴.

$B_i$ and Branching Networks: Let $R_i\left(g\right)$ be the set of all agents that access i and $O_i\left(g\right)$ be the set of all agents that i accesses. The following definitions of $B_i$ and Branching Networks are borrowed from (Billand et al., 2011). Consider $X\subset N$ . Let $Q_X=X\cup \left\{j^{\prime }\mathrm{<mo>\; |\; </mo>}\text{there}\text{exists}\text{a}\text{path}\text{from}{j}^{\prime }toj\text{for}\text{ever}yj\in X\right\}$ . If X is a set that is minimal with respect to the property that $Q_X=N$ , then X is said to be a contrabasis of N. A contrabasis is an i-point contrabasis if there exists $i\in N$ such that every $j\in X$ , $j\ne i$ , accesses i. If i is a point contrabasis of g and $\left|R_i\right|\ge 2$ but $\left|R_j\right|<2$ for all $j\ne i$ and $j\in N$ , g is said to be a $B_i$ network. Observe that if a minimally connected $B_i$ , then i is a unique multi-link recipient and any link that does not involve i points away from i. A network g is a branching network if there exists a unique agent i such that $\left|R_i\right|=0$ and $\left|R_j\right|\le 1$ for all $j\ne i$ .

The payoffs (as in (Billand et al., 2011)): Let $\pi \mathrm{<mo>\; :\; </mo>}{ℝ}^2\to ℝ$ be such that $\pi \left(x\mathrm{,}y\right)$ is strictly increasing in x and strictly decreasing in y. The payoff of player i is given by:

${\pi }_i\left(g\right)=\pi \left({\displaystyle \underset{j\in N_i\left(g\right)\backslash \left\{i\right\}}{\sum }}{V}_j,{\displaystyle \underset{j\in N_i\left(g\right)\backslash \left\{i\right\}}{\sum }}\right)g_{i,j}{c}_{i,j}$ (1)

Note that this payoff assumes that information transmission is perfect since the decay factor $\sigma$ is not included. A special case of this payoff is the so-called linear payoff, which is:

${\pi }_i^L\left(g\right)={\displaystyle \underset{j\in N_i\left(g\right)\backslash \left\{i\right\}}{\sum }}{V}_j-{\displaystyle \underset{j\in N_i\left(g\right)\backslash \left\{i\right\}}{\sum }}{g}_{i,j}{c}_{i,j}$ (2)

The payoffs assuming small decay (as in this current note): As an extension of (Billand et al., 2011) that incorporates small decay, the payoff in Equation (1) above becomes:

${\pi }_i\left(g\right)=\pi \left(I_i\left(g\right),{\displaystyle \underset{j\in N_i\left(g\right)\backslash \left\{i\right\}}{\sum }}\right)$ (3)

And the payoff in Equation (2) becomes:

${\pi }_i^L\left(g\right)=I_i\left(g\right)-{\displaystyle \underset{j\in N_i\left(g\right)\backslash \left\{i\right\}}{\sum }}{g}_{i,j}{c}_{i,j}$ (4)

where (recall that) $I_i\left(g\right)={\displaystyle {\sum }_{j\in N_i\left(g\right)\backslash \left\{i\right\}}}{\sigma }^{d\left(i,j;g\right)}{V}_j$ .

Nash network and strict Nash network: Let $g_{-i}$ be a strategy profile of all agents except i so that $g_i\cup g_{-i}=g$ . If ${\pi }_i\left(g_i\cup g_{-i}\right)\ge {\pi }_i\left({g^{\prime }}_i\cup g_{-i}\right)$ for every ${g^{\prime }}_i$ that is a strategy of i then $g_i$ is a best response of i. If $g_i$ is a best response of i for every $i\in N$ then g is a Nash network. If every agent’ best response is unique then g is called a Strict Nash network.

3. Main Results

My first proposition corresponds to the first part of (Billand et al., 2011). The only exception is that the proposition below allows for the existence of small decay. All proofs are relegated to the Appendix.

Proposition 1. Suppose that the payoff satisfies Equation (3), small decay is assumed, and value structure and cost structure satisfy partner heterogeneity, SNN is a minimally connected $B_i$ or branching network.

By allowing for the presence of small decay, Proposition 2 below extends the second part of Proposition 1 of (Billand et al., 2011): any minimally connected $B_i$ or branching network can be supported as SNN.

Proposition 2. Given the linear payoff (Equation (4)), any minimally connected $B_i$ or branching network can be supported as SNN by some $\sigma \mathrm{,}\mathcal{V}$ and $\mathcal{C}$ , where $\mathcal{V}$ and $\mathcal{C}$ satisfy partner heterogeneity.

A remark is worthmentiong here. While Proposition 1 and 2 above show that the inclusion of small decay does not change the external shape of SNN, identities of agents that receive link in SNN may change. Intuitively, without small decay, an agent j who receives a link from another agent i is the agent that induces the lowest link formation cost in $A_{ij}\left(g\right)$ . However, once small decay exists such is not necessarily the case. Indeed, even if j induces the highest link formation cost the fact that he possesses a higher amount of information than other agents can make him attractive as a link receiver. Example 1 below illustrates this point (Figure 1).

Example 1. Consider the minimally connected branching network rooted at i below. This network is SNN assuming that the payoff is linear (see Equation (4)), $\mathcal{C}=\left\{c_i=1,c_{j_1}=1.0197,c_{j_2}=c_{j_3}=c_{j_4}=1\right\}$ , $\mathcal{V}=\left\{V_i=V_{j_1}=V_{j_2}=V_{j_3}=V_{j_4}=1\right\}$ . Observe that $c_{j_1}>c_{j_k}$ for $k=2,3,4$ . Hence, accessing $j_1$ is not a best response of i if no decay is assumed as in (Billand et al., 2011). However, the presence of small decay $\sigma =0.99$ causes i to be better off accessing $j_1$ rather than $j_2\mathrm{,}{j}_3$ or $j_4$ . Specifically, for $\sigma =0.99$ in $A_{i{j}_1}$ we have $I_{j_1}\left(A_{i{j}_1}\right)=3.97$ , $I_{j_2}\left(A_{i{j}_1}\right)=I_{j_3}\left(A_{i{j}_1}\right)=I_{j_4}=3.9502$ . That is, $j_1$ is best-informed in $A_{i{j}_1}$ . Let $c_{j_1}=1.0197$ , $c_{j_2}=c_{j_3}=c_{j_4}=1$ . Note that while $j_1$ is relatively more costly to form a link with than $j_2\mathrm{,}{j}_3\mathrm{,}{j}_4$ , the fact that he is best informed compensate for this relatively higher cost. Specifically, $I_{j_1}\left(A_{i{j}_1}\right)-I_{j_1}\left(A_{i{j}_k}\right)=0.0198>c_{j_1}-c_{j_k}=0.0197$ for $k=2,3,4$ .

4. Discussion: On the Role of Partner Heterogeneity in a Mixed Model of Network Formation

The purpose of this section is to study the role of partner heterogeneity in a model of network formation that is more general than what is “typically” studied in the literature. Specifically, the roles of agent heterogeneity are studied by assuming either that link formation is unilateral—requiring no mutual consent as in (Bala and Goyal, 2000)—or link formation is bilateral—requiring a mutual consent as (Jackson and Wolinsky, 1996). Note that the subbranch of literature in partner heterogeneity including (Billand et al., 2011), (Billand et al., 2012), (Unlu, 2018) as well as this current note also falls in to the first branch of literature that assumes unilateral link formation. Thus far, there has been no literature that studies the role of agent heterogeneity in a more general setting that encompasses both forms of link formation.

This section intends to break this mold by making use of a mixed model of network formation pioneered by (Olaizola and Valenciano, 2015). This mixed

Figure 1. Example 1.

model assumes that a link incurs no information decay if it is formed bilaterally (both agents pay for the link formation cost, called strong link) and a link incurs a portion of information decay equal to $1-\alpha$ if it is unilaterally formed (only the link sender pays for the link formation cost, called weak link). My Proposition 3 below extends this mixed model by allowing for the presence of partner heterogeneity in $\mathcal{V}$ and $\mathcal{C}$ . It shows that a prominent property of Nash network in this mixed model, which is such that every non-empty Nash network⁵ has at most one connected full subnetwork consisting of strong links or strongly full subnetwork as defined below, disappears once partner heterogeneity is assumed⁶.

Before I proceed to Proposition 3 the following notations, borrowed with some modification from (Olaizola and Valenciano, 2015), are introduced. A link between i and j is weak if $g_{ij}=1$ but $g_{ji}=0$ or vice versa. A link between i and j is strong if $g_{ij}=1$ and $g_{ji}=1$ . We write $ij\in g$ ( $\overline{ij}\in g$ ) to denote the existence of a weak (strong) link between i and j. Note that $ij\in g$ also indicates that the link is sponsored by i. We further write $\widetilde{ij}\in g$ if $ij\in g$ or $\overline{ij}\in g$ . Let $\widetilde{ij}\in g$ then ${\tilde{A}}_{j\to i}\left(g\right)$ is defined as the subnetwork consisting of all agents whose information is sent to i via the link $\widetilde{ij}\in g$ . $I\left({\tilde{A}}_{j\to i}\left(g\right)\right)={\displaystyle {\sum }_{l\in N\left({\tilde{A}}_{j\to i}\left(g\right)\right)}}{\alpha }^{d\left(i,l;g\right)}{V}_l$ is the information that i receives from the link $\widetilde{ij}$ .

Let $C\subseteq N$ . A subnetwork ${g|}_c\subseteq g$ is said to be a subnetwork induced by C or a full subnetwork if: 1) $N\left({g|}_c\right)=C$ and 2) a link exists in ${g|}_c$ if and only if it exists in g. ${g|}_c$ is a weakly full subnetwork of g if for any two nodes $i\mathrm{,}j\in C\left(i\ne j\right)$ there is a chain between j and i in g, and no subset of N strictly containing C meets this condition. The definition of a strongly full subnetwork is defined likewise, except that every chain between j and i has to consist of strong links.

In terms of information flow, every link that is weak incurs (geometric) information decay equal to $1-\alpha$ . Every link that is strong incurs no information decay. Thus if $V_j$ is the information of j and a chain between i and j consists of k weak links, then i receives ${\alpha }^k{V}_j$ . A shortest chain between i and j is the chain that has smallest amount of weak links compared to other path between i and j. Naturally a distance between i and j is defined as amount of links of the shortest chain between i and j.

A payoff of an agent i in g is:

$U_i\left(g\right)={\displaystyle \underset{j\in N_i\left(g\right)\backslash \left\{i\right\}}{\sum }}{\alpha }^{d\left(i,j;g\right)}{V}_j-c{\mu }_i^d(\; g\; )$

where ${\mu }_i^d\left(g\right)=\left|O_i\left(g\right)\right|$ .

Proposition 3. Let $\widetilde{ij}\mathrm{,}\widetilde{ik}\mathrm{,}\widetilde{jl}\in g$ and $\widetilde{ij}=ij,\widetilde{ik}=\overline{ik},\widetilde{jl}=\overline{jl}$ . If g is Nash then:

$\left(1-\alpha \right)I\left({\tilde{A}}_{k\to i}\right)\ge c_i\ge \left(1-\alpha \right)I\left({\tilde{A}}_{j\to i}\right)$ (5)

and

$\left(1-\alpha \right)I\left({\tilde{A}}_{i\to k}\right)\ge c_k$ (6)

Moreover, there exist $\mathcal{V}$ and $\mathcal{C}$ satisfying partner heterogeneity such that g is Nash and the above two inequalities are satisfied.

Corollary 1. If $\mathcal{V}$ and $\mathcal{C}$ assume agent homogeneity, then inequalities 5 and 6 cannot be simultaneously satisfied. Consequently, a Nash network contains at most one strongly full subnetwork. On the contrary, if partner heterogeneity in $\mathcal{V}$ and $\mathcal{C}$ are assumed, there exists a Nash network that consists of more than one strongly connected full subnetwork, which in turn implies that 5 and 6 are satisfied.

The proof for this proposition and its corollary are trivial and hence omitted. Example 2 below, though, illustrates the intuition (Figure 2).

Example 2. Consider the below network, which is a line whose sequence of agents—from left to right—is $i_k\mathrm{,}{i}_i\mathrm{,}{i}_j\mathrm{,}{i}_l$ Note that this line has two non-empty strongly full subnetworks, namely $\widetilde{i_k{i}_i}$ and $\widetilde{i_j{i}_l}$ . We claim that this network is SNN for the following support: $\mathcal{V}=\left\{V_k=1.01,V_i=1.02,V_j=1.03,V_l=1.04\right\}$ , $\mathcal{C}=\left\{c_k=0.01,c_i=0.0204,c_j=0.03,c_l=0.0104\right\}$ , and $\alpha =0.99$ .

It is straightforward (yet tedious) to prove that this network is SNN by checking that the above support causes each agent’s existing strategy to give a strictly higher payoff than his every other strategies. To partially verify that this network is SNN, let us verify that 5 and 6 in Proposition X are satisfied. To do so, first observe that $c_{i_i}$ has to be sufficiently low that $i_k$ is better off accessing $i_i$ . Otherwise, the link $\overline{i_i{i}_k}$ become a weak link. This leads to:

$\left(1-\alpha \right)I\left({\tilde{A}}_{k\to i}\right)\ge c_i$ (7)

Iff:

$\left(1-\alpha \right)\left(V_2+\alpha \left(V_3+V_4\right)\right)>c_2$ (8)

On the contrary, for this network to be Nash $c_i$ is required to be sufficiently high. Otherwise, j is better of accessing i, which in turn causes the link between j and i to be strong instead of weak. This leads to:

$c_i\ge \left(1-\alpha \right)I\left({\tilde{A}}_{j\to i}\right)$ (9)

Figure 2. Example 2: a bold link is a strong link. A dotted link is a weak link such that the arrow points towards the link receiver.

Iff:

$c_i\mathrm{<mo>\; >\; </mo>}\left(1-\alpha \right)\left(V_1+V_2\right)$ (10)

Putting inequalities 8 and 10 together we have:

$\left(1-\alpha \right)\left(V_2+\alpha \left(V_3+V_4\right)\right)>c_i>\left(1-\alpha \right)\left(V_1+V_2\right)$ (11)

Observe that inequality 11 above corresponds to inequality 5 in Proposition 3.

Next, consider $c_k$ . For this network to be Nash $c_k$ has to also be sufficiently low. Otherwise, i is better off not accessing k, which in turn causes the link between i and k be weak rather than strong. This leads to:

$\left(1-\alpha \right)I\left({\tilde{A}}_{i\to k}\right)\ge c_k$ (12)

Iff:

$\left(1-\alpha \right)V_1\ge c_k$ (13)

Observe that inequality 13 above corresponds to inequality 6 in Proposition 3.

Let us partially check our $\left\{V_j\mathrm{,}{c}_j\right\}$ satisfy inequalities 11 and 13. For inequality 11:

$0.030693>0.0204>0.0203$ (14)

For inequality 13:

$0.0101>0.01$ (15)

However, if the above support $\left\{V_j\mathrm{,}{c}_j\right\}$ , which is such that the value structure and cost structure satisfy partner heterogeneity, is replaced by value and cost homogeneity as in (Olaizola and Valenciano, 2015) then this network cannot be SNN. To do so we assume $V_1=V_2=V_3=V_4=1$ and $c_1=c_2=c_3=c_4=c$ , inequality 11 becomes:

$\left(1-\alpha \right)\left(1+2\alpha \right)>c>\left(1-\alpha \right)2$ (16)

and inequality 13 becomes:

$1-\alpha >c$ (17)

which is impossible since such c cannot exist. What is the intuition? Lemma 1 of (Olaizola and Valenciano, 2015) states that as $1-\alpha >c$ then we know that even if a link provides an entry to just one agent, then it is still worth making that link strong since c is sufficiently low. Then due to homogeneity assumption we know that if this fact holds true for a link then it holds true for every link in the network, regardless of how the network appears. Of course, this line of reasoning ceases to hold once we assume partner heterogeneity, as partner heterogeneity allows the value of information and link formation cost to vary from one agent to another.

Having shown the above example, this subsection finishes with the following remark.

Remark 1. Partner heterogeneity can cause a Nash network in the general model of network formation proposed by (Olaizola and Valenciano, 2015) to have more than one non-empty strongly full subnetwork.

5. Conclusion

In this paper, I study the roles of Partner Heterogeneity in Strict Nash network by extending the work of (Billand et al., 2011). I extend this work in two ways. First, I incorporate the assumption that a small amount of information decay exists. Interestingly, the inclusion of small decay does not change the results of (Billand et al., 2011): Strict Nash network is either a minimally connected $B_i$ or branching network (See Proposition 1 and 2 in this note). A difference, though, is that an agent who is attractive as a link receiver is no longer an agent who induces the lowest link formation cost. Rather, it is an agent who provides a better tradeoff in terms of relatively low link formation cost and relatively high quantity of information. This fact is illustrated in Example 1 in this note.

Second, I study the roles of partner heterogeneity in a more general model of network formation pioneered by (Olaizola and Valenciano, 2015). This model is a “mixed” model of network formation in the sense that link formation is allowed to be both unilateral and bilateral, rather than only unilateral as assumed in (Billand et al., 2011) upon which this note is based. I show that the inclusion of partner heterogeneity in this mixed model of network formation breaks away a primary feature of SNN in this model: SNN no longer has at most non-trivial strongly full subnetwork (See the definition of strongly full subnetwork in Discussion section).

As mentioned, to the knowledge of the author this note is the first attempt in the literature to study the role of agent heterogeneity in a model of network formation that is more general than what is typically studied in the literature, which is to assume that link formation is either unilateral or bilateral. Consequently, it motivates several research questions. These are, for examples, questions on the impacts of agent heterogeneity on the characterization of equilibrium networks and efficient networks, as well as existence of tension between the two with these general frameworks of (Olaizola and Valenciano, 2015) and (Olaizola and Valenciano, 2018). These unanswered questions become further research to be explored.

Appendix

Proof of Propositions

Proof of Proposition 1. The minimality is a result of small decay assumption. For connectedness, we prove by contradiction. I divide into two cases: (i) a component, among multiple components, can be singleton and (ii) a component, among multiple components, can never be a singleton. For (i) the proof follows Lemma 5 of (De Jaegher and Kamphorst, 2015). For (ii), in an SNN g let $g^{c_1}$ and $g^{c_2}$ be two non-empty components and let i accesses $i^{\prime }$ in $g^{c_1}$ and j accesses $j^{\prime }$ in $g^{c_2}$ . Observe the fact that i chooses his unique best response means that the strategy to accessing $i^{\prime }$ to obtain information from agents $g^{c_1}$ at the cost of $c_{i^{\prime }}$ is superior to the strategy of removing the link with $i^{\prime }$ and accessing $j^{\prime }$ to obtain information from $g^{c_2}$ at the cost of $c_{j^{\prime }}$ . That is, accessing $i^{\prime }$ to receive information from $g^{c_1}-i{i}^{\prime }$ while paying $c_{i^{\prime }}$ gives $i^{\prime }$ a higher payoff than removing the link $i{i}^{\prime }$ and accessing $j^{\prime }$ to receive information from $g^{c_2}-j{j}^{\prime }$ while paying $c_{j^{\prime }}$ . Similarly, observe that j’s strategy in g is to access $j^{\prime }$ , which also means that j receives information from $g^{c_2}-j{j}^{\prime }$ while paying $c_{j^{\prime }}$ . It follows that j is better off following i’s strategy: removing his link with $j^{\prime }$ and accessing $i^{\prime }$ instead.

Next, we turn to prove that a unique non-empty component of SNN is either a minimal $B_i$ or branching. The proof here makes use of Lemma 3 and Proposition 1 of (Charoensook, 2019). To do so the following notations from (Charoensook, 2019) are introduced. In a minimally connected network g, a removal of a link ${\bar{g}}_{ij}=1$ divides g into two components—one containing i and the other one containing j. These two are denoted by $D^i\left(g-\overline{ij}\right)$ and $D^i\left(g-\overline{ij}\right)$ and called anti-viewpoint of i and viewpoint of i respectively. $D^i\left(g-\overline{ij}\right){\oplus }_{ix}{D}^j\left(g-\overline{ij}\right)$ then denotes a network such that $D^i\left(g-\overline{ij}\right)$ is jointed with $D^j\left(g-\overline{ij}\right)$ by suppposing that i accesses $x\in N\left(D^j\left(g-\overline{ij}\right)\right)$ . Next, consider two agents x and y. i is said to prefer x to y or $x{\succsim }^{i}y$ if: (i) there exists $j\in N_i\left(\bar{g}\right)$ such that $x\mathrm{,}y\in N\left(D^j\left(g-\bar{i}j\right)\right)$ and (ii) ${\pi }_i\left(D^i\left(g-\overline{ij}\right){\oplus }_{ix}{D}^j\left(g-\overline{ij}\right)\right)\ge {\pi }_i\left(D^i\left(g-\overline{ij}\right){\oplus }_{iy}{D}^j\left(g-\overline{ij}\right)\right)$ . Moreover, if the inequality above is strict, i is said to strictly prefer x to y or $x{\succ }^{i}y$ . Next, a minimal network satisfies the Partially Consistent Partner Preference (henceforth, PCPP) if, for every k-agent chain whose sequence of agents is enumerated as $i_1\mathrm{,}{i}_2\mathrm{,}\cdots \mathrm{,}{i}_{k-1}\mathrm{,}{i}_k$ with $k\ge 4$ in this network, either of the following two properties with respect to partner preference holds true: (i) $i_2{\succsim }^{i_1}{i}_{n-1}$ then $i_2{\succsim }^{i_n}{i}_{n-1}$ or (ii) $i_{n-1}{\succsim }^{i_n}{i}_2$ then $i_{n-1}{\succsim }^{i_1}{i}_2$ . Moreover, a two-way flow model is said to satisfy this PCPP condition if every minimal network satisfies the PCPP condition. Using these notations, by Lemma 3 and Proposition 1 of (Charoensook, 2019) it suffices to prove that there exists no k-agent chain $i\mathrm{,}{i}^{\prime }\mathrm{,}\cdots \mathrm{,}{j}^{\prime }\mathrm{,}j$ such that $i^{\prime }{\succsim }_i{j}^{\prime }$ but $j^{\prime }{\succsim }_j{i}^{\prime }$ where $k\ge 3$ , which we do so onwards (FigureA1).

Without loss of generality consider the network $g^1$ . In this network consider the chain $i_1\mathrm{,}{i}_2\mathrm{,}{i}_3\mathrm{,}{i}_4$ . We will show that if $i_2{\succsim }^{i_1}{i}_3$ then $i_2{\succsim }^{i_4}{i}_3$ . To do so first note that in $g^1$ $D^{i_1}\left(g_1-\overline{i_1{i}_2}\right)$ is a singleton (a component with preceisely one agent), which is agent $i_1$ . To ease the notational cumbersomeness we denote $D^i\left(g_1-\overline{ij}\right)$ by $\left[i_1\right]$ 7.

Step 1: First, note that $i_2{\succsim }^{i_1}{i}_3$ in $g_1$ if and only if:

$\pi \left(I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_2}{g}_2\right)\mathrm{,}{c}_2\right)\ge \pi \left(I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_3}{g}_2\right)\mathrm{,}{c}_3\right)$ (18)

See FigureA2 for an illustration of networks $\left[i_1\right]{\oplus }_{i_1{i}_2}{g}_2$ and $\left[i_1\right]{\oplus }_{i_1{i}_3}{g}_2$ . The above inequality leads to:

$\pi \left(I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_2}{g}_2\right)-K_1\mathrm{,}{c}_2\right)\ge \pi \left(I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_3}{g}_2\right)-K_2\mathrm{,}{c}_3\right)$

for any $0<K_1\le K_2<I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_2}{g}_2\right),I_i\left(\left[i_1\right]{\oplus }_{i_1{i}_3}{g}_2\right)$ , Now if we set $K_1={\sigma }^3$ and $K_2={\sigma }^2$ we get:

$\pi \left(I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_2}{g}^2\right)-{\sigma }^3,c_2\right)\ge \pi \left(I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_3}{g}^2\right)-{\sigma }^2,c_3\right)$

Observe that ${\sigma }^3$ is the information benefit that $i_1$ receives from $i_4$ in $I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_2}{g}^2\right)$ . Similarly, ${\sigma }^2$ is the information benefit that $i_1$ receives from $i_4$ in $I_{i_1}\left(\left[i_1\right]{\oplus }_{i_1{i}_2}{g}^3\right)$ . Thus, the above inequality assumes as if the link $\overline{i_3{i}_4}$ is removed from the networks $\left[i_1\right]{\oplus }_{i_1{i}_2}{g}^2$ and $\left[i_1\right]{\oplus }_{i_1{i}_2}{g}^3$ . This observation and the fact that $g_3=g_2-\overline{i_3{i}_4}$ allows us to restate the above inequality as:

$\pi \left(I_{i_1}\left(\left(\left[i_1\right]{\oplus }_{i_1{i}_2}{g}_3\right),c_2\right)\right)\ge \pi \left(I_i\left(\left(\left[i_1\right]{\oplus }_{i_1{i}_3}{g}_3\right),c_3\right)\right)$ (19)

See FigureA3 for an illustration of networks $\left[i_1\right]{\oplus }_{i_1{i}_2}{g}_3$ and $\left[i_1\right]{\oplus }_{i_1{i}_3}{g}_3$ . We further restate the above inequality as:

Figure A1. Networks with six agents.

Figure A2. Two networks as in Equation (18).

Figure A3. Two networks as in Equation (19).

$\pi \left(I_{i_1}+\sigma I_{i_2}\left(g_3\right)\mathrm{,}{c}_2\right)\ge \pi \left(I_{i_1}+\sigma I_{i_3}\left(g_3\right)\mathrm{,}{c}_3\right)$

iff:

$\pi \left(I_{i_2}\left(g_3\right)\mathrm{,}{c}_2\right)\ge \pi \left(I_{i_3}\left(g_3\right)\mathrm{,}{c}_3\right)$

so that

$\pi \left(I_{i_2}\left(g_3\right)+L_1\mathrm{,}{c}_2\right)\ge \pi \left(I_{i_3}\left(g_3\right)+L_2\mathrm{,}{c}_3\right)$

for any $L_1\ge L_2$ . Now set $L_1={\sigma }^1={\sigma }^{d_{i_1{i}_2}}$ and $L_2={\sigma }^2={\sigma }^{d_{i_1{i}_3}}$ we have:

$\pi \left(I_{i_2}\left(g_3\right)+{\sigma }^{d_{i_1{i}_2}},c_2\right)\ge \pi \left(I_{i_3}\left(g_3\right)+{\sigma }^{d_{i_1{i}_3}},c_3\right)$

Since $g_4=g_3+\overline{i_2{i}_1}$ we know that the above inequality can be restated as:

$\pi \left(I_{i_2}\left(g_4\right)\mathrm{,}{c}_2\right)\ge \pi \left(I_{i_3}\left(g_4\right)\mathrm{,}{c}_3\right)$

so that

$\pi \left(\sigma I_{i_2}\left(g_4\right)+X\mathrm{,}{c}_2\right)\ge \pi \left(\sigma I_{i_3}\left(g_4\right)+X\mathrm{,}{c}_3\right)$

Now set $X=I_{i_4}\left(D^{i_4}\left(g_1-\overline{i_3{i}_4}\right)\right)$ the above inequality can be restated as:

$\pi \left(\sigma I_{i_2}\left(g_4\right)+I_{i_4}\left(D^{i_4}\left(g_1-\overline{i_3{i}_4}\right)\right),c_2\right)\ge \pi \left(\sigma I_{i_3}\left(g_4\right)+I_{i_4}\left(D^{i_4}\left(g_1-\overline{i_3{i}_4}\right)\right),c_3\right)$

Finally, note that $g_4$ is nothing else but the viewpoint of $i_4$ via $i_3$ or $D^{i_3}\left(g_1-\overline{i_3{i}_4}\right)$ . Note further that $\sigma I_{i_2}\left(g_4\right)$ on the left-hand side of the inequality above is what $i_4$ receives if he establishes a link with $i_2$ in $g_4=D^{i_3}\left(g_1-\overline{i_3{i}_4}\right)$ , and $\sigma I_{i_3}\left(g_4\right)$ on the right-hand side of the inequality above is what $i_4$ receives if he establishes a link with $i_3$ in $g_4=D^{i_3}\left(g_1-\overline{i_3{i}_4}\right)$ .

Hence, we can restate the above inequality as:

$\begin{array}{l}\pi \left(I_{i_4}\left(D^{i_4}\left(g_1-\overline{i_3{i}_4}\right){\oplus }_{i_4{i}_2}{D}^{i_3}\left(g_1-\overline{i_3{i}_4}\right)\right),c_2\right)\\ \ge \pi \left(I_{i_4}\left(D^{i_4}\left(g_1-\overline{i_3{i}_4}\right){\oplus }_{i_4{i}_3}{D}^{i_3}\left(g_1-\overline{i_3{i}_4}\right)\right),c_3\right)\end{array}$

Iff:

$i_2{\succsim }^{i_4}{i}_3$ .

Hence, we conclude that $i_2{\succsim }^{i_1}{i}_3\to i_2{\succsim }^{i_4}{i}_3$ in $g_1$ . This completes our proof. □

Proof of Proposition 2. First, we consider any SNN that is supported by $\mathcal{V}$ and $\mathcal{C}$ that satisfies partner heterogeneity for $\sigma =1$ . Note that for any $x\mathrm{,}y\in N$ and $x\mathrm{,}y$ in the same viewpoint of i it holds true that $I_x=I_y$ for $\sigma =1$ and ${\lim }_{\sigma \to 1}{I}_y-I_x=0$ . Note further that for $\sigma <1$ in this minimally connected network it holds true that x is preferred to y as a partner if and only if $c_y-c_x\ge I_y-I_x$ where $c_y\ge c_x$ and $I_y\ge I_x$ 8. Since $c_y-c_x\ge {\lim }_{\sigma \to 1}{I}_y-I_x=0$ and I is continuous in $\sigma$ , we conclude that there exists $\underset{\_}{\sigma }$ such that $c_y-c_x\ge I_y-I_x$ —equivalently x is preferred to y—for every $\sigma \in \left(\underset{\_}{\sigma }\mathrm{,1}\right]$ . □

NOTES

¹In the context of telephone call, an interpretation is that some agents possess information whose value is higher than that of others. In terms of call establishment cost, Billand et al. (2012) mentions that “If j is a busy person, then it is difficult to access her. It follows that the time that i spends (the cost that i incurs) to obtain an answer from j will depend on j’s characteristics.”

²Note that there are some discrepancies in terms of notations that I use here and those of (Olaizola and Valenciano, 2015). Specifically the term “component” in (Olaizola and Valenciano, 2015) is equivalent to the term “strongly full subgraph” in this note. “Nash profile” in (Olaizola and Valenciano, 2015) is identical to “Nash network” in this note. I justify and elaborate on these notational discrepancies in Discussion section of this note.

³Following the literature, we assume that i has an entry to his own information.

⁴These notations are follow (De Jaegher and Kamphorst, 2015).

⁵Note that (Olaizola and Valenciano, 2015) uses the term Nash profile rather than Nash network as used in this current note, although they have the same meaning—network such that every agent chooses his best response in pure strategy.

⁶Note that that term “connected full subnetwork consisting of strong links” and “strongly full subnetwork” here have the same meaning as “strong component” in (Olaizola and Valenciano, 2015). The reason for not adopting the same terminology as (Olaizola and Valenciano, 2015) is that (Olaizola and Valenciano, 2015)’s definition of component is different from what is used in this note as well as (Billand et al., 2011) and (Bala and Goyal, 2000). Indeed, the definition of component in (Olaizola and Valenciano, 2015) is precisely the definition of a full subnetwork in this note.

⁷This proof can easily be generalized for any minimal network and any chain with more than three agents. I leave this to my readers.

⁸That is, it may be cheaper to form a link with x than with y but connecting to y gives a higher informational quantity relative to connecting to x. However, if the former outweights the latter then x is preferred to y.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Bala, V., & Goyal, S. (2000). A Noncooperative Model of Network Formation. Econometrica, 68, 1181-1229. https://doi.org/10.1111/1468-0262.00155
[2]	Billand, P., Bravard, C., & Sarangi, S. (2011). Strict Nash Networks and Partner Heterogeneity. International Journal of Game Theory, 40, 515-525. https://doi.org/10.1007/s00182-010-0252-8
[3]	Billand, P., Bravard, C., & Sarangi, S. (2012). Existence of Nash Networks and Partner Heterogeneity. Mathematical Social Sciences, 64, 152-158. https://doi.org/10.1016/j.mathsocsci.2012.01.001
[4]	Charoensook, B. (2019). Bi and Branching Strict Nash Networks in Two-Way Flow Models: A Generalized Sufficient Condition. The BE Journal of Theoretical Economics, 20, Article ID: 20180117. https://doi.org/10.1515/bejte-2018-0117
[5]	De Jaegher, K., & Kamphorst, J. (2015). Minimal Two-Way Flow Networks with Small Decay. Journal of Economic Behavior & Organization, 109, 217-239. https://doi.org/10.1016/j.jebo.2014.10.010
[6]	Galeotti, A., Goyal, S., & Kamphorst, J. (2006). Network Formation with Heterogeneous Players. Game and Economic Behavior, 54, 353-372. https://doi.org/10.1016/j.geb.2005.02.003
[7]	Granovetter, M. (2018). Getting a Job: A Study of Contacts and Careers. University of Chicago Press.
[8]	Jackson, M. O., & Wolinsky, A. (1996). A Strategic Model of Social and Economic Networks. Journal of Economic Theory, 71, 44-74. https://doi.org/10.1006/jeth.1996.0108
[9]	Katz, E., Lazarsfeld, P. F., & Roper, E. (2017). Personal Influence: The Part Played by People in the Flow of Mass Communications. Routledge. https://doi.org/10.4324/9781315126234
[10]	Olaizola, N., & Valenciano, F. (2015). Unilateral vs. Bilateral Link-Formation: A Transition without Decay. Mathematical Social Sciences, 74, 13-28. https://doi.org/10.1016/j.mathsocsci.2014.12.002
[11]	Olaizola, N., & Valenciano, F. (2018). A Unifying Model of Strategic Network Formation. International Journal of Game Theory, 47, 1033-1063. https://doi.org/10.1007/s00182-017-0592-8
[12]	Unlu, E. (2018). Efficient Networks in Models with Player and Partner Heterogeneity. The Manchester School, 86, 100-118. https://doi.org/10.1111/manc.12196