Evolution of a Collusive Price in a Networked Market

Abstract

This paper studies evolution of firms’ behavior in a networked Bertrand oligopoly market, in which firms who are located on vertices of a network compete in price with their neighbors. This network model is also applied to a market with multi-dimensionally differentiated products. In a non-networked market, it is known that the Bertrand–Nash equilibrium pricing is evolutionarily stable. We show, however, that in our large networked market, the Bertrand–Nash equilibrium price is not stable but a collusive price is evolutionarily stable under weak selection. As the magnitude of transportation cost increases, firms charge a more collusive price in the long run. The results suggest that collusive pricing prevails in a large market if and only if it is networked.

1 Introduction

In the classic Bertrand oligopoly market, where firms compete in price, the theory of industrial organization predicts that no firms enjoy excess profits. Since all consumers buy products from firms charging the lowest price, independently of a number of firms, all firms cannot raise a price above their identical marginal cost in the Bertrand–Nash equilibrium.

If a spatial network structure is embedded in a Bertrand duopoly market, on the contrary, it is also well-known that the marginal cost pricing is not stable, by applying the literature on horizontal product differentiation. In the standard Bertrand duopoly model with product differentiation, two firms are assumed to be located in the endpoints and consumers are uniformly distributed on an interval. Then, it is shown that both firms charge a price strictly higher than their marginal cost in the Bertrand–Nash equilibrium [11, 25].¹

In a (spatially) networked market, to buy a product from a firm, consumers distributed on a link must incur some transportation cost, which increases in a distance to that firm on a network. Since a closer firm’s product is more attractive than the other’s if two firms charge the same price, products are differentiated for consumers even when both firms manufacture homogeneous products. Thus, employing the above result, we observe that an equilibrium price is also higher than the marginal cost in a spatially networked market.

Even in a Bertrand oligopoly market, in which a large number of firms participate, the same observation is found as long as the product differentiation is modeled as a single-dimensional network. When firms are dispersed on an interval, Economides [13] shows that every firm charges a price higher than the marginal cost and that the equilibrium price structure is U-shaped, so that the equilibrium prices of firms close to the endpoints are high. When firms are located equidistantly on a circular network, which has no endpoints, Salop [42] shows that all firms charge the same equilibrium price higher than the marginal cost.

This paper further investigates the long-run stability of the Bertrand–Nash equilibrium pricing in a networked market in which more than two firms are spatially distributed on a large regular network of degree $k\ge 2$, by extending the Salop’s circular networked market. A regular network of k is a symmetric network where each vertex has k links and the length of each link is normalized to be one.

Every firm is located on a vertex of a network, and every consumer located on a link chooses one of the two directly linked firms. For example, on a regular network of $k=4$, every firm competes with four directly linked firms. Since in the Salop’s circular network, every firm links with two adjacent firms, i.e., $k=2$, our networked market model includes the Salop’s circular network as a special case.

The paper also provides a new model to study a version of product differentiation. Since the seminal paper by Hotelling [25], the network model has been applied not only to the study of a spatial networked market but also to the study of abstract product differentiation. Similarly, our regularly networked market model can be applied to the following market with multi-dimensionally differentiated products, as an extension of Salop [42].²

Suppose that a product space is networked by the square lattice network, which is a regular network of degree $k=4$. Then, since each firm supplies a product which is located on the intersection of two circular lines, the product space are differentiated by two dimensions. For example, a market of automobiles (in the same class) is differentiated by color and design. If the distance from a consumer to a firm is given by the distance on the lattice (like $L_1$-distance), a consumer must chooses one of the two directly linked firms’ products because the transportation cost is increasing in distance, as long as the price differences are not large. Indeed, in our model, the transportation cost increases quadratically in distance, so that the price difference is so small as to choose one of the two, compared with the difference in transportation costs.

Furthermore, our approach has a technical advantage. Since a regular network is symmetric, there are no endpoints and no corners. Salop [42] argue that this property makes our analysis simple and tractable, and then we can focus on the essential qualitative interactions of firms.³ Since our model is an extension of Salop’s, we apply the same justification to the analysis of multi-dimensional product differentiation.

To solve the long-run pricing behavior of firms on a large regular network of k, we apply evolutionary game theory. This approach follows the seminal paper by Alchian [1]. He argues that when there are many firms, the evolutionary approach is appropriate to the analysis of the long-run behavior for the following reason.

Every firm, in reality, faces uncertainty caused by the imperfect foresight of what prices will be charged by most of the others because firms are often anonymous when there are many firms. If firms have the imperfect foresight, it is natural for firms to imitate simply a price of a presently successful firm because it is hard to implement a complicated history-dependent strategy to maximize profits.

In a non-networked market, or a market with no product differentiation, the literature has been examined the long-run evolutionary stability of the Bertrand–Nash equilibrium price, which is equal to the marginal cost. Although the marginal cost price is not evolutionarily stable [41], Hehenkamp and Leininger [21] and Hehenkamp et al. [23] show that the smallest price strictly above the marginal cost is evolutionarily stable. Alós-Ferrer et al. [6] further find that the marginal cost price is stable under their stochastic imitation Markov process whenever the cost function is linear or quadratic.

From the above existing results, one may conjecture that the Bertrand–Nash equilibrium price is also evolutionarily stable in our networked market.⁴ However, it is not known whether the Bertrand–Nash equilibrium is evolutionarily stable or not in a networked market with spatially differentiated products. This paper, therefore, by focusing on a role of networks, re-examines the long-run evolutionary stability of Bertrand–Nash equilibrium pricing.

Our main motivation is that the presence of this local competition may cause the Bertrand–Nash equilibrium price to be evolutionarily unstable and a higher price to be stable for the following reason. In the non-networked Bertrand market with a large number of anonymous firms, the Bertrand–Nash equilibrium outcome is evolutionarily stable because no collusion survives in the long run. When all firms compete with all anonymous firms, the profit of the deviation from collusion is large for every firm because the deviation attracts all consumers in the market.

In our networked market, however, this argument does not work. While there are a large number of indirectly linked anonymous firms, each firm faces price competition with only specific firms, who are directly linked. This weak level of local price competition can cause the Bertrand–Nash equilibrium price to be evolutionarily unstable and some collusive price to be evolutionarily stable globally in the long run. As the number of direct competitors decreases, the deviation from a collusive price becomes less profitable, and then the relative fitness of a collusive price becomes larger.

Thus, this paper re-examines the evolutionary stability of the Bertrand–Nash equilibrium price and collusive prices in a networked market. To this end, we analyze the evolutionary dynamics of the pricing behavior of firms, by applying the theory of evolutionary games on graphs. This is recently developed by Ohtsuki and Nowak [39] on the basis of the pair approximation [34]. We will show that thanks to the pair approximation, the evolutionary dynamics on a network is approximated by a replicator equation.

The pair approximation is suitable when a large number of small symmetric firms compete on a network. In such a market, it is hard to identify an exact form of a whole network. To solve their average behavior, by symmetry among firms, it is natural to assume that every pair of firms is linked with an identical probability and that each firm has the same number of rivals, which yields a random regular network. It is known that the pair approximation performs well for random regular networks on which there are many vertices (firms).⁵

Our dynamics is based on the following imitation updating of successful behavior. At every time, one firm is chosen for revision at random from the entire population. Then, the chosen firm imitates one of the observed prices subject to his observed distribution of prices and total profits of firms. Each firm keeps his revised price until he receives a next revision opportunity. We assume, in particular, that a network depicts the flow of information, in addition to the structure of product differentiation. Since every firm has k links on a regular network of degree k, the chosen firm observes only $k+1$ pairs of prices and total profits of all his neighbor firms including himself. Then, he imitates one of those with a probability proportional to their fitnesses.

The imitation of firms occurs under weak selection, following Ohtsuki and Nowak [39]. The contribution of each firm’s profit to fitness is weighted by selection intensity w. The selection intensity w is weak if $w \ll 1$. This means that each firm’s fitness is determined not only by the particular profit, but also by many different factors, such as profits from other products, internal management issues, or global market shocks, which are not modeled here [17, 36]. On a large complicated network, on which there are many firms, it is natural to assume that every firm cannot observe all the factors of the others and their contributions to survival. Furthermore, since many factors contribute to firm’s success in the long run, the contribution of each one factor is small. Therefore, this paper assumes the weak selection.

We will show that the selection intensity w plays a crucial role in our replicator dynamics on a large regular network, while it controls only the velocity of the evolution in a non-networked market.⁶ Thanks to the weak selection, we can construct the replicator equation on a network by separating the evolution of local frequencies among directly linked firms and that of global frequencies among all firms in a market.

The main result of this paper is given as follows: Under the weak selection, the Bertrand–Nash equilibrium price never survives, and there is a unique asymptotically stable price that is collusive. The stable collusive price is monotonically increasing with respect to (w.r.t.) the magnitude of transportation cost. In particular, if the price-cap is relatively lower than the magnitude of transportation cost, the stable collusive price reaches the price-cap, which maximizes joint profit. This result contrast with the existing results of non-networked markets with no product differentiation. The product differentiation causes the Bertrand–Nash equilibrium to be unstable in the large networked market.

An intuition that the most collusive price is asymptotically stable is given as follows: A low price attracts consumers but lowers a unit margin, and a high price loses consumers but raises a unit margin. When all firms jointly charge a collusive price, this trade-off between a low price and a high price disappears. Since all firms raise a price to the price-cap simultaneously, each firm enjoys the largest unit margin by keeping the equal share.

Since it is impossible for firms to raise a price beyond the price-cap, we only take into account a mutant firm who charges a slightly lower price. If the price-cap is relatively lower than the magnitude of transportation cost, the mutant is less successful because the deviation attracts only a small number of additional consumers, while it reduces the unit margin. Thus, even if such a firm invades, it is hard to prevail, and hence the collusive price is stable.

Therefore, in networked markets, we find that a collusive price is sustainable under the evolutionary pressure, and the evolutionary stability of the Bertrand–Nash equilibrium is no longer obtained. Thanks to the interplay of local competition and weak selection, firms charge a collusive price in the long run even if they cannot maximize their profits by employing a complicated history-dependent strategy but imitate simply the price of a successful neighbor.

Remark finally that the marginal cost price is also not asymptotically stable, as well as the Bertrand–Nash equilibrium price. In a market with product differentiation, the marginal cost price yields zero profit, but the Bertrand–Nash equilibrium price higher than the marginal cost yields a positive profit. Thus, in our networked market, each firm earns a more excess profit than that in the Bertrand–Nash equilibrium by charging a collusive price.

Related Literature

The study on the Bertrand oligopoly market with product differentiation usually investigates the sequential location-price competition game, in which each firm first chooses a location on a network and then chooses a price. If the product differentiation is represented by a single-dimensional interval, it is well-known that the principle of maximum differentiation holds [11]. Economides [14] shows that it is an equilibrium for firms to locate equidistantly in Salop’s circular networked market.

In a Bertrand duopoly market with multi-dimensional product differentiation, Irmen and Thisse [28] show that the principle of minimum differentiation holds for all but one dominant dimension. The evolutionary stability is also investigated. Hehenkamp and Wambach [22] show that the principle of minimum differentiation emerges in all dimensions.

However, this paper investigates no location game. The difficulty in our Bertrand oligopoly with more than two firms arises because it breaks the following symmetry of a network. Since the length of each link is normalized to be one, every firm has k units of potential consumers in a regular network of k. If firm i moves a little, say $\epsilon$, toward the center of link ij, it implies that i moves $\epsilon$ against the center of link $ij'$ for any other $j' \ne j$. The length of ij decreases to $1-\epsilon$, but that of $ij'$ increases to $1+\epsilon$. By this asymmetry, it is hard to analyze the location choice because our derivation of the replicator dynamics is based on the symmetry of a network. Furthermore, it is well-known that even the existence of Bertrand–Nash equilibria heavily depends on specifications in the Hotelling linear interval model [10, 13].

Our results can be applied to examine the evolutionary stability of a price in a buyer-seller networked market without product differentiation. In a buyer-seller network, a link represents a relationship between a pair of a buyer and a seller. Since every pair must establish a relationship, or a link, to engage in exchange, a network structure plays a crucial role in various buyer-seller markets. For example, Nava [35] finds that trading is efficient in a large buyer-seller networked market with quantity-setting firms. Kranton and Minehart [32] show that the equilibrium price is Walrasian in a buyer-seller networked auction (for further discussion, see, e.g., Goyal [18] and Jackson [29]).

Despite its importance, the existing literature has not focused on the long-run evolutionary stability. Our results can provide an evolutionary justification of those results. In a buyer-seller networked market, only trading relationships are restricted, and products are not differentiated. In the limit of no product differentiation, we show in Corollary 1 that the stable price, equal to the BNE price, converges to the marginal cost. Thus, firms enjoy no excess profit in the long run.

Our results can also provide an evolutionary justification of the prediction of repeated games for collusive pricing. When firms compete repeatedly, it is well-known that firms can enjoy excess profits by (tacit) collusion [33, Chapter 6]. The folk theorem shows that there is a continuum of collusive equilibrium outcomes, in which firms charge a higher price by employing a complicated history-dependent strategy, in addition to the Bertrand–Nash equilibrium.

However, the folk theorem is often criticized because of a lack of criteria to determine which prediction is plausible. Indeed, there is a disagreement concerning whether a collusive equilibrium is stable in the long run. For example, Farrell and Maskin [16] show that renegotiation-proofness favors a Pareto-efficient equilibrium, which is collusive. Bernheim and Whinston [8] find that multimarket contact can facilitate collusion. On the contrary, Green [19] and Kaneko [30] show that if there are many anonymous firms, every equilibrium of repeated games is the repetition of a static Nash equilibrium, in which all firms charge the marginal cost price.⁷ In the experiment by Huck et al. [26], furthermore, no collusive price is observed even when information about individual behavior is provided for subjects.

By applying our results as a criterion, we can select a more plausible equilibrium. When there are many anonymous firms, the Bertrand–Nash equilibrium will emerge in a non-networked market with no product differentiation, but a collusive equilibrium will emerge in a networked market with product differentiation.

The Bertrand–Nash equilibrium pricing is repeatedly examined from various aspects. For example, in addition to the Bertrand–Nash equilibrium, Baye and Morgan [7] and Kaplan and Wettstein [31] show that there are other mixed Nash equilibria in which firms enjoy excess profits even under complete information. However, as argued by Kaplan and Wettstein [31], their sufficient condition for existence that each firm’s profit is unbounded is unrealistic.

If each firm’s cost function is quadratic, there are pure Bertrand–Nash equilibria yielding an excess profit [12]. However, Alós-Ferrer et al. [6] show that only the Walrasian price, at which the marginal cost function intersects with the demand function, is evolutionarily stable. Hirata and Matsumura [24] show that the equilibrium price converges to the Walrasian price as the degree of product differentiation goes to zero.

The evolution of quantity-setting behavior of firms has also been investigated. The results contrast to those of the Bertrand price competition. In the standard Cournot quantity competition with no product differentiation, firms enjoy excess profits in the Cournot-Nash equilibrium by under-supplying products. However, using the evolutionary approach, Schaffer [44] finds that profit-maximizing firms are not the best survivors in some markets. Huck et al. [26, 27] examine the theoretical results by experiment. They find that if possible, firms set the Walrasian quantity as a consequence of imitation learning.

The Walrasian behavior depends on the assumption of firms’ memories. Vega-Redondo [45] show that Walrasian behavior evolves in any quantity-setting oligopoly satisfying the law of aggregated demand is satisfied, as long as firms have no memory. By contrast, Alós-Ferrer [2] shows that if every firm memorizes the quantities produced and the profits realized in the last few periods, the Cournot-Nash equilibrium quantity is also stochastically stable in addition to the Walrasian quantity. However, Alós-Ferrer and Buckenmaier [3] observe that the long-run distribution of outcomes is skewed toward the Walrasian quantity, by running computer simulation.

The evolutionary approach based on imitation has also applied to the study of coordination games. In coordination games, there are two strict Nash equilibria; one is payoff-dominant (efficient) and the other is risk-dominant (safe). On a circular network, it is shown that an information structure plays a crucial role [46]. The inefficient risk-dominant one is favored if players observe only the information of direct neighbors, but the efficient payoff-dominant one is favored if they observe the information of n-step neighbors in addition to direct neighbors [4, 5]. In terms of efficiency, since the Bertrand competition game is in the class of prisoners’ dilemma games, our results suggest that the strictly dominated collusive pricing strategy, which is efficient for firms, is favored by natural selection in a networked market if the magnitude of transportation cost is large.⁸

The remainder of the paper is organized as follows. In Sect. 2, we develop our networked market. In Sect. 3, we solve an evolutionarily stable price. In Sect. 4, we examine the stochastic stability of those evolutionarily stable prices and discuss welfare. In Sect. 5, we conclude with several remarks. In “Appendix”, we provide the proofs of our results.

2 Preliminaries

There are firms in a market. Let I be the set of firms. Each firm $i\in I$ manufactures $x\in {\mathbb {R}}_+$ units of homogeneous products by incurring cost cx, which is symmetric among firms and linear in quantity, where c is the constant uniform marginal cost. Firm i sells each unit at price $p_i$. We assume that each i’s price $p_i\in [c,{\bar{p}}] =S$ for some upper bound $c<{\bar{p}}<\infty$.

The market is networked. We denote a non-directed connected network by $g=(I,L)$, where $L\subset \{ij\}_{i,j\in I}$ ($i\ne j$) is a set of links. If $ij\not \in L$, a pair of firms (i, j) is not directly linked, and if $ij\in L$, a pair of firms (i, j) is directly linked. Let $\eta ^i(g)= \{j|j\in I, ij\in L\}$ be the set of adjacent firms directly linked with i.

We consider a class of regular networks of degree k in which the number of firms |I| is sufficiently large. A regular network g of k is a network in which every firm has k links (i.e., $|\eta ^i(g)|=k$ for all i). The class of regular networks involves the empty network of $k=0$, the circle network of $k=2$, and the complete network of $k=n-1$. Since any regular graph of k with $k=0,1$ is not connected, we assume $k\ge 2$.⁹

Roughly speaking, the degree k, the number of each firm’s adjacent firms, indicates a level of local competition. In the regular network of $k=2$, firms are located on a circle, so that each firm i compete with only two adjacent rival firms $j,j'$. In a cubic regular network of $k=3$, in contrast, each firm i compete with a new rival $j''$ as well as $j,j'$. As k increases, since the number of rivals increases, the competition among firms becomes stronger.¹⁰

Each link $ij\in L(g)$ has length one, and a unit of consumers are uniformly distributed on each link ij. Every consumer on link ij, who demands one unit of products with the identical value $v<\infty$, can buy a unit of products from firm i or firm j, and cannot buy it from any other firm. To buy it from firm i, he must incur transportation cost $d\xi _{ij}^2$, and to buy it from firm j, he must incur $d(1-\xi _{ij})^2$. Here, $\xi _{ij}\in [0,1]$ is the distance from firm i to each consumer located on link ij, and parameter d is a magnitude of the transportation cost. Remark that the magnitude $d>0$ is common among all consumers.

Each firm i charges the same price $p_i$ to consumers for every i’s unit of products. That is, we assume that no firm can discriminate consumers on the basis of links. For example, in a network of $k=2$, every firm i must charge the same unit price $p_i$ for all consumers located on both links ij and ik in $\eta ^i(g)$.

For tractability, we assume that the value is large enough so that $v> {\bar{p}}+d$. This standard assumption, by $v-{\bar{p}}-d>0$, implies that all consumers on ij choose to buy a unit either from firm i or from firm j, and they never choose not to buy for any $p_i,p_j<{\bar{p}}$. It enables us to solve the demand function $D(p_i,p_j)$ by using the indifference condition between i and j, as follows.¹¹

For a profile of prices ${\mathbf {p}}=(p_i)_{i\in I}$, each firm i faces aggregated demand ${\mathcal {D}}_i ({\mathbf {p}}) = \frac{k}{2} + \max \{-\frac{k}{2} ,\min \{ \frac{k}{2} ,\sum _{j\in \eta ^i(g)} \frac{1}{2d}(p_j-p_i) \} \}$. If a consumer buys i’s product, his net payoff is $v-p_i-d\xi _{ij}^2$, and if he buys j’s product, his net payoff is $v-p_j-d(1-\xi _{ij})^2$. Each consumer buy i’s product if $v-p_i-d\xi _{ij}^2>v-p_j-d(1-\xi _{ij})^2$ and buy j’s product otherwise. By $D(p_i,p_j)\in [0,1]$, each firm i faces the aggregated demand function of link ij given by $D(p_i,p_j)= \max \{0, \min \{1, \frac{1}{2} + \frac{1}{2d}(p_j-p_i) \} \}$ for each $j\in \eta ^i(g)$. Summing these up yields the aggregated demand function ${\mathcal {D}}_i({\mathbf {p}})= \sum _{j\in \eta ^i(g)} \max \{ 0, \min \{1, \frac{1}{2} + \frac{1}{2d}(p_j-p_i) \} \} = \frac{k}{2} + \max \{-\frac{k}{2}, \min \{\frac{k}{2}, \sum _{j\in \eta ^i(g)} \frac{1}{2d}(p_j-p_i) \}\}$.

Each firm i earns profit $a(p_i,p_j)=(p_i-c)D(p_i,p_j)$ from each link $ij\in L(g)$, and i’s total profit $\pi _i({\mathbf {p}}) = (p_i-c){\mathcal {D}}_i({\mathbf {p}}) = \sum _{j\in \eta ^i(g)}a(p_i,p_j)$. Thus, each stage game is given by (I, S, a, g). In what follows, we focus on the long-run stability of symmetric profiles where all firms employ the same price, denoted by $p\in [c,{\bar{p}}]$.

Since i’s unique best response to $p_j$ is $p_i=\frac{1}{2}(p_j+c+d)$ if all firms $j\in \eta ^i(g)$ employ the same $p_j \in [c,c+3d]$, profile ${\mathbf {p}}$ with $p_i=c+d$ for all i, in which all firms employ $p=c+d$, is the unique symmetric strict Bertrand–Nash equilibrium (BNE). We say that price p is BNE if $p=c+d$ and that p is collusive if $p>c+d$.

3 Evolutionary Stability of Prices in the Networked Market

To investigate evolutionary stability, we discretize the set S of strategies. Each strategy $p_n \in S(N,N') = \{c,c+\frac{d}{N'},\ldots ,c+\frac{(N'-1)d}{N'}\}\cup \{c+d,c+d+\frac{e}{N-1},c+d+\frac{2e}{N-1},\ldots ,c+d+e \}$ for some $e>0$ and some $2\le N,N'<\infty$. Note that $c,c+d,c+d+e\in S$. The parameter $e\ge 0$ determines the upper bound of price ${\bar{p}}=c+d+e$, and the two parameters $N'$ and N are numbers of strategies in $[c,c+d)$ and $[c+d,c+d+e]$, respectively. We will consider the continuum of strategies $[c,c+d+e]$ by taking the limit of $N,N'\rightarrow \infty$.

Each firm i charges price $p_n \in S$ and earns profit $\pi _i({\mathbf {p}})$ for each unit of i’s products at every time t. The evolutionary fitness of each firm i is given by $W_i=1-w+w\pi _i$, where the parameter w represents the intensity of selection. We assume that selection is weak, i.e., $w \ll 1$. As argued in Introduction, the intensity w can be regarded as the relevance of firms’ profits to their survival in the networked market.

3.1 Imitation Updating in a Networked Market

Firms update their pricing strategies subject to the stochastic process under the following imitation updating rule. At each unit time $\Delta t$, a firm i is chosen at random for updating i’s price $p_i$ from the entire population.

Let u be the mutation rate. We assume that the mutation rate is so small that $u \ll 1$. With probability u, the mutation occurs. If the mutation occurs, the chosen firm i does not imitate any other firm’s strategy and simply employs one of the strategies subject to the uniform distribution on S.

With the remaining probability $1-u$, the chosen firm i observes pairs of prices and profits $(p_j,\pi _j)_{j\in \eta ^i(g)}$ of all adjacent firms.¹² Then, the firm i will keep i’s current strategy or imitate one of the strategies employed by i’s adjacent firms (including i-self) proportional to fitnesses.¹³ The probability that firm i employs j’s strategy is given by $\frac{W_j}{W_i + \sum _{l\in \eta ^i(g)} W_l}$ for each $j\in \eta ^i(g) \cup \{i\}$.

Therefore, the total probability that the chosen firm i switches to strategy $p_{m}$ employed by an adjacent firm is given by $(1-u)\frac{W_j}{W_i + \sum _{l\in \eta ^i(g)} W_l} + u \frac{1}{N+N'}$.

Non-networked markets First, consider the well-mixed population, or the complete network, instead of a networked market. Denote the frequency of price $p_n$ by $x_n$ and a state by ${\mathbf {x}}=(x_1,\ldots ,x_{N'+N})$. Since all firms are linked with each other, each firm observes the strategy distribution x of the others if he is chosen.

Then, regardless of selection intensity w, the mean dynamics is approximated by the standard perturbed replicator equation ([9]), given by $\hbox {d}x_n/\hbox {d}t = {\dot{x}}_n = x_n (f_n(x)-\phi (x)) + u(\frac{1}{N+N'} -x_n)$, where $f_n(x)= \sum _{m} x_m a(p_n,p_m)$ is the average profits of strategy $p_n$ and $\phi (x)$ is the average profits over the population.

Since $(c+d,c+d)$ is the unique strict symmetric Nash equilibrium, the state where all firms employ the BNE price $c+d$ is the unique asymptotically stable state in the limit of $u\rightarrow 0$. Therefore, no collusive price can diffuse and the BNE price $c+d$ uniquely evolves in the non-networked market.

Networked markets Now, we consider the dynamics under the imitation updating rule of pricing in a networked market. Provided that all firms employ the imitation updating rule, Ohtsuki and Nowak [39] construct the replicator equation under the weak selection $w\ll 1$ in a regular network of degree $k\ge 3$ (for $k=2$, see Ohtsuki and Nowak [37]). To derive the replicator dynamics on a network, we employ the pair approximation method, following their construction. In what follows, we take the large population limit $|I| \rightarrow \infty$ keeping k and w fixed.

We denote by $x_{n}$, the global frequency of strategy $p_n$, and by $x_{n,m}$, the global frequency of a pair of strategies $(p_n,p_m)$ in the entire population. Let $q_{n|m}$ be the local frequency of strategy $p_n$ around a firm employing strategy $p_m$. Then, the local frequency $q_{n|m}$ is given by the conditional probability that a focal firm employs $p_n$ given that an adjacent firm employs $p_m$, i.e., $q_{n|m}= x_{n,m}/x_m$. In a networked market, $q_{n|m}\ne x_n$. Each firm i employing $p_m$ meets an adjacent firm employing $p_n$ with probability $q_{n|m}$, not $x_n$.

To solve the steady state of ${\dot{q}}_{n|m}$, we employ the pair approximation.¹⁴ One can introduce a more detailed local frequency such as $q_{n|ml}$, which represents the conditional probability that a focal firm employs $p_n$ given that an adjacent firm employ $p_m$ and that a two-step adjacent firm employs $p_l$. However, the pair approximation assumes $q_{n|ml}= q_{n|m}$, i.e., a two-step adjacent firm does not affect the frequency of focal firm directly. Thanks to the approximation, we can obtain the analytical solutions of ${\dot{q}}_{n|m}=0$ and of ${\dot{x}}_n=0$.

As argued by Ohtsuki and Nowak [39], since the fitness $W_n=1-w+w\pi _n$, global frequencies $x_n$ change at rate w and local frequencies $q_{n|m}$ change at rate 1. By weak selection $w\ll 1$, global frequencies x evolves very slowly, but local frequencies $q_{n|m}$ evolves very quickly. Thus, time scales, $\Delta t$ and $\Delta t/w$, are separate, and then we regard global frequencies $x_n$ as constant until local frequencies $q_{n|m}$ equilibrate at time scale $\Delta t$.

We first show that the local frequency $q_{n|n}$ of strategy $p_n$ around a firm employing the same $p_n$ exhibits assortativity such that $q_{n|n}>x_n>q_{n|m}$ in a networked market. Consider time scale $\Delta t$ and the dynamics of local frequencies $q_{n|m}$. Suppose that firm i employing $p_n$ is chosen for revision.

By the small mutation, $u\ll 1$, we first observe that the total probability that the focal firm i imitates adjacent firm j’s strategy $p_m$ is approximated by

$$\begin{aligned} (1-u)\frac{W_m}{W_n + \sum _{j\in \eta ^i(g)} W_j} + u \frac{1}{N+N'}&= \frac{W_m}{W_n + \sum _{j\in \eta ^i(g)} W_j} + {\mathcal {O}}(u) \\&\approx \frac{W_m}{W_n + \sum _{j\in \eta ^i(g)} W_j} >0. \end{aligned}$$

By $W_n=1-w+w\pi _n$, this probability is

$$\begin{aligned} \frac{W_{m}}{W_{n} + \sum _{j\in \eta ^i(g)} W_j} = \frac{1-w+w\pi _j}{(k+1)(1-w) + w(\pi _i+ \sum _{j\in \eta ^i(g)} \pi _j)} = \frac{1}{k+1} + {\mathcal {O}}(w). \end{aligned}$$

The second equation is obtained by taking Taylor series at $w=0$. By the weak selection, $w\ll 1$, ${\mathcal {O}}(w) \approx 0$ and then $\frac{1}{k+1} + {\mathcal {O}}(w) \approx \frac{1}{k+1}$.

Thus, under the weak selection, the probability that firm i employing $p_n$ imitates strategy $p_m$ is approximated by

$$\begin{aligned} \sum _{\begin{array}{c} j\in \eta ^i(g) \cup \{i\} \\ p_j=p_m \end{array}} \frac{1}{k+1} = \frac{k_m+\delta _{nm}}{k+1} = \frac{\# \text { of firms employing } p_m\text { in }\eta ^i(g)\cup \{i\} }{\# \text { of firms in } \eta ^i(g)\cup \{i\} }, \end{aligned}$$

(1)

where $\delta _{nm}$ is the function such that $\delta _{nm}=1$ if $m=n$ and 0 otherwise, and $k_m$ is the number of adjacent firms employing $p_m$.

The total imitation probability is primely approximated only by the local strategy distribution of i’s adjacent firms. On the contrary, if the selection is not weak ($w\not \ll 1)$, the imitation probability is determined by not only the local distribution but also the fitnesses of adjacent firms. Thus, the weak selection assumption is essential to solve the local frequencies.

By solving steady state ${\dot{q}}_{n|m} = \hbox {d}q_{n|m}/ \hbox {d}t =0$ of local frequency, we obtain the following:

Theorem 1

For any m, n with $n\ne m$, the probabilities $q_{n|m}= \frac{(k-2)x_n}{k-1}$ and $q_{n|n} = \frac{(k-2)x_n+1}{k-1}$, and thus $q_{n|n}>x_n>q_{n|m}$.

The formal proof is given in “Appendix A.1”. The sketch of the proof is as follows: Focus on a pair (i, j). The number of firms employing $p_n$ around j increases by one if any adjacent firm employing $p_l$ ($\ne p_n$) is chosen and imitates $p_n$, or the mutation chooses $p_n$. Similarly, the number of firms employing $p_n$ decreases by one if any adjacent firm employing $p_n$ is chosen and imitates any other $p_l$, or the mutation chooses $p_l (\ne p_n)$. Denote the former probability by $\Pr ^+$, and the latter by $\Pr ^-$. Since the same argument holds for firm i, the local dynamics is approximated by ${\dot{q}}_{n|m} = 2(\Pr ^+ -\Pr ^-)$ under $w,u \ll 1$.

By the theorem, the probability $q_{n|n}$ that an adjacent firm of a firm employing $p_n$ employs the same strategy $p_n$ is higher than expected by global frequency $x_n$, but the probability $q_{n|m}$ that an adjacent firm of a firm employing $p_m$ employs another strategy $p_n$ is less than $x_n$.

Under the weak selection, if most of the adjacent firms employ a strategy $p_n$, then the chosen firm imitates $p_n$ with a high probability, regardless of their profits. Thus, a cluster of a strategy is easy to form, and then the local frequency exhibits assortativity. That is, the local frequency $q_{n|n}$ of strategy $p_n$ around a firm employing the same $p_n$ is higher than that of global frequency $x_n$. This assortativity results in that $q_{n|m}<x_n$ for $n\ne m$.

Remark that for a circular network of $k=2$, $q_{n|n}=1$. In the steady state of the local dynamics ${\dot{q}}_{n|m}=0$, all firms employ the same strategy. Since a firm inside a cluster never observes another strategy, the single lineage cluster of a strategy expands or shrinks, and never fragment into pieces at every time on a circle. Since the local dynamics never stops until this cluster is dead, or dominates the population, $q_{n|n}=1$ in the steady state. However, for $k\ge 3$, $q_{n|n}<1$ whenever $x_n<1$. On regular network of $k\ge 3$, the lineage cluster can fragment into pieces because it is possible for firms inside the cluster to observe and imitate another strategy employed by firms outside the cluster. Intuitively, by this difference, the replicator equation for $k=2$ is different from that for $k\ge 3$, as shown in the following.¹⁵

Next, we consider long time scale $\Delta t /w$ and the dynamics of global frequencies $x_n$. Note that in the rest of this section, we assume no mutation ($u=0$) to focus on the effect of networks. We consider small positive mutation $u>0$ in Sect. 4.1.

By ${\mathcal {O}}(w)/w \not \ll 1$, profits $\pi _i$ affect the global dynamics even if $w\ll 1$. Since profits matter, the global dynamics is not approximated by ignoring factor ${\mathcal {O}}(w)$ even under the weak selection. For example, on a circular network of $k=2$, profits determine which cluster of a strategy is likely to expand or shrink. Furthermore, because of the above assortativity of $q_{n|m}$, the global evolutionary dynamics of global frequencies is different from the standard replicator dynamics.

However, Ohtsuki and Nowak [39] construct the deterministic replicator dynamics on networks, using the pairwise approximation. Applying their results to our model, we observe that firms’ prices evolve subject to the following equations. Denote a state by ${\mathbf {x}}=(x_1,\ldots ,x_{N+N'})$.

Theorem 2

Suppose $u=0$. Define function b as

$$\begin{aligned} b(p_n,p_m)= {\left\{ \begin{array}{ll} \frac{(k+3)a(p_n,p_n)+3a(p_n,p_m)-3a(p_m,p_n)-(k+3)a(p_m,p_m)}{(k+3)(k-2)} \quad \quad \quad \quad \text { if }k\ge 3, \\ 5a(p_n,p_n)+3a(p_n,p_m)-3a(p_m,p_n)-5a(p_m,p_m) \text { if }k= 2. \end{array}\right. } \end{aligned}$$

Then, for each strategy $p_n\in S$,

$$\begin{aligned} {\dot{x}}_n = x_n (f_n({\mathbf {x}})-\phi ({\mathbf {x}})+g_n({\mathbf {x}})), \end{aligned}$$

(2)

where $f_n({\mathbf {x}})= \sum _{m} x_m a(p_n,p_m)$, $\phi ({\mathbf {x}})=\sum _n x_nf_n({\mathbf {x}})$, and $g_n({\mathbf {x}})= \sum _{m} x_m b(p_n,p_m)$.

In the proof, given in “Appendix A.2”, we derive the replicator equation for any small $u\ge 0$. The Eq. (2) is obtained as the case of $u=0$. The intuition is the same, although the derivation is more complicated. We construct probability $\Pr ^+$ that the number of firms employing $p_n$ increases by one, and probability $\Pr ^-$ that the number of firms employing $p_n$ decreases by one. Then, we solve the dynamics $\Pr ^+ - \Pr ^-$.

The first two terms, $f_n$ and $\phi$, are the same as those in the standard replicator equation ${\dot{x}}_n = x_n(f_n({\mathbf {x}})-\phi ({\mathbf {x}}))$. The term $f_n({\mathbf {x}})$ is the average profit of firms adopting strategy $p_n$, and the term $\phi ({\mathbf {x}})$ is the average profit over the population at state ${\mathbf {x}}$ in the non-networked market.

The last additional term $g_n({\mathbf {x}})= \sum _{m} x_m b(p_n,p_m)$ captures the effect from the local competition on a network. To convey an intuition of g, suppose that the strategy set is binary such that $S=\{p_1,p_2\}$. In the networked market, by the assortativity $q_{n|n}>x_n>q_{m|n}$, the average profit for a firm employing strategy $p_1$ is no longer given by $f_{1}({\mathbf {x}})$; when $a(p_1,p_1)>a(p_1,p_2)$, the average profit is greater than $f_{1}({\mathbf {x}})$ because $q_{1|1}a(p_1,p_1) +(1-q_{1|1})a(p_1,p_2) > x_1a(p_1,p_1) +(1-x_1)a(p_1,p_2) = f_{1}({\mathbf {x}})$, and otherwise, it is less than $f_{1}({\mathbf {x}})$. The gap is filled with the function g.¹⁶

Substituting $f_n$ and $g_n$ into (2) yields

$$\begin{aligned} {\dot{x}}_n = x_n \left[ \sum _{m} x_m (a(p_n,p_m)+b(p_n,p_m)) -\phi (x) \right] . \end{aligned}$$

(3)

This implies that the replicator equation (2) of the game (I, S, a, g) on network g is equivalent to the replicator equation (3) of the game $(I,S,a+b)$ without a network structure. This is the novelty of the approach developed by Ohtsuki and Nowak [39]. Remark that since we apply the pair approximation, the equation works well when g is a large random regular network, i.e., $|I|w\gg 1$.

Thus, in what follows, by letting $U=a+b$, we solve the transformed game (I, S, U). Note that by $\sum _n x_n g_n({\mathbf {x}}) =0$, the average profit over the population is $\phi ({\mathbf {x}})=\sum _n x_nf_n({\mathbf {x}})$.

3.2 Evolutionary Stable Price in the Game with Two Strategies

To provide an intuition of our results, we first assume that pricing is binary such that $S=\{c+d,c+d+e \}$, where e is a price increment with $e\le d$. Let x be the frequency of the BNE price $p=c+d$, and then x is regarded as a state by $|S|=2$. The payoff matrix of the game (I, S, U) is given in Table 1.

Table 1 The payoff matrix of the game (I, S, U) when $S = \{c+d,c+d+e\}$ and $k\ge 3$

Define function $\alpha$ as $\alpha (k,d,e,x)= xe - \frac{kd-3e}{(k+3)(k-2)}$ for $k\ge 3$ and $\alpha (k,d,e,x)= xe - 2d +3e$ for $k=2$. By Table 1, we observe that profile $(c+d,c+d)$ is a strict Nash equilibrium if $\alpha (k,d,e,1)>0$, and that $(c+d+e,c+d+e)$ is a strict Nash equilibrium if $\alpha (k,d,e,0)<0$. Thus, asymptotically stable states are given as follows:

Observation 1

Suppose $S=\{c+d,c+d+e \}$. In any regular network with k with $k\ge 2$,

• state $x=1$ is asymptotically stable if and only if $\alpha (k,d,e,1)>0$,

• state $x=0$ is asymptotically stable if and only if $\alpha (k,d,e,0)<0$.

We first observe that $\alpha$ does not depend on marginal cost c of production. Furthermore, we observe that for any d, e, x, there is ${\tilde{k}}$ such that $\alpha (k,d,e,x)<\alpha (k+1,d,e,x)$ for any $k>{\tilde{k}}$. Since $\lim _{k\rightarrow \infty } \alpha (k,d,e,1) = e>0$, by taking sufficiently large ${\bar{k}}>{\tilde{k}}$ such that $0< \alpha ({\bar{k}}+1,d,e,1)$, this monotonicity implies that BNE pricing $p=c+d$ is stable for any $k> {\bar{k}}$.

The observations connect the results of the non-networked market and of the networked market. The BNE price $c+d$, which is stable in the complete market (i.e., $k=\infty$), tends to be stable as k increases. Since k represents the number of direct rival firms, the BNE price diffuses as the level of local competition among firms increases.

Rearranging $\alpha$, we obtain $\alpha (k,d,e,1)>0$ if and only if $e/d>k/(k^2+k-3)$ and $\alpha (k,d,e,0)<0$ if and only if $e/d<k/3$ for any $k\ge 3$. By $e/d< 1$, we obtain the following for uniqueness:

Observation 2

Fix k, d, e. In any regular network of k with $k\ge 3$,

• if $e/d<k/(k^2+k-3)$, state $x=0$ is the unique asymptotically stable state, and

• if $e/d>k/(k^2+k-3)$, both states $x=0$ and $x=1$ are asymptotically stable.

In the regular network of $k=2$,

• if $e/d<1/2$, state $x=0$ is the unique asymptotically stable state,

• if $e/d>2/3$, state $x=1$ is the unique asymptotically stable state, and

• if $1/2<e/d<2/3$, both states $x=0$ and $x=1$ are asymptotically stable.

Thus, the collusive price is uniquely stable when e / d is small for any $k\ge 2$. On the contrary, in the circular network ($k=2$), the BNE price is uniquely stable when ratio e / d is large. When $k\ge 3$, the BNE price is stable when ratio e / d is large but not uniquely stable for any k, d, e.

From the observations, we argue that price increment e by collusion indicates the size of the benefit of the deviation from the collusive price $c+d+e$ to the BNE price $c+d$, and magnitude d of the transportation cost indicates the size of its cost. Thus, the ratio e / d is regarded as the benefit-cost ratio of the deviation to the BNE price.

Fix $k\ge 3$. Recall that $q_{c+d|c+d}$ is the local frequency that the adjacent firm employs the same BNE price $c+d$ around a firm employing the BNE price, and $q_{c+d|c+d+e}$ is the local frequency that the adjacent firm employs the BNE price around a firm employing the collusive price $c+d+e$. By the assortativity, the frequency $q_{c+d|c+d}$ is larger than that in the well-mixed population x, and the frequency $q_{c+d|c+d+e}$ is smaller than x, i.e., $q_{c+d|c+d+e}<x<q_{c+d|c+d}$.

Suppose that firm i employs the BNE price $c+d$. Then, i’s expected profit is $k[q_{c+d|c+d}a(c+d,c+d)+(1-q_{c+d|c+d})a(c+d,c+d+e)]$. If firm i deviates to the collusive price $c+d+e$, then i’s expected profit changes to $k[q_{c+d|c+d+e}a(c+d+e,c+d)+ (1-q_{c+d|c+d+e})a(c+d+e,c+d+e)]$. By $q_{c+d|c+d+e}<x<q_{c+d|c+d}$, the net increase in i’s profit $k\frac{e}{2}[q_{c+d|c+d}-q_{c+d|c+d+e}(1+\frac{e}{d})]>0$ if $e/d>0$ is small enough. As e becomes smaller and/or d becomes larger, the deviation to the collusive price is more profitable.

In words, when the benefit-cost ratio e / d is large, once i raises i’s price, a significant mass of consumers on $\xi _{ij}< 1/2$ switch to buying a product from distant but cheap adjacent firm j because the difference of the transportation costs $d[\xi _{ij}^2-(1-\xi _{ij})^2]$ is relatively smaller than that of prices e. This implies that it is not profitable for firm i to raise i’s price from the BNE $c+d$ to the collusive $c+d+e$. Thus, it is easy to sustain the BNE price $c+d$ when price range e is large and/or magnitude of transportation cost d is small.

On the other hand, when the benefit-cost ratio e / d is small, a significant mass of consumers on $\xi _{ij}< 1/2$ still buy a product from close but expensive adjacent firm i even if i raises i’s price. Thus, it is profitable for i to raise i’s price from $c+d$ to $c+d+e$, and then the BNE price $c+d$ is not stable.

When the benefit-cost ratio is so large that $e/d \in (\frac{k}{k^2+k-3},1)$, both of the BNE and the collusive prices are stable. By $\lim _k \frac{k}{k^2+k-3} = 0$, the interval monotonically expands to (0, 1) w.r.t. k. Although the BNE price $c+d$ is uniquely asymptotically stable in the non-networked market ($k=\infty$), the collusive price is also asymptotically stable in the networked market of the large degree $k<\infty$.

In Sect. 4.1, to select a plausible stable price, we further examine robustness to small mutation rate $u\ll 1$. We will show that there is the unique threshold of the ratio e / d above which the BNE price is uniquely stochastically stable, and so is the collusive price otherwise.

3.3 Evolutionary Stable Price in the Game with More Than Two Strategies

Next, we consider the price competition with more than two strategies. Recall that we pick up $N'$ prices from interval $[c,c+d)$ and N prices from interval $[c+d,c+d+e]$, so that $S(N,N') = \{c,c+\frac{d}{N'},\ldots ,c+\frac{(N'-1)d}{N'}\}\cup \{c+d,c+d+\frac{e}{N-1},c+d+\frac{2e}{N-1},\ldots ,c+d+e \}$, where $N,N'\ge 2$. Let $x_{n'}$ be the frequency of $p_{n'}=c+\frac{n'}{N'}d$ for $n'=0,\ldots ,N'-1$ and $x_n$ be the frequency of $p_n=c+d+\frac{n}{N-1}e$ for $n=0,\ldots ,N-1$. Then, $\sum x_{n'} + \sum x_n=1$. We examine the asymptotic stability of prices by taking the limit of $N,N'\rightarrow \infty$.

Remark that we take two grids of prices, one is on $[c,c+d)$ and the other one is on $[c+d,c+d+e]$. However, each size of the grid is irrelevant whenever N is sufficiently large.¹⁷ In addition, the results are irrelevant to the convergence rates of N and of $N'$. We below show that the evolutionary stability can be separately examined between those two.

One would suppose that since all firms earn a profit lower than the BNE profit if they employ a price $p<c+d$, any price below the BNE price is not stable. Indeed, we first show that all prices $p < c+d$, including the marginal cost price c, are not asymptotically stable. We denote by ${\mathbf {x}}_{n'}$, the state where all firms employ the identical price $p_{n'}=c+\frac{n'}{N'}d$ for $n=0,1,\ldots ,N'-1$, i.e., $x_{n'}=1$.

Theorem 3

In any regular network of k, for any $k\ge 2$ and any $N,N'$, any state ${\mathbf {x}}_{n'}$, in which all firms employ price $p_{n'}<c+d$, is not asymptotically stable.

We then examine the stability of prices $p_n \ge c+d$. We denote by ${\mathbf {x}}_n$, the state where all firms employ the identical price $p_n=c+d+\frac{n}{N-1}e$ for $n=0,1,\ldots ,N-1$, i.e., $x_n=1$. By the proof of Theorem 3 (given in “Appendix A.3”), it suffices to examine the stability within the set $\{c+d,\ldots ,c+d+e \}$ because $p=c+d$ can also invade if any price $p<c+d$ can invade.

Define function $\beta _{n,m}$ as $\beta _{n,m}(k,d,e,N) =3e\frac{n+m}{N-1}+e\frac{m}{N-1}(k+3)(k-2)-kd$ for $n,m=0,\ldots ,N-1$ when $k\ge 3$, and $\beta _{n,m}(k,d,e,N) =3e\frac{n+m}{N-1}+e\frac{m}{N-1}-2d$ for $n,m=0,\ldots ,N-1$ when $k=2$. Note that $\beta _{n,m}$ is strictly increasing w.r.t. both $n,m=0,\ldots ,N-1$.

We first show the following two lemmas (the proofs of Lemmas 1 and 2 are given in “Appendices A.4 and A.5,” respectively).

Lemma 1

Fix the set $S(N,N')$ of strategies. In any regular network of $k\ge 2$,

• state ${\mathbf {x}}_0$ is asymptotically stable if and only if $\beta _{0,1}(k,d,e,N)>0$,

• state ${\mathbf {x}}_{N-1}$ is asymptotically stable if and only if $\beta _{N-1,N-2}(k,d,e,N)<0$,

• for $n=1,\ldots ,N-2$, state ${\mathbf {x}}_n$ is asymptotically stable if and only if $\beta _{n,n-1}(k,d,e,N)<0$ and $\beta _{n,n+1}(k,d,e,N)>0$.

Lemma 1 says that to show the stability of $p_n\ge c+d$, it suffices to show that both deviations to the adjacent prices $p_{n-1}$ and $p_{n+1}$ in $[c+d,c+d+e]$ are not profitable. It implies that the discretization of $[c,c+d)$ does not affect the analysis of prices $p\in [c+d,c+d+e]$.

Since $\beta _{n,m}\le \beta _{m,n}$ for all n, m with $m\le n$, together with the monotonicity of $\beta _{n,m}$, we obtain the following result.

Lemma 2

Fix k, d, e, N. In the regular network of k, there exist ${\underline{n}},{\bar{n}}\in {\mathbb {Z}}$ with $0\le {\underline{n}}\le {\bar{n}}\le N-1$ such that state ${\mathbf {x}}_l$ is asymptotically stable for any l with ${\underline{n}}\le l\le {\bar{n}}$ and state ${\mathbf {x}}_{l'}$ is not asymptotically stable for any $l'$ with $l'<{\underline{n}}$ and $l'>{\bar{n}}$.

By Lemma 2, for finite $N< \infty$, there exists an interval $[p_l,p_h] \subset [c+d,c+d+e]$ such that for any $p\in [p_l,p_h]\cap S \ne \emptyset$, the state where all firms set the same p is asymptotically stable.

Next, we show that there is a unique asymptotically stable collusive price by taking the limit of the number of strategies $N,N' \rightarrow \infty$. Since any $p<c+d$ is not stable by Theorem 3, taking the limit of $N'\rightarrow \infty$ is irrelevant to stable prices. Lemma 2 implies that there exists a non-empty range of stable prices in $[c+d,c+d+e]$.

As N goes to infinity, the range $[p_l,p_h]$ shrinks into the point given as follows. We say that state ${\mathbf {x}}_n$ is limit asymptotically stable if there is a subsequence of sequence $\{ S(N,N') \}_{N,N'=2}^{\infty }$ converging to $[c,c+d+e]$ such that $p_n\in S(N,N')$ and ${\mathbf {x}}_n$ is asymptotically stable for each element $S(N,N')$ of the subsequence.

Our main theorem is given as follows (the proof is given in “Appendix A.6”):

Theorem 4

Fix k, d, e. Let $n^*=\frac{d}{e(k+1)}(N-1)$. When $k\ge 3$,

• if $e/d<1/(k+1)$, state ${\mathbf {x}}_{N-1}$, where all firms employ the most collusive price $p=c+d+e$, is uniquely limit asymptotically stable, and

• if $e/d>1/(k+1)$, state ${\mathbf {x}}_{n^*}$, where all firms employ collusive price $p_{n^*}=c+d+\frac{1}{k+1}d$, is uniquely limit asymptotically stable.

When $k=2$, in the limit of $N,N'\rightarrow \infty$,

• if $e/d<2/7$, state ${\mathbf {x}}_{N-1}$, where all firms employ the most collusive price $p=c+d+e$, is uniquely limit asymptotically stable, and

• if $e/d>2/7$, state ${\mathbf {x}}_{n^*}$, where all firms employ collusive price $p_{n^*}=c+d+\frac{2}{7}d$, is uniquely limit asymptotically stable.

By the theorem, we first observe that the BNE price $c+d$, which is uniquely stable in the well-mixed population, is never stable. Since $\lim \beta _{0,1}= -kd <0$ in the limit of $N\rightarrow \infty$, it is always profitable to deviate from $c+d$ to $c+d+\frac{e}{N-1}$ when all other firms employ $c+d$ for sufficiently large N. Therefore, in our networked market, firms charge a collusive price in the long run.

We next observe that the asymptotically stable collusive price is strictly increasing w.r.t. the magnitude d of transportation cost. Let $k\ge 3$. When the ratio e / d is lower than $\frac{1}{k+1}$, the stable price sticks to the cap $c+d+e$ as a corner solution, and when the ratio is higher than $\frac{1}{k+1}$, the stable price is $c+\frac{k+2}{k+1}d$. Furthermore, when $\frac{e}{d} > \frac{1}{k+1}$, since the slope of the stable price, $\frac{k+2}{k+1}$, is higher than that of the BNE price, 1, w.r.t. d, firms become more collusive as d increases. This corresponds to the observation that when d is extremely high, each firm i is regarded as a monopolist for consumers located on $\xi _{ij}<1/2$ because every consumer buys a product from the close firm regardless of prices.

We finally remark the following as an immediate corollary of Theorem 4.

Corollary 1

Take the limit of $N,N'\rightarrow \infty$. Then,

• in the limit of $k\rightarrow \infty$, the BNE price $c+d$ is uniquely limit asymptotically stable,

• in the limit of $e/d\rightarrow \infty$, the BNE price $c+d$ is uniquely limit asymptotically stable, and

• in the limit of $e/d \rightarrow 0$, the most collusive price $c+d+e$ is uniquely limit asymptotically stable.

By the first part of the corollary, we observe that the result is consistent with that in the well-mixed population with $k=\infty$. As the level of competition increases, or as a networked market approaches to the non-networked market, the stable price monotonically converges to the BNE price, as shown in the case of $|S|=2$.

Fix the upper bound e. Then, the second part implies that in the limit of no transportation cost $d\rightarrow 0$, the BNE price $c+d$ is uniquely stable. In other words, if there is no transportation cost, or no product differentiation, a network does not matter. No collusive price evolves, and the standard Bertrand–Nash equilibrium outcome is stable. Since the BNE price $c+d$ also converges to the marginal cost c in the limit of $d\rightarrow 0$, the standard argument holds, i.e., no firms enjoy positive profit in Bertrand competition. On the contrary, by the last part, the most collusive price is uniquely stable if transportation cost d is sufficiently high. Thus, the magnitude d plays a crucial role in the evolution of the collusive price in our networked market.

4 Discussion

4.1 Stochastic Stability

This section examines the stochastic stability of the above results, by focusing on the game with two strategies, because it is known that it is hard to examine stochastic stability in a game with more than two strategies. We have assumed that each firm i observes adjacent firms’ pairs of prices and profits and imitates one price from those. However, firms sometimes observe non-adjacent firms and imitate a price employed by a non-adjacent firm or test a price which is never observed to improve their profits. Modeling such explorations as an evolutionary mutation, we solve a stochastically stable price.

We find that our result is robust to the mutation. The collusive price is uniquely stochastically stable if the benefit-cost ratio e / d is small, and the BNE price is uniquely stochastically stable otherwise. Furthermore, for sufficiently large degree k, the BNE price is uniquely stochastically stable for any e / d.

We consider the following Markov process with mutation rate $u>0$. At each unit time $\Delta t$, one firm i is chosen at random for updating i’s price $p_i$ from the entire population. Then, with probability $1-u$, the chosen firm i revise his strategy according to the imitation updating rule. However, with probability u, the mutation occurs. The chosen firm i employs one of the strategies subject to the uniform distribution on S. Thus, the total probability that the chosen firm i switches to $p_{m}$ is $(1-u)\frac{W_j}{W_i + \sum _{l\in \eta ^i(g)} W_l} + u \frac{1}{N+N'}>0$.

Recall that the mutation rate is so small that $u\ll 1$, in addition to the weak selection, $w\ll 1$. Then, in the large population limit, finite-horizon pricing behavior is approximated by the following deterministic mean dynamics:

$$\begin{aligned} {\dot{x}}_n = x_n(f_n(x)+g_n(x)-\phi (x) ) + \frac{u}{wk^*(1-u)} \left( \frac{1}{N+N'}-x_n\right) , \end{aligned}$$

(4)

where $k^* = \frac{k(k+3)(k-2)^2}{(k+1)^2(k-1)}$. As shown in Theorem 2, the derivation is given in “Appendix A.2”.

We call this equation the perturbed replicator dynamics on networks. In the game with the two strategies, if the mutation rate is higher than the selection intensity, $w\ll u \ll 1$, then each frequency of a strategy is close to $x_n = \frac{1}{2}$ for $n=1,2$ in the unique stationary state by $u/w\gg 1$. Remark that since the selection is weak $w\ll 1$, this prediction would be plausible in our dynamics, comparing with the standard evolutionary dynamics assuming $w=1$.

If the mutation rate is sufficiently low, $u\ll w \ll 1$, the mutation is not significant by $u/w\ll 1$. Recall that $e/d<1$. By Observation 2, we immediately obtain that in the limit of $u\rightarrow 0$ by keeping w fixed,

• if $e/d< k/(k^2+k-3)$, state $x=0$ is the unique asymptotically stable state, and

• if $e/d> k/(k^2+k-3)$, both states $x=0$ and $x=1$ are asymptotically stable.

Thus, the dynamics converges to the collusive price when e / d is small. Otherwise, the dynamics converges to either price $c+d$ or $c+d+e$ on finite-horizon depending on the initial state. Since $k/(k^2+k-3)$ is decreasing w.r.t. k, this bistability emerges when k is large.

In order to examine which price is more frequently observed independently of the initial state, we investigate the evolution of infinite-horizon pricing behavior by taking the double limit.¹⁸ Since each state is visited infinitely often by $u>0$, we can no longer approximate the behavior by the mean dynamics, and then directly solve the stochastic Markov process given in the above.

One may conjecture that the risk-dominant strategy of the approximated game (I, S, U) (not (I, S, a)) will be chosen.¹⁹ We will show that this intuition holds true.

Since $u>0$, the process is ergodic and has a unique stationary distribution $\mu _{u,I}$. Recall that x is the frequency of price $c+d$. Let $\mu$ be the stationary distribution in the double limit such that $\mu = \lim _{u\rightarrow 0} \lim _{|I|\rightarrow \infty } \mu _{u,I}$. We say that state $x\in [0,1]$ is uniquely stochastically stable if $\mu (O)=1$ for every open interval $O\subseteq [0,1]$ containing x (relative to state space [0, 1]). Then we obtain the following:

Theorem 5

Suppose $S=\{c+d,c+d+e\}$ and $k\ge 3$. In the limit stationary distribution $\mu$,

• $x=1$ is uniquely stochastically stable if and only if $e/d > 2/(k+1)$, and

• $x=0$ is uniquely stochastically stable if and only if $e/d < 2/(k+1)$.

The proof is given in “Appendix A.7”. In the game $(I,\{c+d,c+d+e\},U)$, the BNE price $c+d$ is risk-dominant if $e/d > 2/(k+1)$ and the collusive price $c+d+e$ is risk-dominant if $e/d < 2/(k+1)$. Thus, the theorem shows that the risk-dominant equilibrium is chosen.

Since $2/(k+1)$ converges to 0 as k goes to infinity, the BNE price $c+d$ is stochastically stable only if degree k is sufficiently large, which implies that the network is almost complete. In our networked market with small k, on the contrary, the collusive price $c+d+e$ tends to be stochastically stable.

As shown in Observation 2, the BNE price is stochastically stable if the benefit-cost ratio e / d is large, and the collusive price is stochastically stable otherwise. Furthermore, for any parameters d, e, k, the stochastically stable price is uniquely determined by the risk-dominance criterion.

4.2 Welfare Analysis

We have shown that a collusive price evolves in the game with more than two strategies. By Theorem 4, the collusive stable price $p_{n^*}=c+d+\frac{1}{k+1}d$ if $e/d> 1/(k+1)$ and $c+d+e$ otherwise.

This section analyzes the welfare effect of parameters to discuss some policy implications and a stability of a network, comparing to the non-networked market. In particular, we study how parameters d, e, k affect Total Surplus (TS), Consumer Surplus (CS), and Producer Surplus (PS).

Take number |I| of firms and $k\ge 3$. Then the total number of links is k|I| / 2. Recall that a unit mass of consumers are distributed on each link. Since each consumer’s valuation is v and the average transportation cost is $\frac{d}{12}$, the (average) TS is $\frac{k|I|}{2}[v -c - \frac{d}{12}]$, irrelevant to a price.

The (average) CS is $v-p-\frac{d}{12}$, and the (average) PS is $\frac{1}{2}(p-c)$. If the price is BNE, $p=c+d$, $\hbox {CS}_B=v-c-\frac{13}{12}d$ and $\hbox {PS}_B=\frac{1}{2}d$. If $e/d<1/(k+1)$, since $\hbox {CS}^*=v-c-d(1+\frac{1}{k+1}+\frac{1}{12})$ and $\hbox {PS}^*=\frac{k+2}{2(k+1)}d$, we observe that $\Delta \hbox {CS}= \hbox {CS}^* - \hbox {CS}_B = -\frac{d}{k+1}$ and $\Delta \hbox {PS}= \hbox {PS}^* - \hbox {PS}_B = \frac{d}{2(k+1)}$. Otherwise, since $\hbox {CS}^*=v-c-\frac{13}{12}d-e$ and $\hbox {PS}^*=\frac{1}{2}(d+e)$, we observe that $\Delta \hbox {CS}= -e$ and $\Delta \hbox {PS}= \frac{1}{2}e$. In both cases, TS is constant by $\Delta \hbox {TS}= \Delta \hbox {CS} + 2\Delta \hbox {PS} = 0$.

First, we consider the welfare effect of d, e because parameters d, e can be determined by a market designer or regulator. The magnitude d of transportation cost, for example, is often controlled by using carbon tax or road pricing. After tax $\tau$ is imposed, the total transportation cost is increased to $(d+\tau )\xi _i^2$ when a consumer on $\xi _i$ buy from i. The upper bound of price ${\bar{p}}=c+d+e$ is also sometimes controlled by some price-cap regulation.

The welfare effect of magnitude d is obvious. If e / d is low, both $\Delta \hbox {CS}$ and $\Delta \hbox {PS}$ are irrelevant to d. If e / d is so high that $p_{n^*} = c+d+\frac{1}{k+1}d$, we observe that $\Delta \hbox {CS}$ decreases but $\Delta \hbox {PS}$ increases as d increases, by keeping the price increment e and the number k|I| / 2 of links fixed. In words, when magnitude d is low, since each consumer buys a unit from a cheap firm regardless of distances, firms are subject to stronger competition. Thus, a low magnitude of transportation cost benefits consumers but harms firms. In total, since TS (not $\Delta \hbox {TS}$) decreases as d increases, the benefit of firms is less than the increase in consumers’ transportation cost.

By keeping d and k fixed, we also obtain the welfare effect of the upper bound e. If e / d is high, both $\Delta \hbox {CS}$ and $\Delta \hbox {PS}$ are irrelevant to e. If e / d is so low that the most collusive price $p_{n^*}=c+d+e$ is stable, we observe that $\Delta \hbox {CS}$ decreases but $\Delta \hbox {PS}$ increases as e increases. In words, when the price-cap e is relatively lower than the magnitude of transportation cost d, firms perfectly collude to the price-cap, so that decrease in e benefits consumers. When the price-cap e is relatively higher, however, the decrease in e is neutral to consumers, in addition to firms, because firms cannot sustain the most collusive price. Since the price-cap only affects a price, TS is independent of e.

Suppose that the regulator is pro-consumer, which is often assumed in the literature, and maximizes CS. Then, the observations imply that the regulator should control magnitude d on a network of large k, but price-cap e on a network of small k. The regulation of magnitude d works only when the ratio e / d is relatively higher, but the regulation of price-cap e works otherwise. Since the threshold is given by $1/(k+1)$, the regulation of d is likely to work as the number k of links increases, and that of e is likely to work as k decreases.

Finally, we consider the welfare effect of the degree k, keeping the ratio e / d fixed, in order to show a stability of networks. The total number k|I| / 2 of links decreases as the degree k decreases. Since every link has length one, the total number of consumers, i.e., market size, also decreases. If this market shrinkage increases PS, then a pair of firms can improve their profits by cutting their link, or excluding consumers on their link, although this behavior is harmful to total welfare.

There are two opposite effects of the decrease in k on profits. The first positive one is the competition effect. Since degree k is the level of price competition among firms, firms are subject to weaker competition, and then the profit per link increases, as the number k of rivals decreases. The second negative one is the effect of market shrinkage. Since degree k is the volume of potential consumers, the aggregated demand decreases, as the number k of links decreases.

The first effect on average profit is given as follows. When $e/d< 1/(k+1)$, $\Delta \hbox {CS}= -e$ and $\Delta \hbox {PS} = \frac{1}{2}e$. Both $\Delta \hbox {CS}$ and $\Delta \hbox {PS}$ are irrelevant to k. When $e/d>1/(k+1)$, $\Delta \hbox {CS} = -\frac{1}{k+1}d$ and $\Delta \hbox {PS} =\frac{1}{2(k+1)}d$. As k decreases, $\Delta \hbox {CS}$ decreases but $\Delta \hbox {PS}$ increases. In words, when the level of competition is weak, consumers obtain low payoffs but firms earn high profits. The effect of market shrinkage on aggregated demand is obvious. In symmetric equilibria, each firm’s aggregated demand $\frac{1}{2}k$ decreases as k decreases.

Thus, the effect on total producer surplus per firm, $k\Delta \hbox {PS}$, decreases as k decreases. If $e/d<1/(k+1)$, $k\Delta \hbox {PS} = \frac{ek}{2}$. As k decreases, $k \Delta \hbox {PS}$ decreases. If $e/d>1/(k+1)$, $k \Delta \hbox {PS} =\frac{k}{2(k+1)}d$. As k decreases, $k \Delta \hbox {PS}$ decreases. The harm of demand shrinkage dominates the benefit of weak competition for each firm in total. Hence no firms exclude consumers and every network is immune to the cutting behavior of firms.

5 Conclusion

We have studied the Bertrand price competition in our networked market, in which many firms are distributed on a large regular network. We show that there is a unique asymptotically stable price that is collusive. In our networked market, since each firm competes in price with only directly linked firms, the level of competition is weaker than that in the standard non-networked market. This low level of the local competition enables firms to charge a high price collusively, so that the BNE price is asymptotically unstable. The stable collusive price is increasing w.r.t. the magnitude of transportation cost. If it is relatively higher than the price-cap, then firms charge the price-cap, which is the most collusive price. We believe that our evolutionary equation on a network, developed in biology, shed new light on the study of the Bertrand competition.

On the basis of our results, further investigations will be necessary to develop more precise predictions of firms’ behavior in a networked market. In some markets, it is plausible that firms are assumed to compete not in price but in quantity. Since the conclusion of price competition is often different from that of quantity competition, the collusive price might be unstable in a Cournot networked market. Furthermore, we focus on pricing provided that a network is predetermined. It is equally important to examine what network structure will emerge and which location is chosen. These issues are left for future research.

Appendices

Appendix

Proofs

1.1 Proof of Theorem 1

For simplification of the notation, let N be the total number of strategies. Recall that the local frequency of strategy n around strategy m is given by the conditional probability, i.e., $q_{n|m}= x_{n,m}/x_m$, where $x_{n}$ is the global frequency of strategy $p_n$, and $x_{n,m}$ is the global frequency of a pair of strategies $(p_n,p_m)$. Remark that $\sum _l q_{l|j}=1$.

Since we consider time scale $\Delta t$, we obtain ${\mathcal {O}}(w) \approx 0$ and ${\mathcal {O}}(u) \approx 0$ under weak selection$w\ll 1$ and small mutation $u\ll 1$, respectively.

Take pair (i, j) of firms. First, focus on the firm j employing $p_m$. Recall that $\delta _{nm}$ is the function such that $\delta _{nm}=1$ if $n=m$ and $\delta _{nm}=0$ if $n\ne m$. Then, the number of firms employing $p_n$ around j increases by one if any adjacent firm employing $p_l$ ($\ne p_n$) is chosen and imitates $p_n$, or the mutation chooses $p_n$.

The first probability that an adjacent firm employing $p_l$ ($\ne p_n$) is chosen is given by $q_{l|m}$. Under the weak selection $w\ll 1$, since there are $\delta _{mn}+(k-1)q_{n|l}$ of firms employing $p_n$ (including j-self) in expectation around the adjacent firm, the second imitation probability is approximated by $\frac{\delta _{mn}+(k-1)q_{n|l}}{k+1}$ by (1). The last probability that the mutation chooses $p_n$ is 1 / N.

Thus, by small mutation $u\ll 1$, the probability that the number of firms employing $p_n$ around j increases by one is approximated by

$$\begin{aligned} \mathrm {Pr}^{+}(n|m)&= \sum _{l\ne n} q_{l|m} \left[ (1-u) \left( \frac{\delta _{mn}+(k-1)q_{n|l}}{k+1}\right) + u\frac{1}{N}\right] \\&= \sum _{l\ne n} q_{l|m} \frac{\delta _{mn}+(k-1)q_{n|l}}{k+1} + {\mathcal {O}}(u) \approx \sum _{l\ne n} q_{l|m} \frac{\delta _{mn}+(k-1)q_{n|l}}{k+1}. \end{aligned}$$

Similarly, the number of firms employing $p_n$ decreases by one if any adjacent firm employing $p_n$ is chosen and imitates any other $p_l$ or the mutation chooses $p_l (\ne p_n)$. Around the adjacent firm, there are $(1-\delta _{mn})+(k-1)\sum _{l\ne n} q_{l|n}$ of firms not employing $p_n$ in expectation. By (1), the same derivation shows that this event occurs with probability

$$\begin{aligned} \mathrm {Pr}^{-}(n|m)&= q_{n|m} \frac{1}{k+1}\left[ (1-\delta _{mn})+(k-1)\sum _{l\ne n}q_{l|n}\right] \\&\quad +\, {\mathcal {O}}(u) \approx q_{n|m} \frac{1}{k+1}\left[ (1-\delta _{mn})+(k-1)\sum _{l\ne n}q_{l|n}\right] \end{aligned}$$

Since the same argument hold for the other firm i, by taking $\Delta t \rightarrow 0$, we obtain the approximation dynamics of local frequencies;

$$\begin{aligned} {\dot{q}}_{n|m}&= \frac{{\dot{x}}_{nm}}{x_m} = 2[\mathrm {Pr}^{+}(n|m) - \mathrm {Pr}^{-}(n|m)] \\&= 2\left[ \sum _{l\ne n} q_{l|m} \left[ \frac{\delta _{nm} + (k-1) q_{n|l}}{k+1}\right] - q_{n|m} \left[ \frac{(1-\delta _{nm})+(k-1)\sum _{l\ne n} q_{l|n}}{k+1}\right] \right] \\&= \frac{2}{k+1} \left[ \delta _{nm} + (k-1)\left( \sum _l q_{n|l}q_{l|m}\right) -kq_{n|m} \right] \qquad \left( \text {by } \sum _{l\ne n} q_{l|m}=1 - q_{n|m}\right) . \end{aligned}$$

The steady state ${\dot{q}}_{n|m}=0$ for all n, m of the approximation dynamics is solved as

$$\begin{aligned} q_{n|m} = \frac{(k-2)x_n+\delta _{nm}}{k-1}. \end{aligned}$$

Thus, $q_{n|m} = \frac{(k-2)x_n}{k-1}$ for $n\ne m$, and $q_{n|n} = \frac{(k-2)x_n+1}{k-1}$. We observe the assortativity by $q_{n|n}>x_n>q_{n|m}$ for $n\ne m$.

1.2 Proof of Theorem 2

Given the local frequencies shown in Theorem 1, we further derive the replicator equation of global frequencies. In the proof, we derive the general Eq. (4) for any small mutation $u\ll 1$ using the weak selection approximation $w\ll 1$. By letting $u=0$, we obtain Eq. (2).

Consider time scale $\Delta t/w$, where profits matter by ${\mathcal {O}}(w)/w={\mathcal {O}}(1)$. Let $k_n$ be the number of firms employing $p_n$. Denote by $(n;k_1,\ldots ,k_N)$, a firm who employs $p_n$ and has $k_n$ of adjacent firms employing $p_n$ ($\sum k_n=k$). Define the fitness of firm $(n;k_1,\ldots ,k_N)$ as $W_{(n;k_1,\ldots ,k_N)}$ and the fitness of the firm employing $p_n$ given that an adjacent firm employs $p_m$ as $W_{n|m}$. Then, $W_{n|m} = 1-w+w[a(p_n,p_m)+\sum _l (k-1)q_{l|n}a(p_n,p_l) ]$ and $W_{(n;k_1,\ldots ,k_N)}=1-w+w[\sum _l k_l a(p_n,p_l)]$.

The number of firms employing $p_n$ increases by one if a firm $(m;k_1,\ldots ,k_N)$ ($m\ne n$) is chosen and he imitates one of adjacent firms employing $p_n$, or the mutation selects strategy $p_n$. Since the distribution of adjacent firms’ strategies given that a firm employing m is chosen is given by the multinominal distribution, this probability at state x is given by

$$\begin{aligned} \mathrm {Pr}^{+}_u (n;x)&= (1-u) \sum _{m\ne n} x_m \sum _{k=k_1+\cdots +k_N} \left[ \frac{k!}{k_1!\cdots k_N!}\prod _l q_{l|m}^{k_l}\right] \\&\quad \cdot \,\left[ \frac{k_n W_{n|m}}{W_{(m;k_1,\ldots ,k_N)}+\sum _l k_l W_{l|m}}\right] + u\frac{x_m}{N} . \end{aligned}$$

The number of firms employing $p_n$ decreases by one if an $(n;k_1,\ldots ,k_N)$ firm is chosen and he imitates one of adjacent firms employing $p_m$, or the mutation selects strategy $p_m$ ($p_m\ne p_N$). This probability at state x is given by

$$\begin{aligned}&\mathrm {Pr}^{-}_u (n;x) = (1-u) x_n \sum _{k=k_1+\cdots +k_N} \left[ \frac{k!}{k_1!\cdots k_m!}\prod _l q_{l|n}^{k_l}\right] \\&\quad \quad \cdot \, \left[ 1-\frac{W_{(n;k_1,\ldots ,k_N)}+k_n W_{n|n}}{W_{(n;k_1,\ldots ,k_N)}+\sum _l k_l W_{l|n}}\right] + u \frac{x_n(N-1)}{N}. \end{aligned}$$

From the properties of multinominal distribution, we observe $\sum _{k=k_1+\cdots +k_N} (\frac{k!}{k_1!\cdots k_N!}\prod _{l'} q_{l'|l}^{k_{l'}})k_n = kq_{n|l}$ and $\sum _{k=k_1+\cdots +k_N} (\frac{k!}{k_1!\cdots k_N!}\prod _{l'} q_{l'|l}^{k_{l'}})k_nk_m = kq_{n|l}\delta _{nm}+ k(k-1)q_{n|l}q_{m|l}$.

Furthermore, $(1-wC)^{-1} = 1+wC + {\mathcal {O}}(w^2)$ for some constant C by taking Taylor series at $w=0$. At time scale $\Delta t/w$, ${\mathcal {O}}(w)/w \not \approx 0$ as argued in the above, but ${\mathcal {O}}(w^2)/w \approx 0$ under $w\ll 1$. Thus, by taking the weak selection approximation, we obtain $(1-wC)^{-1} \approx 1+wC$.

Therefore, by keeping w fixed, taking $\Delta t/w \rightarrow 0$ yields the replicator equation

$$\begin{aligned} {\dot{x}}_n&= \mathrm {Pr}^{+}_u (n;x) - \mathrm {Pr}^{-}_u (n;x) \\&\approx (1-u)w\cdot \frac{k(k+3)(k-2)^2}{(k+1)^2(k-1)}\cdot x_n(f_n(x)+g_n(x)-\phi (x)) + u\left( \frac{1}{N}-x_n\right) . \end{aligned}$$

When there is no mutation, $u=0$, by ignoring the constant factor, we obtain the replicator equation (2):

$$\begin{aligned} {\dot{x}}_n = x_n(f_n(x)+g_n(x)-\phi (x)) . \end{aligned}$$

When $u >0$, by letting $k^* = \frac{k(k+3)(k-2)^2}{(k+1)^2(k-1)}$, we obtain the perturbed replicator equation (4):

$$\begin{aligned} {\dot{x}}_n =x_n(f_n(x)+g_n(x)-\phi (x) ) + \frac{u}{wk^* (1-u) } \left( \frac{1}{N}-x_n\right) . \end{aligned}$$

The first term is in ${\mathcal {O}}(1)$ and the second is in ${\mathcal {O}}(u/w)$. Thus, if $u \ll w \ll 1$, the first term dominates the second. However, if $w\ll u\ll 1$, the second term dominates the first by $u/w \gg 1$.

1.3 Proof of Theorem 3

Suppose $k\ge 3$. Let $B(m,n)=[2(k+3)(k-2)(N')^2]^{-1}d(m-n)[N'(k+6)-n-m]$. Then, by $n+m\le 2N'$, $B(m,n)<0$ for all m, n with $m<n$. For any profile $(c+d\frac{n}{N'},c+d\frac{m}{N'}) \in [c,c+d]^2$, the payoff $U(c+d\frac{n}{N'},c+d\frac{m}{N'})$ of the game (I, S, U) is calculated in Table 2.

Table 2 The payoff matrix of the game (I, S, U) when $k\ge 3$ and $|S| \ge 3$ for $p\le c+d$, where $N'\ge n> m\ge 0$ and $B(m,n)=[2(k+3)(k-2)(N')^2]^{-1}d(m-n)[N'(k+6)-n-m]<0$

To prove the theorem, it suffices to show that for any $p_m<c+d$, a mutant firm employing $p_n\ne p_m$ can invade. For $m,n =0,1,\ldots ,N'$ with $n-m=1$, since $\frac{N'-1}{N'}\ge \frac{m}{n}$, we observe that $U(c+d\frac{n}{N'},c+d\frac{m}{N'})>U(c+d\frac{m}{N'},c+d\frac{m}{N'})$ and $U(c+d\frac{n}{N'},c+d\frac{n}{N'})>U(c+d\frac{m}{N'},c+d\frac{n}{N'})$. This implies that at any state $x_n=1$, where all firms employ strategy $p_{n}= c+d\frac{n}{N'}$, a mutant firm employing $p_{n+1}= c+d\frac{n+1}{N'}$ can invade. Thus, state $x_n=1$ is not asymptotically stable for all $n=0,\ldots ,N'-1$.

When $k=2$, we can show the theorem by applying the same argument.

1.4 Proof of Lemma 1

Suppose $k\ge 3$. Recall that $\beta _{n,m}=3e\frac{n+m}{N-1} + e\frac{m}{N-1}(k+3)(k-2) - kd$ and that $\beta _{n,m}$ is strictly increasing w.r.t. both $n,m=0,\ldots ,N-1$.

We show that for $n=0,\ldots ,N-1$, each profile $(p_n,p_n)$ with $p_n\in (c+d,c+d+e) \cap S$ is a strict Nash equilibrium if $\beta _{n,n-1}<0$ and $\beta _{n,n+1}>0$. Take any pair of strategies $(c+d+e\frac{n}{N-1},c+d+e\frac{m}{N-1})$ with $n>m$ and $e\frac{n-m}{N-1}<d$. Then, the payoff matrix U is calculated in Table 3.

Each symmetric profile $(c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1})$ is a strict Nash equilibrium if and only if $U(c+d+e\frac{m}{N-1},c+d+e\frac{n}{N-1})<U(c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1})$ for any $m\ne n$. By $C(m,n) = [2d(k+3)(k-2)(N-1)^2]^{-1}e(n-m)[3e(n+m)-kd(N-1)]$,

$$\begin{aligned}&U\left( c+d+e\frac{m}{N-1},c+d+e\frac{n}{N-1}\right) -U\left( c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1}\right) \\&\quad = \frac{e(n-m)}{2d(k+3)(k-2)(N-1)} \left[ e\frac{m}{N-1}(k+3)(k-2) + 3e\frac{n+m}{N-1} - kd\right] \\&\quad = \frac{e(n-m)}{2d(k+3)(k-2)(N-1)} \beta _{n,m}. \end{aligned}$$

By monotonicity of $\beta _{n,m}$, we obtain $\beta _{n,n-1}>\beta _{n,n-2}>\cdots >\beta _{n,0}$. Thus, for any $m<n$ with $e\frac{n-m}{N-1}<d$, $U(c+d+e\frac{m}{N-1},c+d+e\frac{n}{N-1})<U(c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1})$ if $\beta _{n,n-1}<0$.

Similarly, by monotonicity of $\beta _{n,m}$, we obtain $\beta _{n,n+1}<\beta _{n,n+2}<\cdots <\beta _{n,N-1}$. Thus, for any $m>n$ with $e\frac{m-n}{N-1}<d$, $U(c+d+e\frac{m}{N-1},c+d+e\frac{n}{N-1})<U(c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1})$ if $\beta _{n,n+1}>0$.

By the same argument, we can show that for any $m<n$ with $e\frac{n-m}{N-1}\ge d$, $U(c+d+e\frac{m}{N-1},c+d+e\frac{n}{N-1}) < U(c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1})$ if $\beta _{n,n-1}<0$, and that for $m>n$ with $e\frac{m-n}{N-1}\ge d$, $U(c+d+e\frac{m}{N-1},c+d+e\frac{n}{N-1}) < U(c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1})$ if $\beta _{n,n+1}>0$.

Those imply that for $n=1,\ldots ,N-2$, profile $(c+d+e\frac{n}{N-1},c+d+e\frac{n}{N-1})$ is a strict Nash equilibrium if and only if $\beta _{n,n-1}<0$ and $\beta _{n,n+1}>0$. In addition, it is straightforward that for $n=0$, it is a strict Nash equilibrium if and only if $\beta _{0,1}>0$, and that for $n=N-1$, it is a strict Nash equilibrium if and only if $\beta _{N-1,N-2}<0$.

Since each strict Nash equilibrium is asymptotically stable, we obtain that state $x_n=1$ is asymptotically stable if and only if $\beta _{n,n-1}(k,d,e,N)<0$ and $\beta _{n,n+1}(k,d,e,N)>0$ for $n=1,\ldots ,N-2$, that state $x_0=1$ is asymptotically stable if and only if $\beta _{0,1}(k,d,e,N)>0$, and that state $x_{N-1}=1$ is asymptotically stable if and only if $\beta _{N-1,N-2}(k,d,e,N)<0$.

When $k=2$, we can show the lemma by applying the same argument.

Table 3 The payoff matrix of the game (I, S, U) when $|S| \ge 3$ for $p\ge c+d$, where $C(m,n)= [2d(k+3)(k-2)(N-1)^2]^{-1}e(n-m)[3e(m+n)-kd(N-1)]$, $k\ge 3$, and $N-1> n> m\ge 0$

1.5 Proof of Lemma 2

Suppose $k\ge 3$. When $N=2$, by Observation 2, ${\underline{n}}={\bar{n}}=0$ if $e/d>k/3$, ${\underline{n}}={\bar{n}}=1$ if $e/d<k/(k^2+k-3)$, and $({\underline{n}},{\bar{n}})=(0,1)$ otherwise.

Let $N\ge 3$. We first observe that $\beta _{n,n+1}$ and $\beta _{n,n-1}$ are monotonically increasing in n. By $\beta _{n-1,n}-\beta _{n,n-1}= \frac{e}{N-1}(k+3)(k-2)>0$, we also observe $\beta _{n-1,n}>\beta _{n,n-1}$. By $\beta _{0,1}<\beta _{N-1,N-2}$, it suffices to prove the lemma in the three cases; (i) $\beta _{0,1}>0$, (ii) $\beta _{N-1,N-2}<0$, and (iii) $\beta _{0,1}<0$ and $\beta _{N-1,N-2}>0$.

In the case (i), by monotonicity, $\beta _{n-1,n}>0$ and $\beta _{n,n-1}>0$ for any $n=2,\ldots ,N-1$. By Lemma 1, only the states $x_0=1$ and $x_{1}=1$ are candidates of asymptotically stable states. If $\beta _{1,0}>0$, then $x_0=1$ is uniquely asymptotically stable and ${\underline{n}}={\bar{n}}=0$. If $\beta _{1,0}<0$, then $x_0=1$ and $x_{1}=1$ are asymptotically stable and $({\underline{n}},{\bar{n}})=(0,1)$.

In the case (ii), by monotonicity, $\beta _{n,n+1}<0$ and $\beta _{n,n-1}<0$ for any $n=0,\ldots ,N-1$. By Lemma 1, only the states $x_{N-2}=1$ and $x_{N-1}=1$ are candidates of asymptotically stable states. If $\beta _{N-2,N-1}<0$, then $x_{N-1}=1$ is uniquely asymptotically stable and ${\underline{n}}={\bar{n}}=N-1$. If $\beta _{N-2,N-1}>0$, then $x_{N-2}=1$ and $x_{N-1}=1$ are asymptotically stable and $({\underline{n}},{\bar{n}})=(N-2,N-1)$.

Consider the case (iii). Then, $\beta _{N-2,N-1}> \beta _{N-1,N-2}>0$. Since $\beta _{n,n+1}\le N-2$ is monotonically increasing and $\beta _{0,1}<0$, there exists ${\underline{n}}$ such that ${\underline{n}}=\min \{n\in {\mathbb {Z}}|\beta _{n,n+1}>0 \}$. Similarly, by $\beta _{1,0}< \beta _{0,1}<0$, since $\beta _{n,n+1}$ is monotonically increasing and $\beta _{N-1,N-2}>0$, there exists ${\bar{n}}\ge 1$ such that ${\bar{n}}=\max \{n\in {\mathbb {Z}}|\beta _{n,n-1}<0 \}$. By $\beta _{n-1,n}>\beta _{n,n-1}$, we obtain ${\underline{n}}\le {\bar{n}}$. For any n with ${\underline{n}}\le n\le {\bar{n}}$, since $\beta _{n,n-1}<0$ and $\beta _{n,n+1}>0$, state $x_n=1$ is asymptotically stable by Lemma 1. In addition, state $x_n=1$ is not asymptotically stable by $\beta _{n,n+1}<0$ for any n with $n<{\underline{n}}$, and state $x_n=1$ is not asymptotically stable by $\beta _{n,n-1}>0$ for any n with $n>{\bar{n}}$.

When $k=2$, we can show the lemma by applying the same argument.

1.6 Proof of Theorem 4

Suppose $k\ge 3$. Recall that ${\mathbf {x}}_n$ is the state where all firms employ the identical price $p_n=c+d+\frac{ne}{N-1}$ and that $n^*(k,d,e,N)=\frac{d}{e(k+1)}(N-1)$. Let $S'(N') = \{c,\ldots ,c+\frac{(m'-1)d}{N'}\}$ and $S(N) = \{c+d,\ldots ,c+d+e \}$. Then, $S(N,N')=S'(N')\cup S(N)$. By Lemma 1, the convergence of $S'(N')$ is irrelevant to the stability of ${\mathbf {x}}_n$, in which all firms employ price $p_{n}\in S(N)$, for any n. Thus, below, we consider only sequence $\{S(N)\}$ converging to $[c+d,c+d+e]$.

First, we show that if $e/d<1/(k+1)$, state ${\mathbf {x}}_{N-1}$ is uniquely limit asymptotically stable. Notice that $p_{N-1}=c+d+e \in S(N)$ for any N. By $\beta _{n,n-1} = \frac{n}{N-1} e(k^2+k) - \frac{e}{N-1}(k^2+k-3) -kd$, we observe that $\beta _{N-1,N-2} = e(k^2+k) - \frac{e}{N-1}(k^2+k-3) -kd$. Since $d> (k+1)e$, this implies that $\beta _{N-1,N-2}<- \frac{e}{N-1}(k^2+k-3)<0$. Thus, ${\mathbf {x}}_{N-1}$ is asymptotically stable for any N.

We then show uniqueness. By $\beta _{n,n+1} = \frac{n}{N-1}e(k^2+k) + \frac{e}{N-1}(k^2+k-3) -kd$ and $d>e(k+1)$, we obtain $\beta _{N-2,N-1} = \frac{N-2}{N-1}e(k^2+k) + \frac{e}{N-1}(k^2+k-3) -kd< -3\frac{e}{N-1} < 0$. Since $\beta _{n,n+1}$ is monotonically increasing in n, we obtain that $\beta _{n,n+1}<0$. Thus state ${\mathbf {x}}_n$ is not asymptotically stable for any $n\le N-2$ and any N.

Therefore, by taking the sequence $\{S(N) \}_{N=0}^\infty$, state ${\mathbf {x}}_{N-1}$, where all firms employ $c+d+e$, is uniquely limit asymptotically stable.

Next, we show that if $e/d>1/(k+1)$, state ${\mathbf {x}}_{n^*}$, where all firms employ $p_{n^*}=c+d+\frac{d}{k+1}$ is uniquely limit asymptotically stable.

Suppose $e/d>1/(k+1)$. By $\frac{n^*e}{N-1} = \frac{d}{k+1}$, we obtain that $n^*<N-1$, that $\beta _{n^*,n^*+1} = \frac{e}{N-1}(k^2+k-3)>0$, and that $\beta _{n^*,n^*-1} = -\frac{e}{N-1}(k^2+k-3)<0$. Thus, for any sufficiently large N such that $p_{n^*}\in S(N)$, state ${\mathbf {x}}_{n^*}$ is asymptotically stable. Hence, there is a subsequence of sequence $\{S(N)\}$ in which $p_{n^*}\in S(N)$ and ${\mathbf {x}}_{n^*}$ is asymptotically stable for each element S(N).

We then show the uniqueness. Note that by $p_{n^*} \in (c+d,c+d+e)$, we observe that $n^* \ge 1$ and $n^*\le N-2$, so that $p_{n^*-1},p_{n^*+1}\in S$ for sufficiently large N with $p_{n^*}\in S(N)$. For $n= n^*+1$, we obtain $\beta _{n,n-1} = \frac{n^*+1}{N-1}e(k^2+k) - \frac{e}{N-1}(k^2+k-3) -kd = 3\frac{e}{N-1}>0$. Since $\beta _{n,n-1}$ is monotonically increasing in n, we obtain $\beta _{n,n-1}>0$ for any $n\ge n^*+1$. Thus, state ${\mathbf {x}}_n$ is not asymptotically stable for any $n\ge n^*+1$ and any N.

In the same manner, we can show that state ${\mathbf {x}}_n$ is not asymptotically stable for any $n\le n^*-1$ and any N. Hence state ${\mathbf {x}}_{n^*}=1$ is uniquely limit asymptotically stable.

For $k=2$, let $n^*(d,e,N)=\frac{2d}{7e}(N-1)$. By the same calculation, we obtain that if $e/d<2/7$, state ${\mathbf {x}}_{N-1}$ with $x_{N-1}=1$ is uniquely limit asymptotically stable, and that if $e/d>2/7$, state ${\mathbf {x}}_{n^*}$ with $x_{n^*}=1$ is uniquely limit asymptotically stable.

1.7 Proof of Theorem 5

Step 1: Derive potential functionJ(x) First, we construct the Markov process by introducing the mutation and derive its stationary distribution. Let $X_n = x_n|I|$ be the number of firms employing $p_n$. Recall that the evolutionary dynamics of the game (I, S, a, g) on the regular network of k is approximated by that of the game (I, S, U) on the complete graph, or in the well-mixed population.

When the strategy set S contains only two strategies $c+d$ (say 1) and $c+d+e$ (say 2), the state is represented by the number $X=x|I|$ of firms employing $p=c+d$ ($0\le k \le |I|$). Recall that $(1-wC)^{-1} \approx 1+wC$ under $w\ll 1$ and that $q_{n|m} = x_n$ for any m in the well-mixed large population.

By the weak selection, $w\ll 1$, the probability that the number of firms employing 1 increases by one at state X is approximated by

$$\begin{aligned} \mathrm {pr}^+_u (1;X)&= (1-u)(1-x)\frac{kx[1-w+w(f_1(x)+g_1(x))]}{1-w+w(f_2(x)+g_2(x))+k[1-w+w\phi (x)]}\\&\quad + u(1-x) \frac{1}{2} \\&\approx (1-u) \frac{kx(1-x) }{(k+1)^2} [1+w[(k+1)(f_1(x)+g_1(x)) - f_2(x)-g_2(x)) - k\phi (x) ] \\&\quad + \frac{u(1-x)}{2}, \end{aligned}$$

and the probability that the number of firms employing $p_n$ decreases by one at state X is approximated by

$$\begin{aligned}&\mathrm {pr}^-_u (1;X) = (1-u)x\frac{k(1-x)[1-w+w(f_2(x)+g_2(x))]}{1-w+w(f_1(x)+g_1(x))+k[1-w+w\phi (x)]} + ux \frac{1}{2} \\&\quad \approx (1-u) \frac{kx(1-x)}{(k+1)^2} [1+w[(k+1)(f_2(x)+g_2(x)) - f_1(x)-g_1(x)) - k\phi (x) ] + \frac{ux}{2}. \end{aligned}$$

Then, the transition probability from X to $X+1$ is $\mathrm {pr}^+_u (1;X)$, that from X to $X-1$ is $\mathrm {pr}^-_u (1;X)$, and that from X to X is $1-\mathrm {pr}^+_u(1;X)-\mathrm {pr}^-_u(1;X)$. By $u>0$, those are strictly positive. Thus, the Markov process is irreducible and then it has the unique stationary distribution. It is well-known (e.g., Sandholm [43]) that the stationary distribution $\mu _{u,I}$ is given by the equation

$$\begin{aligned} \frac{\mu _{u,I}(x)}{\mu _{u,I}(0)}&= \prod _{X'=1}^{X} \frac{\mathrm {pr}^+_u(1;X'-1)}{\mathrm {pr}^-_u(1;X')}. \end{aligned}$$

By taking the logarithm and the double limit, define potential function J(x) as follows:

$$\begin{aligned} J(x)&:= \lim _u \lim _{|I|} \frac{1}{|I|} \log \frac{\mu _{u,I}(x)}{\mu _{u,I}(0)} = \int _0^x \left[ \log \frac{\mathrm {pr}^+_0 (1;y)}{\mathrm {pr}^-_0 (1;y)} \right] dy \\&\quad = \int _0^x \big [ \log [1+w[(k+1)(f_1(y)+g_1(y)) - f_2(y)-g_2(y)) - k\phi (y) ] \\&\qquad - \,\log [1+w[(k+1)(f_2(y)+g_2(y)) - f_1(x)-g_1(y)) - k\phi (y) ] \big ] dy \\&\quad \approx \int _0^x[ w(k+2)(f_1(y)+g_1(y)- f_2(y)-g_2(y)) ] dy \\&\quad = \frac{w(k+2)}{2}(x^2U(1,1)+(2x-x^2)U(1,2)-x^2U(2,1)-(2x-x^2)U(2,2)). \end{aligned}$$

The above approximation holds by $\log (1+x)\approx x$ at near $x=0$ and $w\ll 1$.

Step 2: Solve the stochastically stationary state Sandholm [43, Theorem 12.4.1] shows that a state x is stochastically stable if x maximizes J(x). Thus, by Step 1, we obtain the potential function J(x) whose maximizer is stochastically stable, which is given by $J(x)=x^2[U(c+d,c+d)-U(c+d+e,c+d)] +(2x-x^2)[U(c+d,c+d+e)-U(c+d+e,c+d+e)]$. Since they are strict Nash equilibria when $k/3>e/d>k/(k^2+k-3)$, only states $x=0$ and $x=1$ are the candidates of a stochastically stable state. By $J(0)=0$, the state $x=0$ is uniquely stochastically stable if $J(1)<0$ and the state $x=1$ is uniquely stochastically stable if $J(1)>0$. By $J(1)= U(c+d,c+d)-U(c+d+e,c+d)+U(c+d,c+d+e)-U(c+d+e,c+d+e) = \frac{e^2}{2d}-\frac{2kde-6e^2}{2d(k+3)(k-2)}$, we obtain $J(1)>0$ if and only if $e/d > 2/(k+1)$ and $J(1)<0$ if and only if $e/d < 2/(k+1)$.