CUBO A Mathematical Journal Vol.11, No¯ 02, (117–126). May 2009 Network Oligopolies with Multiple Markets László Kapolyi System Consulting Zrt., 1126. Budapest, Béla Király út 30/C, Hungary email: system@system.hu ABSTRACT Cournot oligopolies with multiple markets are examined when transportation costs from each manufacturer to all markets are also included into the profit functions. Under general and realistic conditions the equilibrium always exists, and based on the Kuhn-Tucker conditions a computer method is introduced to compute it. The dynamic extension of the model is also introduced with gradient adjustment, and the asymptotic stability of the equilibrium is examined. In the case of independent markets and linear price and cost functions the solution algorithm is simplified and the global asymptotic stability of the equilibrium is proved. RESUMEN Son examinados oligopolios Cournot con mercados multiples cuando los costos de transporte de todas las manofacturas de todos los mercados son incluidos en la función de utilidad. Bajo condiciones generales y realistas siempre existe equilibrio, y basados en condiciones de Kuhn- Tucker un método computacional es introducido para calcularlo. La extensión dinámica del modelo es también presentada con adaptación gradiente, es examinada la estabilidad asintótica. En el caso de mercados independientes y funciones de precio y costo lineales el algoritmo de solución es simplificado y es provada la estabilidad asintótica global del equilibrio. Key words and phrases: Oligopoly, multiple market, equilibrium, stability. Math. Subj. Class.: 91A06, 91A80. 118 László Kapolyi CUBO 11, 2 (2009) 1 Introduction The classical oligopoly theory considers a homogeneous market and several firms offering a certains product to the market. This simple model has been examined and extended by many authors in the last few decades. Models with product differentiation, multi-product oligopolies, labor managed firms, rent-seeking games were analysed to mention only a few. A comprehensive summary of these models and their properties is given in Okuguchi (1976) and in Okuguchi and Szidarovszky (1999). Emition control, waste management, technology spill-over, secondary market competition were also included into oligopoly models, however very few attempts were made to examine the effect of multiple markets. They were mostly treated as multi- product oligopolies, where the same good sold in different markets was considered as different products. If we introduce transportation costs into the models, their structure becomes different because of the additional additive cost terms. In this paper we make the first attempt to analyze the properties of oligopoly models including trans- portation costs to multiple markets. The paper is organized as follows. After the mathematical model is formulated, conditions are given for the existence of the noncooperative Nash equilibrium based on the theory of concave games. Then a computer method is introduced to find the equilibrium. In applying this method we have to find either feasible solutions for a system of usually nonlinear equalities and inequalities, or op- timal solutions of a nonlinear programming problem. These methods can be significantly simplified in the cases of independent markets and linear cost and price functions. A similar algorithm will be then proposed to find the completely cooperative solution. A gradient adjustment process is then formulated as a dynamic extension of the model, and its asymptotical stability will be examined. In the case of independent markets and linear cost and price functions we will show that the equilibrium is always globally asymptotically stable. 2 Mathematical Model Consider a network of N firms that produce the same product or offer the same service to M different markets. Let xki be the quantity offered by firm k to market i, then the supply on market i is given as si = ∑N k=1 xki and the output of firm k is qk = ∑M i=1 xki. The production cost Ck(qk) of firm k depends on qk, and the price on each market i depends on the supplies on all markets, since consumers might have choices where they want to purchase the goods. So the price on market i is given as pi(s1, . . . , sM ). Assume also that there is a transportation cost (including possible duties) for each firm for supplying its product on the different markets: Tk1(xk1) + · · · + TkM (xkM ). Based on the above notation, the profit of firm k equals Πk = M ∑ i=1 xkipi(s1, . . . , sM ) − Ck(qk) − M ∑ i=1 Tki(xki). (1) It is also assumed that each xki value is nonnegative and bounded from above: xki ∈ [0, Lki] . In this way an N -person game is defined is which the N firms are the players, the strategy of each player is a vector xk = (xk1, . . . , xkM ) ∈ [0, Lk1] × · · · × [0, LkM ] = Sk, and the payoff function of player k is its CUBO 11, 2 (2009) Network Oligopolies with Multiple Markets 119 profit, Πk. The solution of this game is the noncooperative Nash equilibrium, which is a set of strategy vectors x ∗ k (1 ≤ k ≤ N ) such that for all players k, 1. x∗k ∈ Sk; 2. Πk(x ∗ 1, . . . , x ∗ k−1, xk, x ∗ k+1, . . . , x ∗ N ) ≤ Πk(x ∗ 1, . . . , x ∗ N ) (2) with all xk ∈ Sk. Assume that all functions pi, Ck and Tki are twice continuously differentiable. Notice that ∂Πk ∂xki = pi + xki ∂pi ∂si + ∑ j 6=i xkj ∂pj ∂si − C′k − T ′ ki = pi + M ∑ l=1 xkl ∂pl ∂si − C′k − T ′ ki, (3) furthermore ∂ 2 Πk ∂x 2 ki = 2 ∂pi ∂si + xki ∂ 2 pi ∂s 2 i + ∑ j 6=i xkj ∂ 2 pj ∂s 2 i − C′′k − T ′′ ki (4) and ∂ 2 Πk ∂xki∂xkj = ∂pi ∂sj + ∂pj ∂si + M ∑ l=1 xkl ∂ 2 pl ∂si∂sj − C′′k . (5) For the sake of convenient notation let J p be the Jacobian of p = (p1, . . . , pM ) and Hl the Hessian of pl. Then the Hessian matrix of Πk with respect to vector xk can be conveniently written as J p + J T p + M ∑ l=1 xklHl − C ′′ k · E − Dk, (6) where E is the M × M matrix with all unity elements, and Dk = diag (T ′′ k1, . . . , T ′′ kM ) . Now we make the following assumptions: (A) −p is monotonic in the sense that ( s (1) − s(2) )T ( p ( s (1) ) − p ( s (2) )) ≤ 0 (7) for all s(1) = ( s (1) 1 , . . . , s (1) M ) and s(2) = ( s (2) 1 , . . . , s (2) M ) ; (B) pl is concave for all l; 120 László Kapolyi CUBO 11, 2 (2009) (C) T ′′ki ≥ 0 for all k and i; (D) C′′k ≥ 0. Notice that (A) implies that J p + J T p is negative semidefinite (see for example Ortega and Rheinboldt, 1970). Condition (B) implies that all matrices Hl are negative semidefinite, and (C) implies that Dk is positive semidefinite. Consequently the Hessian of Πk with respect to xk is negative semidefinite, so Πk is concave in xk. Therefore the Nikaido–Isoda theorem (Forgo et al., 1999) implies that there is at least one Nash equilibrium. Here we used the fact that E is positive semidefinite with eigenvalues 0 and M (see for example Okuguchi and Szidarovszky, 1999). 3 Computation of the Equilibrium The equilibrium output of any firm k is the optimal solution of the problem maximize M ∑ i=1 xkipi(s1, . . . , sM ) − Ck(qk) − M ∑ i=1 Tki(xki) (8) s.to 0 ≤ xki ≤ Lki for all i. The Kuhn–Tucker conditions are sufficient and necessary because of the concavity of Πk. They can be written as follows. There exist constants uk1, . . . , ukM , vk1, . . . , vkM such that uki ≥ 0, vki ≥ 0 (all i), (9) 0 ≤ xki ≤ Lki (all i), (10) ( ∂Πk ∂xk1 , . . . , ∂Πk ∂xkM ) + (uk1, vk1, . . . , ukM , vkM )                1 −1 1 −1 ... 1 −1                = (0, . . . , 0), (11) ukixki = 0 (all i), (12) vki (Lki − xki) = 0 (all i). (13) Here we gave only the nonzero elements of the matrix and used the fact that the constraints of problem (8) have the form xki ≥ 0 and Lki − xki ≥ 0. The (xk1, . . . , xkM ) (k = 1, . . . , N ) part of any feasible solution of this equality-inequality system provides Nash-equilibrium. CUBO 11, 2 (2009) Network Oligopolies with Multiple Markets 121 We can also rewrite this feasibility problem as a single objective optimization problem: minimize N ∑ k=1 M ∑ i=1 (ukixki + vki(Lki − xki)) subject to uki ≥ 0, vki ≥ 0, 0 ≤ xki ≤ Lki (all k and i) (14) ∂Πk ∂xki + uki − vki = 0 (all k and i), which can be solved by routine methods. The dimension of this problem can be reduced by introducing new variables αki = uki − vki. (15) From the last constraint we have αki = − ∂Πk ∂xki (16) and the nonnegativity of uki and vki implies that vki = uki − αki ≥ −αki, that is, αki + vki ≥ 0 for all k and i. Substituting (15) and (16) into the objective function we have a simplified model: minimize N ∑ k=1 M ∑ i=1 ( − ∂Πk ∂xki xki + vkiLki ) subject to vki ≥ 0 vki ≥ ∂Πki ∂xki (all k and i) (17) 0 ≤ xki ≤ Lki. In the objective function Lki > 0, so the objective is minimal if and only if vki is minimal. From the first two constraints of (17) we see that the minimal value of vki is the larger of 0 and ∂Πk ∂xki . Hence a more simple version of the optimization model is the following: minimize N ∑ k=1 M ∑ i=1 ( − ∂Πk ∂xki xki + Lki · max { 0; ∂Πk ∂xki }) (18) subject to 0 ≤ xki ≤ Lki. 4 The Case of Independent Markets In this section we assume that the market price pi depends on only the supply si on market i, so pi = pi(si). In this special case Πk = M ∑ i=1 xkipi(si) − Ck(qk) − M ∑ i=1 Tki(xki) (19) 122 László Kapolyi CUBO 11, 2 (2009) and therefore ∂Πk ∂xki = pi + xkip ′ i − C ′ k − T ′ ki, (20) furthermore ∂ 2 Πk ∂x 2 ki = 2p ′ i + xkip ′′ i − C ′′ k − T ′′ ki (21) and with j 6= i, ∂ 2 Πk ∂xki∂xkj = −C′′k . (22) Therefore the Hessian of Πk has the more special diagonal form        2p ′ 1 − T ′′ k1 + xk1p ′′ 1 2p ′ 2 − T ′′ k2 + xk2p ′′ 2 . . . 2p ′ M − T ′′ kM + xkM p ′′ M        − C′′k · E. (23) Recall that E is positive semidefinite, so this matrix is negative semidefinite if for all i, (A’) p′i < 0; (B’) p′′i ≤ 0 in addition to assumptions (C) and (D). The Nikaido–Isoda theorem implies that under conditions (A’), (B’), (C) and (D) there is at least one Nash-equilibrium. In this special case the optimization problem (17) reduces to the following: minimize N ∑ k=1 M ∑ i=1 (xki (−pi − xkip ′ i + C ′ k + T ′ ki) + vkiLki) subject to vki ≥ 0 (24) vki ≥ pi + xkip ′ i − C ′ k − T ′ ki 0 ≤ xki ≤ Lki. Assume next that all function pi, Ck and Tki are linear pi(si) = Ai − Bisi, Ck(qk) = ak + bkqk and Tki = αki + βkixki. Then p ′ i = −Bi, C ′ k = bk, T ′ ki = βki, so we have a simple optimization problem: minimize N ∑ k=1 M ∑ i=1 (xki (−Ai + Bisi + xkiBi + bk + βki) + vkiLki) subject to vki ≥ 0 (25) vki − Ai + Bisi + xkiBi + bk + βki ≥ 0 0 ≤ xki ≤ Lki. CUBO 11, 2 (2009) Network Oligopolies with Multiple Markets 123 In this problem all constraints are linear (notice that si = ∑N k=1 xki), and the objective function can be rewritten as follows: N ∑ k=1 M ∑ i=1 vkiLki + N ∑ k=1 M ∑ i=1 xki(−Ai + Bisi + xkiBi + bk + βki) = N ∑ k=1 M ∑ i=1    vkiLki + xki (βki + bk − Ai) + Bixki  2xki + ∑ l 6=k xli      (26) which is a quadratic function of its unknows. For the actual solution of this problem standard software is available. 5 Cooperative Solutions The most commonly applied cooperative solutions (such as the Shapley value, see for example, Forgó et al., 1999) maximizes the total profit of all firms, and then this maximal profit is distributed among the firms in a well defined, concept-dependent way. The total profit equals Π = N ∑ k=1 Πk = M ∑ j=1 sj pj (s1, . . . , sM ) − N ∑ k=1 Ck(qk) − N ∑ k=1 M ∑ j=1 Tkj (xkj ). (27) The maximal solution of this function can be obtained in the following way. Notice first that ∂Π ∂xki = pi + si ∂pi ∂si + ∑ j 6=i sj ∂pj ∂si − C′k − T ′ ki (28) and the constraints can be rewritten as xki ≥ 0 Lki − xki ≥ 0, so the Kuhn–Tucker conditions guarantee the existence of nonnegative constants uki and vki such that uki ≥ 0, vki ≥ 0 (all k and i) 0 ≤ xki ≤ Lki ( ∂Π ∂x11 , . . . , ∂Π ∂x1M , . . . , ∂Π ∂xN 1 , . . . , ∂Π ∂xN M , ) + (u11, v11, . . . , uN M , vN M )                1 −1 1 −1 . . . 1 −1                = (0, . . . , 0) (29) 124 László Kapolyi CUBO 11, 2 (2009) ukixki = 0 vki(Lki − xki) = 0. From the third condition we see that for all k and i, ∂Π ∂xki = uki − vki. (30) So the set of feasible solutions of this system of equalities and inequalities contains the optimal solutions. If Π is concave as an N M -variable function, then the Kuhn-Tucker conditions are sufficient and necessary, so every feasible solution of system (29) is optimal for problem (27). Another way is the direct optimization of the objective function Π subject to the constraints 0 ≤ xki ≤ Lki for all k and i. 6 Dynamic Extensions Assuming continuous time scales – as usual is the theory of dynamic economics – it is assumed that the firms adjust their production levels proportionally to their marginal profits. This concept can be mathematically modeled as ˙xki = Kki ∂Πk ∂xki = Kki  pi + M ∑ j=1 xkj ∂pj ∂si − C′k − T ′ ki   (31) for all k and i, where Kki > 0 is a constant known as the speed of adjustment of firm k. The motivation of this construct is the following. If ∂Πk ∂xki > 0, then the profit of firm k increases by the increasing value of xki. If ∂Πk ∂xki < 0, then the profit increases by decreasing value of xki. If this partial derivative is zero, then the current production level is at a stationary point, so the firm does not want changes. Notice first that the interior equilibria are the steady states of this system. Using linearization, the local asymptotic stability of the equilibrium is guaranteed if all eigenvalues of the Jacobian of the right hand side functions are in the left half of the complex plane. Let gki denote the right hand side of equation (k, i). Simple differentiation shows that ∂gki ∂xki = Kki  2 · ∂pi ∂si + xki ∂ 2 pi ∂s 2 i + ∑ j 6=i xkj ∂ 2 pj ∂s 2 i − C′′k − T ′′ ki   (32) ∂gki ∂xkj = Kki ( ∂pi ∂sj + ∂pj ∂si + M ∑ l=1 xkl ∂ 2 pl ∂si∂sj − C′′k ) (33) and if l 6= k, then ∂gki ∂xlj = Kki ( ∂pi ∂sj + M ∑ r=1 xkr ∂ 2 pr ∂si∂sj ) (34) for all j. Based on these derivatives, the Jacobian can be represented in a block form (J kl) where J kl is an M × M matrix: J kl =    Kk ( J p + J T p + ∑ j xkj Hj − C ′′ k · E − Dk ) if l = k Kk ( J p + ∑ j xkj Hj ) if l 6= k (35) CUBO 11, 2 (2009) Network Oligopolies with Multiple Markets 125 with Kk = diag(Kk1, Kk2, . . . , KkM ) and the notations of (6). The equilibrium is locally asymptotically stable if all eigenvalues of the Jacobian have negative real parts. The structure of the Jacobian is complicated, so we will only illustrate this condition in the linear case, when pi(si) = Ai − Bisi, Ck(qk) = ak + bkqk and Tki = αki + βkixki (as in constructing the optimization problem (25)). Then with the notation P = diag(−B1, −B2, . . . , −BM ), the Jacobian is        2K1P K1P . . . K1P K2P 2K2P . . . K2P ... ... ... KN P KN P . . . 2KN P        where each block is diagonal. By interchanging the rows and columns, this matrix can be rearranged as a blockdiagonal matrix diag(A1, A2, . . . , AM ) with N × N blocks, Ai =        −2K1iBi −K1iBi . . . −K1iBi −K2iBi −2K2iBi . . . −K2iBi ... ... ... −KN iBi −KN iBi . . . −2KN iBi        so the equilibrium is locally asymptotically stable if the eigenvalues of each block have negative real parts. This is guaranteed if the eigenvalues of matrix        2K1i K1i . . . K1i K2i 2K2i . . . K2i ... ... ... KN i KN i . . . −2KN i        have positive real parts for all i. This matrix can be rewritten as D + k · 1T with Di = diag(K1i, K2i, . . . , KN i), ki = (K1i, K2i, . . . , KN i) T , and 1T = (1, 1, . . . , 1). The characteristic polynomial has the form ϕi(λ) = det ( D + k · 1T − λI ) = det (D − λI) det ( I + (D − λI)−1k · 1T ) = N ∏ l=1 (Kli − λ) [ 1 + N ∑ l=1 Kli Kli − λ ] . The roots of the first factor are all positive. Let h(λ) denote the bracketed factor. Clearly lim λ→±∞ h(λ) = 1, lim λ→Kli±0 h(λ) = ∓∞, h ′ (λ) = N ∑ l=1 Kli (Kli − λ)2 > 0. 126 László Kapolyi CUBO 11, 2 (2009) So h(λ) locally strictly increasing. Therefore there is one root between each consecutive pair of poles (which are the positive Kki numbers) and an additional root after the largest pole. We found this way N real positive roots. Equating the bracketed term with zero leads to a polynomial equation of degree N , so we found all roots, they are real and positive. So the equilibrium is always locally asymptotically stable. Notice that in the linear case system (31) is also linear, so local stability implies global asymptotical stability, therefore independently of the initial conditions the trajectories of the system converge to the Nash-equilibrium. 7 Conclusions In this paper Cournot oligopolies were examined with multiple markets, when additional transportation costs were included into the profit functions of the firms. After the mathematical model was formulated sufficient conditions were presented for the existence of the Nash equilibrium, and computer method were presented for determining the equilibrium based on the Kuhn–Tucker conditions. This method was simplified in the case of independent markets, and was further modified to find the completely cooperative solution. A gradient adjustment dynamic model was finally introduced and its asymptotical stability examined. In the case of independent markets and linear price and cost functions the equilibrium is always globally asymptitocally stable with respect to gradient adjustments. Received: April 02, 2008. Revised: May 05, 2008. References [1] Forgó, F., Szép, J. and Szidarovszky, F., Introduction to the Theory of Games. Kluwer Academic Publishers, Dordrecht/London, 1999. [2] Okuguchi, K., Expectations and Stability in Oligopoly Models. Springer-Verlag, Berlin/New-York, 1976. [3] Okuguchi, K. and Szidarovszky, F., The Theory of Oligopoly with Multi-Product Firms. Springer Verlag, Berlin/New York, 1999. [4] Ortega, J. and Rheinboldt, W., Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970. [5] Puu, T., Attractors, Bifurcations, and Chaos: Nonlinear Phenomena in Economics (2nd ed.). Springer- Verlag, Berlin/New York, 2003. [6] Vives, X., Oligopoly Pricing. MIT Press, Cambridge, Mass, 1999. N08-network