Open access peer-reviewed chapter

Polyhedral Complementarity Approach to Equilibrium Problem in Linear Exchange Models

Written By

Vadim I. Shmyrev

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

DOI: 10.5772/intechopen.77206

Chapter metrics overview

1,069 Chapter Downloads

View Full Metrics


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 r be given. Let Rω×ξ be a one-to-one correspondence: R=ΩiΞii=1r with Ωiω, Ξiξ.

We say that the complexes ω and ξ are in duality by R if 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 x that belongs to Ω6 and Ξ6.

Figure 1.

Polyhedral complementarity.

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


where Ωi is the relative interior of Ωi.

Now p is 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 n commodities (goods) and m consumers. Let J=1n and I=1m be the index sets of commodities and consumers.

Each consumer iI possesses 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 iI has to choose a consumption vector xiR+n maximizing his linear utility function cixi under budget restriction:

ciximax,pxipwi,xi0.The problem of consumeri.

Let x˜i be a vector xi that solves this program.

A price vector p˜0 is an equilibrium price vector if 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 pj is also normalized to 1, restricting the price vector p to 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 set BI×J is named a structure, if for each iI there exists ijB.

Say that a consumption prescribed by xi is consistent with structure B 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 B.

We name them zones:


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

3. The parametric transportation problem of the model.

Given a price vector p consider 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 zij are introduced by zij=pjxji.

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

The answer on the question about B reads: B is 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 ΩB and ΞB in 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, ΞB is 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 ΓB with the set of vertices V=12m+n and 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 zij can be obtained from the conditions zZp and


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


Thus, ΩB 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 ΩB is also a polyhedron ΩB' with B' B . Therefore, we have on the simplex σ a polyhedral complex ω=ΩBBB. The polyhedrons ΞB form 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 c1 and c2 only up to positive multipliers:


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

Figure 2.

Polyhedral complexes in exchange model.

Figure 3.

Complementarity problem: c12 is 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=λi for all jJ, and thus, pwi=λi for 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 potentiality of the mappings G associated with the arising polyhedral complementarity problems.

Let f be the function on Rn that fp for 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 G be the mentioned associated mapping.

Theorem 1. The subdifferential of the function f has the representation:


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

Consider the convex function h, defining it as follows:


Introduce the function


Theorem 2. The fixed point of G coincides with the minimum point of the convex function φp on σ.

Another theorem for the problem can be obtained if we take into account that the mapping G and the inverse mapping G1 have 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 of G is the maximum point of the concave function ψq on σ.

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

Proposition 2. For all p,qσ the inequality


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

Corollary. φr=ψr if and only if the point r is the fixed point of the mapping G.

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

2. Algorithms

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 φp or ψq on 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 LM is singleton.

Let be r=LM.

Lemma. The point r is the minimum point of the function φp on L and the maximum point of the function ψq on M.

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=ΞBk and have the point qkΞk. Let LkΩk, MkΞk be 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+j for jJν be the vertices of ν-th component. It is easy to verify that the linear system (3) for Lk is going to be equivalent to this one:


The linear system (1) for the cell Ξk defines coordinates qj on each connected component up to a positive multiplier:


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

For the obtained point, rk can be realized in two cases.

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

It should be noted that the dimension of the cell Ξ reduces. It will certainly be rkΞk when the current cell Ξk degenerates 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 qk by rk with an increase of the function’s ψq value. We verify qkΩk? For this, we obtain from the equations of the transportation problem the variables zij,ijBk, as linear functions zijp and check zijqk0. If it is true, the point qk is the required fixed point. Otherwise, we have zslqk<0. We accept Bk+1=Bk\sl,qk+1=qk and 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 B1B and a point q1ΞB1. We depict the structures as matrices m×n with elements from ×, and × corresponds to an element of B. For example, the structure B12=12132122 will 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 q1 the price vector q1=0.05,0.35,0.6. It is easy to verify that B1B and q1ΞB1.

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


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


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


This point reaches a face of ΞB1 at t=t=0.1111: the inequality (7) for q=qt is fulfilled as equality. We obtain B2=B112 and q2=qt.


Step 2. The graph ΓB2 has 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ΞB2 since the inequality (8) is violated. The new moving point qt=1tq2+tr2 has the coordinates:


At t=0.0625 this point reaches the boundary of the cell Ξ(B2). It is the point c1 in the simplex σ. The inequality (8) for q=qt is 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 q3 and 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 11 should be removed from the structure B3:


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




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


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


At t=0.625 the inequality (9) becomes equality, the point qt attains to the point c12=0.375,0.25,0.375 that 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 qt to 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 G no 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=ΞBk and two points pkΩk,qkΞk. Let LkΩk, MkΞk be 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 n1 and under additional condition jJpj=1 the system defines uniquely the solution rk=rBk. This is the intersection point of the affine hulls of the cells ΩB and ΞB. It can be shown that rkσ.

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

Otherwise, we consider for t01 two moving points:


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

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

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

(ii) t is limited by some of the inequalities (2) in description of the cell ΞBk. Corresponding pair il should be added to Bk: Bk+1=Bkil. We accept qk+1=qt,pk+1=pt and pass to the next step.

We consider the situation when t is 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].

Lemma Let A be a nonnegative and indecomposed matrix, and x is its positive eigenvector, λ is the corresponding eigenvalue. If for a positive vector x˜ the vector z˜=λx˜Ax˜ has all components equal zero except z˜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 pt reaches the face of its cell earlier than the point qt does. 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 G 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 G 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 [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 n products, m participants-consumers, and l participants-firms is considered. Let J=1n,I=1m, and K=m+1m+l be the sets of the numbers of products, consumers, and firms. Thus, S=IK is the set of numbers of all participants.

The consumer iI has the initial endowments wiR+n and also the initial money stock αi. His total budget after selling the initial endowments is equal to αi+pwi. Thus, the i th consumer will choose the purchase vector xi looking for an optimal solution to the following problem:


under the conditions


The firm kK plans to deliver to the market the products to a total sum of at least λk. If xk=x1kxnk denotes a plan of k th firm then the total cost of such a supply at the prices pj equals pxk. The quality of the plan is estimated by the firm in tending to minimize the function ckxk . Here, ck=c1kcnk 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 k th 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˜i and x˜k iI and 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=1 and iIwi=e with 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 set BS×J is named a structure, if for each sS there exists sjB.

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

As mentioned before, we consider the family B of 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 ΩB and 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 vector p˜σ is an equilibrium price vector of generalized linear exchange model if and only if p˜ΩB ΞB for some BB.

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 i remains the same: pxiλi. But for the λi,iI and λ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=plnpfp and ψq=flnq. For these functions, the main results of classical case remain valid.

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

Theorem 8. A vector p˜ is an equilibrium price vector if and only if p˜ 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 k th firm solves the following problem:


Here, ζk is allowable resource and djk indicate the resource cost per unit of product j.

Let λkp be the optimal value of this problem. The consumer iI has 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 i th consumers becomes αi+kKθikλkp. Thus, the i 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 À.


  1. 1. Eaves BC. A finite algorithm for linear exchange model. Journal of Mathematical Economics. 1976;3(2):197-204
  2. 2. Shmyrev VI. On an approach to the determination of equilibrium in elementary exchange models. Soviet Mathematics - Doklady. 1983;27(1):230-233
  3. 3. Shmyrev VI. An algorithm for the search of equilibrium in the linear exchange model. Siberian Mathematical Journal. 1985;26:288-300
  4. 4. Shmyrev VI. A generalized linear exchange model. Journal of Applied and Industrial Mathematics. 2008;2(1):125-142
  5. 5. 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
  6. 6. Eisenberg E, Gale D. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics. 1959;30(1):165-168
  7. 7. 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
  8. 8. 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
  9. 9. 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
  10. 10. 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
  11. 11. Rubinstein GS, Shmyrev VI. Methods for minimization quasiconvex function on polyhadron (in Russian). Optimization. 1971;1(18):82-117
  12. 12. Lemke CE. Bimatrix equilibrium points and mathematical programming. Management Science. 1965;2(7):681-689
  13. 13. Gale D. The linear exchange model. Journal of Mathematical Economics. 1976;3(2):205-209
  14. 14. Rockafellar R. Convex Analisis. USA: Princeton University; 1970

Written By

Vadim I. Shmyrev

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