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 receiver1. 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 formation2.
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:
is the set of all agents. Let
,
.
if i forms a link with j or accesses j and
otherwise. A collection of such decision of i is a strategy of i, which is
. Since link formation is unilateral, a strategy profile
is, equivalently, a network.
Structure of information: Let
if
or
or both, and
otherwise. We say that an undirected link between i and j exists if
. Of course,
is called an undirected network.
Value of Information and link formation cost:
represents the value of information that i receives from j if information is transmitted perfectly. A value structure is
. If
for every
then
is said to satisfy partner heterogeneity (in information value). Similarly,
is cost that i bears if he forms a link with j and
is the cost structure. If
for every
is said to satisfy partner heterogeneity (in link formation cost). Throughout this paper, we assume that
and
satisfy partner heterogeneity.
Information transmission and decay: A chain between k and j—
—is defined as a sequence of agents
such that
and
for
. A path from k to j—
—is defined likewise except that
instead of
. If a chain between i and j exists, we sat that i observes j and vice versa. In g, let
be the set of agents that i observes including i himself3. 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
and j receives
. This note extends this aforementioned paper by assuming that information transmission is not perfect. This imperfect transmission is represented by the decay factor
. Consider two ij-chains,
and
.
is said to be shorter than
if
. The distance between i and j,
, 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
.
Small Decay Assumption: Since an ex-post information value that i receives from j is
, by reducing the distance
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.,
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
is a subnetwork of g if
. Let
denotes the set of all agents in
. Let
be defined as g with the modification that
and
be defined as g with the modification that
. 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
. Suppose that g is minimally connected. Given that
let
be a subnetwork consisting of links of all agents that i is able to obtain information by accessing j. Let
,
is said to be better-informed than
if
.
is best-informed in
if
for every
4.
and Branching Networks: Let
be the set of all agents that access i and
be the set of all agents that i accesses. The following definitions of
and Branching Networks are borrowed from (Billand et al., 2011). Consider
. Let
. If X is a set that is minimal with respect to the property that
, then X is said to be a contrabasis of N. A contrabasis is an i-point contrabasis if there exists
such that every
,
, accesses i. If i is a point contrabasis of g and
but
for all
and
, g is said to be a
network. Observe that if a minimally connected
, 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
and
for all
.
The payoffs (as in (Billand et al., 2011)): Let
be such that
is strictly increasing in x and strictly decreasing in y. The payoff of player i is given by:
(1)
Note that this payoff assumes that information transmission is perfect since the decay factor
is not included. A special case of this payoff is the so-called linear payoff, which is:
(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:
(3)
And the payoff in Equation (2) becomes:
(4)
where (recall that)
.
Nash network and strict Nash network: Let
be a strategy profile of all agents except i so that
. If
for every
that is a strategy of i then
is a best response of i. If
is a best response of i for every
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
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
or branching network can be supported as SNN.
Proposition 2. Given the linear payoff (Equation (4)), any minimally connected
or branching network can be supported as SNN by some
and
, where
and
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
. 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)),
,
. Observe that
for
. Hence, accessing
is not a best response of i if no decay is assumed as in (Billand et al., 2011). However, the presence of small decay
causes i to be better off accessing
rather than
or
. Specifically, for
in
we have
,
. That is,
is best-informed in
. Let
,
. Note that while
is relatively more costly to form a link with than
, the fact that he is best informed compensate for this relatively higher cost. Specifically,
for
.
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
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
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
and
. It shows that a prominent property of Nash network in this mixed model, which is such that every non-empty Nash network5 has at most one connected full subnetwork consisting of strong links or strongly full subnetwork as defined below, disappears once partner heterogeneity is assumed6.
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
but
or vice versa. A link between i and j is strong if
and
. We write
(
) to denote the existence of a weak (strong) link between i and j. Note that
also indicates that the link is sponsored by i. We further write
if
or
. Let
then
is defined as the subnetwork consisting of all agents whose information is sent to i via the link
.
is the information that i receives from the link
.
Let
. A subnetwork
is said to be a subnetwork induced by C or a full subnetwork if: 1)
and 2) a link exists in
if and only if it exists in g.
is a weakly full subnetwork of g if for any two nodes
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
. Every link that is strong incurs no information decay. Thus if
is the information of j and a chain between i and j consists of k weak links, then i receives
. 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:
where
.
Proposition 3. Let
and
. If g is Nash then:
(5)
and
(6)
Moreover, there exist
and
satisfying partner heterogeneity such that g is Nash and the above two inequalities are satisfied.
Corollary 1. If
and
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
and
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
Note that this line has two non-empty strongly full subnetworks, namely
and
. We claim that this network is SNN for the following support:
,
, and
.
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
has to be sufficiently low that
is better off accessing
. Otherwise, the link
become a weak link. This leads to:
(7)
Iff:
(8)
On the contrary, for this network to be Nash
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:
(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:
(10)
Putting inequalities 8 and 10 together we have:
(11)
Observe that inequality 11 above corresponds to inequality 5 in Proposition 3.
Next, consider
. For this network to be Nash
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:
(12)
Iff:
(13)
Observe that inequality 13 above corresponds to inequality 6 in Proposition 3.
Let us partially check our
satisfy inequalities 11 and 13. For inequality 11:
(14)
For inequality 13:
(15)
However, if the above support
, 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
and
, inequality 11 becomes:
(16)
and inequality 13 becomes:
(17)
which is impossible since such c cannot exist. What is the intuition? Lemma 1 of (Olaizola and Valenciano, 2015) states that as
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
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
and
be two non-empty components and let i accesses
in
and j accesses
in
. Observe the fact that i chooses his unique best response means that the strategy to accessing
to obtain information from agents
at the cost of
is superior to the strategy of removing the link with
and accessing
to obtain information from
at the cost of
. That is, accessing
to receive information from
while paying
gives
a higher payoff than removing the link
and accessing
to receive information from
while paying
. Similarly, observe that j’s strategy in g is to access
, which also means that j receives information from
while paying
. It follows that j is better off following i’s strategy: removing his link with
and accessing
instead.
Next, we turn to prove that a unique non-empty component of SNN is either a minimal
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
divides g into two components—one containing i and the other one containing j. These two are denoted by
and
and called anti-viewpoint of i and viewpoint of i respectively.
then denotes a network such that
is jointed with
by suppposing that i accesses
. Next, consider two agents x and y. i is said to prefer x to y or
if: (i) there exists
such that
and (ii)
. Moreover, if the inequality above is strict, i is said to strictly prefer x to y or
. 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
with
in this network, either of the following two properties with respect to partner preference holds true: (i)
then
or (ii)
then
. 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
such that
but
where
, which we do so onwards (FigureA1).
Without loss of generality consider the network
. In this network consider the chain
. We will show that if
then
. To do so first note that in
is a singleton (a component with preceisely one agent), which is agent
. To ease the notational cumbersomeness we denote
by
7.
Step 1: First, note that
in
if and only if:
(18)
See FigureA2 for an illustration of networks
and
. The above inequality leads to:
for any
, Now if we set
and
we get:
Observe that
is the information benefit that
receives from
in
. Similarly,
is the information benefit that
receives from
in
. Thus, the above inequality assumes as if the link
is removed from the networks
and
. This observation and the fact that
allows us to restate the above inequality as:
(19)
See FigureA3 for an illustration of networks
and
. We further restate the above inequality as:
iff:
so that
for any
. Now set
and
we have:
Since
we know that the above inequality can be restated as:
so that
Now set
the above inequality can be restated as:
Finally, note that
is nothing else but the viewpoint of
via
or
. Note further that
on the left-hand side of the inequality above is what
receives if he establishes a link with
in
, and
on the right-hand side of the inequality above is what
receives if he establishes a link with
in
.
Hence, we can restate the above inequality as:
Iff:
.
Hence, we conclude that
in
. This completes our proof. □
Proof of Proposition 2. First, we consider any SNN that is supported by
and
that satisfies partner heterogeneity for
. Note that for any
and
in the same viewpoint of i it holds true that
for
and
. Note further that for
in this minimally connected network it holds true that x is preferred to y as a partner if and only if
where
and
8. Since
and I is continuous in
, we conclude that there exists
such that
—equivalently x is preferred to y—for every
. □
NOTES
1In 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.”
2Note 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.
3Following the literature, we assume that i has an entry to his own information.
4These notations are follow (De Jaegher and Kamphorst, 2015).
5Note 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.
6Note 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.
7This proof can easily be generalized for any minimal network and any chain with more than three agents. I leave this to my readers.
8That 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.