Open access peer-reviewed chapter

Polyhedral Complementarity Approach to Equilibrium Problem in Linear Exchange Models

By Vadim I. Shmyrev

Submitted: October 27th 2017Reviewed: April 12th 2018Published: November 5th 2018

DOI: 10.5772/intechopen.77206

Downloaded: 721


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
  • algorithm

1. Introduction

It is known that the problem of finding an equilibrium in a linear exchange model can be reduced to the linear complementarity problem [1]. Proposed by the author in [2], 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 [3], but also for more complicate linear models, in which there are two sets of participants: consumers and firms producing goods [4] (more references one can find in [5]). 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 [6], 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 [7]. 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 [9]. 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 Rn, 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 [11]. 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 P) [12].


2. Polyhedral complementarity problem

The basic scheme of the considered approach is the polyhedral complementarity. We consider polyhedrons in Rn. Let two polyhedral complexes ωand ξwith the same number of cells rbe given. Let Rω×ξbe a one-to-one correspondence: R=ΩiΞii=1rwith Ωiω, Ξiξ.

We say that the complexes ωand ξare in duality byRif the subordination of cells in ωand the subordination of the corresponding cells in ξare opposite to each other:


The polyhedral complementarity problem is to find a point that belongs to both cells of some pair ΩiΞi:


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 xthat belongs to Ω6and Ξ6.

Figure 1.

Polyhedral complementarity.

The polyhedral complementarity problem can be reformulated as a fixed point one. To do this the associated mappingis introduced as follows:


where Ωiis the relative interior of Ωi.

Now pis the solution of complementarity problem if pGp.


3. Classical linear exchange model

We demonstrate the main idea of the approach on the classical linear exchange model in the well-known description [13].

Consider a model with ncommodities (goods) and mconsumers. Let J=1nand I=1mbe the index sets of commodities and consumers.

Each consumer iIpossesses a vector of initial endowments wiR+n. The exchange of commodities is realized with respect to some nonnegative prices pj, forming a price vector pR+n.

The consumer iIhas to choose a consumption vector xiR+nmaximizing his linear utility function cixiunder budget restriction:

ciximax,pxipwi,xi0.The problem of consumeri.

Let x˜ibe a vector xithat solves this program.

A price vector p˜0is an equilibrium price vectorif there exist solutions x˜i, i=1,,m,for the individual optimization problems such that


In what follows, we normalize the initial endowment of each commodity to 1, that is, iwi=11Rn. The sum of pjis also normalized to 1, restricting the price vector pto lie in the unit simplex


For the sake of simplicity assume ci>0, iI. It is sufficient for existence of equilibrium [13].


4. The main idea of the approach

The equilibrium problem can be considered in two different ways.

1.The traditional point of view: supply–demand balance.

Given a price vector p, the economy reacts by supply and demand vectors:


The goods’ balance is the condition of equilibrium:


2.Another point of view.

The presented consideration is based on the new notion of consumption structure.

Definition.A setBI×Jis named a structure, if for eachiIthere existsijB.

Say that a consumption prescribed by xiis consistent with structure Bif


This notion is analogous to the basic index set in linear programming.

Two sets of the price vectors can be considered for each structure B.

We name them zones:


ΞBis the set of prices by which the consumers prefer the connections of the structure, ignoring the budget conditions and balances of goods. ΩBis 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: What kind of the structuresBBshould be considered and what should be the collectionB?

3.The parametric transportation problem of the model.

Given a price vector pconsider the following transportation problem of the model:


under conditions


The equations of this problem represent the financial balances for the consumers and commodities. The variables zijare introduced by zij=pjxji.

This is the classical transportation problem. The price vector pis a parameter of the problem. Under the assumption about withis problem is solvable for each pσ.

The answer on the question about Breads: Bis the collection of all dual feasible basic index sets of the transportation problem and of all their subsets being structures.

4.Polyhedral complexes of the model.

For BB, we obtain the description of zones ΩBand ΞBin the following way.


Here, σis the relative interior of σ.

It is easy to give these descriptions in more detail.

For qΞB, we have the linear system


Thus, ΞBis the intersection of a polyhedron with σ.

To obtain the description of ΩB, we should use the well-known tools of transportation problems theory. Given BB, introduce a graph ΓBwith the set of vertices V=12m+nand the set of edges im+jijB. Let τbe the number of components of this graph, let Vνbe the set of vertices of νth component, Iν=IVνand Jν=jJm+jVν.. It is not difficult to show that the following system of linear equations must hold for pΩB:


Under these conditions, the values zijcan be obtained from the conditions zZpand


presenting linear functions of p: zij=zijp. Now, for pΩB, we have in addition the system of linear inequalities


Thus, ΩBis 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 ΩBis also a polyhedron ΩB'with B'B. Therefore, we have on the simplex σa polyhedral complexω=ΩBBB. The polyhedrons ΞBform on σanother polyhedral complex ξ=ΞBBB. It is clear that


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 c1and c2only up to positive multipliers:


Thus, c1and c2can 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 c12is its solution: c12Ω12. Thus, the corresponding vector p=3/82/83/8is the equilibrium price vector of the model.

Figure 2.

Polyhedral complexes in exchange model.

Figure 3.

Complementarity problem:c12is the solution.


5. The Fisher’s model

1.Reduction to optimization problem

A special class of the models is formed by the models with fixed budgets. This is the case when each consumer has all commodities in equal quantities: wji=λifor all jJ, and thus, pwi=λifor all pσ. Such a model is known as the Fisher’s model. Note that we have this case in the abovementioned example.

The main feature of these models is the potentialityof the mappings Gassociated with the arising polyhedral complementarity problems.

Let fbe the function on Rnthat fpfor pσis the optimal value in the transportation problem of the model, and fp=for pσ. This function is piecewise linear and concave. It is natural to define its subdifferential using the subdifferential of convex function f: fp=fp.

Let Gbe the mentioned associated mapping.

Theorem 1. The subdifferential of the functionfhas the representation:


where e=11and lnq=lnq1lnqn. (The addend tein this formula arises because it holds jJpj=1for pσ.)

Consider the convex function h, defining it as follows:


Introduce the function


Theorem 2. The fixed point ofGcoincides with the minimum point of the convex functionφponσ.

Another theorem for the problem can be obtained if we take into account that the mapping Gand the inverse mapping G1have the same fixed points. For the introduced concave function f, we can consider the conjugate function:


(see [14]) With this function, we associate the function ψq=flnq, which is defined on σ.

Proposition 1. For the Fisher’s model, the following formula is valid:


Theorem 3. The fixed point ofGis the maximum point of the concave functionψqonσ.

For the functions φpand ψq, there is a duality relation as for dual programs of linear programming:

Proposition 2. For allp,qσthe inequality


holds. This inequality turns into equality only if p=q.

Corollary.φr=ψrif and only if the pointris the fixed point of the mappingG.

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 [6].


The mentioned theorems allow us to propose two finite algorithms for searching fixed points.

Algorithmically, they are based on the ideas of suboptimization [11], 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 φpor ψqon the affine hull of the current cell.

Consider a couple of two cells Ωω, Ξξcorresponding to each other.

Let LΩ, MΞbe their affine hulls. It will be shown that LMis singleton.

Let be r=LM.

Lemma.The pointris the minimum point of the functionφponLand the maximum point of the functionψqonM.

Now, we describe the general scheme of the algorithm [8] that is based on Theorem 2. The other one using the Theorem 1 is quite similar [9].

On the current k-step of the process, there is a structure BkB. We consider the cells Ωk=ΩBk,Ξk=ΞBkand have the point qkΞk. Let LkΩk, MkΞkbe the affine hulls of these cells. We need to obtain the point of their intersection rk.

Return to the transportation problem of the model and to the descriptions of cells. Consider the graph ΓBk. This graph can have more than one connected components. Let τbe number of connected components, and iIν, m+jfor jJνbe the vertices of ν-th component. It is easy to verify that the linear system (3) for Lkis going to be equivalent to this one:


The linear system (1) for the cell Ξkdefines coordinates qjon each connected component up to a positive multiplier:


To obtain the coordinates of the point rk, we need to put pj=qjin corresponding Eq. (6), which gives the multiplier tν.

For the obtained point, rkcan be realized in two cases.

(i) rkΞk. Since rkis a maximum point on Mkfor the strictly concave function ψq, the value of the function will increase for the moving point qt=1tqk+trk)when tincreases in [0,1]. In considered case, this point reaches a face of Ξkat some t=t<1. Some of corresponding inequalities (2) for p=qtis fulfilled as equality. Choose one of them. Corresponding edge lm+jwill be added to graph. It unites two of connected components. We obtain Bk+1=Bklj, accept qk+1=qtand pass to the next step.

It should be noted that the dimension of the cell Ξreduces. It will certainly be rkΞkwhen the current cell Ξkdegenerates into a point, and we have rk=qk. But it can occur earlier.

(ii) rkΞk. In this case, we can assume qk=rk. Otherwise, we can simply replace qkby rkwith an increase of the function’s ψqvalue. We verify qkΩk? For this, we obtain from the equations of the transportation problem the variables zij,ijBk, as linear functions zijpand check zijqk0. If it is true, the point qkis the required fixed point. Otherwise, we have zslqk<0. We accept Bk+1=Bk\sl,qk+1=qkand pass to the next step.

Theorem 4. If the transportation problem of the model is dually nondegenerate, the described suboptimization method leads to an equilibrium price vector in a finite number of steps.

Figure 4 illustrates two described cases on one step of the algorithm. The point qΞis the current point of the step.

Figure 4.

Illustration of one step of the algorithm.


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 B1Band a point q1ΞB1.We depict the structures as matrices m×nwith elements from ×, and ×corresponds to an element of B. For example, the structure B12=12132122will be depicted as the matrix


(this is the structure for the cell Ω12). Let us start with the structure


It means that both consumers prefer only first good. Let us choose as q1the price vector q1=0.05,0.35,0.6. It is easy to verify that B1Band q1ΞB1.

Step 1. The graph ΓB1has three connected components and the system (6) has the form


Thus, we have r1=1,0,0. The cell ΞB1is given by the system


We have q1ΞB1and r1ΞB1. It is the case (i) in the description of algorithm. We have to move the point q1to the point r1. For the moving point qtit will be:


This point reaches a face of ΞB1at t=t=0.1111: the inequality (7) for q=qtis fulfilled as equality. We obtain B2=B112and q2=qt.


Step 2. The graph ΓB2has two connected components and the system (6) has the form


For the point r2, we have to consider this system with the additional equation


corresponding to (7), this gives r2=0.3333,0.6667,0. We have r2ΞB2since the inequality (8) is violated. The new moving point qt=1tq2+tr2has the coordinates:


At t=0.0625this point reaches the boundary of the cell Ξ(B2). It is the point c1in the simplex σ. The inequality (8) for q=qtis fulfilled as equality. Thus, we obtain:


Step 3. Now, we have the case (ii) in the description of algorithm: the cell Ξ(B3)contains unique point q3and thus r3=q3. We have to verify r3ΩB3? For this, we obtain from the equations of the transportation problem the variables zij,ijB3, and check zijq30. For these variables, we have the system:


We obtain z11= 0.1667–0.5 = −0.3333 < 0. Thus the element 11should be removed from the structure B3:


Step 4. We have to obtain the point r4. The graph ΓB4has two connected components and the system for this point has the form:




It is easy to see that the description of the cell ΞB4has the form:


For q=r4, the inequality (9) is violated, so r4ΞB4. For the new moving point qtwe have:


At t=0.625the inequality (9) becomes equality, the point qtattains to the point c12=0.375,0.25,0.375that is the boundary of ΞB4. We obtain the new structure:


and new point q5=c12. 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 qtto the equilibrium.

Figure 5.

Movement to equilibrium in the example model.


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 Gno longer has the property of potentiality. But, the complementarity approach makes possible to propose a modification of the proses [3]. We name it a method of meeting paths.

As mentioned earlier, on the current k-step of the process, we have a structure BkB. We consider two cells Ωk=ΩBk,Ξk=ΞBkand two points pkΩk,qkΞk. Let LkΩk, MkΞkbe the affine hulls of these cells. For the points of their intersection LkMk, we obtain from (1), (3) the common system:


where the sets Jν,Jνcorrespond to ν-th connected component of the graph ΓBk.

Under some assumption about starting structure this system has rank n1and under additional condition jJpj=1the system defines uniquely the solution rk=rBk. This is the intersection point of the affine hulls of the cells ΩBand ΞB.It can be shown that rkσ.

If rkΩBk,rkΞBk, we have an equilibrium price vector.

Otherwise, we consider for t01two moving points:


It can be shown that in consequence of the assumption ci>0, iI,there exists t=maxtunder the conditions ptΩBk,qtΞBk.

It is the case when t<1. The two variants may occur:

(i) tis limited by some of the inequalities zijpt0,ijBk. Corresponding pair ijshould be removed from Bk: Bk+1=Bk\ij. We accept qk+1=qt,pk+1=ptand pass to the next step.

(ii) tis limited by some of the inequalities (2) in description of the cell ΞBk. Corresponding pair ilshould be added to Bk: Bk+1=Bkil. We accept qk+1=qt,pk+1=ptand pass to the next step.

We consider the situation when tis limited by both above conditions as degenerate.

Nondegeneracy condition.Only one of the above two cases can occur.

This condition will be satisfied if a bit to move the starting points p0,q0.

Under this condition, it holds t>0. To justify this, the following lemma was proved [3].

LemmaLet A be a nonnegative and indecomposed matrix, andxis its positive eigenvector,λis the corresponding eigenvalue. If for a positive vectorx˜the vectorz˜=λx˜Ax˜has all components equal zero exceptz˜i1,z˜i2, then the following two conditions are equivalent:


Theorem 5. Under nondegeneracy condition, the process of meeting paths is always finite.

Figure 6 illustrates one step of this method. In the figure, the point ptreaches the face of its cell earlier than the point qtdoes. For the next step the cell Ωwill be reduced, the cell Ξwill be extended.

Figure 6.

Illustration of a meeting paths step.

It should be noted that for the model with variable budgets, an iterative method was proposed [10] that uses the developed simple algorithm for Fisher?s model in each step of the process.


8. Generalizations

  1. 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 [7]): pjxjiβij. In this case, the mappings Gassociated 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 Gare not potential and algorithm becomes more complicated. Such a model arises if the functions of participants are not linear, but piecewise linear concave separable [5].

  2. 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 nproducts, mparticipants-consumers, and lparticipants-firms is considered. Let J=1n,I=1m,and K=m+1m+lbe the sets of the numbers of products, consumers, and firms. Thus, S=IKis the set of numbers of all participants.

The consumer iIhas the initial endowments wiR+nand also the initial money stock αi. His total budget after selling the initial endowments is equal to αi+pwi. Thus, the ith consumer will choose the purchase vector xilooking for an optimal solution to the following problem:


under the conditions


The firm kKplans to deliver to the market the products to a total sum of at least λk. If xk=x1kxnkdenotes a plan of kth firm then the total cost of such a supply at the prices pjequals pxk. The quality of the plan is estimated by the firm in tending to minimize the function ckxk. Here, ck=c1kcnkis 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 kth firm makes its choice according to a solution of the optimization problem:


under the conditions


An equilibrium is defined by a price vector p˜and a collection of vectors x˜iand x˜kiIand kK, representing some solutions to optimization problems of the participants for p=p˜and satisfying the balance of products:


From this follows that we have to suppose iIαi=kKλk. As before, we suppose also that jJpj=1and iIwi=ewith e=11. Thus, in the equilibrium, we have


The polyhedral complementarity approach can be used for this generalized model as well. The main results remain valid [4], but the consideration becomes more complicated. Some features are discussed.

The structure notion is generalized:

Definition.A setBS×Jis named a structure, if for eachsSthere existssjB.

As before, we suppose that all vectors cs,sSare 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 pσ.

As mentioned before, we consider the family Bof structures B: it is the collection of all dual feasible basic index sets of the transportation problem and of all their subsets being structures.

For each BB, we define the balance zone ΩBand the preference zone ΞB. The description of these sets is quite similar to those of the classical case. Thus, in this way, we again obtain two polyhedral complexes.

Theorem 6. A vectorp˜σis an equilibrium price vector of generalized linear exchange model if and only ifp˜ΩBΞBfor someBB.

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 iremains the same: pxiλi. But for the λi,iIand λk,kK, we obtain the condition iIλi=1+kKλk.

For this variant of model, we have the reduction to optimization problems as well. To do this, we consider the function fp, which gives the optimal value of the transportation problem by given price vector p. Having this function, we introduce as before the functions φp=plnpfpand ψq=flnq. For these functions, the main results of classical case remain valid.

Theorem 7. A vectorp˜is an equilibrium price vector if and only ifp˜is a minimum point of the functionφonσ.

Theorem 8. A vectorp˜is an equilibrium price vector if and only ifp˜is a maximum point of the functionψonσ.

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 kth firm solves the following problem:


Here, ζkis allowable resource and djkindicate the resource cost per unit of product j.

Let λkpbe the optimal value of this problem. The consumer iIhas the initial money stock αi, iIαi=1. The revenues of the firms are divided between consumers in some proportions, those are given by θik. The total budget of ith consumers becomes αi+kKθikλkp. Thus, the ith 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 À.

© 2018 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Vadim I. Shmyrev (November 5th 2018). Polyhedral Complementarity Approach to Equilibrium Problem in Linear Exchange Models, Optimization Algorithms - Examples, Jan Valdman, IntechOpen, DOI: 10.5772/intechopen.77206. Available from:

chapter statistics

721total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Multicriteria Support for Group Decision Making

By Andrzej Łodziński

Related Book

First chapter

Digital Image Processing with MATLAB

By Mahmut Sinecen

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us