Abstract
The classical Spatial Price Equilibrium of economic markets may result in over-production at supply markets and under-supply at demand markets. This paper considers the policy instruments of levying taxes at supply markets to avoid over-production and granting subsidy for traders to guarantee supply at demand markets. The decision process of determining appropriate rates of tax and subsidy is characterized by an implicit complementarity problem. Consequently, a direct type algorithm is applied to solve the complementarity model. Preliminary numerical results are also reported.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
We consider the economic markets of a certain commodity, which is produced at the supply markets and consumed at the demand markets. For the realistic case that the supply and demand markets are spatially separated, the commodity needs to be shipped from supply markets to demand markets by traders. Associated with the purchase prices at supply markets and the sale prices at demand markets; and under the assumption of perfect competition, the well-known Spatial Price Equilibrium (SPE) is ultimately attained, where the sale price equals the purchase price plus the cost of shipment whenever there is trade between a pair of supply and demand markets. We refer to Dafermos and Nagurney (1989), Ferris and Pang (1997), Florian and Los (1982), Friesz et al. (1984), Gabriel et al. (2003), Harker (1986), Lederer (2003), Miller et al. (1996), Nagurney (1993), Reggiani et al. (2002), Samuelson (1952), Scarf and Hansen (1973), Tobin and Friesz (1983) for the theoretical and computational development on SPE.
Thus, once the purchase and sale prices are given, the optimal levels of productions at supply markets, the shipment pattern operated by traders and the virtual levels of supply at demand markets are determined by the endogenous equilibrium conditions. Note that the equilibrium is attained according to the profit-maximizing principles. Hence, the avaricious producers have incentives to increase the amounts of productions as long as their profits can be improved. This inevitable fact may result in over-production at supply markets and thus cause negative consequences such as the over-exploitation of raw resources and environmental pollution. At the same time, the rational traders reduce the amounts of shipments whenever there is no profit to earn between some pairs of supply and demand markets, caring nothing about the necessary supply at some particular demand markets. This undesired characteristic may lead to the lack of necessary supply at demand markets. Therefore, when such situations occur, the governmental authority would like to step into the markets to control the levels of production and supply by implementing some policy instruments, with the aims at avoiding over-production and guaranteeing supply.
In this paper, we consider the policy instruments of tax and subsidy to accomplish these targets. More specifically, the governmental authority levies certain amounts of taxes at supply markets so as to prevent producers from over-production; whereas the authority grants subsidy for traders to encourage more commodities to be shipped to demand markets so as to avoid under-supply. For simplicity, we assume that both the purchase and sale prices are fixed. Then, the question arising naturally is: how does the governmental authority determine the rates of tax and subsidy so that the resulted SPE has such levels of productions that do not exceed the alarm levels at supply markets and such levels of supply that guarantee the necessary requirement at demand markets?
We shall show that the desired rates of tax and subsidy with the aforementioned aims correspond to the solutions of a complementarity problem, and thus the procedure of approaching to the desired rates can be characterized by solving the complementarity model. Recall that the complementarity problem is a special case of the so-called variational inequalities (VI for short), which serve as the unified mathematical model for various equilibrium problems arising in diversing applications, see, e.g., Dafermos (1980, 1990), Ferris and Pang (1997), Friesz et al. (1983, 1993, 2006), Jofré et al. (2007), Konnov (2008), Nagurney (1993).
Recent decades have witnessed the extensive development on the computational aspects of economic equilibria since the pioneering works of Friesz et al. (1984), Scarf and Hansen (1973), Zangwill and Garcia (1981). For our derived complementarity model, the main computational challenge is its implicit nature in the sense that the underlying function, which is determined by the SPE (with fixed taxes and subsidy), has no explicit formulation available. This implicit feature of the complementarity model excludes the applications of such methods for solving VI that require the knowledge of derivatives or other analytic properties. Therefore, we will apply a direct method that uses only the function values during the iterative process of solving the complementarity model. As we shall explain in detail, it is reasonable to assume that the function values are available since the resulted levels of production, shipments and supply at SPE can be observed under the implementation of taxes and subsidy in practice. In addition, the attempt to reduce the numbers of iterations as many as possible is desired not only because of saving the computational loads, but also due that it reduces the times of adjusting the rates of tax and subsidy and thus makes the policy instruments more stable and acceptable. The algorithm we shall apply is demonstrated to have this advantage, verified by some preliminary numerical experiments.
The rest of the paper is organized as follows. In Section 2, we establish the mathematical model for SPE with tax and subsidy. Then, Section 3 provides the implicit complementarity model for the governmental authority to determine appropriate rates of tax and subsidy with the concerns of over-production and supply-guarantee. Section 4 focuses on the computational aspects of the implicit complementarity model. In particular, some numerical results are reported.
2 SPE with tax and subsidy
We assume that there are m supply markets and n demand markets involved in the production and consumption of the concerned commodity. The following notations are used:
- S i :
-
the i-th supply market, i = 1, ..., m;
- D j :
-
the j-th demand market, j = 1, ..., n;
- x ij :
-
the shipment from S i to D j ;
- s i :
-
the level of production at S i
- d j :
-
the level of supply at D j
- f i :
-
the purchase price at S i ;
- g j :
-
the sale price at D j ;
- t ij :
-
the shipment cost between S i and D j .
Then it is conventional to assume that the following conservation conditions hold, see, e.g., Nagurney (1987):
It is well-known (see, e.g., Florian and Los 1982; Samuelson 1952) that the classical SPE is characterized by the following conditions:
Now, with the consideration of levying taxes at supply markets to avoid over-production and granting subsidy for traders to guarantee necessary supply, the new SPE can be obviously characterized by the following conditions:
where y i is the tax levied at S i and z j is the subsidy for those traders who ship the commodity to D j . It is easy to notice (see, e.g., Ferris and Pang 1997; Nagurney 1993) that (2.2) can be written as an equivalent complementarity problem: for any i = 1, ..., m and j = 1, ..., n, we have
We start to reformulate (2.3) into a compact mathematical form for the convenience of analysis. Let \(e_n \in {\mathbb{R}}^{n}\) denote the column vector that each entry equals 1 and \(I_n \in {\mathbb{R}}^{n\times n}\) denote the identity matrix. Utilizing the following notations:
then the complementarity problem (2.3) is equivalent to:
Alternatively, the VI reformulation of (2.4) is to find (x,s,d) ∈ Ω such that
where
Although the structures of both (2.1) and (2.2) are pretty simple, the solvability of these SPE depends heavily on the involving price and cost functions, i.e., f, g and t. Throughout this paper, we consider the separable case for the purchase price, sale price and shipment cost:
-
1.
the purchase price depends separably upon the level of production, i.e., f i = f i (s i );
-
2.
the sale price depends separably upon the level of supply, i.e., g j = g j (d j );
-
3.
the transaction cost depends separably upon the amount of shipments, i.e., t ij = t ij (x ij ).
We further make some reasonable and mild assumptions on functions f i , g j and t ij .
Assumptions
-
A1
f i (∀ i ∈ {1,2, ⋯ ,m}) strongly increases with respect to s i , i.e., there is a constant τ > 0 such that
$$(s - \tilde{s})^T \left( f(s) - f(\tilde{s})\right) \ge \tau \| s - \tilde{s}\|^2, \quad \forall \;\; s, \tilde{s} \in {\mathbb{R}}^m_+.$$(2.6) -
A2
g j (∀ j ∈ {1,2, ⋯ ,n}) strongly decreases with respect to d j , i.e., there is a constant τ > 0 such that
$$\left(d - \tilde{d}\right)^T \left( g(\tilde{d}) - g(d)\right) \ge \tau \| d - \tilde{d}\|^2, \quad \forall \;\; d, \tilde{d} \in {\mathbb{R}}^n_+.$$(2.7) -
A3
t ij (x ij ) (∀ i ∈ {1,2, ⋯ ,m}, ∀ j ∈ {1,2, ⋯ ,n}) is a non-decreasing function with respect to the quantity of shipment x ij :
$$\left(x - \tilde{x}\right)^T \left( t(x) - t(\tilde{x})\right) \ge 0, \quad \forall \;\; x, \tilde{x} \in {\mathbb{R}}^{mn}_+.$$(2.8)
In particular, some existing methods for solving SPE (e.g., Dafermos and Nagurney 1989; Marcotte et al. 1992; Nagurney 1986) assume that these functions are explicit with linear structures:
where a i , b j , c ij , ξ i , η j and ζ ij are known constants. Note that (2.3) with (2.9) is a symmetric monotone linear complementarity problem, which amounts to solving a convex quadratic programming with non-negative constraints (see, e.g., Fletcher 1987).
3 The implicit complementarity model
This section is devoted to modelling the decision process of seeking appropriate rates of tax and subsidy to an implicit complementarity problem.
We first emphasize the fact that when the SPE (2.2) (with the given y and z) is attained, the corresponding levels of production and supply and the shipment pattern can be observed. In other words, we do not need to solve the VI (2.5) since its solution (x,s,d) can be observed once y and z are given. Note that with the assumptions A1–A3, the VI (2.5) has the unique solution (x,s,d) for each given pair of (y, z). However, although (x,s,d) depends on (y, z) in a functional manner, the explicit expression of this function and its analytic properties are “hidden” to us.
On the other hand, let the vector s max denote the alarm levels of over-production at supply markets (\(s^{\max}_i\) is the alarm level at S i ); and the vector d min denote the alarm levels of under-supply at demand markets (\(d^{\min}_j\) is the alarm level at D j ). We assume that both s max and d min are determined by the governmental authority in advance. Obviously, the consistent relationship
should be satisfied.
Then the target of the governmental authority is to determine appropriate y * and z * such that the corresponding levels of production and supply at SPE (2.2), denoted by s * and d *, should satisfy
Mathematically, the governmental authority is to find y * ∈ ℝm and z * ∈ ℝn such that
and
where (s *,d *) are determined by the VI problem (2.5).
The complementarity emerging in both (3.2) and (3.3) deserves further explanations. If \(s^{\max}_i -s^*_i>0\), i.e., the level of production at S i does not exceed the alarm level, then no tax should be levied, i.e., \(y^*_i=0\). Otherwise, the level of production keeps decreasing while the rate of tax increases, until the SPE is eventually attained, which implies that \(y^*_i>0\) and \(s^{\max}_i-s^*_i=0\). This is exactly the complementarity in (3.2), and similar explanations apply to the complementarity in (3.3).
By denoting
Equations (3.2)–(3.3) can be compactly rewritten into the following complementarity problem:
We reiterate that F(u) is a “black-box” function since the explicit expression and the related analytical properties of s(u) and d(u) (determined by (2.5)) are “hidden”. In this sense, the complementarity problem (3.5) is “implicit”. Note that the implicit complementarity model (3.5) is the dual problem of the constrained SPE problem with the constraint (3.1), which has many practical applications such as the road pricing scheme for mitigating traffic congestion.
Overall, the decision process of the governmental authority to seek desired rates of tax and subsidy for avoiding over-production and under-supply is characterized by the implicit complementarity model (3.5).
4 Computation
The implicity of F excludes the possibility of applying those existing methods for VI that require the derivative information or other analytic properties of F to solve the model (3.5). Therefore, it is practical to apply the so-called direct type methods which only need the function values of F during the whole iteration to solve the model (3.5). Recall that the function values of F can be observed in practice. In this section, we first prove some mathematical properties of F, then present the algorithm that is efficient for solving the model (3.5). Some simulation experiments are finally conducted and the numerical results are reported.
4.1 Mathematical properties
Theorem 1
Under Assumptions A1–A3, F(u) is monotone and Lipschitz continuous. In detail, we have
and
Proof
Let \(\; (\bar{x},\bar{s},\bar{d})\) and \(\;(\tilde{x},\tilde{s},\tilde{d})\) be the solutions of problem (2.5) by setting \((y,z)=(\bar{y},\bar{z})\) and \((y,z)=(\tilde{y},\tilde{z})\), respectively. Setting \((y,z)=(\bar{y},\bar{z})\) and \((x',s',d')=(\tilde{x},\tilde{s},\tilde{d})\) in (2.5), one obtains
Similarly, setting \((y,z)=(\tilde{y},\tilde{z})\) and \((x',s',d')=(\bar{x},\bar{s},\bar{d})\) in (2.5), we have
Adding (4.3) and (4.4) together, we get
It follows from (2.7)–(2.8) that
or in a compact vector form
Note that \(\; u= \left( \begin{array}{c} y\\ z \end{array} \right) \) and \(\; F(\bar{u}) - F(\tilde{u}) = \left( \begin{array}{c} \tilde{s} - \bar{s} \\ \bar{d} - \tilde{d} \end{array} \right)\) (see (3.4)), the first assertion follows from (4.5) immediately. The second assertion follows from (4.1) and Cauchy-Schwarz inequality directly. □
4.2 Algorithm
Among the effective direct type methods for solving VI are the classical extra-gradient method and its variants, see, e.g., He and Liao (2002), He et al. (2004), Khobotov (1987), Korpelevich (1976). Note that the extra-gradient type methods require the monotonicity and Lipschitz continuity of the underlying mapping to guarantee the convergence. Therefore, thanks to Theorem 1, the extra-gradient type methods are applicable for solving the implicit complementarity model (3.5). We here apply the improved extra-gradient method integrating optimal step-sizes in He et al. (2004) to solve the model (3.5).
Let ℝ+ m + n denote the positive orthant of ℝm + n and v + denote the projection of v on ℝ+ m + n, that is,
Then, for the current rates of tax and subsidy u k, the governmental authority updates the rates according to the following steps:
The algorithm for adjusting rates of tax and subsidy
- Step 1. :
-
Prediction step
Select a β k > 0, such that
$$\begin{array}{lll}&&\beta_k \| F(u^k) - F(\tilde{u}^k) \| \le \nu \| u^k - \tilde{u}^k \|, \nonumber\\ && 0 < \nu < 1, \qquad \hbox{(usually $\nu \in [0.9,0.95$]),} \end{array}$$(4.6)where
$$\tilde u^{k} = \left[u^k - \beta_k F(u^k) \right]^+.$$(4.7) - Step 2. :
-
Correction step
Adjust the rates of tax and subsidy via the scheme
$$u^{k+1}= \left[u^k - \alpha_k \beta_k F\left(\tilde{u}^k\right)\right]^+,$$(4.8)where
$$\alpha_k = \upgamma \frac{ \left(u^k - \tilde u^k\right)^T q\left(u^k,\beta_k\right)} {\| q\left(u^k,\beta_k\right) \|^2 }, \quad \upgamma\in [1,2), \quad \hbox{(usually $\upgamma \in [1.8,1.95$])}$$and
$$q\left(u^k,\beta_k\right) = u^k - \tilde{u}^k - \beta_k \left[ F\left(u^k\right) - F\left(\tilde{u}^k\right) \right].$$(4.9)
Remark 1
If 0 < β k ≤ ντ, then from (4.2), we have
and thus the condition (4.6) is satisfied. Since we do not know the value of τ > 0 in prior, some strategies of adjusting {β k } self-adaptively are necessary to accelerate the convergence of the above algorithm, e.g., He and Liao (2002), He et al. (2004). Denoting
then we adjust {β k } via the following scheme:
Theorem 2
The sequence {uk} generated by the scheme (4.6)–(4.9) converges to a solution of the model (3.5), i.e., the desired rates of tax and subsidy is computable.
Proof
The proof is omitted, see e.g., He et al. (2004) for the detail. □
4.3 Numerical result
Note that the involved projection of the above algorithm is pretty easy to compute. Therefore, the main computational load in the decision process of seeking desired rates of tax and subsidy is to observe the function values of F(u). Obviously, the observations are money- or time-consuming. Hence, we prefer to reduce the numbers of observing function values of F(u) as many as possible. In addition, one iterate of the sequence {u k} means equivalently an adjustment of the rates of tax and subsidy. Apparently, the policy instruments with high frequency of adjustment are not preferable. Hence, we also need to reduce the number of iterations of the above algorithm as many as possible. We are about to demonstrate that the above algorithm has these advantages, thus justify that it is applicable for the governmental authority to find the appropriate rates of tax and subsidy with the concerns of over-production and supply-guarantee.
For the purpose of simulation, we generate f, g and t as the way described in (2.9), where the involving coefficients are generated randomly in the following intervals:
We assume that m = 20 and n = 50. Therefore, the number of variables of the model (3.5) is 70. Furthermore, let the elements of s max and d min be uniformly 150 and 40, respectively. Let the iteration start with u 0 = 0 and \(e(u^k):=\| \min\{ u^k, F(u^k)\}\|_{\infty}\) be the error measure when solving the problem (3.5). Let ν = 0.9 and μ = 0.5. All the codes were written by Matlab 7.0 and were run in an IBM T42 laptop.
The following table lists the total numbers of computing function values (No. F) and its corresponding errors (e(u k)) during the iterative procedure.
k | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 |
No. F | 0 | 5 | 9 | 13 | 17 | 21 | 25 | 29 |
e(u k) | 7.6e+1 | 6.6e+1 | 5.8e+0 | 5.0e−1 | 2.5e−2 | 3.4e−4 | 3.6e−5 | 2.5e−6 |
According to this table, averagely, we need to calculate the function values of F(u) twice at each iteration. This satisfactory performance is mainly due to the self-adaptive strategy of adjusting β k . In addition, recall that the iterations start from the initial iterate u 0 = 0. However, in the practical decision, the governmental authority can determine a better initial iterate based on experiences and relevant information. Therefore, in real-life decisions, the performance of the implemented algorithm is expected to be better than what we reported.
Note that if we take α k ≡ 1 in the correction step (4.8) (which is feasible, as proved in He and Liao 2002; He et al. 2004), the algorithm reduces to Khobotov’s extra-gradient method (Khobotov 1987), whose average numbers of computing function values and CPU time are about 8 times more than those in the above table.
References
Dafermos S (1980) Traffic equilibrium and variational inequalities. Transp Sci 14:42–54
Dafermos S (1990) Exchange price equilibria and variational inequalities. Math Program 46:391–402
Dafermos S, Nagurney A (1989) Supply and demand equilibration algorithms for a class of market equilibrium problems. Trasp Sci 23:118–124
Ferris MC, Pang JS (1997) Engineering and economic applications of complementarity problems. SIAM Rev 39:669–713
Fletcher R (1987) Practical methods of optimization, second edition. Wiley, New York
Florian M, Los M (1982) A new look at static spatical price equilibrium models. Reg Sci Urban Econ 12:579–597
Friesz TL, Bernstein D, Smith TE, Tobin RL, Wie BW (1993) A variational inequality formulation of the dynamic network traffic equilibrium problem. Oper Res 41(1):179–191
Friesz TL, Harker PT, Tobin RL (1984) Alternative algorithms for the general network spatial price equilibrium problem. J Reg Sci 24(4):475–507
Friesz TL, Rigdon MA, Mookherjee R (2006) Differential variational inequalities and shipper dynamic oligopolistic network competition. Transp Res Part B Methodol 40(6):480–503
Friesz TL, Tobin RL, Harker PT (1983) A nonlinear complementarity formulation and solution procedure for the general derived demand network equilibrium problem. J Reg Sci 23(3):337–359
Gabriel SA, Manik J, Vikas S (2003) Computational experience with a large-scale multi-period, spatial equilibrium model of the north American natural gas system. Netw Spatial Econ 3:97–122
Harker PT (1986) Alternative models of spatial competition. Oper Res 34(3):410–425
He BS, Liao LZ (2002) Improvements of some projection methods for monotone nonlinear variational inequalities. J Optim Theory Appl 112:111–128
He BS, Yuan XM, Zhang JJZ (2004) Comparison of two kinds of prediction-correction methods for monotone variational inequalities. Comput Optim Appl 27:247–267
Jofré A, Rockafellar RT, Wets RJ-B (2007) Variational inequalities and economic equilibrium. Math Oper Res 32(1):32–50
Khobotov EN (1987) Modification of the extragradient method for solving variational inequalities and certain optimization problems. USSR Comput Math Phys 27:120–127
Konnov IV (2008) Decomposition approaches for constrained spatial auction market problems. Netw Spatial Econ. doi:10.1007/s11067–008-9083-6
Korpelevich GM (1976) The extragradient method for finding saddle points and other problems. Ekon Mat Metody 12:747–756
Lederer PJ (2003) Competitive delivered spatial pricing. Netw Spatial Econ 3:421–439
Marcotte P, Margquis G, Zubieta L (1992) A Newton-SOR method for spatial price equilibrium. Transp Sci 26:36–47
Miller TC, Friesz TL, Tobin RL (1996) Equilibrium facility location on networks. Springer, Heidelberg
Nagurney A (1986) An algorithm for the single commodity spatial price equilibrium problem. Reg Sci Urban Econ 16:573–588
Nagurney A (1987) Competitive equilibrium problems, variational inequalities, and regional science. J Reg Sci 27(4):503–517
Nagurney A (1993) Network economics—a variational inequality approach. Kluwer, Deventer
Reggiani A, De Graaff T, Nijkamp P (2002) Resilience: an evolutionary appraoch to spatial economics systems. Netw Spatial Econ 2:211–229
Samuelson PA (1952) Spatial price equilibrium and linear programming. Am Econ Rev 42:283–303
Scarf HE, Hansen T (1973) Computation of economic equilibria. Yale University Press, New Haven
Tobin RL, Friesz TL (1983) Formulating and solving the spatial price equilibrium problem with transshipment in terms of arc variables. J Reg Sci 23(2):187–198
Zangwill WI, Garcia CB (1981) Equilibrium programming: the path following approach and dynamics. Math Program 21:262–289
Author information
Authors and Affiliations
Corresponding author
Additional information
Bing-sheng He was supported by NSFC Grant 10571083 and Jiangsu NSF Grant 2008255.
Xiao-Ming Yuan was partially supported by NSFC grants 10701055 and 70732003.
Rights and permissions
About this article
Cite this article
He, Bs., Xu, W., Yang, H. et al. Solving Over-production and Supply-guarantee Problems in Economic Equilibria. Netw Spat Econ 11, 127–138 (2011). https://doi.org/10.1007/s11067-008-9095-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11067-008-9095-2