Abstract

1
Introduction
Goods have network externalities when their value to each user depends on the adoption decisions of others. Externalities are important not only for consumption goods but also for intermediate goods. As argued by Carvalho (2014), for example, modern production is an intricate network of firms. In such a network, a single supplier of inputs serves multiple downstream firms who are themselves linked with each other in the form of mutual production of final products or technology transfers. A downstream firm would find a higher value for the same inputs as used by other downstream firms that are linked to it. 1 Despite their importance in reality, our understanding of network externalities is limited when those goods are supplied competitively. The objective of this paper is to study price competition in the presence of such externalities: We formulate a highly stylized model of price competition in which users located at the nodes of a network experience positive externalities when their neighbors adopt the same good or technology.  In our model, two symmetric firms each supply goods or technologies that are incompatible with each other.  Users of either good experience larger positive externalities when more of their neighbors in the network adopt the same good. In stage 1, the two firms post prices simultaneously.  The prices can be perfectly discriminatory and negative, and are publicly observable. In stage 2, the buyers simultaneously decide which good to adopt or not to adopt either. When no network externalities are present, it is clear that the unique subgame perfect equilibrium of this game has both firms offer c , the constant marginal cost of production, to all buyers. We find that marginal-cost pricing is consistent with an equilibrium with monopolization by one of the firms in an arbitrary network when the externalities are linear in the number of neighbors adopting the same good. In contrast with the case with no externalities, however, we show that various pricing strategies are consistent with an equilibrium under linear externalities. In effect, when both firms offer the same price vector z , it is consistent with a monopolization equilibrium if the sum of markups and markdowns it entails for any subset of buyers is less than or equal to (the factor of proportion times) the number of links they jointly have with the complementary set. The latter quantity can be interpreted as the aggregate externalities that these buyers could enjoy if they were connected with the rest of the network. With no markup and markdown to any buyer, marginal cost pricing is clearly an equilibrium under linear externalities. When the externalities are non-linear, on the other hand, we show that marginal cost pricing is consistent with an equilibrium only when the buyer network is either a cycle or complete. 1  We also show that under non-linear externalities, there exists no equilibrium with monopolization in which every buyer is arged the same price.  These observations lead us to the study of equilibrium pricing strategies that are robust against slight perturbations in the externalities from linearity. Our central focus in this investigation is a class of bipartition pricing, which entails price discrimination based on a binary partition of the buyer set: Discounts are offered to the buyers in one subset but markups are charged to the buyers in the other subset. Furthermore, the size of a markup or markdown to any buyer is proportional to the number of his neighbors in the other subset. We consider small perturbations in the externalities from linearity, and define equilibrium pricing strategies under linear externalities to be robust if there exists a non-degenerate set of approximately linear externalities under which there exists an equilibrium pricing strategy that is "close" to the original pricing
2
strategy. We show that in a large class of networks, bipartition pricing given some binary partition of buyers is in fact robust. One important class of networks that admits a natural interpretation of robust bipartition pricing identified above is bipartite networks in which the buyer set is partitioned into two subsets and each buyer in one subset has neighbors only in the other subset. Bipartite networks are a graph-theoretical representation of two- sided markets that have received much attention in the literature: The two subsets correspond to the two sides of the market such as buyers and sellers of a certain good, and the two firms correspond to platforms that compete in offering marketplace to them. In a robust bipartition equilibrium over a bipartite network, all users on one side of the market are charged markups while all users on the other side are offered discounts. Furthermore, the size of the markup or discount to each user is proportional to the number of users on the other side of the market who are directly connected to them.  This is the first result that demonstrates that this popular pricing strategy arises as an equilibrium of price competition under local network externalities, and also identifies how the markups or markdowns are related to the specification of those externalities. 2 As mentioned above, the key assumption of our model is the ability of the firms to perfectly price discriminate the buyers. This assumption is more likely satisfied in intermediate goods markets with a limited number of participants than large consumption goods markets.  One good example is provided by the international competition in the sales of infrastructures that has recently become a major form of international trade. In a market for high-speed rails, for example, there are typically a small number of firms capable of providing a system, a buyer is either a country or a region and hence is also limited in number, and the good has externalities since it is not simply a physical product but includes the operation and management of the system:  Countries contemplating the adoption of a high-speed rail would be concerned with the rail system adopted by their neighbors if future connection between their systems is anticipated.3 It is well recognized that games with adoption externalities possess multiple In our model, this corresponds to the potential multiplicity of Nash equilibria. equilibria (NE) in the subgame played by the buyers after the posting of the prices by the firms. In the set of equilibria, our analysis makes use of two NE that are extreme as follows: The A -maximal NE is one in which the set of buyers who choose A is maximal in the sense that buyer i chooses A in it as long as he chooses A in some NE. The B -maximal equilibrium is one in which the set of buyers who choose B is maximal in the same sense. Our analysis builds on the assumption that the buyers play the B -maximal equilibrium after any deviation by firm A , and the A - maximal equilibrium after any deviation by firm B . We show that these behavioral patterns support the broadest spectrum of equilibria of the firms' price competition game by minimizing the profitability of deviations. The paper is organized as follows: After discussing the related literature in Sec- tion 2, we formulate a model of price competition in Section 3. A leading example is given in Section 4.  Section 5 considers the subgame played by the buyers in stage 2. Section 6 derives necessary conditions for an equilibrium in terms of the firms' payoffs. Section 7 provides a characterization of an equilibrium under linear externalities and introduces bipartition pricing strategies. The possibility of uni- form pricing and marginal cost pricing under non-linear externalities is discussed in Section 8. Section 9 discusses the robustness of bipartition pricing strategies. Application of the analysis to two-sided markets is discussed in Section 10. Section 11 concludes with a discussion. All the proofs are collected in the Appendix. 4
2
Related Literature
This paper contributes to two strands of literature. First, it contributes to the literature on network competition and two-sided markets through the introduction of local network externalities. Beginning with Katz and Shapiro (1985), most work on the topic supposes that the externalities are global in the sense that the adoption decision of any single buyer affects all other buyers equally.5 In the context of two- sided markets, this implies that the participation of any agent on one side of the market equally affects the utility of all participating agents on the other side of the market. 6  In contrast, we suppose that the adoption decision of any buyer affects only his neighbors on the network. In two-sided markets, our formulation implies that the participation of any agent may have different effects on different agents on the other side of the market.7 Second, it presents a general analysis of price competition between suppliers of goods with local network externalities.  Models of price competition under local network externalities include Banerji and Dutta (2009), Bloch and Quérou (2013), Blume et al. (2009) and Jullien (2011). Blume et al. (2009) and Bloch and Quérou (2013) study price competition under local network externalities when market seg- mentation among the firms is exogenously given. Banerji and Dutta (2009) study price competition using a graph representation of local externalities when there is no price discrimination. A model of Stackelberg price competition by Jullien (2011) is most closely related to the present model and entails a very general specification of local externalities.  Our specification of local externalities is more restrictive than that in Jullien (2011), but allows us to derive an explicit characterization of an equilibrium. 8 The multiplicity of equilibria is often a central concern in games with network externalities. Since the pioneering work of Dybvig and Spatt (1983), this concern has led the literature to focus on such issues as implementing efficient or revenue maximizing equilibria under complete and incomplete information, intertemporal patterns of adoption decisions, as well as the validity of introductory pricing. 9  As mentioned in the Introduction, we abstract from the issue by supposing that when- ever there is a deviating firm, the buyers coordinate on its least favorable NE. The literature makes different assumptions in this regard.  For example, Ambrus and Argenziano (2009) assume that the agents' actions satisfy correlated rationalizabil- ity, which implies that they coordinate on the pareto-efficient alternative whenever there is one, and Jullien (2011, Assumption 2) assumes that a change in price offer by one firm to buyers outside its market segment does not affect the decisions of those inside it. One key idea used in the present paper is that of divide-and-conquer, which has been studied by Segal (2003), Winter (2004) and Bernstein and Winter (2012) among others in contracting problems in which a single principal offers a contract to the set of agents whose participation decisions create externalities to other agents. 10
Model
3
Two firms A and B compete for the set I = {1, . . . , N} of N ≥ 3 buyers. Adoption of either firm's good generates externalities to the buyers according to a buyer network. Formally, a buyer network is represented by a simple undirected graph G whose nodes correspond to the buyers, and adoption externalities exist between buyers i and j if they are adjacent in the sense that there is a link between i and j . When buyer j is adjacent to buyer i, we also say that j is i's neighbor.
5
The buyer network G is connected in the sense that for any pair of buyers i and j , there exists a path from i to j . That is, there exist buyers i 1 , i 2 , . . . , i m , such that ż 1 is adjacent to i, i2 is adjacent to i1, . . . , and im is adjacent to j . For any buyer i in network G , denote by Ni the set of i's neighbors in G . The degree di = | Ni | of buyer i is the number of i 's neighbors. Define also M to be the number of links in G. Since each link counts twice when aggregating the number of degrees in G , we have M = i ∑ i ∈ I d i .
For r = 2,...,N − 1, the network G is r-regular if all buyers have the same degree r , and regular if it is r-regular for some r . G is cyclic if it forms a single cycle, and complete if every pair of buyers are adjacent to each other. The value of either firm's good to any buyer i is determined by the number of neighbors of i who adopt the same good. We denote by v n ≥ 0 the value of either good to any buyer when n of his neighbors adopt the same good. In particular, v 0 denotes the stand-alone value, or the value to any buyer of either good when none of his neighbors adopts the same good. Implicit in this assumption is that the two goods A and B are incompatible with each other since the value of either good to any buyer is assumed the same whether his neighbor adopts the other good or nothing. The value does not depend on the identity of a buyer or the identity of the firm who supplies the good. The externalities are positive in the sense that ν n is increasing in n. Let d be the highest degree in the network G: d = max i ∈ I d i . We will refer to the vector ( v 0 , . . , v d ) as externalities and denote it by v . Denote by VG the set of relevant externalities.
Each firm supplies the good at the constant marginal cost c ≥ 0 and no fixed cost. We will assume throughout that c ≤ v 0 so that the firms can serve even a single buyer without making a loss. 11  The firms can perfectly price discriminate the buyers, and we let p i and q i denote the prices offered to buyer i by firm A and firm B , respectively. The price vectors p = ( pi )i ∈ I ∈ R N and q = ( qi )i ∈ I ∈ R N are quoted simultaneously and publicly observed. The buyers then simultaneously decide whether to buy either good, or buy neither. Buyer i's action x i is an element of the set S i = { A, B, 0} , where 0 represents no purchase. Each firm's strategy is an element of R N , whereas buyer i's strategy σ i is a mapping from the set R 2 N of price vectors ( p,q ) to S i . Given the price profile ( p,q ), buyer i's payoff under the action profile x is given by

6
If we denote by σ = ( σ i ) i ∈ 1 the buyers' strategy profile, the payoffs π A ( p, q, σ ) and π B ( p,q,σ) of firms A and B , respectively, under the strategy profile ( p,q,σ) are given by
and buyer i's payoff π i (p,q,σ) under the strategy profile (p,q,σ) is given by π i (p,q,σ) = u i (σ(p,q),p,q). A price vector ( p*,q*) and a strategy profile σ = ( σ i ) i ∈ I together constitute a subgame perfect equilibrium (SPE) if given any price vector ( p,q) ∈ R 2N , the action vector ( σ i (p, q))i∈1 is a Nash equilibrium of the subgame following ( p, q ), and given σ , the price vectors p* and q* are optimal against each other.
4
Leading Example
Consider the line network with three buyers 1, 2 and 3 in Figure 1. ● Is marginal cost pricing consistent with an equilibrium? Suppose that both firms engage in marginal cost pricing: pc = qc = (c, c, c). If all buyers choose B , hence, the payoffs to buyers 1, 2 and 3 equal v 1 − c, v 2 − c and v 1 − c, respectively. Suppose now that firm A offers the price vector p = (p1,p2,p3) such that
For buyer 1, choosing A is strictly dominant since it yields at least v 0 — p 1 whereas choosing Ø yields 0 and choosing B yields v 1 — c if his neighbor, buyer 2, chooses B . The same reasoning applies to buyer 3. It follows that x i = A is the unique outcome that survives the elimination of strictly dominated strategies for i = 1 and 3. Given this, however, buyer 2 finds A optimal since it yields v 2 – p 2 , whereas 0 yields 0 and B yields v 0 − c. In other words, x 2 = A is the unique outcome that survives two rounds of elimination of strictly dominated strategies. If we give the orientation i → j to the link between buyers i and j when i precedes j in this iterative elimination process, then p satisfying (2) is depicted as in the left panel of
7
Figure 1. Note that such a p induces all buyers to choose A as long as they choose a rational response to the price offers. Hence, marginal cost pricing by both firms can only be consistent with an equilibrium if no such deviation by firm A yields a strictly positive payoff. The inequalities in (2) imply ∑ i ( p i − c) < v 2 + v 0 − 2v 1 , barely satisfies (2). In other words, there exists a profitable deviation p satisfying (2) if
Suppose next that firm A offers the price vector p = (p1,p2,p3) such that
This time, buyer 2 finds x 2 = A dominant in the first round of the iterative elim- ination process, and buyers 1 and 3 find x i = A dominant in the second round of the process. The orientation of the links hence is now given as in the right panel of Figure 1. The inequalities in (4) imply ∑ i ( p i − c ) < 2 ν 1 − ν 2 − ν 0 , and by the same logic as above, there exists a profitable deviation p satisfying (4) if
From (3) and (5), we see that marginal cost pricing is not an equilibrium if
which is true for a generic specification of ( v 0 , v 1 , v 2 ).  On the other hand, if the externalities are linear in the sense that v d − v 0 = hd for some h > 0 for every d = 1,2, . . . , then equality holds in (6). We can verify that under linear externalities, marginal cost pricing is indeed consistent with an equilibrium. In this network, hence, an equilibrium involving marginal cost pricing under linearity is not robust We show that this observation on against slight perturbations in externalities. marginal cost pricing extends to any network that is not a cycle or complete. ● Pricing strategies consistent with a monopolization equilibrium? Sup- pose that the externalities are either linear or satisfy (3), and consider the price pair (p*,q*) such that
In other words, buyers 1 and 3 are offered markdowns from marginal cost c whereas buyer 2 is charged a markup from c. Note that when the externalities are linear, the price vectors in (7) reduce to p = q = ( − h + c, 2 h + c, − h + c) so that the size of the markup or markdown equals the number of their neighbors who receive the
8
opposite treatment from the firms. 12 Suppose that the buyers choose firm B under this price pair σ(p*,q*) = ( B, B, B ), and that when firm A deviates from p* to p, buyers choose A only when they find A iteratively strictly dominant under (p,q*). By (3), firm B 's payoff is positive under ( p *, q *). Consider firm A 's price vector p that makes A dominant for buyer 1 in the first round, then iteratively dominant for buyers 3 and 2 in this order in subsequent rounds. p then must satisfy
When the externalities are linear as defined above, the first two terms on the right- hand side equal zero whereas the third term is < 0 as can be readily verified. It follows that no such deviation p is profitable also when the externalities are approx- imately linear. If, on the other hand, firm A 's price vector p makes A dominant for buyers 2 in the first round and iteratively dominant for buyers 1 and 3 a subsequent round as in the right panel of Figure 1, p satisfies
Hence, no such p is profitable either. We can indeed verify that firm A has no profitable deviation, and conclude that the pricing strategies in (7) are consistent with a monopolization equilibrium when the externalities are linear, or approxi- mately linear and also satisfy (3). Put differently, the equilibrium price vector ( p, q ) under linearity in (7) is robust against slight perturbations in externalities which satisfy (3). This marks a sharp contrast with the marginal cost pricing equilibrium discussed above. 14
9
Nash Equilibrium in the Buyers' Game
5
In this section, we fix the price vector ( p,q ), and consider an equilibrium of the buyers' subgame following ( p,q ) in which the set of actions of each buyer i equals S i = { A, B, 0} , and his payoff function u i is defined by (1). The simultaneous-move game ( I, S = Π i ∈ I S i , ( u i ∈ I ) among the buyers is one of strategic complementar- ities given that any buyer's incentive to choose A (resp. B ) increases when more buyers choose A (resp. B ). As such, the buyers' game typically has multiple equilib- ria. Among them, we are interested in two pure Nash equilibria x A and x B that are extreme in the set of buyers who choose either A or B . Formally, x A is A-maximal in the sense that if y is any Nash equilibrium and if any buyer i chooses A in y ( i.e., y i = A ), then he also chooses A in x A ( x ; A = A ). Likewise, x B is B-maximal in the sense that if y is any Nash equilibrium and if any buyer i chooses B in y ( yi = B ), then he also chooses B in x B (x B = B). 15, 16 Formally, if we define D A (resp. D B and D 0 ) to be the set of buyers for whom x i = A (resp. x i = B and x i = ∅) is iteratively dominant, and D ≡ D A ∪ D B ∪ D q , then any buyer i ∈ D must choose his iteratively dominant action in any NE. It follows that any pair of NE may be different from each other only in the actions chosen by buyers not in D . The A -maximal and B -maximal NE can then be constructed by simply having all buyers for whom A and B are rationalizable choose A and B , respectively, as seen in the following proposition. Proposition 5.1 (Maximal NE) Define xA and xB by
and
Then x A and x B are the A-maximal and B-maximal NE, respectively. We denote by σ A the buyers' strategy profile that chooses the A -maximal NE for any price pair ( p,q), and by σ B the strategy profile that chooses the B -maximal NE after any ( p,q) . It is clear from Proposition 5.1 that when the buyers play σ B
10
the set of buyers who choose A under any ( p,q) equals D A ( p,q). Likewise, when they play σ A , the set of buyers who choose B equals DB(p,q):
Suppose now that the price vector ( p*, q*) is given, and that we want to examine if any deviation by firm A to an alternative price vector p is profitable. A different deviation p will induce a different iterative elimination process, and as will be seen, the exact order in which the buyers find the choice of A iteratively dominant under the price vector ( p,q* ) determines whether this deviation by firm A is profitable or not.  For this reason, our analysis requires the description of the iterative elimination of dominated strategies in the buyers' game in some more detail. For any product subset S ′ = Π i S ′ ⊂ S of action profiles such that S ′ ≠ ∅ , buyer i ′ s action x i ∈ S ′ is (strictly) dominated in S ′ (by another pure action) if there exists x ′ ∈ S ′ such that
x i ∈ S i is dominant in S ′ if any other action x i ∈ S i is dominated in S ′ (by x i ). Let S 0 = S , and for k = 1,2,..., let S k be the set of buyer i's k-rationalizable actions, i.e., the actions that survive the elimination of all dominated strategies in Sk −1. If x i is the unique k -rationalizable action for buyer i for the first time in the iteration process (i.e., Sk-1 ⇒ Sk = {xi}), we say that action xi is k-dominant. Since each buyer has at most two dominated actions, the above process stops in or before 2N rounds. Let then K be the last round of the iteration process: SK+1 = SK. Define
For any k ≥ 1, U ξ =1 D ξ x is the set of buyers for whom x i = A is the unique k- rationalizable action, and the set of buyers for whom x i = A is iteratively dominant equals D A = ∪ k = 1 D k . On the other hand, R k is the set of buyers for whom x i = A is rationalizable. DB, D0, RK and RK have similar interpretations. Since the above iteration process depends on the price profile ( p,q), we often write D k ( p,q) and so on to make this dependence explicit. For any i, define α j = 0 and β j = d j . For k ≥ 2, define α j to be the number of i 's neighbors j for whom x j = A is the unique ( k − 1)-rationalizable action, and βξ to be the number of his neighbors j for whom xj = B is ( k − 1)-rationalizable. x i = A is the unique k -rationalizable action for buyer i if and only if the payoff from choosing A along with αξ of his neighbors is higher than that from oosing B along with βξ of his neighbors, or from choosing θ . In other words, i ∈ U ξ =1 D λ if and only if
or equivalently,
11 If x i = A is k -dominant ( i ∈ D k ) for buyer i and x j = A is either l -dominant (j ∈ D ξ ) for ℓ > k or not iteratively dominant (j ξ D A ) for buyer j , we say that i precedes j in the elimination process, and write i <( p,q ) j or simply i < j . 17 When buyers i and j are adjacent, the precedence relation < induces an orientation of the link between i and j : The link ij is given the orientation i → j if i < j .
Subgame Perfect Equilibrium
6
We now turn to the original two-stage game including the firms. We first observe that if a price vector ( p*, q*) is sustained in some SPE, then it must be sustained in an SPE in which the buyers choose an extreme response to either firm's deviation. Formally, a strategy profile σ of the buyers is extremal with respect to (p*,q*) if
In other words, when firm A unilaterally deviates from p*, then all buyers play the B -maximal NE that least favors firm A , and when firm B unilaterally deviates from q*, then they play the A-maximal NE that least favors firm B. Proposition 6.1 (Bang-bang property) (p*,q*) is an SPE price vector if and only if (p*,q*,σ) is an SPE for σ that is extremal with respect to (p*,q*). Consider next firm A's best response p to B's price q when the buyers play the B-maximal strategy σ B . We say that the set J of buyers is independent if no pair of buyers in J are adjacent to each other.18 The following lemma shows that if p is any "optimal" deviation by firm A , then D k ( p, q ) is independent. In other words, p is never optimal if there exists a pair of adjacent buyers who belong to the same round of the elimination process. Intuitively, this is because making A dominant for adjacent buyers i and j simultaneously requires offering lower prices to both of them than making x i = A dominant for buyer i first, then making x j = A dominant for buyer j next conditional on i choosing x i = A . For illustration, consider the line network of Section 4. If firm A offers p that makes A dominant for buyers 1 and 2 simultaneously, then p must satisfy
On the other hand, if it offers p ′ that makes A dominant for buyer 1 first and then buyer 2 next, p' should satisfy P ′ 1 < min { v 0 − v ¹ + q † , v 0 } and p ⁄ 2 < min {q ∗ , v ¹ }. It is clear that p ′ can be taken so that p 1 + p 2 < p 1 + p ′ 2
12
Lemma 6.2 (Strict precedence between adjacent buyers) Let the price vector (p,q) be given and suppose that buyers i and j are adjacent. If i and j both find x i = x i = A k-dominant for the same k under (p,q), then there is another price vector p ′ such that firm A's payoff under ( p ′ , q ) is strictly higher than that under ( p, q ), and that i precedes j under (p',q): π A (p',q,σ B ) > π A (p,q,σ B ) and i <(p',q) Î · Note that p may or may not entail strict precedence between non-adjacent buy- ers. Note in general that firm A 's optimal deviation may be to make the choice of A iteratively dominant for only a subset of buyers, and that the buyers may choose A even if it is not iteratively dominant. In this sense, if we consider p that makes A iteratively dominant for every buyer, then it gives a lower bound for firm A 's deviation payoff. Formally, given the price vector q of firm B, p is firm A's divide- and-conquer ( DC ) price vector against q if it (1) entails strict precedence between every pair of adjacent buyers ("divide"), and (2) makes A iteratively dominant for all buyers ("conquer"). If p is a DC price vector, hence, the entire buyer network G is given an orientation → induced by the precedence relation <. Let a price vector (p,q) be given. For any buyer i ∈ D A (p,q) andイ≡ <(p,q) ; define
to be the number of i’s neighbors who precede him in the elimination process.  When no confusion arises, we omit the dependence of sみon κ and simply write s i . We refer to s i as buyer i's in-degree and d i — s i as i's out-degree. In terms of the orientation → induced by <, buyer i's in-degree is simply the number of links directed toward i , and his out-degree is the number of links directed toward i's neighbors. Recall also that αξ is the number of i's neighbors for whom x i = A is the unique ( k − 1)-rationalizable action ( i.e., { A } = S k − 1), and β k is the number of his neighbors for whom x i = B is ( k − 1)-rationalizable ( i.e., B ∈ S k − 1 ). Hence, if x i = A is k -dominant for buyer i (i.e., i ∈ D k ), then
In the example of Section 4, the sequence of in-degrees is given by ( s 1 , s 2 , s 3 ) = (0,2,0) in the left panel of Figure 1 and ( s 1 , s 2 , s 3 ) = (1,0,1) in the right panel. When → induces an orientation to every link of the network G , then the sum of in-degrees of all buyers and the sum of out-degrees of all buyers both equal the total number M of links in G :
Define now O G to be the set of all possible orientations → of the buyer network G . If s = ( s i ) i ∈ 1 is the sequence of in-degrees for the relation <, then the corresponding
13
sequence of out-degrees d − s ≡ (d i − s i ) i ∈ 1 equals the sequence of in-degrees for
the reverse relation < ′ such that i < ′ j if and only if j ← i. By (9) and (12), a sufficient condition for the dominance of x i = A for i in (9) is given by
By offering p that barely satisfies (14) for every i , hence, firm A captures all the buyers ( D A ( p, q ) = I ) and achieves the profits arbitrarily close to
We hence have the following lemma that gives a lower bound for each firm's equi- librium payoff. Lemma 6.3 (Lower bound on equilibrium payoffs) If (p*,q*,σ) is an SPE, then
Lemma 6.3 shows that a firm's payoff from DC is closely linked to the value of
(17) is the key quantity referred to as firm A 's benchmark payoff given <. Since c ≤ v 0 ≤ v d i − s i , (15) reduces to (17) when firm B engages in marginal cost pricing q c = (c,...,c). The benchmark payoff can hence be interpreted as the maximal payoff achieved by employing DC against marginal cost pricing. 20
7
Linear Externalities
When there are no adoption externalities c ≤ v 0 = ... = v đ , it is clear that a subgame perfect equilibrium price ( p*, q*) is unique and equal to the marginal cost: p* = q* = (c, . . . ,c). In this section, we will examine if and how this result can be
14
extended when the externalities increase linearly in the size of adoption. Specifically, we say that the externalities v = ( v o , . . , v đ ) are linear if there exists h > 0 such that vd = v0 = dh   for every d = 0, 1, . . . , d. Linearity is a working assumption in many models of network externalities in the literature.21  We first establish that marginal cost pricing survives as an equilibrium under linear externalities. Proposition 7.1 (MC pricing under linear externalities) Let G be an arbitrary buyer network.  If the externalities v are h-linear for some h > 0, p* = q* = (c, . . . ,c) is an equilibrium price vector. To see the intuition behind Proposition 7.1, suppose that firm B monopolizes the market under p* = q* = (c,...,c) and that the B-extremal NE σB is played when firm A deviates. If firm A offers a DC price vector p , then by (15), its payoff satisfies
It can also be checked that firm A cannot profitably deviate by offering p that attracts only a subset of buyers. Unlike in the case of no externalities, however, there exists a large multiplicity of equilibria in the price competition game with linear externalities. The following proposition provides a complete characterization of the set of pricing strategies con- sistent with a monopolization equilibrium when the two firms offer the same price vector. For any J ⊂ I , denote by L ( J ) the number of links in J , and for any J , J ′ ⊂ I with J ∩ J ′ = ∅, denote by L ( J , J ′ ) the number of links between J and J ′ . Proposition 7.2 Let G be an arbitrary buyer network and suppose that the exter- nalities v are h-linear for some h > 0. Let z = ( zi )ie1 be any price vector.
2) Suppose that v 0 > c. If (p*,q*) = (z,z) is consistent with a monopolization
15
One key step of the proof for Proposition 7.2(1) is Lemma A.2 in the Appendix which shows that no deviation p is profitable unless it satisfies the following condi- tion: Under ( p,q*), every buyer i has either x i = A as the unique k -rationalizable action, or x i = B as one of the k -rationalizable actions. This point is illustrated in the line network of Section 4. Suppose that firm B monopolizes the market with the price vector q* satisfying q*, q* < 0, q* > v* = v° + h, and ∑ i (q* − c) = 0. Suppose also that firm A deviates to p such that under ( p,q*), all three buyers find A iteratively dominant with the precedence relationship 1 × 3 × 2 (as in the right panel of Figure 1). Since buyer 1 finds x 1 = B dominated in round 1, and since q ξ > v 1 , buyer 2 finds x 2 = B dominated in round 2 so that it is not 2-rationalizable. However, x 2 = A is not 1- or 2-dominant and hence is not the unique 2-rationalizable action for buyer 2. This p hence violates the above condition. Furthermore, ββ = 0 since buyer 3 has no neighbor for whom B is 2-rationalizable. It follows that p should satisfy:
where the last equality holds since q ² > v ¹ > v 0 .  It hence follows that p is not a The above observation in turn implies αξ + βξ = d i for every i and k since every neighbor of i either has A as his unique ( k – 1)-rationalizable action (who counts towards α ξ ) or B as one of the ( k − 1)-rationalizable actions (who counts towards βξ ). 22  This substantially simplifies checking the profitability of deviations since the deviating firm's payoff can be evaluated in terms of the indegrees and the markups/markdowns imposed by firm B :
It is readily seen (Lemma A.1 in the Appendix) that ∑ i ∈ D n ( v s i − v d i − s i ) = − h L ( D A , I D A ) so that no deviation p is profitable against q* which satisfies (18) for J = D A . The intuition behind Proposition 7.2(2) is rather simple: Suppose for example: that J = { i } and that q ξ > hL( J, I \ J ) = hd i . In this case, min { v 0 − v d i + q ξ , v 0 } = v 0 and hence firm A can profitably attract buyer i (i.e., i E D A (p,q*)) by offering p with p i ∈ (c,v 0 ) and p j = c for j̸= i. This observation basically extends to the case where | J | ≥ 2. Among the large set of pricing strategies consistent with a monopolization equi- librium identified in Proposition 7.2, we are interested in a particular class that
16
entails price discrimination of buyers as follows.  Specifically, consider price dis- crimination based on a binary partition of the buyer set: Buyers in one subset are charged markups and those in the other subset are offered discounts. Formally, a bipartition of the set I of buyers is an ordered pair ( I 1 , I 2 ) of subsets I 1 , I 2 ⊂ I such that I 2 = I \ I 1 . For any i ∈ I , denote by d k the number of his neighbors in set I k :
We say that z = ( z i ) i ∈ I is a bipartition price vector given the bipartition ( I 1 , I 2 ) if
Hence, every buyer in I 1 is charged a markup and every buyer in I 2 is offered a markdown from c.  Furthermore, the size of the markup or markdown to each buyer is proportional to the number of his neighbors in the other subset. We can also verify that the markups and markdowns sum up to zero: ∑ i ∈ I ( z i − c ) = 0. A profile (p*,q*,σ) is a bipartition equilibrium with monopolization given (I1,I2) if it is an SPE with monopolization by one of the firms and (p*,q*) = (z,z) for some bipartition price vector z given ( I 1 , I 2 ). Proposition 7.3 below establishes the existence of a bipartition equilibrium under linear externalities. Proposition 7.3 (Bipartition equilibrium) Let G be an arbitrary buyer network and suppose that the externalities v are h-linear for some h > 0. For any bipartition ( I 1 , I 2 ) of the set I , let z be the bipartition price vector given ( I 1 , I 2 ). Then ( p,q) = (z,z) is consistent with a bipartition equilibrium. Since the choice of the bipartition is arbitrary, the total number of bipartition equilibria is still very large. It is interesting to note that the bipartition equilibrium of Proposition 7.3 reduces to the marginal cost pricing equilibrium of Proposition 7.1 when the bipartition is given by ( I , I 2 ) = ( Ø, I ): In this case, no buyer has a neighbor in the other subset, and hence a bipartition equilibrium entails offering the marginal cost to every buyer.
8
Marginal Cost Pricing under Generic Externalities
We next consider the consequence of introducing some generic property of external- ities. The externalities v = ( v 0 , . . , v d ) are generic if for any orientation → ∈ O G of the buyer network,
Since the sequence d — s of out-degrees for any orientation → equals the sequence s of in-degrees for the reverse orientation as noted before, (20) implies that the
17
benchmark payoff for some orientation is strictly positive as long as there exists an orientation in O G for which s and d − s are not permutations of each other. The externalities v satisfying (20) are indeed generic in the set V G of possible externalities in G . The condition (6) of the leading example in Section 4 corresponds to (20). The following lemma shows that under (20), the benchmark payoff is strictly positive for some orientation if and only if the buyer network is neither cyclic nor complete. Lemma 8.1 (Positivity of the benchmark payoff) If the buyer network G is neither cyclic nor complete, then s and d – s are not permutations of each other for some orientation → so that
Lemma 8.1(1) is illustrated in Figure 2 for a regular network. The sequences of in-degrees and out-degrees of buyers 1, 2 and 4 in the left panel equal
respectively, whereas those in the right panel equal
respectively. Since the sequences of in-degrees and out-degrees of all other buyers are the same in both panels, we see that if s and d — s are permutations of each other in the left-panel, they cannot be so in the right-panel, and vice versa. Suppose now that firm B monopolizes the market with uniform pricing q* (q* = ··· = q N ≥ c). In this case, since c ≤ v 0 ≤ v 4 − 8 i by assumption, the second term on the right-hand side of (15) is non-negative:
18 Since π A (p*,q*,σ) = 0, Lemma 8.1 and (21) together imply that (16) is violated for firm A , implying the impossibility of a monopolization equilibrium with uniform pricing. 23  As seen in the following proposition, further inspection of (21) shows that the monopolizing firm must offer a markdown from c to some buyer and also charge a markup above v 0 to another buyer. Furthermore, the largest externalities in a network cannot be too small compared with v 0 . The last condition is a non-trivial restriction for networks in which the largest degree d is small as in line networks. Proposition 8.2 (No monopolization equilibrium with uniform pricing) Suppose that the buyer network G is neither complete nor cyclic, and that the externalities v are generic (20).  Let (p*,q*,σ) be an equilibrium with monopolization by one firm, say firm B: σ(p*,q*) = (B,...,B).  Then mini q* < c, maxi q* > v 0 and vd > 2v0 — c. As depicted in Figure 2, there are networks that are not cyclic or complete, but are symmetric with respect to every buyer. It follows from Proposition 8.2 that those identical buyers must also face price discrimination. We are now ready to state our main result in this section. Suppose that both firms engage in marginal cost pricing p* = q* = (c,...,c) to all the buyers. By Proposition 8.2, it cannot be consistent with a monopolization equilibrium unless the network is complete or cyclic. On the other hand, it is indeed consistent with a monopolization equilibrium in these classes of networks essentially because for any precedence relation <, the associated sequences of indegrees and outdegrees are permutations of each other. Proposition 8.3 (MC pricing in cyclic and complete networks) Let a buyer net- work G be given and the externalities v are generic (20).  (p*,q*) = (z,z) for z = (c,...,c) is consistent with a monopolization equilibrium if and only if G is either cyclic or complete.
9
Robustness of a Bipartition Equilibrium
We now examine the robustness of the equilibrium under linear externalities against slight perturbation in the externalities. To this end, we consider externalities that are approximately linear: For h > 0, the externalities v = ( v 0 , . . . , v β ) are ε -close to h-linear if | vd − v 0 − hd| < ε for d = 1, . . . , d.
19
We also say that the (sequence of) externalities ( v ( n )) n ∈ N  approach h-linearity if for any ε > 0, there exists n such that v ( n ′ ) is ε -close to h -linear for n ′ ≥ n . Given h > 0, an equilibrium ( p, q, σ ) under h -linearity is robust if there exists a non-degenerate set V* of externalities such that (i) V* contains h-linear externalities, and (ii) for every v ∈ V * , there exists an equilibrium (p v ,q v ,σ v ) such that (p v ,q v ) → (p,q) as v approaches h -linearity from within V* and that σ v ( p v , q v ) = σ ( p, q ). The following result readily follows from Propositions 8.2 and 8.3. Proposition 9.1 (Non-robustness of MC pricing) Suppose that ν 0 > c and let (p,q) = (z,z) for z = (c, . . . ,c). Then the monopolization equilibrium (p,q,σ) under h-linearity is robust if and only if the buyer network G is a cycle or complete. In contrast with the non-robustness of MC pricing seen in Proposition 9.1, Propo- sition 9.2 below identifies a sufficient condition for bipartition pricing to be robust. Consider the set of precedence relations ↓ according to which every buyer in I 1 precedes every buyer in I 2 : i < j if i ∈ I 1 and j ∈ I 2 , and let O ⋆ be the corresponding set of orientations of the buyer network. For each orientation → ∈ O c ; and each degree d = 1,...,d, define λ T to be "the number of buyers whose indegree equals d " minus "the number of buyers whose outdegree equals d":
Clearly, λ→ = 0 if and only if s and d − s are permutations of each other under the orientation →. The sufficient condition is described in terms of these vectors λ→. A subset J ⊂ I is maximally independent if (1) it is independent ( i.e. , contains no pair of adjacent buyers), and (2) there exists no J' ⇒ J that is independent. Proposition 9.2  Let the network G be given, and ( I 1 , I 2 ) be the bipartition of the set of buyers such that I 1 is maximally independent. Suppose that h > v 0 – c > 0. The bipartition equilibrium (p,q,σ) under h-linearity is robust if no convex combi- nation of the collection of vectors Λ ≡ {λ → : λ ↛≠ 0, → ∈ O ∗ } equals zero. The interpretation of Proposition 9.2 is as follows: Since every buyer in I 1 pre- cedes every buyer in I 2 according to any orientation in O c , if → ∈ O c , then its reverse is not an element of O ξ . This is important since the non-robustness of the marginal cost pricing equilibrium (Lemma 8.1 and Proposition 8.3) results from the fact that the benchmark payoff under one orientation is always the negative of that under the reverse orientation. It may however be the case that even within O ξ , there exists an orientation that generates the same sequence of indegrees (up to permutations) as that generated by the reverse of some → ∈ O ξ .  The condition
20
that no convex combination of vectors in {λ → : λ ↛= 0 ξ } equals zero in particular excludes such a possibility.24 The following corollary presents easy-to-verify sufficient conditions for the re- quirement in Proposition 9.2, and shows that a robust bipartition equilibrium exists in a large class of networks. Corollary 9.3  Suppose that the network G has a maximally independent set J ⊂ I that satisfies one of the following conditions: 1) |J| > |J'| for any independent set J' ⊂ I \ J. 2) max i ∈ J d i > max i ∈ I \ J d i . 3) I \ J is independent. If h > v 0 – c > 0, then for the bipartition (I 1 , I 2 ) = (J, I \ J), the bipartition equilibrium under h-linearity is robust.
10
Two-sided Markets
An extremely clear-cut characterization of equilibrium pricing under approximate linearity is obtained when we focus on an important class of networks known as bipartite networks.  A buyer network G is bipartite if there exists a bipartition ( I 1 , I 2 ) such that the only links of G are between I 1 and I 2 . 25  Any tree, which is a network with no cycle, is bipartite. For example, the line network in Figure 1 is bipartite with the partition I 1 = {1,3} and I 2 = {2}. More generally, a network is bipartite if and only if the length of every cycle is even. Bipartite networks are the most fundamental class of networks in graph theory. 26  A bipartite network is complete if every buyer in I 1 is adjacent to every buyer in I 2 . A complete bipartite network is a graph-theoretical representation of a two-sided market with global externalities that receives much attention in the economics literature. For example, we can think of I 1 as the set of sellers and I 2 as the set of buyers of a certain good. In this case, firms A and B are interpreted as the platforms that offer marketplace to these sellers and buyers, and their prices are interpreted as participation fees required for registration into their platforms. Under global externalities, the value of a platform for an agent on one side of the market is monotonically increasing in the number of agents on the other side of the market who adopt that platform. Our characterization below applies also to two-sided markets with local externalities where the value of a platform to any agent depends on whether the adopters of the platform on the other side are linked to him or not.
21
Proposition 10.1 (Monopolization equilibrium in a two-sided market) Suppose that the buyer network G is bipartite with the bipartition ( I 1 , I 2 ). Let h, v 0 and c ≥ 0 satisfy h > v 0 – c > 0.  If the externalities v are sufficiently close to h-linear, and ∑ i∈ I (v đ − v 0 ) ≥ ∑ i∈ I 2 (v đ − v 0 ), then (p ∗ ,q ∗ ) = (z,z) is consistent with a monopolization equilibrium if
According to Proposition 10.1, the agents on one side are charged markups and those on the other side are offered markdowns. Whi side should be offered dis- counts is determined by the inequality that compares the aggregate externalities that each side enjoys when all agents on the other side adopt the same platform: Markups are charged to the side that enjoys the larger aggregate externalities. This pricing strategy is a natural extension of the bipartition pricing identified in Propo- sition 7.3 given that the size of a markup/markdown to any buyer (divided by h) approaches the number of his neighbors on the other side in the limit as the exter- nalities approach linearity. Put differently, Proposition 10.1 shows the robustness of bipartition pricing for a bipartite network. The pricing strategy described in Proposition 10.1 has empirical support. While the theoretical literature finds such a pricing strategy optimal when the platform is a monopoly or when the externalities are global, Proposition 10.1 shows that it is valid even when there is competition and when the externalities are local. In particular, it is the first to identify the exact relationship between the externalities and the direction and size of price discrimination. 27, 28 The literature often discusses global but asymmetric externalities in two-sided markets.29  In those models, the network effect of the adoption decision of side 1 on side 2 is different from that of side 2 on side 1. Such a model is replicated in the present framework by considering a complete bipartite network with different numbers of buyers on each side. Which side should receive discounts in such markets again depends on the specification of externalities. Figure 3 illustrates the markups and markdowns specified in Proposition 10.1 when

22
so that I 1 = {1} and I 2 = {2,3,4,5}. Buyer 1 at the hub is charged a markup whereas all the buyers in the periphery are offered a discount. We can interpret the discount to the peripheral buyers as a protection against the inducement from the other firm. In fact, when (23) holds, it is relatively more difficult for the other firm, say firm A , to induce the hub buyer to switch:  When for example firm B engages in marginal cost pricing q c = (c,...,c), firm A must pay buyer 1 more than v 4 — v 0 to make x 1 = A 1-dominant, whereas he needs to pay just above 4( ν 1 − ν 0 ) to make x i = A 1-dominant for all peripheral buyers. When the inequality (23) is reversed, then buyer 1 now receives a discount, whereas the peripheral buyers are charged a markup. Again, which buyer(s) should be protected depends sensitively on the specification of externalities. One interesting observation concerns how an equilibrium changes when a link is added to or removed from a network. Suppose that the network C ′ is obtained from the original bipartite network G by adding a link between buyer i in I 1 and buyer j in I 2 . If buyer i is charged a markup and buyer j is offered a markdown in G , the addition of the link typically only affects only the prices charged to buyers i and j : With the new link, the price increases by approximately h for buyer i and decreases by approximately h for buyer j . In some cases, however, the new link may cause the regime shift in the pricing strategy. In other words, the addition of a new link may cause I 1 to be the side that receives a discount, and I 2 to be the side that is charged a markup.  When 2( v 1 – v 0 ) + v 4 – v 0 < 3( v 2 – v 0 ) and ( v 1 − v 0 ) + ( v 4 − v 0 ) > ( v 2 − v 0 ) + ( v 3 − v 0 ) in Figure 4, for example, the buyers in I 1 are charged markups in G but offered discounts in G ′ which is obtained from G by adding a link between 2 and 8.30
23
11
Discussion
The essential feature of the market for goods with network externalities is the mul- tiplicity of equilibria. In the present context, this corresponds to the multiplicity of equilibria in the buyers' subgame. Our construction of an equilibrium is based on the assumption that following any deviation by either firm, the buyers coordinate on the extreme equilibrium that least favors the deviator. While this assumption supports the broadest spectrum of equilibrium, it is not consistent with, for exam- ple, the assumption that the buyers choose the Pareto efficient alternative whenever there is one.31 Fundamental multiplicity of equilibria also exists in the pricing game between the firms when the externalities are linear. In this case, any pricing strategy is consistent with an equilibrium as long as the sum of markups and markdowns (divided by the factor of proportion h ) it entails for any subset of buyers does not exceed the number of links they have with the rest of the network. Even if we re- strict attention to bipartition pricing strategies, there is freedom in the choice of a binary partition as well as in the choice of the partition element to which discounts are offered.  On the other hand, the entire set of equilibrium pricing strategies is unknown under non-linear externalities. We have shown that marginal cost pricing is no longer consistent with a monopolization equilibrium except in the two special classes of networks under non-linear externalities.  As for bipartition pricing, we have identified conditions under which it is robust and in a bipartite network, have uniquely pinned down the equilibrium pricing strategy under approximate linearity that is "close" to robust bipartition pricing under linearity. These findings may suggest that the number of equilibrium pricing strategies is fewer under non-linear externalities than under linear externalities. There are a number of interesting extensions of the present model including, for
24
example, the model with a general number of firms, firms with asymmetric exter- nalities, or a positive degree of compatibility between the goods. 32, 33 It would also be interesting to consider alternatives to the assumptions of perfect price discrimi- nation, public observability of prices, and perfect knowledge of the firms about the network. 34
Appendix
Proof of Proposition 5.1   We show that x A is a NE. It will be then clear that x A is a A-maximal NE since any NE y must be rationalizable ( i.e., y ∈ S K ), and since x ; A = A whenever A is rationalizable. For buyer i ∈ D, x ; A is dominant and hence is optimal. If i has no dominant action ( i f D ) and x i = A is rationalizable, then x A = A by definition. If
then θ would be rationalizable and dominate x i = A. If
then B would be rationalizable and dominate x i = A since buyer j ≠ i plays x A = B only if x j = B is iteratively dominant and plays x A = A whenever A is rationalizable. In either case, we would have A f S K+1 C S K , a contradiction. If i has no dominant action ( i f D ) and x i = A is not rationalizable, then the set of rationalizable actions equals Sj k = { B, 0} and x : A = 0 by definition. If
then A would be rationalizable, a contradiction. If
then x i = B would be rationalizable and dominate x i = ∅ since buyer j̸= i plays x A = B only if it is iteratively dominant. This is a contradiction to the fact that x i = 0 is rationalizable.
25
Proof of Lemma 6.2.    Denote D k = D k (p,q) for k = 1,...,K, and suppose that adjacent buyers 1 and 2 both find x 1 = x 2 = A k -dominant ( i.e., 1, 2 ∈ D k (p,q)) for some k ≤ K . Then it follows from (9) that for i = 1, 2,
Consider now p' such that p', = p i for i ≠ 2, and
We then have
Since 1 is adjacent to 2 (1 ∈ N 2 ), in round k + 1 of the iteration process under ( p ′ , q ), we have,
and
It then follows from (24) that
so that x 2 = A is (k + 1)-dominant (2 ∈ D k +1 (p ′ ,q)) by (9). This further implies that D A (p',q) = D A (p,q). Hence implying that p ′ is a strictly better response to (q, σ B ) than p .
Proof of Proposition 6.1.   If ( p*,q*,σ ) is an SPE for σ which is extremal with respect to ( p*, q*), then ( p*, q*) is clearly an SPE price vector. Conversely, suppose that (p*,q*,ô) is an equilibrium for some strategy profile ô of the buyers. Let σ be the buyers' strategy profile which (i) is extremal with respect to ( p*, q*), and (ii) chooses the same action profile as ô on the path: σ(p*,q*) = ô(p*,q*). To show that ( p*,q*,σ ) is an equilibrium, we derive a contradiction by supposing that firm A has a profitable deviation p from p* against (q*, σ):
26 By the definition of σ , only those buyers who have A as their iteratively dominant action choose A: {i : σ i (p,q*) = A} = D A (p,q*). Define an alternative price vector p' of firm A as follows:
We will show that if x i = A is iteratively dominant for buyer i under (p,q*), then it is also iteratively dominant under ( p ′ , q ∗ ): D A ( p ′ , q ∗ ) ⊃ D A ( p, q ∗ ). We will show this by proving that ∪ ξ=1 D ξ (p ′ ,q *) ⊃ ∪ ξ=1 D ξ (p,q *) and R ξ (p ′ ,q *) ⊂ R ξ (p,q *) for each k = 1, . . . , K , where K is the number of the maximum number of iterations under ( p, q*), and R k , is the set of buyers for whom x i = B is k -rationalizable as defined in (8). Suppose first that k = 1. We have
If i ∈ D 1 (p,q*), then p i = p i and hence (27) holds. It follows that D 1 (p,q*) ⊂ D 1 (p',q*). On the other hand,
If i ∈ R B (p ′ ,q *) and i ∈ D A (p,q *), (29) holds since then p ′ i = p i . Let i ∈ R B (p ′ ,q *) and i̸∈ D A (p,q*). If v 0 − p i > 0, then v d i − q i ≥ v 0 − p i must hold since otherwise, x i = A would be 1-dominant for i under (p,q*), a contradiction. If v 0 − p i ≤ 0, then v d − q ∗ ≥ 0 clearly holds by (28). It follows that (29) holds in both cases so that R b (p',q*) ⊂ R b (p,q*). As an induction hypothesis, suppose that U k =1 D k (p,q*) ⊂ U k =1 D k (p',q*) and Rfs(p,q*)つRfs(p',q*) for ℓ = 1,...,k − 1 for some k ≥ 2. We then have ãξ ≡ αξ (p',q*) ≥ αξ (p,q*) ≡ αξ and βξ ≡ βξ (p',q*) ≤ βξ (p,q*) ≡ βξ for every i. Note that
Take any i ∈ ∪ k =1 D λ (p,q*).  Given that p i = p i for any such i , (31) holds since ãξ ≥ αξ and βξ ≤ βξ . It follows that i ∈ U ξ =1 D ξ (p ′ ,q *). We hence conclude that Uk=1 D*a(p,q*) ⊂ Uk=1 D*a(p',q*). On the other hand,
If i ∈ R ξ (p ′ ,q *) and i ∈ D A (p,q *), then p i = p i so that (32) implies (33) since ã* ≥ o* and β* ≤ β*. Let i ∈ R* (p',q*) and i̸∈ D A (p,q*). If v α* − p i > 0, then
27
vβk − q i ≥ v α k − p i must hold since otherwise, x i = A would be k -dominant for i under ( p,q*), a contradiction. If va* − p, ≤ 0, then vβ* − q, ≥ vβ* − q, ≥ 0 holds by (32). It follows that (33) holds in both cases so that R ξ (p ′ ,q*) ⊂ R ξ (p,q*). This completes the induction step. The above argument shows that π A (p ′ ,q*,σ) = π A (p,q*,σ) since any buyer i ∈ D A (p,q*) chooses A also under (p ′ ,q*) for the same price p i = p i , and the contribution to firm A 's payoff of any buyer i ∈ D A (p ′ ,q*) \ D A (p,q*) equals zero since p i = c. Finally, { i : ô i (p ′ ,q*) = A} ⊃ D A (p ′ ,q*), and if ô i (p ′ ,q*) = A and i & D A (p',q*), then i's contribution to firm A's payoff equals zero since p', = c. It hence follows that π A ( p ′ ,q * , ô ) = π A ( p ′ ,q * ,σ ). This, along with π A(p*,q*,ô) = π A(p*,q*,σ) by the definition of σ , shows that if (25) holds, then p' is a profitable deviation for firm A against (q*, ô), which is a contradiction. Proof of Lemma 6.3.  Let ε > 0 and orientation → ∈ O G be given. Define the price vector p = (pi)i∈1 by
satisfies
Since ε > 0 and → ∈ O ς are arbitrary, if (16) does not hold, then we would have a ■ contradiction π A (p,q*,σ) > π A (p*,q*,σ). Proof of Proposition 7.1. Let p* = q* = (c,...,c). Let σ be the extremal strategy profile with respect to (p*,q*) with σ(p*,q*) = (B,...,B) so that B mo- nopolizes the market under ( p *, q *). Now consider any deviation p̸= p * by firm A and write D k = D k (p,q*) (k = 1,...,K). Since v 0 − q ∗ = v 0 − c ≥ 0, x i = B is never dominated by x i = ∅ . Furthermore, if x i = A dominates x i = B , then x i = A also dominates x i = 0. If follows that for any i and k , either x i = A is the unique ( k − 1)-rationalizable action ( S k − 1 = { A }) or x i = B is ( k − 1)-rationalizable (B ∈ S k − 1 ). Hence, for any i and k ,
It then follows from (9) that
Denote the number of links in J ⊂ I by L ( J ), and that between J and J ′ ⊂ I \ J by L(J, J'). We then have

28
Hence, firm A's payoff satisfies Therefore, p is not a profitable deviation. ■ Proof of Proposition 7.2 The proof uses three lemmas (Lemmas A.1, A.2, and A.3) presented below. 1) Suppose that (18) holds. Let σ be extremal with respect to (p*,q*) and σ(p*,q*) = ( B , . . . , B ). It follows from Lemma A.2 that if p is any profitable deviation, then β k = d i − α k for any i and k . Hence, if i ∈ D A (p,q*), p i must satisfy
Take any J ⊂ I and take any p such that D A (p,q*) = J. It then follows from Lemma A.1 that
Hence, firm A has no profitable deviation. 2) Suppose that (18) fails.  Suppose that firm B monopolizes the market under (p*,q*): σ(p*,q*) = (B,...,B). In view of Proposition 6.1, we may suppose that σ is extremal with respect to (p*,q*). If ∑ i ∈ I (z i − c) = π B (p*,q*,σ) < 0, then (p*,q*) is clearly inconsistent with an SPE. Suppose then that LiEJ ( zi - c ) > hL( J, I \ J ) for some J ⊂ I . By setting K = ∅ in Lemma A.3, we see that when the buyers play the B-maximal NE σ B , firm A can choose p so that D A (p,q*) = J and make its payoff arbitrarily close to
29 By assumption, the RHS of (37) is > 0, implying that there exists p such that π A (p,q*,σ B ) > 0. Since σ is extremal with respect to (p*,q*), we have π A (p,q*,σ) = π A (p,q*,σ B ) > 0 = π A (p*,q*,σ) so that p is a profitable deviation against q*. ■ Lemma A.1 Let the network G be given and suppose that the externalities are h-linear for h > 0. Then for any (p,q) and D A = D A (p,q),
Proof of Lemma A.1   The conclusion follows since v å  = v å -a å  = h(2a å  = d å ), Ek=1  EiED", of = L(DA), and Ek=1  EiED", di = 2L(DA) + L(DA,I \ DA). Lemma A.2 Let the buyer network G be given. Suppose that the externalities v are h-linear for h > 0. Let q* be any price vector satisfying
If firm A's price vector p is such that π A (p,q*,σ B ) ≥ 0, then the following holds under (p,q*): For any i ∈ I and k = 1,...,K , either
Furthermore, for any such p, αξ + βξ = d i for every i and k. Proof of Lemma A.2   Note that the second statement of the proposition follows from (39): For any i ∈ I and k ≥ 2, every neighbor j of i has either x j = A as their unique ( k − 1)-rationalizable action or x j = B as one of the ( k − 1)-rationalizable actions. Hence, αξ + βξ = d i . Write D k ≡ D k (p,q*). We show that the failure of (39) implies π A (p,q*,σ B) < 0. For simplicity, we suppose that (39) fails for a single i so that B f S k and {A}̸= S k for some k . Let k ≥ 2 be the smallest such k so that B ∈ S k − 1 and B̸∈ S k . We must have v b k < q k since if v b k ≥ q k , for B̸∈ S k to take place, x i = B must be dominated by x i = A in Sk − 1 so that v − p i > v β i − q i ≥ 0. This, however, shows that x i = A also dominates x i = 0 and hence is the unique k-rationalizable action ( Sk = {A}), which is a contradiction. For any j ≠ i, (39) holds by assumption, and hence for any ℓ = 1, . . . , K ,

30
Suppose first that i ∈ D m for some m ≥ k . By the above observation, for any j and ℓ such that j ∈ D ξ , β ξ is given as follows:
Furthermore, since β m ≤ β k , if x i = A is m -dominant, then p i should satisfy
Using (40) and (41), we can evaluate firm A's payoff under (p,q*,σB) as follows:
Rewriting of (42) yields

31
where the last inequality follows from Lemma A.1 and (38). Linearity then implies that
When m − 1 ≥ k + 1, (44) reduces to
The same inequality holds true also when m = k + 1 or m = k since α ? n = α k +1 in those cases. 35 When i ξ D A , (42) holds with m replaced by K + 1 and without the last term v α m − c ≥ 0 on the right-hand side. It follows that π A (p,q *,σ B ) < 0 in this case as well. Suppose that the externalities are h -linear.  Given firm B 's price vector q and disjoint sets K , J ⊂ I of buyers, suppose that firm A offers p such that under ( p, q ), (i) x i = A is iteratively dominant for i ∈ K ∪ J , and (ii) the buyers in K precede the buyers in J. Let r A (J | K, q) denote the supremum of firm A 's payoff from J when it chooses a price vector p satisfying these conditions:
Lemma A.3 For any K and J ⊂ I such that K ∩ J = ∅, if we denote g i = min { q i , vdi − d i } , then
Proof. We proceed by induction on the size of J. Take any J such that J = {j} for any j ∈ I . Then j finds A dominant and is preceded by buyers in K if v d ξ − p j >
32
max { v đ j − d j − q j , 0} so that any p j with p j < v đ j − v đ j − d j − v d* − v d j − d* + q j will ensure that j ∈ D A (p,q). Hence, (46) holds since
Let n ≥ 1 be given, and suppose as an induction hypothesis that (46) holds for every J such that | J | ≤ n . Take any J such that | J | = n + 1. Suppose without loss of generality that 1 ∈ J and let J − 1 = J \ {1}. Note that r(J | K,q) satisfies
The first term on the right-hand side equals the bound when buyer 1 precedes buyers in J −1 , and the second term equals the bound when buyers in J −1 precede buyer 1. By the induction hypothesis, we can evaluate each term on the right-hand side of (47) as follows. First, since
and
we have
Next, since

33
and
we have
We now consider the following two cases separately. Let å j = | N j \ ( K ∪ J )| be the number of j's neighbors not in K ∪ J. Case 1. If q j ≤ v d j for every j ∈ J, then
Case 2. If q j > v å s for some j ∈ J , suppose without loss of generality that q 1 > v å 1 so that
First, if ∑ j ∈ J _, ( q j − c) > n(v 0 − c) + hL(J − 1, I \ (K ∪ J − 1)), then it follows from (49) that

34
Next, if n(v 0 − c) + hL(J_1,I \ (K U J)) < ∑ j ∈J_1 (¯ j − c) ≤ n(v 0 − c) + hL(J_1,I \ (K ∪ J_1)), then it follows from (48) that
(48) that
In all cases, we have shown that (46) holds for any J with | J | = n +1. This completes the proof. ■ Proof of Proposition 7.3.  The proof uses Lemma A.4 presented below. Take any bipartition ( I 1 , I 2 ) of the buyer set and let z be the corresponding bipartition price vector. Define p* = q* = z and σ to be extremal with respect to (p*,q*) with σ(p*,q*) = ( B , . . , B ). Suppose that p̸= p* is an arbitrary deviation by firm A . By Lemma A.2, we may restrict attention to p such that β k (p,q*) = d i − α k (p,q*) for any i and k . If i ∈ D A , then (9) implies that Furthermore, Lemma A.4 shows that
It hence follows that
Therefore, no deviation p is profitable.

35
Lemma A.4 Let the network G be given and suppose that the externalities are h- linear for h > 0.  If ( I 1 , I 2 ) is any bipartition and q* = z for the bipartition price vector z  given (I1, I2) defined in (19), then for any p,
Proof.   It follows from Lemma A.1 and the definition of q* that
Since
and
the right-hand side of (50) reduces to − L ( D A , I 1 \ D A ) − L ( I 2 ∩ D A , I \ D A ). ■ Proof of Lemma 8.1.   1) Suppose that G is neither cyclic nor complete. We will consider the following two cases separately. i) G is not regular. Since G is not regular, we may suppose, with renaming of buyers if necessary, that buyers 1 and 2 are adjacent, and that d 1 = d and d 2 < d , where d ≥ 2 is the highest degree in G . Suppose further that buyer 3 is adjacent to 1 but not to 2. To see that there exists such a buyer, suppose to the contrary that every neighbor of 1 (except 2) is also a neighbor of 2. Then 2 has at least d neighbors, a contradiction. Name other buyers arbitrarily. Consider first the orientation → that is induced by the precedence relation ← such that
We then have
36 If s is not a permutation of d — s, then we are done.  Suppose then that s is a permutation of d − s , and consider an alternative orientation → ′ of G that is induced by < ′ which agrees with < defined above everywhere except between 1 and 2: 3 < ′ 2 < ′ 1 < ′ i for every i ≥ 4, and ( i < ′ j ⇔ i < j ) for i, j ≥ 4. Let s' = (s, ')iEI be the sequence of in-degrees corresponding to this alternative orientation → ′ .  Then
We also have
The following two cases are considered separately. a) d2 = 1. In this case, (52) and (53 ) imply that
Hence, since d — s is a permutation of s, we must have
It then follows from (54) that
b) d2 ≥ 2. In this case, we have d ≥ 3 since d > d j ≥ 2, and also
Hence, since d – s is a permutation of s,
37 It then follows from (54) that
ii) G is r-regular with 2 < r < N − 1. Since G is connected and not complete, we may suppose, with renaming if nec- essary, that buyers 1 and 2 are adjacent, and that buyer 3 is adjacent to 2 but not to 1. To see that this is possible, suppose to the contrary that for any pair of adjacent buyers i and j , any buyer k̸= i adjacent to j is also adjacent to i . We then show that G must be complete. Take any pair of buyers i and j . Since G is connected, there is a path k 1 = i → k 2 → · · · → k m − 1 → k m = j . Since k 2 is adjacent to i = k 1 and k 3 is adjacent to k 2 , k 3 is adjacent to i as well by the above. Now since k 4 is adjacent to k 3 , it is also adjacent to i . Proceeding the same way, we conclude that j = k m is adjacent to i = k 1 , implying that G is complete. We now name buyers other than 1, 2, and 3 arbitrarily. For the orientation → induced by < such that 1 × 2 × 3 × i for any i ≥ 4, the associated sequence s = ( s i )i ∈ 1 of indegrees satisfies
If d — s is a not permutation of s, then we are done. Suppose then that d — s is a permutation of s. We then must have
Consider an alternative orientation induced by < ′ that agrees with < everywhere except between 2 and 3:
If we denote by s ′ = ( ṣ̥̥) i∈1 the sequence of indegrees associated with즉′ , then it satisfies
38 Since r > 2, if (59) holds, then the same argument as in the non-regular case shows that implying that d – s ′ is not a permutation of s ′ . 2) Suppose that G is cyclic, and let the orientation → ∈ O G be given. Denote by s = ( s, ζ ) i∈ I the sequence of indegrees associated with ą. Let J 2 = { i : s, = 2} and J 0 = { i : s i = 0}, and consider any distinct (and non-adjacent) buyers in J 2 such that there is no buyer in J 2 on the shorter path between them. Clearly, there exists exactly one buyer on that path who belongs to J 0 . It follows that |J 2 | = |J 0 |. Since s i = d i − s i = 1 for any buyer who is not in J 2 or J 0 , s is a permutation of d − s . Suppose next that G is complete, and let the orientation → ∈ O G be given. If we denote by s = ( s ζ ) i∈1 the sequence of indegrees associated with즉, then s is a permutation of the sequence 0, 1, 2, . . . , N − 1. Since d i − s i = ( N − 1) − s i , it follows that d — s is also a permutation of 0, 1, 2, . . . , N — 1. Hence, s is a permutation of d — s. Proof of Proposition 8.2.  Suppose that G is neither cyclic or complete, and let (p*,q*,σ) be any SPE. By Lemma 8.1, ∑ i (v*i − v4i− si ) > 0 for some → ∈ O G . Lemma 6.3 then implies that for any such → ∈ O G ,
Suppose now that firm B monopolizes the market: σ(p*,q*) = ( B , . . , B ) so that π A(p*,q*,σ) = 0 and π B(p*,q*,σ) = ∑ i (q* − c) ≥ 0.  If min i q* ≥ c, then π A(p*,q*,σ) = 0 ≤ ∑ i (min {q*,v 0 } − c), contradicting (60). If maxi q* ≤ v 0 , then we have a contradiction to (60) since
Note now that q * ≤ v d i − v 0 +c for every i since otherwise firm A can profitably switch buyer i to A by p such that c < p i < v 0 − v d i +q ĩand p j = c for j̸= i. If v ā ≤ 2v 0 − c, then we have a contradiction to the above since max i q i ≤ v ī − v 0 + c ≤ v 0 . Proof of Proposition 8.3  Let p* = q* = (c,...,c), and suppose that σ is ex- tremal with respect to (p*,q*) with σ(p*,q*) = (B,...,B). 1) G is a cycle. Fix any deviation p̸= p ∗ by firm A and write D ˆ= D ˆ= (p,q ∗ ). Since v 0 − q ∗ = v 0 − c ≥ 0, x i = B is never dominated by x i = ∅ for any buyer i . Furthermore, if x i = A dominates x i = B, x i = A also dominates x i = θ . It follows that for any i
39
and k , either x i = A is the unique (k − 1)-rationalizable action ({ A } = S k − 1), or x i = B is ( k − 1)-rationalizable ( B ∈ S k − 1). Hence for any i and k ,
Suppose now that x i = A is k -dominant ( i ∈ D k ). Then we have by (9),
More specifically, i finds x i = A 1-dominant if p i < v 0 − v 2 + c , and k -dominant for k > 1 either if (i) p i < c and exactly one of i ' s two neighbors precedes i ( αξ = 1), or (ii) p i < v 2 − v 0 + c and both his neighbors precede him ( α ξ = 2). In particular, if buyer i precedes both his neighbors, then i ∈ D 1 . Firm A 's payoff under ( p,q*,σ) hence satisfies
Since no buyer finds x i = A k -dominant for k ≥ 2 if neither of his neighbors precedes him, the number of components ( i.e, connected clusters of buyers) in U e =1 D ξ A is less than or equal to that in D 1 for any k. 36  It follows that
We can therefore conclude that π A (p,q*,σ) < 0. 2) G is complete. Define D k = D k (p,q*) (k = 1,...,K) as above. Denote by α k the number of buyers who find x i = A k -dominant for 1, . . . , k − 1:
Since G is complete, for any buyer i , the number αξ of i 's neighbors who precede him equals α k . Furthermore, by Lemma 6.2, we only need consider p such that each D k contains a single buyer. (If D k contains two or more buyers, then since G is
40
complete, those buyers are adjacent.) Hence, without loss of generality, let D k = { k } for each k = 1, . . . , N . Just as in the case of a cyclic network, q * = (c, . . . ,c) implies that β k = d i − α k for any i and k . It follows that
Firm A's payoff under (p,q*, σ) hence satisfies
It can then readily be verified that the right-hand side is maximized when K = N and that the maximum value equals zero. Hence, firm A has no profitable deviation. □ Proof of Proposition 9.1. If G is either cyclic or complete, then (pv,qv) = (z,z) is consistent with a monopolization equilibrium for any externalities v by Proposition 8.3. Conversely, suppose that G is neither cyclic nor complete. Note that if ( pv, qv) is sufficiently close to ( z, z ), then max i q i < v 0 must hold since v 0 > c. Proposition 8.2 then shows that ( p v , q v ) cannot be consistent with a monopolization equilibrium unless the externalities are non-generic. The proof uses Lemmas A.5 and A.6 presented below. Proof of Proposition 9.2 Given the externalities v , we begin by defining the price vector z v . As v approaches h-linear externalities, this price vector z v approaches the bipartition price vector z defined in (19). Fix any orientation → ∈ O ∞ , and let s = ( s i ) i ∈ 1 . Let
Suppose that I 2 consists of T components ( I 2 t ) t =1,..., T . 37  For each component I 2 t , let
Define the set V* of externalities by
V* is non-degenerate as will be seen below, and contains the h -linear externalities as one of its elements since then ζ 1 = ζ 2 . Let now a price vector z v be defined by
In Figure 5, for example, ζ2,1 and ζ2,2 equal
and hence the price vector z is given by
Note that as v approaches h -linear externalities, v đ² − v 0 → d 2 h , and  ≥ j ∈ 1 2 t d j so that zv → z for the bipartition price vector z defined in (19). In what follows, we set p* = q* = zv and let σ be extremal with respect to ( p *, q *) with monopolization by firm B on the path: σ( p *, q *) = ( B , . . , B ). By construction, we have
We first note that the set V* is non-degenerate under the stated condition of Proposition 9.2. For this, define
Note that
To show that V* is non-degenerate, hence, it suffices to show that the set defined by the corresponding strict inequalities is non-empty:
42 By Theorem 22.2 of Rockafellar (1997, p198), this holds if and only if no convex combination of the collection of vectors {λ } : λ }̸̸≠ 0, → ∈ O͡ξ } equals zero, as required by the proposition. The remainder of the proof shows that no deviation p by firm A is profitable when ν ∈ Z* is ε-close to h -linear, z v satisfies | z i − z i | < ε for every i , and ε < min { 3N, v 0 = c, h = v 0+ c}. By Lemma A.6, we may restrict attention to p for which 2d β k = d i − α k for any i and k . In this case, if x i = A is k -dominant for buyer i ( i.e., i ∈ D k ), then it should satisfy
We now proceed in the following steps. 1. Any profitable deviation p attracts at least one buyer in I 1 : I 1 ∩ D A̸= ∅ . If D A ⊂ I 2 , then every neighbor of i ∈ D A should also belong to D A since otherwise, L(I 2 ∩ D A , I \ D A ) ≥ 1 and hence π A (p,q*,σ) < 0 under approximate linearity by Lemma A.5.  Proceeding iteratively, every buyer who is connected to i should belong to D A . Since the network G is connected, there must exist j ∈ I 1 ∩ D A , a contradiction. 2. Any profitable deviation p attracts at least one buyer in I 2 and all his neighbors: I2 ∩ D A̸= ∅ and N i ⊂ D A for i ∈ I 2 ∩ D A . Since I 1 is independent, if D A ⊂ I 1 , then
It follows that if p is a profitable deviation, then I 2 ∩ D A̸= ∅ . If N i \ D A̸= ∅ for some i ∈ I 2 ∩ D A , there is a link between I 2 ∩ D A and I \ D A . Since β ξ = d i − α j for every i and k, π A (p,q*,σ) < 0 by Lemma A.5. 3. If p is any profitable deviation, then x i = A is 1-dominant for any buyer i ∈ I 1 and is k -dominant for k ≥ 2 for any buyer i ∈ I 2 : D λ ⊂ I 1 , and D λ ⊂ I 2 for k ≥ 2. i)  If i ∈ I 2 , then S k ⊂ { A , B } for k = 1 , . . . , K . If i ∈ I 2 , v 0 − q ∗ = v 0 + d 1 h − c > 0 so that x i = ∅ is dominated by x i = B in S 0 .
43
ii)  If i ∈ I 1 ∩ D k  for some k ≥ 2, then N i ∩ D k − 1 ≠ ∅ .
Suppose to the contrary that i ∈ I 1 ∩ D k and N i ∩ D k − 1 = ∅ for some i and k ≥ 2. We then have α k − 1 = α k . Furthermore, since S k − 1 ⊂ { A, B } for every j ∈ N i ⊂ I 2 by (3i), j̸∈ D k − 1 implies that B ∈ S k − 2 ⇒ B ∈ S k − 1 . It follows that βξ− 1 = βξ . Hence, if x i = A is not ( k − 1)-dominant, then it cannot be k-dominant since
This is a contradiction to i ∈ D k iii) If I 1 ∩ D k ≠ ∅ for some k ≥ 2, then p is not profitable. Let k ≥ 2 and i ∈ I 1 ∩ D k . We have N i ∩ D k − 1 ≠ ∅ by (3ii). It then follows that β ξ ≤ | N i | − 1 = d ξ − 1. By Lemma A.6, we conclude that π A (p, q*, σ B ) < 0. iv) If i ∈ I 2 ∩ D 1 , then p is not profitable. Let i ∈ I 2 ∩ D 1 . Since I 1 is maximally independent, there exists j ∈ N i ∩ I 1 . For this j, we have β 2 ≤ | Nj | − 1 = đ 2 − 1 and hence π A (p,q*,σ B ) < 0 by Lemma A.6. v)  If p is a profitable deviation, then D k ⊂ I 1 , D k ⊂ I 2 for k ≥ 2 , N i ⊂ D A for i E I 2 N D A . Suppose that π A (p,q*,σ) ≥ 0. By (3iii) and (3iv), we must have D λ ⊂ I 1 □ and D k ⊂ I 2 for k ≥ 2. By Step 2, N i ⊂ D A for i ∈ I 2 ∩ D A .
4. No deviation p is profitable.
By Step 3, we may restrict attention to p such that D 1 (p,q*) ⊂ I 1 , and D 2 (p,q*) ⊂ I 2 for k ≥ 2. By Steps 1 and 2, we may also suppose that I 1 ∩ D A̸= ∅ and that I 2 ∩ D A consists of components of I 2 that are adjacent only to I 1 ∩ D A . Suppose for simplicity that I 2 ∩ D A consists of a single component I 2 t of I 2 . Then

■
44
Lemma A.5  Let the network G and the bipartition ( I 1 , I 2 ) of the buyer set be given. For each ε > 0, take externalities ν(ε) and the price vector q*(ε) such that ν(ε) is ε- close to h-linear (h > 0), and that | q i (ε) − z i | < ε for every i for the bipartition price vector z given (I 1 , I 2 ). Then for ε > 0 sufficiently small, π A (p,q*(ε),σ β ) < 0 for any p such that βξ = d i − αξ for every i and k, and L(D A , I 1 \D A )+ L(I 2 ∩ D A , I \D A ) ≥ 1. Proof.   Let ε <ֲנN . Take p such that βξ = d i − αξ for every i and k . Then
where next to the last inequality follows from Lemma A.4 and our assumption that L(D A , I 1 \ D A ) + L (I 2 ∩ D A , I \ D A ) ≥ 1, and the last inequality from our choice of ■ ε. Lemma A.6  Let the buyer network G and the bipartition ( I 1 , I 2 ) of the buyer set be given. Take h, v 0 , and c ≥ 0 such that h > v 0 − c ≥ 0. For each ε ≥ 0, take externalities ν(ε) and price vector q*(ε) such that ν(ε) is ε-close to h-linear, and that |q į (ε) – z į | < ε for every i for the bipartition price vector z given ( I 1 , I 2 ) defined in (19).  Then for ε sufficiently small, if p is such that π A (p,q*(ε),σ β ) ≥ 0, then the following holds for every i and k:
Furthermore, if p is any such price vector, then αξ + βξ = d i for every i and k.
45

where this time, the second inequality follows from Lemma A.5 as ε < A . Since να 5 −α 5 − 1 (ε) < h + 2ε, and
(68) implies
By the same logic as in the proof of Lemma A.2, the same inequality holds true when m = k + 1 or m = k , or when i̸∈ D A . Since − h + v 0 − c + 2 d i ∈ < 0 by our ■ choice of ε, π A (p,q*(ε),σ B ) < 0 for any p that fails (66).
46
Proof of Corollary 9.3
1) Let e = (1, . . . ,1) ∈ R d . Then e · λ ≤ |J ′ | − |I 1 | for any λ ∈ Λ , where J ′ is the set that has the largest number of elements among independent sets which are subsets of I 2 . By assumption, |J ′ | − |I 1 | < 0 so that e · λ < 0 for any λ ∈ Λ . It follows that for any convex combination ∑ k ζ k λ k of vectors (λ k ) k in Λ , we have e · ∑ k ζ k λ k = ∑ k ζ k (e · λ k ) < 0 so that ∑ k ζ k λ k̸= 0. 2)  Let ê = (0, . . , 0, 1) ∈ R đ . Then ê · λ = − |{ i ∈ I 1 :  d i = d } | < 0 for any λ ∈ Λ . It then follows from the same argument as above that no convex combination of vectors in Λ equals zero. 3) When every component of I 2 is a singleton, every orientation → ∈ O ξ ; yields the same vector λ→ = λ so that Λ is a singleton.  Hence, the condition is satisfied. ■ Proof of Proposition 10.1  Since I 2 is independent, for each i ∈ I 2 , { i } is a component of I 2 . Hence, ζ 2 t in (63) in the proof of Proposition 9.2 equals ζ2t = vdi − v0   for each t ∈ I2, implying that the price vector p* = q* given in the proposition equals zv in (64). Furthermore, the set V* of externalities defined in the proof of Proposition 9.2 is given by V* = {v :  ∑ i∈I , (v đ − v 0 ) ≥  ∑ i∈I , (v đ i − v 0 )}. Proposition 9.2 then shows that for ε > 0 sufficiently small, if ν ∈ V* is ε-close to h -linear, then there exists an ■ equilibrium with p* = q* = zv. [1] Attila Ambrus, and Rossela Argenziano (2009), "Asymmetric networks in two- sided markets," American Economic Journal: Microeconomics, 1(1), 17-52. [2] Masaki Aoyagi (2010), "Optimal sales schemes against interdependent buyers," American Economic Journal: Microeconomics, 2(1), 150-182. [3] Masaki Aoyagi (2013), "Coordinating adoption decisions under externalities and incomplete information," Games and Economic Behavior, 77, 77-89. [4] Mark Armstrong (1998), "Network interconnection in telecommunications," Economic Journal , 108, 545-564. [5] Pio Baake, and Anette Boom (2001), "Vertical product differentiation, network externalities, and compatibility decisions," International Journal of Industrial Organization, 19, 267-284. [6] A. Banerji, and Bhaskar Dutta (2009), "Local network externalities and market segmentation," International Journal of Industrial Organization , 27, 605-614. [7] Shai Bernstein, and Eyal Winter (2012), "Contracting with heterogeneous ex- ternalities," American Economic Journal: Microeconomics, 4(2), 50-76. [8] Francis Bloch, and Nicolas Quérou (2013), "Pricing in social networks," Games and Economic Behavior, 80, 243-261. [9] Lawrence E. Blume, David Easley, Jon Kleinberg, and Éva Tardos (2009), "Trading networks with price setting agents," Games and Economic Behavior, 67, 36-50. [10] Béla Bollobás (1998), Modern Graph Theory, Springer: New York. [11] Wilko Bolt, and Alexander F. Tieman (2008), "Heavily skewed pricing in two- sided markets," International Journal of Industrial Organization, 26, 1250- 1255. [12] Luís M. B. Cabral (2011), "Dynamic price competition with network effects," Review of Economic Studies, 78, 83-111. [13] Luís M. B. Cabral, David J. Salant, and Glenn A. Woroch (1999), "Monopoly pricing with network externalities," International Journal of Industrial Orga- nization, 17, 199-214. [14] Bernard Caillaud and Bruno Jullien (2001), "Competing Cybermediaries," Eu- ropean Economic Review, 45, 797-808. [15] Bernard Caillaud and Bruno Jullien (2003), "Chicken and egg: competition among intermediation service providers," Rand Journal of Economics, 34(2), 309-328. [16] Ozan Candogan, Kostas Bimpikis, and Asuman Ozdaglar (2012), "Optimal pricing networks with externalities,"  Operations Research, 60(4), 883-905. [17] Vasco Carvalho (2014), "From micro to macro via production networks," work- ing paper, University of Cambridge. [18]  Philip H. Dybvig, and Chester S. Spatt (1983), "Adoption externalities as public goods," Journal of Public Economics, 20, 231-247. [19] Oystein Fjeldstad, Espen R. Moen, and Christian Riis (2010), "Competition with local network externalities," working paper. [20] Jean J. Gabszewicz and Xavier Y. Wauthy (2004), "Two-sided markets and price competition with multihoming," working paper. [21] Andrei Hagiu (2006), "Pricing and commitment in two-sided platforms," Rand Journal of Economics, 37(3), 720-737. [22] Jason Hartline, Vehav S. Mirrokni, and Mukund Sundararajan (2008), "Op- timal marketing strategies over social networks," Proceedings of WWW 2008, Beijing, China, 189-198. [23] Bruno Jullien (2011), "Competition in multi-sided markets: divide and con- quer," American Economic Journal: Microeconomics, 3, 186-219. [24] Ulrich Kaiser and Julian Wright (2006), "Price structure in two-sided markets: Evidence from the magazine industry," International Journal of Industrial Or- ganization, 24, 1-28. [25] Michael L. Katz, and Carl Shapiro (1985), "Network externalities, competition, and compatibility," American Economic Review, 75, 424-440. [26] Jean-Jacques Laffont, Patrick Rey, and Jean Tirole (1998), "Network competi- tion: I. Overview and nondiscriminatory pricing," Rand Journal of Economics, 29(1) 1-37. [27] Jean-Jacques Laffont, Patrick Rey, and Jean Tirole (1998), "Network competi- tion: II. Price discrimination," Rand Journal of Economics, 29(1) 38-56. [28] Paul Milgrom, and John Roberts (1990), "Rationalizability, learning, and equi- librium in games with strategic complementarities," Econometrica, 58(6), 1255- 1277. [29] Jack Ochs, and In-Uck Park (2010), "Overcoming the coordination problem: dynamic formation of networks," Journal of Economic Theory, 145, 689-720. [30] Alexei Parakhonyak, and Nick Vikander (2013), "Optimal sales schemes for network goods," working paper. [31] In-Uck Park (2004), "A simple inducement scheme to overcome adoption ex- ternalities," Contributions to Theoretical Economics, 4(1), Article 3. [32] Geoffrey G. Parker, and Marshall W. Van Alstyne (2005), "Two-sided network effects:  A theory of information product design,"  Management Science, 51(10), 1494-1504. [33] Giacomo Pasini, Paolo Pin, and Simon Weidenholzer (2008), "A network model of price dispersion," working paper. [34] R. Tyrrell Rockafellar (1997), Convex Analysis, Princeton University Press: Princeton, N.J. [35] Jeffrey H. Rohlfs (1974), "A theory of interdependent demand for a communi- cations service,"  Bell Journal of Economics, 5(1), 16-37. [36] Ilya Segal (2003), "Coordination and discrimination in contracting with exter- nalities: Divide and conquer?" Journal of Economic Theory, 113, 147-327. [37] Tadashi Sekiguchi (2009), "Pricing of durable network goods under dynamic coordination failure," working paper. [38] Arun Sundararajan (2003), "Network effects, nonlinear pricing and entry de- terrence," discussion paper, NYU. (Not to be included in the paper.) This section analyzes an equilibrium with market segmentation by the two firms We say that an equilibrium (p*,q*,σ) entails complete market under  linearity. segmentation if every buyer chooses either A or B : i.e.,there exists a bipartition ( I 1 , I 2 ) of the buyer set I such that I 1 , I 2̸= ∅ and I 1 = { i : σ i ( p ∗ ,q ∗ ) = A } and I 2 = { i : σ i (p*,q*) = B}. The following proposition presents a sufficient condition for the non-existence of an equilibrium with complete market segmentation. As can be readily verified, this condition holds in the line network of Section 4. Proposition B.1 (Non-existence of a complete segmentation equilibrium) Suppose that the buyer network G is such that for any bipartition ( I 1 , I 2 ) of the set of buyers,
Suppose that the externalities are h-linear for h > 0. Then there exists no equilib- rium with complete market segmentation. Proof. Suppose that for some bipartition ( I 1 , I 2 ) with I 1 , I 2  ≠ 0 , there exists and equilibrium ( p*, q*, σ ) such that buyers in I 1 choose firm A , and buyers in I 2 choose firm B in equilibrium. For any j ∈ I 1 , v d j − p j ≥ max < v d j − q j , 0 k so that p j d ž )h + p ž . Suppose without loss of generality that + p = (d 2 −
Suppose now that firm A offers a DC price vector p such that under ( p,q*), buyers in I 1 precede those in I 2 in the elimination process. Since buyer i finds A dominant if p i < min { v ³ i − v đ − s i + q i , v ³ i }, firm A 's payoff from buyers in I 1 is bounded from below  by
On the other hand, by setting K = I 1 and J = I 2 in Lemma A.3 and noting that q j = min {q j ,v j } = q j for j ∈ I 2 , we see that firm A 's payoff from buyers in I 2 is bounded from below by
Since (p*,q*,σ) is an equilibrium, ∑ j ∈ 1 , (q ξ − c) ≥ 0 so that r( I 2 | I 1 ,q*) ≥ 1 hL( I 1 , I 2 ). It follows that firm A 's payoff from offering a DC price vector p isfies
which is a contradiction to our assumption that ( p *,q *,σ ) is an equilibrium. ■ It remains an open question whether the existence of a bipartition ( I 1 , I 2 ) such that ∑ i ∈ I , ( d † − d † ) ≥ 0 and ∑ i ∈ I , ( d † − d † ) ≥ 0 ensures the existence of a complete segmentation equilibrium.  It is, however, not difficult to show that MC cost pricing is consistent with a complete segmentation equilibrium under h -linearity if there exists a bipartition ( I 1 , I 2 ) such that d 2 ≥ d 2 for every i ∈ I 1 and d 2 ≥ d 2 for every i ∈ I 2 . In other words, ( p,q,σ) is a complete segmentation equilibrium if ( p,q) = ( z,z) for z = (c,...,c) and σ is extremal with respect to (p,q) with σ i (p,q) = A for i ∈ I 1 and σ i (p,q) = B for i ∈ I 2 . In what follows we show a slightly stronger condition on the network guarantees the existence of a complete segmentation equilibrium when the externalities are approximately linear. Specifically, we say that the buyer network is bi-cohesive if there exists a bipartition ( I 1 , I 2 ) of the set I of buyers such that for m, n = 1, 2, and m ≠ n,
Intuitively, in each element of a bipartition ( I 1 , I 2 ), there are core and peripheral buyers: The core buyers are those who have strictly more neighbors in the same set than in the other set, while the peripheral buyers have as many neighbors in the same set as in the other set. The definition of a bi-cohesive network is a natural extension of a cohesive set that is studied extensively in social network theory, and is also closely related to the definition of a cohesive network proposed by Morris (2000).³ 8  A line of four or more buyers is bi-cohesive if I 1 consists of at least two buyers on the left, and I 2 consists of at least two buyers on the right. The buyers on the two ends can be taken as core buyers in this case. The regular network in Figure 2 is also bi-cohesive when we take I 1 = {1,2,3,4} and I 2 = {5,6,7,8}. Buyers 2 and 3 are core buyers for I 1 and buyers 6 and 7 are core buyers for I 2 . More generally, the following lemma describes a sufficient condition for a network to be bi-cohesive based on the notion of connectedness. 39 Two paths from i to j are disjoint if they have no link in common. For any integer n , we say that a subset J ⊂ I is n-connected if for any i, j ∈ J , there are n disjoint paths within J connecting i to j . Lemma B.2 (Buyer clusters and bi-cohesiveness) A network is bi-cohesive if for an integer n, there exist two n-connected disjoint sets of buyers J 1 and J 2 with | J 1 | , |J2| ≥ 2 such that there exist at most n disjoint paths connecting J1 to J2. Let m ≤ n be the number of disjoint paths connecting J 1 and J 2 . By Proof. Menger's theorem, there exists a set L of m links such that removal of those links separates J 1 from J 2 . Denote L = { i 1 j 1 , . . , i m j m } , where i k j k is the link between buyers ik and jk (k = 1, . . . ,m). Define I 1 and I 2 to be the sets of buyers that are connected to J 1 and J 2 , respectively, after the removal of links in L . Without loss of generality, we name the links so that i1,...,im are connected to J1, and j1,...,im are connected to J 2 , after the removal of L . Take i 1 . If i 1 ∈ J 1 , then i 1 has at least n neighbors in J 1 ⊂ I 1 and at most m neighbors in I 2 . If i 1̸ξ J 1 , then i 1 again has at least as many neighbors in I 1 as he does in I 2 since otherwise, we would have a smaller set L ′ of links than L whose removal separates J 1 from J 2 . If there is a buyer in I 1 other than i 1 , . . . , im , then he is a core buyer of I 1 since he has no neighbor in I 2 by definition. If, on the other hand, there is no other buyer in I 1 than i 1 , . . . , im, then at least one of them is a core buyer: Since | J 1 | ≥ 2, m ≥ 2 so that at least one of i 1 , . . . , i m has strictly fewer neighbors in I 2 than m , whereas he has at least n ≥ m neighbors in J 1 ⊂ I 1 . ■ According to Lemma B.2, a network is bi-cohesive if there are at least two "clusters" of buyers who are closely linked among themselves. Such clusters can be a natural consequence of geographic and other proximity among some subsets of buyers. Proposition B.3 (Complete segmentation equilibrium under approximate linear- ity) Suppose that G is bi-cohesive. For any h > 0, there exists ε > 0 such that if the externalities are ε-close to h-linear, there exists an SPE (p*,q*,σ) in which buyers in I 1 choose firm A and buyers in I 2 choose firm B. In this SPE, p i 1 = c + δ and q i, = c − δ for a single core buyer i, ∈ I 1, p i, = c − δ and q i, = c + δ for a single core buyer i2 ∈ I2, and p i = q i = c for any other buyer i, where
As seen, δ is the maximal benchmark payoff that is strictly positive under generic externalities (Lemma 8.1). Each firm's equilibrium payoff equals δ , while the sum of the markups and markdowns over all buyers equals zero ( i.e., ∑ i ( p ∗ − c ) = ∑ i (q ; − c) = 0). Figure 6 illustrates the equilibrium for the line network of four buyers. As in Proposition 6.1, any deviation by either firm results in the play of the extreme equilibrium that least favors the deviating firm. Note that the core- periphery pricing strategy is a natural form of price discrimination: It charges a markup to a core buyer of the own market segment who finds it more difficult to unilaterally switch to the other firm because of the adoption decision of the majority of his neighbors. To see that neither firm has an incentive to deviate, suppose that firm A employs a DC price vector p . We can verify that βξ (p,q*) = d i − αξ (p,q*) for every i for whom x i = A is k -dominant. It follows that
As noted above, MC pricing is consistent with a complete segmentation equilib- rium in a bi-cohesive network. Since δ → 0 in (73) as the externalities approach h -linearity, the pricing strategy of Proposition B.3 equals MC pricing in the limit. Hence, we readily conclude that MC pricing under linearity is robust for a segmen- tation equilibrium in a bi-cohesive network. Corollary B.4 (Robustness of MC pricing for a segmentation equilibrium in a bi- cohesive network) Suppose that the network G is bi-cohesive with bipartition ( I 1 , I 2 ), and let (p,q) = (z,z) for z = (c,...,c) and σ be extremal with respect to (p,q) with σ i (p,q) = A for i ∈ I 1 and σ i (p,q) = B for i ∈ I 2 . Then the equilibrium (p,q,σ) under h-linearity is robust. Let
When the externalities are ε-close to h -linear,
and hence δ < 2Nε.
Let (I 1 , I 2 ) be the partition of the buyer set I , and let i A E I 1 and i B E I 2 be the core buyers of the respective sets: |N i λ ∩ I 1 | > |N i λ ∩ I 2 | and |N i B ∩ I 2 | > |N i B ∩ I 1 |. We specify (p*,q*,σ) as follows:
and
We first show that the buyers' action profile following (p*,q*) is a NE. If i E I 1 \ { i A }, then x i = A is a best response since γ|NiNI1| _ pi = γ|NiNI1| _ c ≥ γ|NiNI2| _ c = γ|NiNI2| _ qi.
Hence, if we take
55 then for any ε < ε , (73) implies that
The symmetric argument shows that x i = B is a best response for each i ∈ I 2 following (p*,q*). We will next show that firm A has no profitable deviation. Let p be any deviation by firm A, and D k = D k (p,q*). Suppose that i ∈ D k . By Lemma 6.2, we may assume that Ni ∩ D λ = 0. For any j ∈ Ni, we observe that
We can see that (75) holds as follows: First, take j ≠ iB. Since then q ∗ ≤ c ≤ v 0 , x j = B is not dominated by x j = ∅. Hence, if x j = A is not dominant in S ℓ− 1 for ℓ = 1, . . . , k − 1 (i.e., j̸= ∪ ξ − 1̃D́A ), then B ∈ S k − 1 . On the other hand, if j = iB, then qj = δ + c. Since i ∈ D k . i ∈ U k =1 D k . Since i̸= i B , B ∈ S k − 1 by the above. It follows that β k ≥ 1. Hence,
Hence, (75) holds for any i , which in turn implies that βξ = d i − αξ for any i and k. Hence, by (9), if i ∈ D k , then
Therefore, firm A's payoff π A under ( p,q*) satisfies
We will show that π A ( p,q*,σ) ≤ 0 for any p by considering the following two cases separately. Suppose first that D A ⊆ I so that I \ D A̸= ∅ . Since the right-hand side of (76) is continuous in ε , if we show that it is less then −h under exact linearity, then π A (p,q*) < 0 holds under approximate linearity. Under exact linearity, (76) becomes
Since ∑ k =1 ∑ i ∈ D k α k = L( D A ) and ∑ k =1 ∑ i ∈ D k d i = 2 L( D A ) + L( D A , I \ D A ), we have π A (p,q*,σ) < −hL(D A , I \ D A ) ≤ −h, where the inequality follows since I \ D A ≠ Suppose next that D A = I. In this case, (q * − c) = 0 by definition so that the definition of δ implies
[1] Stephen Morris (2000), "Contagion," Review of Economic Studies, 67, 57-78. [2] Stephen B. Seidman (1983), "LS Sets and cohesive subsets of graphs and hyper- graphs," Social Networks, 5, 92-96.