Bargaining Dynamics and Varied Linking Costs in
Stable Networks

Erik Darpö
Linköping University
Alvaro Domínguez

Asian Growth Research InstituteMaría Martín Rodríguez
UIC Barcelona

Working Paper Series Vol. 2024-04
March 2024

The view expressed in this publication are those of the author(s) and do
not necessarily reflect those of the Institute.

No part of this article may be used or reproduced in any mannerwhatsoever without written permission except in the case of brief
quotations embodied in articles and reviews. For information, pleasewrite to the Institute.

Asian Growth Research InstituteBargaining Dynamics and Varied Linking Costs in
Stable Networks∗
Erik Darpö1 , Alvaro Domı́nguez2 , and Marı́a Martı́n-Rodrı́guez3
1

Linköping University.

2 Asian Growth Research Institute.
3 UIC Barcelona.

March 26, 2024

Abstract
In a scenario featuring two distinct player types, we examine the pairwise stability of stationary networks where agents engage in infinite-horizon bargaining games akin to Manea’s framework. Link formation and maintenance costs
are contingent upon communication ease and complementarities, with connections between individuals of different types becoming less expensive whencomplementarities are sufficiently strong. In such instances, various bipartite
components emerge as stable, characterized by a lack of direct connections
between players of the same type. These components exhibit inequitable distributions of surplus, resulting in asymmetric splits among linked individuals.
This contrasts with scenarios where connections between individuals of thesame type are less costly, leading to predominantly equitable stable components. OUr findings highlight how complementarities and the relative scarcity
of certain types can influence the fairness of bargaining outcomes within networks.
Keywords: Bargaining, Heterogeneity, Networks, Pairwise stability.
JEL classification: C72, C78, D85

1Introduction

Collaborations among researchers to produce scientific outcomes are the norm nowadays in many disciplines. The average number of co-authors across all disciplines ofstudy has grown from 9.47 in 2012 to 25.10 in 2016. In the physical sciences, the∗We would like to thank Antonio Cabrales, Simona Fabrizi, Makoto Hanazono, Steffen Lippert,
Angel Lopez, Daniel Marszalec and Nikolas Tsakas for useful comments and suggestions. Anyremaining errors are solely our responsibility.

1average number of authors has increased from 9.46 to 38.61 for the above period,
surpassing a thousand authors in the most extreme cases. In the same spirit, between 1980 and 2016, 76% of the papers published in Economics have two or moreauthors.1
How researchers associate depends on their own skills and the characteristics ofthe projects, which are all assumed to be financed through research funds normalized
to one monetary unit per project. Suppose that there are two types of players, saytheorists and empiricists, and two mutually exclusive states of the world, say projects
that require a single skill of either type or both skills simultaneously.2 We aim tocharacterize the stable networks in this setting.
When deciding whether to create or break a link, players face a trade-off: on
the one hand, the received share of the funding depends on their relative position in
the network, which affects their bargaining power. On the other hand, players paya cost for building and sustaining links with other researchers and for developing
projects.
Although it is natural to assume that creating and maintaining a link between
researchers with different skills is more expensive, the project development costdepends on the state of the world. In particular, if projects require a single typeof skill, the development cost will be lower between two researchers with the sameability; however, it will be the opposite if projects require both types of skills.
The aggregate cost and the bargaining outcomes determine the structures of thestable components of the network. If in the overall it is cheaper to connect witha researcher with the same skill —which happens if projects require a single skill
and may happen if they require both— we get the familiar result that only pairs,
lines of three and odd cycles are stable.3 If in the overall it is cheaper to connect
with a researcher with a different skill —for which projects requiring both skills isa necessary condition— many other components also become stable, such as oddlines, stars (isolated or connected) and star-like trees.
All these new stable components are bipartite graphs4 such that there are nolinks between two players of the same type.5 This implies that, given the features ofthe bargaining game, all players of the same type in the component receive the same
share and that it differs from 1/2. Intuitively, these components are stable for certain
cost ranges because, although two players getting the low share can improve theirbargaining power by creating a link among themselves, this action is comparatively
expensive.
There are several ways in which players can be “different.” Besides the interpretation based on skills, it is also possible to think in terms of the countries where
the researchers are based, resulting in domestic or international collaborations. As
an illustration, articles in science and engineering with at least one international
1

Please refer to https://www.natureindex.com/news-blog/paper-authorship-goes-hyper for
more details.
2
We thank Angel Lopez for suggesting this interpretation.
3
These results are the same as in the framework by Gauer and Hellmann (2017), where all links
are equally costly to form.
4
A bipartite graph is a graph that does not contain any odd-length cycle.
5
Further regularity constraints are derived in Section 4.

2

co-author have grown from 16% in 1997 to 25% in 2012; in the same vein, domestic
collaborations rose from 36% to 44% during the same period.6 By field, international
co-authorship has also increased: shares range from 56% for astronomy, 27-34% formathematics, physics and biological sciences to 17-21% for chemistry and the social
sciences.7
When talking about domestic or international collaborations, it also makes sense
to consider that nature chooses the state of the world. For instance, authorities cancall for projects that require researchers from different countries to collaborate to beeligible to receive funding. To illustrate, the European Union will allocate EUR 1.65
billion to the Marie Sklodowska-Curie Actions out of the EUR 50.5 billion of Horizon
2020, the EU Framework Program for Research and Innovation, which accounts for
3.27% of the total budget.8 Further examples of funding for international collaborations include the Humboldt Research Fellowship for Postdoctoral Researchers inGermany and the JSPS Postdoctoral Fellowships for Research in Japan.
This paper contributes to the literature on stability of bargaining networks. The
consideration of two types of players naturally results in cost heterogeneity. The
novel result of additional bipartite graphs becoming stable in this setup widens ourunderstanding of the conditions for these structures to appear. The importanceof this result is double: first, it resembles some of the structures that research
networks exhibit in real life9 and second, as it determines the cost ranges for whichthese components are stable, it may help design policies oriented toward achieving
networks with certain attributes.
Section 2 describes the model. Section 3 characterizes the stable components andnetworks when connections between players of the same type are cheaper. Section 4
performs the analogous exercise when connections between players of different types
are cheaper, and Section 5 concludes. The mathematical proofs are presented inAppendix A.

1.1

Literature Review

Our paper contributes to the literature of bargaining in networks in which the linking
costs are heterogeneous because players are of different types.
The literature of R&D networks has modeled the reduction in production costs
via connections with other firms as a reason behind these collaborations. Ex-ante
identical firms are also identical ex-post if the equilibrium network is symmetric, butheterogeneous ex-post if the equilibrium network is asymmetric. In contrast, ourlinking cost are heterogeneous by assumption and symmetric networks are stablein equilibrium for certain cost ranges. Moreover, in our setup the stability of asymmetric equilibrium network does not imply that players pay the same cost.
6

In reality, these two figures expand simultaneously at the expense of single-authored papers.
This information is available at https://www.nsf.gov/statistics/seind14/index.cfm/
chapter-5/c5s4.htm
82.37% is destined to fund collaborations among the EU members and the remaining 0.92% tofund collaborations with the rest of the world, including the UK.
9
See for example Newman (2004).
73

Goyal and Moraga-Gonzalez (2001) study R&D networks in which the marginal
cost decreases in the own effort of the firm and the effort of their neighbors. The
cost of the own effort is increasing and exhibits decreasing returns. A link makes thetwo firms involved more competitive, which in turn affects the degree of competitionin the market. The complete network is stable when firms compete in independent
markets and in Cournot oligopolies. In our framework, the complete network isnever stable: additional links may not change the bargaining power of the players
involved, making its creation unprofitable.
Goyal and Joshi (2003) study R&D networks in which the marginal cost decreases linearly in the number of links. In Cournot oligopolies with non-negligible
linking costs, firms have increasing returns from links, which implies that any stablenetwork can have at most one non-singleton component and that this component
must be complete.10 Our framework also allows for more than one isolated nodein equilibrium, but it is not always the case that there is one non-singleton component and that these components are complete. As before, the characteristics of theconsidered bargaining process are behind this difference.
Whereas the positive effect of creating a link in R&D networks happened througha cost reduction, in information networks it happens through the additional information owned by other players that now becomes accessible.
Galeotti et al. (2006) study strict Nash equilibria in networks in which one agent
pays the linking cost but the information flows both ways. Information is acquired
through direct and indirect connections, and the authors allow for value and costheterogeneity.11 With homogeneous values and a linking cost that increases in the
distance between groups of players, all equilibria different from the empty network
consist of center-sponsored stars.12 By contrast, we find stars and related structures
when it is cheaper to link with the different group. Their no decay assumption withregards the information acquisition and the fact that pairwise stability is a weakerequilibrium concept than strict Nash equilibrium explain this difference.
Galeotti and Goyal (2010) also study networks in which one agent pays the linking cost but the information flows both ways. Players decide whether to acquire theinformation personally or from others through direct and indirect connections. Since
the returns from information are increasing and concave while the costs of acquiring
information personally are linear, strict Nash equilibria exhibit the core-peripheryarchitecture. No heterogeneity is necessary for this result, but introducing a slight
cost advantage in personally acquiring information predicts a unique equilibrium inwhich the low cost player is the single hub of the star. The stability of the star in
our setup with bargaining depends on the form of the heterogeneity: stars of n ≥ 4
are not stable when it is cheaper to connect with players of the same type.13
10

To get equilibria such that they are unique with respect to the size of the dominant group given
the linking cost, and the size of this group is monotonically decreasing in the linking cost, Dawid
and Hellmann (2014) study the same framework but make it dynamic and look for stochastic
stable networks: one existing or potential new link is randomly chosen every period to be reviewed
by the two involved firms, who will make a mistake with a small probability.
11
These heterogeneities extend the framework by Bala and Goyal (2000).
12
Depending on the costs, the equilibrium is either a generalized star or several unconnected stars.
13
Gauer and Hellmann (2017) also get this result in bargaining networks with homogeneous costs.

4

In bargaining networks, the positive effect of an additional link happens througha subtler channel than in information networks. Whereas in the latter it happens bysimple aggregation, in the former an additional link may alter the relative bargaining
power of the players involved.14
Manea (2011) studies an infinite-horizon bargaining game in a stationary, undirected network.15 Stationarity is modeled as follows: players reaching an agreement
leave the market but are replaced by identical players in the subsequent period thatassume the same positions in the network, and so the network structure remains thesame. Taking the network structure as given, the author shows that not all existing
links will be used when players are patient enough; that is, there are pairs of players
that, when selected to bargain, do not reach an agreement and instead prefer towait to be matched with another trading partner.
These disagreement links motivates the approach by Gauer and Hellmann (2017).
We also build a model of two stages in which the strategic network formation happens in the first stage and a stationary bargaining game à la Manea takes place inthe second stage. The main difference is that they consider homogeneous linking
costs while we introduce heterogeneity. Our results are qualitatively similar whenconnections between players of the same type are cheaper: stable non-singleton components are pairs, lines of three and odd cycles. However, when connections between
players of different types are cheaper, many other bipartite graphs such that there
are no links between players of the same type also become stable.
Other authors have focused on bargaining in non-stationary networks. Nonstationarity means that the players who reach an agreement leave the game without
being replaced in the subsequent period. Kranton and Minehart (2001), CorominasBosch (2004) and Elliott and Nava (2019) restrict their attention to bipartite graphs
by studying relationships between buyers and sellers or employers and employees.
On the contrary, our bipartite graphs are equilibrium results. Abreu and Manea(2012a,b) consider a general setting in which some agents may act as both buyers andsellers for other agents in the networks. Analogously, we also obtain pairwise stablestructures that are not bipartite graphs. Finally, Polanski (2007) and Bloch et al.
(2019) also analyze general architectures but the equilibrium payoffs are determinedby the classification of nodes in the the Gallai–Edmonds decomposition.

2

The model

We consider a two-stage game. In the first stage, t = 0, players form undirected,
costly links. The cost of each link is determined by (i) the types of the connecting
players, and (ii) the state of the world. Both the players’ types and the state of
the world are exogenously determined and common knowledge. In the second stage,t = 1, 2, ..., given the network formed previously, an infinite-horizon game in whichpairs of players connected by a single link are randomly matched to bargain à la
Manea takes place.
14
15

Seminal contributions to the bargaining literature are Nash (1950, 1953) and Rubinstein (1982).
Rubinstein and Wolinsky (1985) analyze the first model of decentralized bargaining in stationary
markets.

5

□ Networks
Let N = {1, 2, ..., n}, n ≥ 3 be the set of players. There are two types ofplayers, E and T . We consider NE = {1, 2, ..., nE } and NT = {1, 2, ..., nT } such thatnE + nT = n.
Denote a link between players i, j ∈ N , i ̸= j, by ij = ji := {i, j}. The complete
network, g N , is defined as the network in which every pair of distinct players are
16
connected
 to eachNother by a single link. Then, the set of all undirected networks
is G = g | g ⊆ g . We represent the neighbors of player i in the network g by
the set Ni (g) = {j ∈ N | ij ∈ g} and refer to ηi (g) = |Ni (g)| as its cardinality or,equivalently, as the degree of player i. A player is isolated if they have no neighbors.
Given a network g, a path between i and j is a sequence of players i1 , i2 , ..., iM
such that im im+1 ∈ g for all m ∈ {1, ...M − 1}, with i1 = i and iM = j. The set
C ⊆ N is a component of network g if there exists a path between any two players
in C and it is Nj (g) ∩ C = ∅ for all j ∈/ C. A subnetwork g ′ ⊆ g is componentinduced if there is a component C of g such that g ′ = g|C , where the network
g|K := {ij ∈ g | i, j ∈ K} is the subnetwork restricted to the players K ⊂ N .
Finally, let g + ij := g ∪ {ij} denote the network obtained by adding link ij
to the existing network g, and g − ij := g \ {ij} denote the network obtained bydeleting link ij from the existing network g.
□ Costs
In order to generate the unit of surplus for which they will bargain later on,
players need to incur a cost composed of two factors: the cost of forming andsustaining a collaboration link, and the cost of running a project. These components
depend on the players’ types, E and T , and the state of the world, S and B, which
are assumed to be mutually exclusive. Both the types and the state of the world
are exogenously determined and common knowledge.
The cost of forming and sustaining a link depends on the players’ types. For thesake of exposition, consider that E and T stand for empiricists and theorists. It ischeaper to link with an agent of the same type: communication is easier because of
the similar background. Then, we can write cℓ,a < cℓ,d , where cℓ,a := cℓ,EE = cℓ,T T
and cℓ,d := cℓ,ET = cℓ,T E .
The cost of running a project depends on both the players’ types and the stateof the world. Consider that S means that projects require a single skill whereas
B signifies that projects require both skills. If the state of the world is S, thencP,a < cP,d holds, where cP,a := cP,EE = cP,T T and cP,d := cP,ET = cP,T E . However,if the state of the world is B, the developing costs relate in the opposite way:
cP,a > cP,d .
The underlying idea behind these inequalities is that, to complete a project inthe state of the world S, a pair of players with different skills need to pay an extra
cost because one of them needs to instruct the other in the skill they don’t have.
On the contrary, to complete the project in the state of the world B, two playerswith the same skill need to pay an extra cost to acquire the knowledge mastered by
16

Formally, the complete network is the set of all subsets of N of size 2.

6the other type.17
Denote the lowest overall cost by c and the highest overall cost by c > c. If
projects require a single skill, links between players of the same type are cheaperin the overall: c = ca := cℓ,a + cP,a and c = cd := cℓ,d + cP,d . However, if projects
require both skills, links between players of different types are cheaper in the overall(that is, c = cd ) if and only if cℓ,d − cℓ,a < cP,a − cP,d ; in other words, if and only ifcomplementarities are strong enough to make the difference in the cost of runningthe project more than offset the difference in the cost of linkage.
□ Bargaining
Given a network g, the bargaining stage à la Manea is as follows.18 Each periodt = 1, 2, ... a link ij ∈ g is selected according to a uniform matching technology,
which is a probability distribution over g’s links such that each link is chosen withequal probability. The chosen link generates one unit of surplus that the two involved
players can divide among themselves.19 Then, with probability 1/2, one of the twoplayers is chosen as the proposer to make an offer to the other player, the responder.
The offer specifies how to split the unitary surplus. If the responder rejects theoffer, then both players receive a payoff of zero and stay in the game for the next
period. If the responder accepts the offer, then both players exit the game with theshares agreed upon and in the next period two players identical to the ones wholeft replace them such that the network structure remains the same. The network
structure, and all offers and responses are common knowledge.
The stationary equilibrium payoffs v ∗ correspond to the unique fixed point of thecontraction that expresses the expected payoff of each player as the weighted sumof (a) their own continuation payoff, obtained whenever being the responder,20 and(b) the maximum between the share agreed upon when being the proposer, obtained
when the other player accepts the offer, and their own continuation payoff, obtained
when the other player rejects the offer. The weights are the probabilities of being
involved in the bargaining as the responder and as the proposer, given the network
structure. For each player, the equilibrium payoff is found to depend only on theirposition in the network and the discount factor δ.
We assume players that tend to be infinitely patient; that is, δ → 1. In thiscase, the limit equilibrium payoffs depend solely on the network structure and canbe computed using a simple algorithm. To implement it, we define two sets: M
and Lg (M ). For any set of players M ⊆ N and any network g, let Lg (M ) :={j ∈ N |ij ∈ g, i ∈ M } be the corresponding partner set in g; that is, the set ofplayers who have g-links to players in M . Moreover, a set M ⊆ N is g-independent
if there is no g-link between two players in M , M ∩ Lg (M ) = ∅.
Definition 1 (Manea, 2011). For a given network g and player set N , the algorithm
17

We assume that this extra cost affects both players evenly.
See Manea (2011) for a detailed explanation.
19
Continuing with the interpretation of the research networks, the selected link means that the
researchers are selected to run a project and the unit of surplus would be the research fund,which is normalized to 1.
20
When being the responder, the player always gets their own continuation payoff: this is what
they get when they reject the offer and so the proposer will never offer more than this value.
18

7

A(g) provides a sequence (rs , xs , Ms , Ls , Ns , gs )s=1,2,...,s̄ which is defined recursively
as follows. Let N1 := N and g1 := g. For s ≥ 1, if Ns = ∅ then stop and set s̄ = s.
Otherwise let|Lgs (M )|
,
(1)
rs :=
min
M ⊆N,M ∈I(g)|M |where I(g) denotes the set of nonempty g-independent subsets of N .
If rs ≥ 1 then stop and set s̄ = s. Otherwise, set xs = rs /(1+rs ). Let Ms be the unionof all minimizers M in (1). Denote Ls := Lgs (Ms ). Let Ns+1 := Ns \ (Ms ∪ Ls )and gs+1 := g|Ns+1 be the subnetwork of g induced by the players in Ns+1 .
Let the result of A(g) be given by the sequence (rs , xs , Ms , Ls , Ns , gs )s=1,2,...,s̄ .
The limit equilibrium payoffs are then given byvi∗ = xs
vj∗ = 1 − xs∀i ∈ Ms , ∀s < s̄,∀j ∈ Ls , ∀s < s̄,vk∗ = 1/2

∀k ∈ Ns̄ .

At each step s, the algorithm A(g) determines the largest mutually estranged set
minimizing the shortage ratio in the subnetwork induced by the remaining players
Ns , gs := g|Ns . As Ms is gs -independent, these players can only bargain with thosein the partner set Ls . If the partner set is small compared to Ms , then players in
Ls are in a powerful bargaining position, which allows them to get larger sharesof the unitary surplus. By minimizing the shortage ratio, the algorithm identifies
the players in strongest and weakest bargaining positions, since they will not findagreements with other players in equilibrium.
The limit equilibrium payoff for the players in the mutually estranged set Ms
is xs = rs /(1 + rs ) = |Ls | / |Ls + Ms | < 1/2, whereas their partners in Ls obtain
1 − xs = |Ms | / |Ls + Ms | > 1/2.21 These players with extremal limit payoffs are
removed and the algorithm continues to the next step. It stops when there are no
more players left or when the minimal shortage ratio is larger than one, in whichcase all remaining players receive 1/2.
□ Stability
When forming the network, the players anticipate the outcome of the bargaining
stage v ∗ . The linking decisions reflect the following trade-off: on the one hand,creating a link to run a project may benefit the bargaining power of the players
involved by altering their relative positions in the network; on the other hand, there
is a cost for creating links and developing projects. As it was explained before, thisaggregate cost depends on the players’ types and the state of the world.
At t = 0, each player tries to maximize their profit, expressed asu∗i (g) := vi∗ (g) − η i (g)c − η i (g)c,(2)

where η i (g) represents the number of i’s neighbors that it was expensive to link
with, and η i (g) denotes the number of i’s neighbors that it was cheap to link with.
21

Notice that xs is increasing in the shortage ratio.

8

The profit profile u∗ = (u∗i )i∈N is component-decomposable because u∗i (g) =and g, where Ci ⊆ N represents the component of player i in
network g. The algorithm A(g) assigns isolated players the payoff 0.23
We use the equilibrium notion of Pairwise Stability and do not explicitly model
the network formation in stage t = 0:u∗i (g|Ci(g) ) ∀i ∈ N
22Definition 2 (Jackson and Wolinsky, 1996). A network g is pairwise stable if:
1. for all ij ∈ g : ui (g) ≥ ui (g − ij) and uj (g) ≥ uj (g − ij), and
2. for all ij ∈/ g : if ui (g + ij) > ui (g), then uj (g + ij) < uj (g)The implicit assumption of network formation behind this stability concept isthat any player can unilaterally delete a given link, but both players need to agree
to build a link. An existing link is sustained if none of the two players involved isstrictly worse off by doing so, and an existing link is deleted if at least one of thetwo players involved is strictly better off by doing so. Therefore, the networks thatallow neither (mutually) profitable link formation nor profitable link deletion are
pairwise stable.

3

Pairwise Stable Networks

Pairwise stable networks are composed of pairwise stable components that have no
incentives to create links among themselves. From Manea (2011), a link ij ∈ g canonly lead to an agreement if vi∗δ (g) + vj∗δ (g) ≤ 1 holds for δ large enough. Otherwise,
it is a disagreement link : irrelevant for the bargaining power of the agents (andso for the bargaining outcome) while costly to form and sustain. Intuitively, theselinks should not form. Let g ∗ be the limit equilibrium network of g, defined as the
network obtained by deleting all disagreement links from g for δ → 1.
Proposition 1 (Gauer and Hellmann, 2017). If g is pairwise stable, then g = g ∗and, hence, vi∗ (g) + vj∗ (g) = 1 ∀ij ∈ g.
We reproduce below the necessary conditions for a network to be pairwise stable
derived by Gauer and Hellmann (2017), which are independent of the cost structure.
By Proposition 1, if players receive the same payoff in a component C, then any
pair of players i, j ∈ C such that ij ∈ g must get vi∗ (g) = vj∗ (g) = 1/2. DefineÑ (g) := {i ∈ N |vi∗ (g) = 1/2}.
Theorem 1 (Gauer and Hellmann, 2017). If a network g is pairwise stable, thenfor any component C of g it holds that C ∩ Ñ (g) ∈ {∅, C}. If C ∩ Ñ (g) = C, thenit must be a separated pair or an odd cycle.24,25
22

See Gauer and Hellmann (2017) for further details on this point.
Continuing with our interpretation in terms of research networks, this means that single authors
cannot access any research funding because running a project individually is unaffordable.
24
A separated pair denotes a subnetwork induced by a two-player component.
25
A cycle with m players is induced by a component with cardinality m ≥ 3 such that all players
have exactly two links. It is called odd if its cardinality is an odd number.
23

9

Corollary 1 (Gauer and Hellmann, 2017). If a network g is pairwise stable, thenfor any non-equitable component C of g there exists a unique partition M ∪˙ L = C
with |M | > |L| and g|M = g|L = ∅ such that payoffs are given by vi∗ (g) = x ∀i ∈ M
and vj∗ (g) = 1 − x ∀j ∈ L, where x = |L|/(|M | + |L|).
In words, if a pairwise stable network contains a non-equitable component, thenit must be bipartite: by Proposition 1, the payoffs of the connected players must add
up to 1, what implies that players receiving the same payoff within a non-equitablecomponent cannot be linked.

3.1

Cheap Links Between Players of the Same TypeIn this subsection, we present the sufficient conditions for a network to be pairwise
stable when links between players of the same type are cheaper in the overall.
Recall from the previous section that this is the case when (a) the state of theworld is S; that is, when projects require a single skill of either type to be developed,or (b) the state of the world is B if and only if cℓ,d − cℓ,a > cP,a − cP,d ; that is, when
projects require both skills to be developed but the complementarities are not strong
enough to make the difference in the cost of running the project more than offset
the difference in the cost of linkage.
We say that a component is homogeneous if all players in it are of the same type,and heterogeneous otherwise.
The two lemmas deal with the stability of individual components, whereas thethree theorems characterize pairwise-stable networks with more than one component.
3.1.1

Components

Lemma 1. Sufficient conditions for components to be pairwise stable:(i) The homogeneous pair is pairwise stable if c ≤ 12 .
The heterogeneous pair is pairwise stable if c ≤ 12 .
(ii) The homogeneous line of length three is pairwise stable if c = 16 .
The heterogeneous line of length three such that two nodes of the same typeare consecutive is pairwise stable if c = 16 .
1(iii) The homogeneous odd cycle with at most 2c
players is pairwise stable if c ≤ 16 .
1
The heterogeneous odd cycle with at most 2c
players is pairwise stable if c ≤ 16 .

Proof.
In the Appendix.
Lemma 2. The following components are not pairwise stable:(i) Heterogeneous lines of length three such that two nodes of the same type are
not consecutive.
10

(ii) Lines of length four or above.
(iii) Even cycles.
Proof.
In the Appendix.
These results include those in Gauer and Hellmann (2017) as particular cases.
There are two results worth a comment: the heterogeneous lines of length three,
and the heterogeneous odd cycles.
Notice that, for heterogeneous lines of length three to be pairwise stable, it must
be that the two nodes of the same type are consecutive. The intuition for this result
is as follows: if the two nodes of the same type are not consecutive, the two existing
links are expensive, which requires c ≤ 1/6. However, being of the same type, forthe two peripheral nodes it is profitable to connect themselves if c ≤ 1/6, which is
automatically implied by the previous condition; that is, in a line of length three, it
is not possible to sustain two expensive links while preventing a cheap one.
On the other hand, when the two nodes of the same type are consecutive in theline of length three, there are a cheap link and an expensive link. Since the two
peripheral nodes are different, the structure is stable if c = 1/6, because that is thelimiting value to simultaneously sustain the existing expensive link and prevent theformation of the cycle by adding an expensive link. Also, since the expensive link ismaintained, so is the cheap existing one.
With respect to the heterogeneous odd cycles, the pairwise-stability conditionis the same regardless of the number of nodes of each type and their positions in
the cycle: since the cycle is odd, it is not profitable to add any link and so the
only concern is to sustain the existing ones. In this structure, any pair of players
involved in a link break would see themselves at the extremes of an odd line, andthis symmetry explains why sustaining one expensive link in the cycle is not lessdemanding than sustaining more than one expensive link.
3.1.2

Networks

Theorem 2 (Pairwise stability of the empty network).
The empty network is pairwise stable if c ≥ 12 .
Proof.
In the Appendix.
This result coincides with Gauer and Hellmann (2017): whereas in our setup the
empty network may include nodes of different types, preventing the formation ofa cheap link automatically prevents the formation of an expensive link, and so therelevant cost is c only.
Theorem 3 (Pairwise stable networks including only pairs and isolated nodes).
(i) Networks consisting of the union of one isolated node and homogeneous pairs
such that at least one is of the same type as the isolated, are pairwise stable if1< c ≤ 12 .
6
11

(ii) Networks consisting of the union of one isolated player and homogeneous pairs
such that all are of the sametype and different from the isolated, are pairwise
stable if c ≤ 12 and c > max 16 , c .
(iii) Networks consisting of the union of homogeneous pairs, regardless of theirtypes, and two isolated nodes such that each one of them is of a different type
are pairwise stable if 61 < c ≤ 12 ≤ c. Additionally, if c = 21 , then there canexist two isolated nodes of the same type or three or more isolated nodes ofany type.
(iv) Networks consisting of the union of pairs such that at least one is heterogeneousand one isolated node are pairwise stable if 16 < c < c ≤ 12 . Additionally, if
1< c < c = 12 , then there can exist two isolated nodes such that each one of6them is of a different type.
Proof.
In the Appendix.
Figure 1 depicts some of the equilibrium networks derived in Theorem 3.

Figure 1: Stable networks with only pairs and isolated nodes.
The first statement of Theorem 3 contains the result in Gauer and Hellmann(2017) as a particular case, while it also allows for the existence of homogeneous
pairs different from the isolated player. However, in the second statement all pairs
are homogeneous and different from the isolated node, which is reflected in thestability condition: to prevent the link between an isolated node and a pair of thesame type, 1/6 < c is sufficient, whereas to prevent the link between an isolated
node and a pair of different type, the sufficient condition becomes 1/6 < c.
An important difference with Gauer and Hellmann (2017) is that there can be
two isolated nodes rather than one in a network with only homogeneous pairs fordifferent values of the costs within certain intervals. Of course, this happens because
the condition to sustain the homogeneous pairs depends on c and the condition toprevent the link between the two isolated nodes that are of different types depends
on c. However, to allow for the existence of two or more isolated nodes of the same
type, we need to fix the cheap cost at the particular limiting value 1/2.
Finally, it is also possible to sustain heterogeneous pairs with one isolated nodefor different values of the costs within certain intervals. Nonetheless, in order to allow
12

for two isolated nodes of different types to exist in this structure, the expensive costneeds to take the particular limiting value 1/2. Notice that it is impossible to allow
for three or more isolated nodes while sustaining heterogeneous pairs, because inthat case it would be impossible to prevent the link between two isolated nodes ofthe same type.
Theorem 4 (Pairwise stable networks that include cycles).
(i) Networks consisting of the union of homogeneous odd cycles, regardless of their
1
players, and two isolated nodes, one of each type, aretypes, with at most 2c
1
pairwise stable if c ≤ 6 and c ≥ 21 .
(ii) Networks consisting of the union of homogeneous cycles, regardless of their
1
types, with at most 2c
players, and either homogeneous pairs, regardless of theirtypes, or at most one isolated player are pairwise stable if c ≤ 61 . Additionally,
if c = 61 and given that there is no isolated player, then there can also behomogeneous lines of length three, regardless of their types.
(iii) Networks consisting of the union of homogeneous cycles, regardless of their
1
types, with at most 2c
players, and pairs such that at least one of them isheterogeneous are pairwise stable if c ≤ 16 and c ≤ 12 . Additionally, if c = 61 ,then there can also be homogeneous lines of length three, regardless of theirtypes.
(iv) Networks consisting of the union of homogeneous odd cycles, regardless of their
1
types, with at most 2c
players, one isolated player and homogeneous pairs suchthat all are of the same type and different from the isolated node are pairwise
stable if c ≤ 16 < c. Additionally, if c = 16 , then there can also be homogeneouslines of length three such that all are of the same type and different from theisolated node.
(v) Networks consisting of the union of odd cycles such that at least one is hetero1
1
geneous, with at most 2c
players in the homogeneous cycle(s) and at most 2c
players in the heterogeneous cycle(s), and either pairs or at most one isolated
player are pairwise stable if c ≤ 61 .
1(vi) Networks consisting of the union of odd cycles, with at most 2c
players in thehomogeneous cycle(s) and 3 players in the heterogeneous cycle(s), and one
heterogeneous line of length three are pairwise stable if c = 61 . Additionally, if
1< c, then there can also be pairs.
15

Proof.
In the Appendix.
Figure 2 depicts some of the equilibrium networks derived in Theorem 4.

13

Figure 2: Stable networks including odd cycles.
Notice that the first statement of Theorem 4 cannot be obtained in Gauer andHellmann (2017), because if a homogeneous odd cycle is sustainable, then the two
isolated nodes of the same type will form a pair. However, if the isolated nodes
are of different types, the sufficient condition to sustain the homogeneous odd cycle
depends on c whereas the sufficient condition to prevent the formation of a heterogeneous pair depends on c.
The second statement of Theorem 4 includes the results in Gauer and Hellmann(2017) as a particular case, while it is not restricted to structures in which all pairs
and cycles are of the same type (just being homogeneous is enough).
The lines of length three deserve further attention, as their existence in the
pairwise stable network structures limits the characteristics of the other components.
In particular, homogeneous lines can co-exist with isolated nodes of different type,pairs, other homogeneous lines and homogeneous cycles with three players, but notwith heterogeneous cycles. On the other hand, heterogeneous lines cannot co-exist
with other lines or isolated players, but they can with pairs and cycles. Moreover,they limit the number of players in the heterogeneous cycles to three, but they do
not limit the number of players in the homogeneous cycles.
Finally, it is important to remark that there are multiple equilibria for certain
parametric conditions. For example, if c ≤ 1/6 ∧ 1/6 < c ≤ 1/2, a network
structure with the characteristics defined in Theorem 2 (ii) is pairwise stable, andso is a network structure with the characteristics defined in Theorem 3 (iii). Our
results simply state that the two configurations are pairwise stable, but nothing issaid about which configuration would be finally reached, or with which probability.
14

3.2

Cheap Links Between Players of Different Types

In this subsection, we present the sufficient conditions for a network to be pairwise
stable when links between players of different types are cheaper in the overall.
Recall from the previous section that this is the case when the state of the world
is B if and only if cℓ,d − cℓ,a < cP,a − cP,d ; that is, when projects require both skills tobe developed and the complementarities are strong enough to make the difference inthe cost of running the project more than offset the difference in the cost of linkage.
As before, a component is homogeneous if all players in it are of the same typeand heterogeneous otherwise.
The lemma below deals with the stability of individual components.
3.2.1

Components

Lemma 3. Sufficient conditions for components to be pairwise stable:(i) The homogeneous pair is pairwise stable if c ≤ 12 .
The heterogeneous pair is pairwise stable if c ≤ 12 .
(ii) The homogeneous line of length three is pairwise stable if c = 16 .
The heterogeneous line of length three such that two nodes of the same typeare not consecutive is pairwise stable if c ≤ 16 ≤ c.
(iii) A star with n leaves, all of the same type and different from the root,26 is1
n−1
pairwise stable if c ≤ n(n+1)
and c ≥ 2(n+1).
(iv) Odd lines such that all nodes in odd positions are of one type and all nodes ineme <even positions are of the other type are pairwise stable if c ≤ (m − m)/2m
1/2m ≤ c.27
1(v) The odd cycles with at most 2c
players, regardless of whether they are homogeneous or heterogeneous, are pairwise stable if c ≤ 16 .

(vi) Star-like trees such that nodes of different types alternate and all the branches
1have the same, odd number of nodes are pairwise stable if c ≤ −1+4|L|
2 <
1
≤ c.
2+4|L|(vii) A succession of L ≥ 2 stars each with n ≥ 2 leaves, connected such that the
hubs k and k + 1 share a common leaf for k = {1, ..., L − 1} and so that all
the hubs are of the same type and different from the leaves is pairwise stable1
if c ≤ (1+n(|L|−1))(1+n|L|)< 1−2|L|+n|L|≤ c.
2+2n|L|26

The heterogeneous line of length three such that two nodes of the same type are not consecutive
is a particular case of this star.
27
The heterogeneous line of length three such that two nodes of the same type are not consecutive
is a particular case.

15

(viii) An expanded star in which every player {1, ..., L} connected to the root by alink, all of them of the same type and different from the root itself, has thesame number of exclusive neighbors n − 1, all of the same type as the root, is1< 1−2|L|+n|L|≤ c.
pairwise stable if c ≤ (1+n(|L|−1))(1+n|L|)
2+2n|L|
Proof.
In the Appendix.
Figure 3 depicts some of the pairwise stable components derived in Lemma 3.

Figure 3: Some non-equitable pairwise stable components
There are other bipartite graphs that are stable. Their complete characterizationis still Work in Progress.

4

Conclusions

This paper contributes to the literature of pairwise stable bargaining networks. We
study a two-stage infinite-horizon bargaining game with two types of players andtwo states of the world, both of which are exogenously given. In the first stage,
players form links whose overall cost depends on the players’ types and the state of
the world. In the second stage, players bargain à la Manea according to a uniform
matching technology over the links they formed in the previous stage.
In our framework, components are homogeneous if they are composed only of
players of the same type and are heterogeneous otherwise. Some of our equilibriumarchitectures are akin to those in Gauer and Hellmann (2017) in that we also obtainstable odd-cycles and pairs of players, both for homogeneous as well as for heterogeneous components. In this context, their work can be seen as a special case of ours
since they only consider a single type of player and therefore a single cost.
16Our main results are related to stable components with bipartite structures suchas stars, odd lines and star-like trees. These architectures are feasible in contexts
when complementarities among players of different types are sufficiently strong, withno two players of the same type having a link amongst them. Our results contrast
with those of Gauer and Hellmann (2017) who obtain only one stable bipartite
structure that consists of a line of three: in our setup, any odd-length line withinterspersed heterogeneous players are pairwise stable. Furthermore, the line they
get is only stable for one value of the cost, whereas our bipartite structures are stablefor certain cost intervals.
Future research could focus along two lines that we find interesting. The firstone consists in different kinds of projects coexisting, some requiring a single skill
and others requiring both. In this case, it would be meaningful to model a search
process in which players would try to find their best match. A second line is to extend
our work to stationary and non-stationary bargaining with three or more types ofplayers. In the stationary case, it is possible to consider a similar framework in which
projects require either one or two skills but the complementarities depend on the
distance between groups. For the non-stationary case, one could think of firms in
different sectors interacting that could potentially collude and then withdraw fromthe collusion market.28

A

Appendix

In the proofs below we do heavy use of two lemmas in Gauer and Hellmann (2017):
Lemma A.1 (Gauer and Hellmann, 2017). If a network g is pairwise stable and thealgorithm A provides (r1 , x1 , M1 , L1 , N1 , g1 ), i.e. s = 1, such that r1 ∈ (0, 1), thenfor all i, j ∈ M1 it is1vi∗ (g + ij) = vj∗ (g + ij) = .
2
Further, if the player set N = {1, ..., n} is extended by an isolated player n + 1 such∗(g +that the network g remains unchanged, it similarly is vi∗ (g + i(n + 1)) = vn+1
i(n + 1)) = 1/2.
Lemma A.2 (Gauer and Hellmann, 2017). If a network g is pairwise stable and thealgorithm A provides (r1 , x1 , M1 , L1 , N1 , g1 ), i.e. s = 1, such that r1 ∈ (0, 1), thenfor all j ∈ L1 , i ∈ M1 and kl ∈ g it isvj∗ (g − kl) ≥1≥ vi∗ (g − kl).
2

Proof. Lemma 1(i) Pairs: according to the definition of Pairwise Stability, we only need to findthe condition for the existing link to be kept.
28

This idea is inspired by Elliott and Galeotti (2019), who study the case of supermarkets withdifferent stores weakly competing for consumers.

17

Homogeneous: the cost for each player to sustain the link is c. When broken,
they become isolated and get 0. Then, 1/2 − c ≥ 0 ⇔ c ≤ 1/2. Therefore, thehomogeneous pair is pairwise stable if c ≤ 12 .
Heterogeneous: the cost for each player to sustain the link is c. When broken,
they become isolated ad get 0. Then, 1/2 − c ≥ 0 ⇔ c ≤ 1/2. Therefore, theheterogeneous pair is pairwise stable if c ≤ 21 .
(ii) Lines of length three: according to the definition of Pairwise Stability, we needto check that the two links connecting each peripheral player with the central
node are kept, and that the peripheral players do not want to create a linkamong themselves.
Homogeneous: the cost for each player to sustain a link is c. When broken,
the central node becomes part of a pair, receiving the gross payoff 1/2, and the
peripheral node becomes isolated, getting 0. Then, for the link to be sustained:· central node: 32 − c ≥ 12 ⇔ c ≤ 16 .
· peripheral node: 13 − c ≥ 0 ⇔ c ≤ 13 .
Thus, the link is sustained if c ≤ 1/6.
The cost for each peripheral player to form a new link is c. Then, as thepayoffs are the same for both peripheral nodes,· create if 12 − c > 31 ⇔ c < 16 .
Thus, the link is not created if c ≥ 1/6.
Therefore, the homogeneous line of length three is pairwise stable if c = 61 .
Heterogeneous: the cost for players of the same type to sustain a link is c, whilefor players of different types it is c. When broken, the central node becomespart of a pair, receiving the gross payoff 1/2, and the peripheral node becomes
isolated, getting 0. Then,• central node with peripheral node of the same type:· central node: 23 − c ≥ 12 ⇔ c ≤ 16 .
· peripheral node: 13 − c ≥ 0 ⇔ c ≤ 31 .
The link is sustained if c ≤ 1/6.
• central node with peripheral node of different type:· central node: 32 − c ≥ 12 ⇔ c ≤ 16 .
· peripheral node: 13 − c ≥ 0 ⇔ c ≤ 31 .
The link is sustained if c ≤ 1/6.
The cost for each peripheral player to form a new link is c, in which case an
odd cycle is created and each player receives the gross payoff 1/2. Then, as
the payoffs are the same for both peripheral nodes,
18

· create if 12 − c > 13 − ⇔ c < 16 .
Thus, the link is not created if c ≥ 1/6.
Therefore, the heterogeneous line of length three such that two nodes of thesame type are consecutive is pairwise stable if c = 16 .
(iii) Odd cycles: according to the definition of Pairwise Stability, we need to findthe conditions for each node to keep the links with its two neighbors, and forno additional link to be created.
Homogeneous: the cost for each player to sustain a link is c. If the link isbroken, each node ends up at one of the extremes of an odd line of length m,receiving the gross payoff (m − 1)/2m. Then,
1
m−1
1
−c≥
⇔c≤
2
2m
2m
As m ≥ 3, c ≤ 16 .
Notice that, after creating a link between two nodes of the cycle that wereunconnected, the gross payoff for each player remains 12 , as the cycle is odd.
Then, these players were strictly better off without the additional link for anyc > 0.
1players is pairwise
Therefore, the homogeneous odd cycle with at most 2c
1
stable if c ≤ 6 .

Heterogeneous: the cost for players of the same type to sustain a link is c,while for players of different types it is c. If the link is broken, each node ends
up at one of the extremes of an odd line of length m, receiving the gross payoff(m − 1)/2m. Sustaining links between players of different types automaticallyguarantees that links between players of the same type are sustained as well.
Also, notice that in heterogeneous odd cycles there is always at least one linkthat costs c for the players involved. Then,
m−1
1
1
−c≥
⇔c≤
.
2
2m
2m
As m ≥ 3, c ≤ 16 .
Again, after creating a link between two nodes of the cycle that were unconnected, the gross payoff for each player remains 21 , as the cycle is odd. Then,these players were strictly better off without the additional link for any c > 0.
1
Therefore, the heterogeneous cycle with at most 2c
players is pairwise stable1
if c ≤ 6 .

Notice that the pairwise stability condition does not depend on the number ofnodes of each type or on their positions within the heterogeneous cycle.

19

Proof. Lemma 2(i) Heterogeneous lines of length three such that two nodes of the same type are
not consecutive.
In this structure, every existing link costs c to each player. If any link isbroken, the central player becomes part of a pair, receiving the gross payoff
1/2, and the peripheral player becomes isolated, getting the payoff 0. Then,· central node: 23 − c ≥ 21 ⇔ c ≤ 16 .
· peripheral node: 13 − c ≥ 0 ⇔ c ≤ 13 .
The links are sustained if c ≤ 1/6.
The cost for each peripheral player to form a new link is c, in which case an
odd cycle is created and each player receives the gross payoff 1/2. Then, as
the payoffs are the same for both peripheral nodes,· create if 12 − c > 31 ⇔ c < 16 .
The link is not created if c ≥ 1/6, but this condition contradicts c ≤ 1/6, andso the structure is not pairwise stable.
(ii) Lines of length four or above.
We first focus on the even lines. In these structures, each node receives thegross payoff 12 . Consider the node connected to a peripheral player. It has tosustain two links in the even line, whereas if it kept the connection with theperipheral player only, it would still receive the gross payoff 12 while sustaining
just one link, which makes it strictly better off for any positive value of thecost.
We now focus on the odd lines with five or more nodes, m. In these structures,the set M is composed of the odd nodes, so |M | = (m + 1)/2. Therefore,|L| = (m − 1)/2 and r = |L|/|M | = (m − 1)/(m + 1) < 1. Accordingly, thegross payoff of the odd nodes is xodd = r/(1 + r) = (m − 1)/2m and the gross
payoff of the even nodes is xeven = 1/(1 + r) = (m + 1)/2m.
Consider the link between a peripheral player and the subsequent node. If
it breaks, the peripheral node becomes isolated, so getting the payoff 0, andthe interior node becomes the extreme of an even line, so receiving the gross
payoff 12 . The link with a peripheral player of the same type is sustained if(m + 1)/2m − c ≥ 1/2 ⇔ c ≤ 1/2m (and if c ≤ 1/2m when the peripheral
player is of different type).
Consider now the link between two interior nodes. When it breaks, the nodeoccupying the even position in the odd line becomes the extreme node of aneven line, receiving the gross payoff 1/2, whereas the node occupying the odd
position in the odd line turns into the extreme node of a new odd line oflength m
e < m, getting the gross payoff (me − 1)/2m.
e When the two interior
20

nodes are of the same type, the even node keeps the link if (m + 1)/2m − c ≥1/2 ⇔ c ≤ 1/2m, whereas the odd node keeps the link if (m − 1)/2m −e − 1)/2me ⇔ c ≤ (m − m)/2me
m.
e Thus, the link is sustained if c ≤c ≥ (m1 m−me
min 2m , 2mm. Analogously, when 
the two interior nodes are of different
e
e
1 m−m
, 2mm
.
types, the link is sustained if c ≤ min 2meTake an odd line such that the two peripheral nodes are of the same type.
If the line connecting the two peripheral nodes were created, an odd cycle
would result, implying that each node receives the gross payoff 1/2. Thus,
the link will not be created if c ≥ 1/2m. If the line is homogeneous, keeping
all the links requires c ≤ (m − m)/2me
me < 1/2m (the last strict inequality
coming from the fact that m ≥ 5), which contradicts c ≥ 1/2m.
If the line is 1 m−
me, which, 2mmheterogeneous, keeping all the links requires c < c ≤ min 2mecontradicts c ≥ 1/2m.
Take an odd line such that the two peripheral nodes are of different types.
Notice that it is always possible to connect one of the peripheral nodes with aninterior odd node of the same type. If such a link were created, the resulting
structure would be an odd cycle connected to an even line and each player
would get the gross payoff 1/2. Thus, such a link will not be created if c ≥1/2m. As thisis by definition heterogeneous, keeping all links requires 1 linem−mec < c ≤ min 2m , 2mm, which contradicts c ≥ 1/2m.
e(iii) Even cycles.
In these structures, each player receives the gross payoff 1/2. However, if a linkis broken, the resulting structure is an even line and, again, each player getsthe gross payoff 1/2. Therefore, the players that broke the link are strictly
better off in the line, as they sustain a single link rather than two for any
strictly positive value of the costs.

Proof. Theorem 2
Suppose that there are three or more nodes. In that case, there will always be atleast two nodes of the same type. Then, c ≥ 1/2 is sufficient to prevent the creationof any link: preventing the connection between two nodes of the same type also
prevents the connection between two nodes of different types, as the former link ischeaper than the latter.
Proof. Theorem 3
Notice the following:(a) Two pairs never create a link to connect themselves. The reason is that thegross payoff of the nodes creating the link remains 1/2, so the new structure
makes them strictly worse off for any strictly positive value of the costs, as
they have to sustain two links rather than one.
21

(b) To prevent the formation of a link between an isolated node and the extreme ofa pair that is of the same type, 1/6 < c is required (as for the node belonging
to the pair is not profitable to become the central node of a line of length three
if 1/2 > 2/3 − c ⇔ c > 1/6). Analogously, to prevent the formation of a link
between an isolated and the extreme node of a pair that is of different type,
1/6 < c is required.
Consider a network with the characteristics specified in (i). The condition tosustain the homogeneous pairs is c ≤ 1/2, as it was stated in Lemma 1. To preventthe formation of a link between the isolated node and a pair that is of the same
type, 1/6 < c is required. Since c > c, the previous condition also guarantees that alink between the isolated node and a pair that is of different type will not be formed.
The intersection of all the conditions is 61 < c ≤ 21 ∧ c > c, which makes the network
pairwise stable.
Consider a network with the characteristics specified in (ii). Again, the condition
to sustain the homogeneous pairs is c ≤ 1/2. However, since there are no pairs of
the same type as the isolated node, only 1/6 < c is required to prevent the formationof links. As by assumption c > c, the intersection of all the conditions is c ≤ 12 ∧c > max 16 , c , which makes the network pairwise stable.
Consider a network with the characteristics specified in the first part of statement(iii). Again, the condition to sustain the homogeneous pairs is c ≤ 1/2. As in (i),1/6 < c is sufficient to prevent the formation of a link between an isolated node
and a pair of the same type, and it also automatically prevents the creation of alink between an isolated node and a pair of different type. Finally, to prevent theformation of a link between the two isolated nodes that are of different types, 1/2 ≤ cis required. The intersection of all conditions is 16 < c ≤ 12 ≤ c ∧ c > c, which makes
the network pairwise stable.
Consider the particular case 16 < c = 12 < c. c = 1/2 is the intersection betweenc ≤ 1/2, sufficient to sustain homogeneous pairs, and c ≥ 1/2, sufficient to preventthe link between two isolated nodes of the same type. Plus, as c > c, c > c ≥ 1/2
also prevents the link between two isolated nodes of different types (notice that,whenever there are three or more isolated nodes, there are at least two of them of
the same type).
Finally, consider a network with characteristics specified in the first part of statement (iv). In this case, the condition to sustain the heterogeneous pair(s) is c ≤ 1/2,
which also sustains the homogeneous pairs, if there is any. Notice that, as there is
at least one heterogeneous pair, there is always a node of the same type as theisolated that belongs to a pair. The link between these two nodes is prevented if
1/6 < c (which is also sufficient to prevent the link between the isolated node and anode of different type that belongs to a pair). The intersection of all conditions is1< c < c ≤ 12 , which makes the network pairwise stable.
6
Consider the particular case 61 < c < c = 12 . c = 1/2 is the intersection betweenc ≤ 1/2, sufficient to sustain heterogeneous pairs, and c ≥ 1/2, sufficient to preventthe link between two isolated nodes of different types, which allows to introduce
one more isolated node different from the previous one. Notice that introducing
one more isolated node of the same type is not pairwise stable: as c ≤ 1/2, a link22

between them will be created.
Proof. Theorem 4
Recall from the proof of Theorem 3 that two pairs do not create a link among
themselves; that 1/6 < c is sufficient to prevent the formation of a link between an
isolated node and the extreme of a pair that is of the same type; and that 1/6 < cis sufficient to prevent the formation of a link between an isolated node and theextreme of a pair that is of different type.
Also, notice that:(a) An odd cycle never creates a link with another structure, including an isolatednode, because the player in the cycle creating such a link keeps receiving thegross payoff 1/2 while paying to sustain three links rather than two.
(b) A link between a homogeneous line of length three and an isolated node ofdifferent type can be prevented if 1/6 = c < c. If the line is either heterogeneous or homogeneous but of the same type as the isolated node, the creationof a link with the isolated player cannot be prevented. The reason is that thelink between an isolated node and the extreme of a length-3 line that is of
the same type is not created if c > 1/6. In the former case, the homogeneousline is sustained if c = 1/6, which contradicts c > 1/6. In the latter case, theheterogeneous line is sustained if c = 1/6, which again contradicts c > 1/6
because c > c by assumption.
(c) A pair and a length-3 line such that they have extreme nodes of the same type
do not create a link if c > 1/15. Analogously, a pair and a length-3 line suchthat they do not have extreme nodes of the same type do not create a link if
c > 1/15. Also, notice that the central node of a line of length three does notcreate a link with a pair for any strictly positive level of the costs, as its gross
payoff remains invariant after the creation of such a link.
(d) Two homogeneous length-3 lines of the same type do not create a link if
c ≥ 1/6; analogously, two homogeneous length-3 lines of different types do
not create a link if c ≥ 1/6. On the contrary, a link between a heterogeneous
length-3 line and another length-3 line cannot be prevented. The reason is thata heterogeneous line always has one extreme that can connect with an extremeof the same type of another line (regardless of whether this line is homogeneousor heterogeneous). This link is not created if c ≥ 1/6, but the heterogeneousline is sustained if c = 1/6, which contradicts the previous condition because
c > c by assumption.
Consider a network with the characteristics specified in (i). Homogeneous odd
cycles with at most 1/2c players are stable if c ≤ 1/6. When adding two isolated
nodes, each of a different type, the whole network is pairwise stable by just preventing the link between them, as the cycles do not connect either with an isolated nodeor among themselves. Then, the network is pairwise stable if c ≤ 16 ∧ c ≥ 12 . Notice23that either pairs or lines of length three cannot fit in this network, as a link with
the isolated node of the same type as the extreme node is not created if c > 1/6,
which makes the cycles unstable.
Consider a network with the characteristics specified in the fist part of statement (ii). Homogeneous odd cycles with at most 1/2c players are stable if c ≤ 1/6.
This condition automatically allows to add to the network either one isolated nodeor homogeneous pair(s): cycles do not create links with any other component, andc ≤ 1/6 is stricter that c ≤ 1/2, which is the sufficient condition to sustain homogeneous pairs. Then, a network with these components is pairwise stable if c ≤ 16 ∧c > c. Note that if there was at least one homogeneous pair of the same type as theisolated node, they would connect as c ≤ 1/6. See case (iv) for the pairwise stableconditions when all pairs are homogeneous and different from the isolated node.
Consider the particular case c = 16 < c. If the network is only composed of homogeneous odd cycles and homogeneous pairs, then there can also be homogeneouslines of length three: cycles and pairs keep being stable, lines are sustained andthey do not create links either between themselves (c = 1/6 ≥ 1/6) or with pairs(1/15 < c = 1/6 < c). However, if the network is composed of homogeneous odd
cycles and one isolated node, homogeneous length-3 lines in general do not fit: aslong as there is one line of the same type as the isolated player, a link between themcannot be prevented (as c = 1/6 contradicts c > 1/6). See case (iv) for the pairwise
stability conditions when all lines are homogeneous and different from the isolated
node.
Consider a network with the characteristics specified in the first part of statement(iii). Homogeneous odd cycles with at most 1/2c players are stable if c ≤ 1/6, andheterogeneous pairs are stable if c ≤ 1/2 (which makes homogeneous pairs alsosustainable, as c > c). Then, the network is pairwise stable if c ≤ 16 ∧ c < c ≤ 21 .
Consider the particular case 16 = c < c ≤ 21 . In this case, homogeneous lines oflength three also fit in this network: cycles and pairs keep being stable, lines are
sustained and they do not create links either between themselves (c = 1/6 ≥ 1/6)
or with pairs (1/15 < c = 1/6).
Consider a network with the characteristics specified in the first part of statement(iv). Homogeneous odd cycles with at most 1/2c players are stable if c ≤ 1/6, andso are homogeneous pairs as c ≤ 1/6 is stricter than c ≤ 1/2. If c > 1/6, given that
all homogeneous pairs are of the same type, an isolated node of different type fits,
since c > 1/6 prevents any link between these pairs and the isolated player. Then,the network is pairwise stable if c ≤ 16 < c. Notice that if there was at least one
heterogeneous pair or one homogeneous pair of the same type as the isolated node,
the network would not be pairwise stable because the condition to prevent the link
between one of these pairs and the isolated player is c > 1/6, which contradicts thecondition to sustain the cycles.
Consider the particular case c = 16 < c. If this is the case, homogeneous length-3
lines such that all are of the same type and different from the isolated node also fit:
cycles and pairs keep being stable, lines are sustained, neither lines nor pairs create alink with the isolated player as c > 1/6, lines do not create links between themselvesbecause c = 1/6 ≥ 1/6, and lines and pairs do not connect because 1/15 < c = 1/6.
24

Consider a network with the characteristics specified in (v). Heterogeneous odd
cycles with at most 1/2c players are stable if c ≤ 1/6, and so are homogeneous odd
cycles with at most 1/2c players since c > c. This condition automatically allows to
add to the network either one isolated node or pair(s), which can be homogeneous
and/or heterogeneous: cycles do not create links with any other component andc ≤ 1/6 is stricter than both c ≤ 1/2 and c ≤ 1/2, which are the sufficient conditions
to sustain heterogeneous and homogeneous pairs, respectively. Then, a network withthese components is pairwise stable if c < c ≤ 16 . Notice that, for these parametricconditions, a link between a pair and an isolated node cannot be prevented asc < c ≤ 1/6 contradicts both c > 1/6 and c > 1/6, so these components cannot
co-exist in this network.
Finally, consider a network with the characteristics specified in the first part ofstatement (vi). Heterogeneous odd cycles with 3 players are stable if c = 1/6, which
also sustains the heterogeneous line of length three. Since c > c by assumption,
homogeneous cycles with at most 1/2c are also allowed, so the network is pairwise
stable if c < c = 61 . Notice that more length-3 lines do not fit: as c < 1/6, theirextremes would always connect.
1
Consider the particular case 15< c < c = 16 . Then, pairs homogeneous and/or
heterogeneous also fit: c = 1/6 is stricter than both c ≤ 1/2 and c ≤ 1/2, so allowing
for pairs, and 1/15 < c prevents the creation of links between the heterogeneous line
and a pair. However, since 1/15 < c, the number of players of the homogeneous odd
cycle(s) can never be larger than seven.
Proof. Lemma 3(i) Pairs: according to the definition of Pairwise Stability, we only need to findthe condition for the existing link to be kept.
Homogeneous: the cost for each player to sustain the link is c. When broken,
they become isolated and get 0. Then, 1/2 − c ≥ 0 ⇔ c ≤ 1/2. Therefore, thehomogeneous pair is pairwise stable if c ≤ 12 .
Heterogeneous: the cost for each player to sustain the link is c. When broken,
they become isolated ad get 0. Then, 1/2 − c ≥ 0 ⇔ c ≤ 1/2. Therefore, theheterogeneous pair is pairwise stable if c ≤ 12 .
(ii) Lines of length three: according to the definition of Pairwise Stability, we needto check that the two links connecting each peripheral player with the central
node are kept, and that the peripheral players do not want to create a linkamong themselves.
Homogeneous: the cost for each player to sustain a link is c. When broken,
the central node becomes part of a pair, receiving the gross payoff 1/2, and the
peripheral node becomes isolated, getting 0. Then, for the link to be sustained:· central node: 32 − c ≥ 21 ⇔ c ≤ 16 .
· peripheral node: 13 − c ≥ 0 ⇔ c ≤ 13 .

25

Thus, the link is sustained if c ≤ 1/6.
The cost for each peripheral player to form a new link is c. Then, as thepayoffs are the same for both peripheral nodes,· create if 12 − c > 13 ⇔ c < 16 .
Thus, the link is not created if c ≥ 1/6.
Therefore, the homogeneous line of length three is pairwise stable if c = 61 .
Heterogeneous: the cost for players of the different types to sustain a link isc. When broken, the central node becomes part of a pair, receiving the gross
payoff 1/2, and the peripheral node becomes isolated, getting 0. Then, for thelink to be sustained:· central node: 32 − c ≥ 12 ⇔ c ≤ 16 .
· peripheral node: 13 − c ≥ 0 ⇔ c ≤ 13 .
Thus, the link is sustained if c ≤ 1/6.
The cost for each peripheral player to form a new link is c, in which case an
odd cycle is created and each player receives the gross payoff 1/2. Then, as
the payoffs are the same for both peripheral nodes,· create if 12 − c > 13 ⇔ c < 16Thus, the link is not created if c ≥ 1/6.
Therefore, the heterogeneous line of length three such that two nodes of thesame type are not consecutive is pairwise stable if c ≤ 16 ≤ c.
(iii) Stars with n ≥ 2 leaves, all of the same type and different from the root.
To prove that the algorithm finishes in one step, we notice that there are only
two options: root ∈ M and root ∈/ M . If root ∈ M , then |L| = n and sor = n > 1. If root ∈/ M , since the only neighbor of any leaf is the root, theshortage ratio decreases as the cardinality of M increases. Therefore, |M | = n,
|L| = 1 and r = 1/n < 1.
Notice that all the links of this structure are cheap. When an existing link
breaks, using an analogous argument, the algorithm finishes in one step forthe non-singleton component with |M | = n − 1 and |L| = 1. The leaf that
becomes isolated gets payoff 0. Then, for the link to be sustained:n
1· root: n+1− c ≥ n−1
⇔ c ≤ n(n+1).
n11· leaf: n+1− c ≥ 0 ⇔ c ≤ n+1.
1.
Since all the links are qualitatively equal, all links are sustained if c ≤ n(n+1)

Since there are links connecting each node in |M | with the single node in |L|,
the only links that can be formed are among leaves. By Lemma A.1, each leaf
gets the gross payoff 1/2 and so the link is created if
26

1
n−1
⇔ c < 2(n+1).
· 21 − c > n+1
n−1
Thus, the link is not created if c ≥ 2(n+1). Therefore, this structure is pairwise1
n−1≤ 2(n+1)≤ c.
stable if c ≤ n(n+1)(iv) Odd lines such that nodes of different types alternate: given the alternating
types of the nodes, all the existing links are cheap. Furthermore, the creationof odd cycles implies establishing an expensive link, which has to be deterred
for the structure to be pairwise stable.29
Let us focus on the odd lines with five or more nodes, m ≥ 5, as the line ofthree nodes has been discussed previously. In these structures, the set M iscomposed of the odd nodes, so |M | = (m + 1)/2. Therefore, |L| = (m − 1)/2
and r = |L|/|M | = (m − 1)/(m + 1) < 1. Accordingly, the gross payoff of the
odd nodes is xodd = r/(1 + r) = (m − 1)/2m and the gross payoff of the evennodes is xeven = 1/(1 + r) = (m + 1)/2m.
Consider the link between a peripheral player and the subsequent node. If
it breaks, the peripheral node becomes isolated, so getting the payoff 0, andthe interior node becomes the extreme of an even line, so receiving the gross
payoff 21 . The link is sustained if (m + 1)/2m − c ≥ 1/2 ⇔ c ≤ 1/2m.
Consider now the link between two interior nodes. When it breaks, the nodeoccupying the even position in the odd line becomes the extreme node of aneven line, receiving the gross payoff 1/2, whereas the node occupying the odd
position in the odd line turns into the extreme node of a new odd line of lengthme < m, getting the gross payoff (me − 1)/2m.
e The even node keeps the link
if (m + 1)/2m − c ≥ 1/2 ⇔ c ≤ 1/2m, whereas the odd node keeps the linke − 1)/2me ⇔ c ≤ (m − m)/2me
m.
e Thus, the link is
if (m − 1)/2m − c ≥ (m1 m−mesustained if c ≤ min 2m , 2mm.
eNotice that, as m ≥ 5, to keep all the links requires c ≤ (m−m)/2me
me < 1/2m.
Regarding the creation of a new link such that an odd cycle results, noticethat only the nodes in odd positions could be benefited by it. For the nodesin even positions, the gross payoff would not change after the creation of thelink, so they would be strictly worse off.
When two nodes occupying odd positions create a link, each one of them getsthe gross payoff 1/2, but such a link is expensive. Then,1⇔ c < 2m
· create if 21 − c > m−1
2m

Thus, the link is not created if c ≥ 1/2m, and the entire structure is pairwise
stable if c ≤ (m − m)/2me
me < 1/2m ≤ c.
(v) Odd cycles: according to the definition of Pairwise Stability, we need to findthe conditions for each node to keep the links with its two neighbors, and forno additional link to be created.
29

Even cycles are never created.

27

Since the cycles are odd, regardless of whether they are homogeneous or heterogeneous, there will be two consecutive nodes of the same type; that is, there
exists at least one expensive link that, if sustained, implies the sustainabilityof the cheap links as well.
If such a link is broken, each node ends up at one of the extremes of an odd
line of length m, receiving the gross payoff (m − 1)/2m. Then,
1
m−1
1
−c≥
⇔c≤
.
2
2m
2m
As m ≥ 3, c ≤ 16 .
After creating a link between two nodes of the cycle that were unconnected,
the gross payoff for each player remains 12 , as the cycle is odd. Then, theseplayers were strictly better off without the additional link for any c > 0.
1
players is pairwise stable if c ≤ 16 .
Therefore, an odd cycle with at most 2c(vi) Star-like trees such that nodes of different types alternate and all the branches
have the same, odd number of nodes:
Let n ≥ 2 be the number of branches and p ≥ 1 be the number of nodes ofdifferent type from the root in each branch. Then, the set |L| = np ≥ 2 iscomposed of all the nodes of different type from the root and the set |M | =|L| + 1 is composed of all the nodes of the same type as the root. Then, thepayoff for each agent in |M | is xM = |L|/(2|L| + 1) and the payoff for eachagent in |L| is xL = (|L| + 1)/(2|L| + 1).

Figure 4: Star-like tree.
As it can be seen in Figure 4, there are two types of links: (a) and (b). If alink of type (a) breaks, the two resulting components are (i) an even line, and(ii) a star-like tree with n − 1 branches of the original length and one branchwith k ∈ [0, p − 1] nodes of type different from the root, each matched by asubsequent node of the same type as the root. If a link of type (b) breaks, the28two resulting components are (i) an odd line of length 2(p − k) + 1, and (ii) astar-like tree with n − 1 branches of the original length and one branch withk ∈ [1, p] nodes of type different from the root such that only the last one is
not matched by a subsequent node of the same type as the root.
If a link of type (a) breaks, the shortage ratio of the first component is r̃(1) = 1,
and so the payoff for the node that is now in the line is x̃L = 1/2. The shortage
ratio of the second component is r̃(2) = ((n − 1)p + k)/((n − 1)p + k + 1) and so
the payoff for the node that remains in the star-like tree component becomesx̃M = ((n − 1)p + k)/(2(n − 1)p + 2k + 1). Then:np+1
1− c ≥ 21 ⇔ c ≤ 2+4np· node in the line: 2np+1· node in the star-like tree:(n−1)p+knp
p−k− c ≥ 2(n−1)p+2k+1⇔ c ≤ (2(n−1)p+2k+1)(2np+1)
= K.
2np+1
Notice that K is a function of k. Then, we need to find the strictest conditionon the costs: the value of k that minimizes K. Since ∂K/∂k < 0, K achieves
its minimum at k = p − 1, and so all links of type (a) are sustained if c ≤1130= −1+4|L|2.
−1+4n2 p2
If a link of type (b) breaks, the shortage ratio of the first component is r̃(1) =2(p − k)/(2(p − k) + 2), and so the payoff for the node that is now in the line
is x̃M = 2(p − k)/(4(p − k) + 2). The shortage ratio of the second componentis r̃(2) = 1 and so the payoff for the node that remains in the star-like treecomponent becomes x̃L = 1/2. Then:2(p−k)(n−1)p+k
np· node in the line: 2np+1− c ≥ 4(p−k)+2⇔ c ≤ (2(p−k)+1)(1+2n)= K̂· node in the star-like tree:np+1
1− c ≥ 12 ⇔ c ≤ 2+4np.
2np+1
Notice that K̂ is a function of k. Then, we need to find the strictest conditionon the costs: the value of k that minimizes K. Since ∂K/∂k > 0, K achieves
1=
its minimum at k = 1, and so all links of type (b) are sustained if c ≤ 2+4np
1
31.
2+4|L|
1
Therefore, no link breaks if c ≤ −1+4|L|2.

Now we need to check that no link is formed. There are 8 possible typesof links that can be formed: (1) between two nodes of different type fromthe root that are in different branches (for example, nodes 19 and 20); (2)between two nodes of different type from the root that are in the same branch(for example, nodes 2 and 10); (3) between two nodes of different types thatare in different branches (for example, nodes 2 and 7); (4) between two nodesof different types that are in the same branch (for example, nodes 6 and 18);(5) between the root and a node of different type (for example, nodes 1 and
1
1
2+4np > −1+4n2 p2 .
(n−1)p+11
31(2(p−1)+1)(1+2n) > 2+4np .

30

2910); (6) between two nodes of the same type as the root that are in different
branches (for example, nodes 6 and 15); (7) between two nodes of the same
type as the root that are in the same branch (for example, nodes 6 and 14);and (8) between the root and a node of the same type (for example, nodes 1
and 9).
Links (1)-(5) will not be formed: the payoff of the nodes belonging to set |L|(that is, all nodes of type different from the root) cannot increase but creating
the link is costly. If any of the other three types formed, the algorithm would
finish in two steps and it would give a payoff of 1/2 for each of the nodes thatcreated the new link. Since in all cases the connecting players belong to theset |M |:np
11⇔ c < 2+4np= 2+4|L|.
· create if 21 − c > 2np+1
1
Thus, the link is not created if c ≥ 2+4|L|.
1
1
Therefore, the entire structure is pairwise stable if c ≤ −1+4|L|
2 < 2+4|L| ≤ c.

(vii) Succession of L ≥ 2 stars each with n ≥ 2 leaves, connected such that the
hubs k and k + 1 share a common leaf for k = {1, ..., L − 1} and so that all
the hubs are of the same type and different from the leaves:
We need to prove first two intermediate results:
Result 1: A structure of two stars connected through one leaf cannot be
stable if each star has a different number of leaves.

Figure 5: Non-symmetric, connected stars.
Without loss of generality, assume that the leaves (including the common leaf
3) of the stars with centers identified by 1 and 2 in Figure 5 are such thatn1 ≥ n2 + 1. In the first step, the algorithm minimizes the shortage ratio by
taking |M1 | = n1 − 1 (that is, the leaves of star 1 excluding the common leaf
3) and |L1 | = 1. This implies that the link between the center 1 and the leaf
3 is a disagreement link, so both players are strictly better off by cutting it.
Result 2: A structure formed by a succession of L ≥ 2 stars each withn ≥ L + 1 leaves cannot be stable if the stars are connected through two or
more leaves.32
32

If L = 2 and n = 2, we have a cycle of 4. In that case, the minimum shortage ratio is 1 and any
pair of players is better off by cutting the link.

30

Figure 6: Stars connected through more than one leaf.
Let L ≥ 2 and n ≥ L + 1. In that case, the sets that minimize the shortage
ratio are |L| = L (that is, the centers of the stars) and |M | = n|L|−(2|L|−1) =(n − 2)|L| + 1 (that is, all the leaves). Consider that the link between 1 and 3
in Figure 6 breaks. The sets |L| and |M | are the same, so the payoffs remain
the same and players 1 and 3 are strictly better off by cutting the link.
We are now ready to derive the conditions for pairwise stability of the structure
consisting of a succession of L ≥ 2 stars each with n ≥ 2 leaves, connected
such that the hubs k and k + 1 share a common leaf for k = {1, ..., L − 1} andso that all the hubs are of the same type and different from the leaves.

Figure 7: Connected stars.
For this structure, the sets |L| and |M | that minimize the shortage ratio are|L| = L (that is, the set of hubs) and |M | = n|L|−(|L|−1) = (n−1)|L|+1 (thatis, the set of leaves). Then, the payoff for each agent in |M | is xM = |L|/(n|L|+1) and the payoff for each agent in |L| is xL = ((n − 1)|L| + 1)/((n|L| + 1)).
As it can be seen in Figure 7, there are two types of links: (a) and (b). If alink of type (a) breaks, the two resulting components are (i) an isolated node,and (ii) a component such that one of the stars has n − 1 leaves and the others
have n leaves. If a link of type (b) breaks, the two resulting components are(i) a component with J ≥ 1 stars such that one of the stars has n − 1 leaves
and the others have n leaves, and (ii) a component with (L − J) stars suchthat all have n leaves.
If a link of type (a) breaks, the shortage ratio becomes r̃ = 1/(n − 1) and thegross payoff for the isolated node is 0 whereas the gross payoff for the node in|L| becomes x̃L = (n − 1)/n. Then:
31

|L|
|L|
− c ≥ 0 ⇔ c ≤ n|L|+1· isolated node: n|L|+1
1· node in |L|: (n−1)|L|+1− c ≥ n−1
⇔ c ≤ n+|L|n2.
n|L|+1n
1
A link of type (a) is sustained if c ≤ n+|L|n2.

If a link of type (b) breaks, the shortage ratio of the first component is r̃(1) =1/(n − 1), and so the payoff for the hub after the link breaks is x̃L = (n − 1)/n.
The shortage ratio of the second component is r̃(2) = (L − J)/(n(L − J) −(L − J − 1)) and so the payoff of the leaf after the link breaks is x̃M =(L − J)/(n(L − J) + 1). Then:1· hub: (n−1)|L|+1− c ≥ n−1
⇔ c ≤ n+|L|n2
n|L|+1
n
|L|
|L|−J
J
· leaf: n|L|+1− c ≥ n(|L|−J)+1⇔ c ≤ (1+n(|L|−J))(1+n|L|)= J.

Notice that J is a function of J. Then, we need to find the strictest condition on the costs: the value of J that minimizes J . Since ∂J /∂J > 0, J
achieves its minimum at J = 1, and so all links of type (b) are sustained if
1.
c ≤ (1+n(|L|−1))(1+n|L|)1.
No link breaks if c ≤ (1+n(|L|−1))(1+n|L|)

Now we need to check that no link is formed. There are 7 possible types oflinks that can be formed: (1) between two leaves exclusive of the same hub(for instance, nodes 6 and 7); (2) between an exclusive leaf and a connecting
leaf that are neighbors of the same hub (for instance, nodes 8 and 9); (3)between two exclusive leaves of different hubs (for instance, nodes 7 and 10);(4) between an exclusive leaf of one hub and a connecting leaf of anotherhub (for instance, nodes 11 and 15); (5) between two connecting leaves (forinstance, nodes 9 and 12); (6) between two hubs (for instance, nodes 1 and 2);and (7) between a hub and an exclusive leaf of some another hub (for instance,
nodes 5 and 17).
Links (6) and (7) will not be formed: the payoff of the hubs, since they are
in set |L|, will not increase while it is costly to create the link. If any of theother five types formed, the algorithm would finish in three steps and it would
give a payoff of 1/2 for each of the nodes that created the new link. Since inall cases the connecting players belong to the set |M |:|L|· create if 21 − c > n|L|+1⇔ c < 1−2|L|+n|L|
2+2n|L|Thus, the link is not created if c ≥ 1−2|L|+n|L|.
2+2n|L|
1
Therefore, the entire structure is pairwise stable if c ≤ (1+n(|L|−1))(1+n|L|)<
1−2|L|+n|L|≤ c.
2+2n|L|(viii) Expanded star in which every player {1, ..., L} connected to the root by a link,
all of them of the same type and different from the root itself, has the same
number of exclusive neighbors n − 1, all of the same type as the root:
32

The set |L| ≥ 2 is composed of the nodes directly connected to the root,
and the set |M | = (n − 1)|L| + 1 is composed of the exclusive neighbors of
the nodes in |L| and the root. Then, the algorithm finishes in one step, theminimum shortage ratio is r = |L|/((n − 1)|L| + 1) and the equilibrium payoffs
are xM = |L|/(n|L| + 1) and xL = ((n − 1)|L| + 1)/(n|L| + 1).

Figure 8: Expanded star.
As it is shown in Figure 8, there are two types of links. If a link of type(a) breaks, the two resulting components are (i) an isolated node, and (ii) a
component such that |L − 1| of the nodes originally in set |L| keep their n − 1
exclusive neighbors and the remaining node now has n − 2 exclusive neighbors.
If a link of type (b) breaks, the two resulting components are (i) a star withn − 1 leaves, and (ii) a component identical to the original one but with |L| − 1
players directly connected to the root instead.
If a link of type (a) breaks, the shortage ratio becomes r̃ = 1/(n − 1) and thegross payoff for the isolated node is 0 whereas the gross payoff for the node in|L| becomes x̃L = (n − 1)/n. Then:|L||L|− c ≥ 0 ⇔ c ≤ n|L|+1· isolated node: n|L|+1
1· node in |L|: (n−1)|L|+1− c ≥ n−1
⇔ c ≤ n+|L|n2.
n|L|+1n
1
A link of type (a) is sustained if c ≤ n+|L|n2.

If a link of type (b) breaks, the shortage ratio for the first component becomesr̃( i) = 1/(n − 1), the shortage ratio for the second component becomes r̃( ii) =(|L| − 1)/((n − 1)(|L| − 1) + 1), and so the gross payoff for the root of thesmall star is (n − 1)/n whereas the gross payoff for the original root becomesx̃L = (|L| − 1)/(n(|L| − 1) + 1). Then:1· root of the small star: (n−1)|L|+1− c ≥ n−1
⇔ c ≤ n+|L|n2
n|L|+1
n

33

|L|
|L|−1
1
− c ≥ n(|L|−1)+1⇔ c ≤ (1+n(|L|−1))(1+n|L|).
· original root: n|L|+1
1
A link of type (b) is sustained if c ≤ (1+n(|L|−1))(1+n|L|).
1.
No link breaks if c ≤ (1+n(|L|−1))(1+n|L|)

Now we need to check that no link is formed. There are 5 possible types oflinks that can be formed: (1) between nodes directly connected to the root(for instance, nodes 2 and 3); (2) between a node directly connected with theroot and an exclusive neighbor of some another player (for instance, nodes 2
and 21); (3) between two exclusive neighbors of the same player (for instance,
nodes 8 and 9); (4) between two exclusive neighbors of different players (forinstance, nodes 7 and 21); and (5) between the root and one exclusive neighbor(for instance, nodes 1 and 9).
Links (1) and (2) will not be formed: the payoff of the player(s) in set |L| will
not increase while it is costly to create the link. If any of the other three types
formed, the algorithm would finish in three steps and it would give a payoffof 1/2 for each of the nodes that created the new link. Since in all cases theconnecting players belong to the set |M |:|L|⇔ c < 1−2|L|+n|L|· create if 12 − c > n|L|+1
2+2n|L|Thus, the link is not created if c ≥ 1−2|L|+n|L|.
2+2n|L|
1<
Therefore, the entire structure is pairwise stable if c ≤ (1+n(|L|−1))(1+n|L|)
1−2|L|+n|L|≤ c.
2+2n|L|

References
Abreu, D. and Manea, M. (2012a). Bargaining and efficiency in networks. Journalof Economic Theory, 147(1):43–70.
Abreu, D. and Manea, M. (2012b). Markov equilibria in a model of bargaining in
networks. Games and Economic Behavior, 75(1):1–16.
Bala, V. and Goyal, S. (2000). A noncooperative model of network formation.
Econometrica, 68(5):1181–1229.
Bloch, F., Dutta, B., and Manea, M. (2019). Efficient partnership formation in
networks. Theoretical Economics, 14(3):779–811.
Corominas-Bosch, M. (2004). Bargaining in a network of buyers and sellers. Journalof Economic Theory, 115(1):35–77.
Dawid, H. and Hellmann, T. (2014). The evolution of r&d networks. Journal of
Economic Behavior & Organization, 105:158–172.
34

Elliott, M. and Galeotti, A. (2019). The role of networks in antitrust investigations.
Oxford Review of Economic Policy, 35(4):614–637.
Elliott, M. and Nava, F. (2019). Decentralized bargaining in matching markets:
Efficient stationary equilibria and the core. Theoretical Economics, 14(1):211–
251.
Galeotti, A. and Goyal, S. (2010). The law of the few. American Economic Review,100(4):1468–92.
Galeotti, A., Goyal, S., and Kamphorst, J. (2006). Network formation with heterogeneous players. Games and Economic Behavior, 54(2):353–372.
Gauer, F. and Hellmann, T. (2017). Strategic formation of homogeneous bargaining
networks. Games and Economic Behavior, 106:51–74.
Goyal, S. and Joshi, S. (2003). Networks of collaboration in oligopoly. Games andEconomic behavior, 43(1):57–85.
Goyal, S. and Moraga-Gonzalez, J. L. (2001). R&d networks. Rand Journal of
Economics, pages 686–707.
Jackson, M. O. and Wolinsky, A. (1996). A strategic model of social and economic
networks. Journal of economic theory, 71(1):44–74.
Kranton, R. E. and Minehart, D. F. (2001). A theory of buyer-seller networks.
American economic review, 91(3):485–508.
Manea, M. (2011). Bargaining in stationary networks. American Economic Review,101(5):2042–80.
Nash, J. F. (1950). The bargaining problem. Econometrica: Journal of the Econometric Society, pages 155–162.
Nash, J. F. (1953). Two-person cooperative games. Econometrica: Journal of the
Econometric Society, pages 128–140.
Newman, M. E. (2004). Coauthorship networks and patterns of scientific collaboration. Proceedings of the national academy of sciences, 101(suppl 1):5200–5205.
Polanski, A. (2007). Bilateral bargaining in networks. Journal of Economic Theory,134(1):557–565.
Rubinstein, A. (1982). Perfect equilibrium in a bargaining model. Econometrica:
Journal of the Econometric Society, pages 97–109.
Rubinstein, A. and Wolinsky, A. (1985). Equilibrium in a market with sequential
bargaining. Econometrica: Journal of the Econometric Society, pages 1133–1150.

35