New development of original approach to the equilibrium problem in a linear exchange model and its variations is presented. The conceptual base of this approach is the scheme of polyhedral complementarity. The idea is fundamentally different from the well-known reduction to a linear complementarity problem. It may be treated as a realization of the main idea of the linear and quadratic programming methods. In this way, the finite algorithms for finding the equilibrium prices are obtained. The whole process is a successive consideration of different structures of possible solution. They are analogous to basic sets in the simplex method. The approach reveals a decreasing property of the associated mapping whose fixed point yields the equilibrium of the model. The basic methods were generalized for some variations of the linear exchange model.
- exchange model
- economic equilibrium
- fixed point
- polyhedral complementarity
- optimization problem
- conjugate function
It is known that the problem of finding an equilibrium in a linear exchange model can be reduced to the linear complementarity problem . Proposed by the author in , a polyhedral complementarity approach is based on a fundamentally different idea that reflects more the character of economic equilibrium as a concordance the consumers’ preferences with financial balances. In algorithmic aspect, it may be treated as a realization of the main idea of linear and quadratic programming. It has no analogues and makes it possible to obtain the finite algorithms not only for the general case of classical linear exchange model , but also for more complicate linear models, in which there are two sets of participants: consumers and firms producing goods  (more references one can find in ). The simplest algorithms are those for a model with fixed budgets, known more as Fisher’s problem. The convex programming reduction of it, given by Eisenberg and Gale , is well known. This result has been used by many authors to study computational aspects of the problem. Some reviews of that can be found in . The polyhedral complementarity approach gives an alternative reduction of the Fisher’s problem to a convex program [2, 8]. Only the well-known elements of transportation problem algorithms are used in the procedures obtained by this way . These simple procedures can be used for getting iterative methods for more complicate models [5, 10].
The mathematical fundamental base of the approach is a special class of piecewise constant multivalued mappings on the simplex in , which possesses some monotonicity property (decreasing mappings). The problem is to find a fixed point of the mapping. The mappings in the Fisher’s model proved to be potential ones. This makes it possible to reduce a fixed point problem to two optimization problems which are in duality similarly to dual linear programming problems. The obtained algorithms are based on the ideas of suboptimization . The mapping for the general exchange model is not potential. The proposed finite algorithm can be considered as an analogue of the Lemke’s method for linear complementarity problem with positive principal minors of the restriction matrix (class ) .
2. Polyhedral complementarity problem
The basic scheme of the considered approach is the polyhedral complementarity. We consider polyhedrons in . Let two polyhedral complexes and with the same number of cells be given. Let be a one-to-one correspondence: with , .
We say that the complexes and are
The polyhedral complementarity problem is to find a point that belongs to both cells of some pair :
This is natural generalization of linear complementarity, where (in nonsingular case) the complexes are formed by all faces of two simplex cones.
Figure 1 shows an example of the polyhedral complementarity problem. Each of two complexes has seven cells. There is a unique solution of the problem—the point that belongs to and .
The polyhedral complementarity problem can be reformulated as a fixed point one. To do this the
where is the relative interior of .
Now is the solution of complementarity problem if .
3. Classical linear exchange model
We demonstrate the main idea of the approach on the classical linear exchange model in the well-known description .
Consider a model with commodities (goods) and consumers. Let and be the index sets of commodities and consumers.
Each consumer possesses a vector of initial endowments . The exchange of commodities is realized with respect to some nonnegative prices , forming a price vector .
The consumer has to choose a consumption vector maximizing his linear utility function under
Let be a vector that solves this program.
A price vector is an
In what follows, we normalize the initial endowment of each commodity to 1, that is, . The sum of is also normalized to 1, restricting the price vector to lie in the unit simplex
For the sake of simplicity assume , . It is sufficient for existence of equilibrium .
4. The main idea of the approach
The equilibrium problem can be considered in two different ways.
The traditional point of view: supply–demand balance.
Given a price vector , the economy reacts by supply and demand vectors:
The goods’ balance is the condition of equilibrium:
Another point of view.
The presented consideration is based on the new notion of consumption
Say that a consumption prescribed by is consistent with structure if
This notion is analogous to the basic index set in linear programming.
Two sets of the price vectors can be considered for each structure .
We name them
is the set of prices by which the consumers prefer the connections of the structure, ignoring the budget conditions and balances of goods. is the set of prices by which the budget conditions and balances of goods are possible when the connections of the structure are respected, but the participants’ preferences are ignored.
Now, it is clear that
We show that in this way the equilibrium problem is reduced to polyhedral complementarity one.
The question is as follows:
The parametric transportation problem of the model.
Given a price vector consider the following
The equations of this problem represent the financial balances for the consumers and commodities. The variables are introduced by .
This is the classical transportation problem. The price vector is a parameter of the problem. Under the assumption about this problem is solvable for each .
The answer on the question about reads:
Polyhedral complexes of the model.
For , we obtain the description of zones and in the following way.
Here, is the relative interior of .
It is easy to give these descriptions in more detail.
For , we have the linear system
Thus, is the intersection of a polyhedron with .
To obtain the description of , we should use the well-known tools of transportation problems theory. Given , introduce a graph with the set of vertices and the set of edges . Let be the number of components of this graph, let be the set of vertices of th component, and . It is not difficult to show that the following system of linear equations must hold for :
Under these conditions, the values can be obtained from the conditions and
presenting linear functions of : . Now, for , we have in addition the system of linear inequalities
Thus, is described by a linear system of equalities and inequalities. Therefore, it is also a polyhedron.
It is easy to see that each face of the polyhedron is also a polyhedron with . Therefore, we have on the simplex a
Thus, the complexes , are in duality, and we obtain the reduction of the equilibrium problem to a polyhedral complementarity one.
Example. In the model, there are 3 commodities and 2 consumers:
We need and only up to positive multipliers:
Thus, and can be considered as points of the unit price simplex .
Figure 2 illustrates the polyhedral complexes of the model. Each of both complexes has 17 cells. Figure 3 illustrates the arising complementarity problem. The point is its solution: . Thus, the corresponding vector is the equilibrium price vector of the model.
5. The Fisher’s model
Reduction to optimization problem
A special class of the models is formed by the models with
The main feature of these models is the
Let be the function on that for is the optimal value in the transportation problem of the model, and for . This function is piecewise linear and concave. It is natural to define its subdifferential using the subdifferential of convex function : .
Let be the mentioned associated mapping.
where and . (The addend in this formula arises because it holds for .)
Consider the convex function , defining it as follows:
Introduce the function
Another theorem for the problem can be obtained if we take into account that the mapping and the inverse mapping have the same fixed points. For the introduced concave function , we can consider the conjugate function:
(see ) With this function, we associate the function , which is defined on .
For the functions and , there is a duality relation as for dual programs of linear programming:
holds. This inequality turns into equality only if .
Thus, the equilibrium problem for the Fisher’s model is reduced to the optimization one on the price simplex. It should be noted that this reduction is different from well-known one given by Eisenberg and Gale .
The mentioned theorems allow us to propose two finite algorithms for searching fixed points.
Algorithmically, they are based on the ideas of suboptimization , which were used for minimization quasiconvex functions on a polyhedron. In considered case, we exploit the fact that the complexes and define the cells structure on similarly to the faces structure of a polyhedron.
For implementation of the algorithms, we need to get the optimum point of the function or on the affine hull of the current cell.
Consider a couple of two cells , corresponding to each other.
Let , be their affine hulls. It will be shown that is singleton.
Let be .
On the current -step of the process, there is a structure . We consider the cells and have the point . Let , be the affine hulls of these cells. We need to obtain the point of their intersection .
Return to the transportation problem of the model and to the descriptions of cells. Consider the graph . This graph can have more than one connected components. Let be number of connected components, and , for be the vertices of -th component. It is easy to verify that the linear system (3) for is going to be equivalent to this one:
The linear system (1) for the cell defines coordinates on each connected component up to a positive multiplier:
To obtain the coordinates of the point , we need to put in corresponding Eq. (6), which gives the multiplier .
For the obtained point, can be realized in two cases.
(i) . Since is a maximum point on for the strictly concave function , the value of the function will increase for the moving point when increases in [0,1]. In considered case, this point reaches a face of at some . Some of corresponding inequalities (2) for is fulfilled as equality. Choose one of them. Corresponding edge will be added to graph. It unites two of connected components. We obtain , accept and pass to the next step.
It should be noted that the dimension of the cell reduces. It will certainly be when the current cell degenerates into a point, and we have . But it can occur earlier.
(ii) . In this case, we can assume . Otherwise, we can simply replace by with an increase of the function’s value. We verify ? For this, we obtain from the equations of the transportation problem the variables , as linear functions and check . If it is true, the point is the required fixed point. Otherwise, we have . We accept and pass to the next step.
Figure 4 illustrates two described cases on one step of the algorithm. The point is the current point of the step.
6. Illustrative example
We show how the described method works on the Fisher’s model example of Section 3.
For the start, we need a structure and a point We depict the structures as matrices with elements from , and corresponds to an element of . For example, the structure will be depicted as the matrix
(this is the structure for the cell ). Let us start with the structure
It means that both consumers prefer only first good. Let us choose as the price vector . It is easy to verify that and .
Step 1. The graph has three connected components and the system (6) has the form
Thus, we have . The cell is given by the system
We have and . It is the case (i) in the description of algorithm. We have to move the point to the point . For the moving point it will be:
This point reaches a face of at : the inequality (7) for is fulfilled as equality. We obtain and .
Step 2. The graph has two connected components and the system (6) has the form
For the point , we have to consider this system with the additional equation
At this point reaches the boundary of the cell . It is the point in the simplex . The inequality (8) for is fulfilled as equality. Thus, we obtain:
Step 3. Now, we have the case (ii) in the description of algorithm: the cell contains unique point and thus . We have to verify ? For this, we obtain from the equations of the transportation problem the variables , and check . For these variables, we have the system:
We obtain = 0.1667–0.5 = −0.3333 < 0. Thus the element should be removed from the structure :
Step 4. We have to obtain the point . The graph has two connected components and the system for this point has the form:
It is easy to see that the description of the cell has the form:
For , the inequality (9) is violated, so . For the new moving point we have:
At the inequality (9) becomes equality, the point attains to the point that is the boundary of . We obtain the new structure:
and new point . It is easy to verify that we obtain the equilibrium of the model.
The equilibrium price vector is
The optimal solutions of the consumer’s problems are:
Figure 5 shows the moving of the point to the equilibrium.
7. Method of meeting paths
The described algorithms are nonapplicable for the general linear exchange model, when the budgets of consumers are not fixed. In this case, the associating mapping no longer has the property of potentiality. But, the complementarity approach makes possible to propose a modification of the proses . We name it
As mentioned earlier, on the current -step of the process, we have a structure . We consider two cells and two points . Let , be the affine hulls of these cells. For the points of their intersection , we obtain from (1), (3) the common system:
where the sets correspond to -th connected component of the graph .
Under some assumption about starting structure this system has rank and under additional condition the system defines uniquely the solution . This is the intersection point of the affine hulls of the cells and It can be shown that .
If , we have an equilibrium price vector.
Otherwise, we consider for two moving points:
It can be shown that in consequence of the assumption , there exists under the conditions
It is the case when . The two variants may occur:
(i) is limited by some of the inequalities . Corresponding pair should be removed from : . We accept and pass to the next step.
(ii) is limited by some of the inequalities (2) in description of the cell . Corresponding pair should be added to : . We accept and pass to the next step.
We consider the situation when is limited by both above conditions as degenerate.
This condition will be satisfied if a bit to move the starting points .
Under this condition, it holds . To justify this, the following lemma was proved .
Figure 6 illustrates one step of this method. In the figure, the point reaches the face of its cell earlier than the point does. For the next step the cell will be reduced, the cell will be extended.
It should be noted that for the model with variable budgets, an iterative method was proposed  that uses the developed simple algorithm for Fisher?s model in each step of the process.
The models with upper bounds: the considered approach permits to develop the algorithms for deferent variations of the classical exchange model. The simplest of those models is the model in which the costs are limited for certain goods (the spending constraints model ): . In this case, the mappings associated with the arising polyhedral complementarity problem are potential too. Some modifications of the developed algorithms are needed. More difficult is the model with upper on the purchase volumes of goods. In this case, the mappings are not potential and algorithm becomes more complicated. Such a model arises if the functions of participants are not linear, but piecewise linear concave separable .
The generalized linear exchange model: the polyhedral complementarity approach is applicable to models with the production sector too. Some firms are added, those supply goods to the market. Describe more in detail one of those models.
The model with products, participants-consumers, and participants-firms is considered. Let and be the sets of the numbers of products, consumers, and firms. Thus, is the set of numbers of all participants.
The consumer has the initial endowments and also the initial money stock . His total budget after selling the initial endowments is equal to . Thus, the th consumer will choose the purchase vector looking for an optimal solution to the following problem:
under the conditions
The firm plans to deliver to the market the products to a total sum of at least . If denotes a plan of th firm then the total cost of such a supply at the prices equals . The quality of the plan is estimated by the firm in tending to minimize the function . Here, is a fixed nonnegative vector whose components determine a comparative scale of the “undesirability” of various products for the firm (e.g., their relative production costs).
Thus, the th firm makes its choice according to a solution of the optimization problem:
under the conditions
An equilibrium is defined by a price vector and a collection of vectors and and , representing some solutions to optimization problems of the participants for and satisfying the balance of products:
From this follows that we have to suppose . As before, we suppose also that and with . Thus, in the equilibrium, we have
The polyhedral complementarity approach can be used for this generalized model as well. The main results remain valid , but the consideration becomes more complicated. Some features are discussed.
The structure notion is generalized:
As before, we suppose that all vectors are positive. The parametric transportation problem of the model is changed and becomes a net problem:
It can be shown that this problem is solvable for all .
As mentioned before, we consider the family of structures : it is the collection of all dual feasible basic index sets of the transportation problem and of all their subsets being structures.
For each , we define the balance zone and the preference zone . The description of these sets is quite similar to those of the classical case. Thus, in this way, we again obtain two polyhedral complexes.
The generalized model can be considered with fixed budgets, and in this way, we obtain the generalization of the Fisher’s model. The budget condition of the consumer remains the same: . But for the and , we obtain the condition .
For this variant of model, we have the reduction to optimization problems as well. To do this, we consider the function , which gives the optimal value of the transportation problem by given price vector . Having this function, we introduce as before the functions and . For these functions, the main results of classical case remain valid.
The finite algorithms developed for Fischer’s model do not require any significant changes and are applicable for this generalized model.
3. The production-exchange models Arrow-Debreu type: these are modifications of previous model. Describe the simplest variant of the model. On the market, there is one unit of each good. The firms produce additional goods, spending some resource that is limited and seek to maximize revenue from the sale of manufactured goods. Thus, the th firm solves the following problem:
Here, is allowable resource and indicate the resource cost per unit of product .
Let be the optimal value of this problem. The consumer has the initial money stock , . The revenues of the firms are divided between consumers in some proportions, those are given by . The total budget of th consumers becomes . Thus, the th consumer has the following problem:
under the conditions
The condition of good balances in equilibrium is given as before by the equality (12).
The polyhedral complementarity approach is applicable for this model too, but the consideration becomes much more complicated. An iterative method can be developed that uses the abovementioned generalized linear exchange model as an auxiliary in each step of the process.
This chapter was supported by the Russian Foundation for Basic Research, project 16-01-00108 À.
Eaves BC. A finite algorithm for linear exchange model. Journal of Mathematical Economics. 1976; 3(2):197-204
Shmyrev VI. On an approach to the determination of equilibrium in elementary exchange models. Soviet Mathematics - Doklady. 1983; 27(1):230-233
Shmyrev VI. An algorithm for the search of equilibrium in the linear exchange model. Siberian Mathematical Journal. 1985; 26:288-300
Shmyrev VI. A generalized linear exchange model. Journal of Applied and Industrial Mathematics. 2008; 2(1):125-142
Shmyrev VI. An iterative approach for searching an equilibrium in piecewise linear exchange model. In: Kochetov Yu. et al., editors. Lecture Notes in Computer Sciences. vol. 9869. Heidelberg, Germany: Springer; 2016. pp. 61‐72
Eisenberg E, Gale D. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics. 1959; 30(1):165-168
Devanur NR, Papadimitriou CH, Saberi A, Vazirani VV. Market equilibrium via a primal–dual algorithm for a convex program. Journal of the ACM (JACM). 2008; 55(5):22
Shmyrev VI. An algorithmic approach for searching an equilibrium in fixed budget exchange models. In: Driessen TS et al., editors. Russian Contributions to Game Theory and Equilibrium Theory. Berlin, Germany: Springer; 2006. pp. 217-235
Shmyrev VI. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics. 2009; 3(4):505-518
Shmyrev VI, Shmyreva NV. An iterative algorithm for searching an equilibrium in the linear exchange model. Siberian Advances in Mathematics. 1996; 6(1):87-104
Rubinstein GS, Shmyrev VI. Methods for minimization quasiconvex function on polyhadron (in Russian). Optimization. 1971; 1(18):82-117
Lemke CE. Bimatrix equilibrium points and mathematical programming. Management Science. 1965; 2(7):681-689
Gale D. The linear exchange model. Journal of Mathematical Economics. 1976; 3(2):205-209
Rockafellar R. Convex Analisis. USA: Princeton University; 1970