Polyhedral Complementarity Approach to Equilibrium Problem in Linear Exchange Models

Abstract

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.

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 ${\mathbb{R}}^n$, 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 ${\mathbb{R}}^n$. Let two polyhedral complexes $\omega$ and $\xi$ with the same number of cells $r$ be given. Let $R\subset \omega \times \xi$ be a one-to-one correspondence: $R={\left\{\left({\mathrm{\Omega }}_i,{\mathrm{\Xi }}_i\right)\right\}}_{i=1}^r$ with ${\mathrm{\Omega }}_i\in \omega$, ${\mathrm{\Xi }}_i\in \xi$.

We say that the complexes $\omega$ and $\xi$ are in duality by $R$ if the subordination of cells in $\omega$ and the subordination of the corresponding cells in $\xi$ are opposite to each other:

$${\mathrm{\Omega }}_i\prec {\mathrm{\Omega }}_j⟺{\mathrm{\Xi }}_i\succ {\mathrm{\Xi }}_j.$$

The polyhedral complementarity problem is to find a point that belongs to both cells of some pair $\left({\mathrm{\Omega }}_i,{\mathrm{\Xi }}_i\right)$:

$$p^{\ast }\text{is}\text{the}\text{solution}⟺p^{\ast }\in {\mathrm{\Omega }}_i\cap {\mathrm{\Xi }}_i\text{for}\text{some}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^{\ast }$ that belongs to ${\mathrm{\Omega }}_6$ and ${\mathrm{\Xi }}_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:

$$G\left(p\right)={\mathrm{\Xi }}_i\forall p\in {\mathrm{\Omega }}_i^{\circ },$$

where ${\mathrm{\Omega }}_i^{\circ }$ is the relative interior of ${\mathrm{\Omega }}_i$.

Now $p^{\ast }$ is the solution of complementarity problem if $p^{\ast }\in G\left(p^{\ast }\right)$.

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=\left\{1,\dots ,n\right\}$ and $I=\left\{1,\dots ,m\right\}$ be the index sets of commodities and consumers.

Each consumer $i\in I$ possesses a vector of initial endowments $w^i\in R_{+}^n$. The exchange of commodities is realized with respect to some nonnegative prices $p_j$, forming a price vector $p\in R_{+}^n$.

The consumer $i\in I$ has to choose a consumption vector $x^i\in R_{+}^n$ maximizing his linear utility function $\left(c^i{x}^i\right)$ under budget restriction:

$$\left.\begin{array}{l}\left(c^i{x}^i\right)\to \text{max},\\ \left(p,x^i\right)⩽\left(p,w^i\right),\\ x^i⩾0.\end{array}\right|\Rightarrow \text{The problem of consumer}i.$$

Let ${\tilde{x}}^i$ be a vector $x^i$ that solves this program.

A price vector $\tilde{p}\ne 0$ is an equilibrium price vector if there exist solutions ${\tilde{x}}^i$, $i=1,\dots ,m,$ for the individual optimization problems such that

$$\sum _{i\in I}{\tilde{x}}^i=\sum _{i\in I}{w}^i.$$

In what follows, we normalize the initial endowment of each commodity to 1, that is, ${\sum }_i{w}^i=\left(1,\dots ,1\right)\in R^n$. The sum of $p_j$ is also normalized to 1, restricting the price vector $p$ to lie in the unit simplex

$$\sigma =\left\{p\in R_{+}^n|\sum _{j\in J}{p}_j=1\right\}.$$

For the sake of simplicity assume $c^i>0$, $\forall i\in I$. 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^{\circ }.$ The traditional point of view: supply–demand balance.

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

$$p\begin{array}{l}\nearrow \text{demand}D\left(p\right)\\ \searrow \text{supply}S\left(p\right)\end{array}.$$

The goods’ balance is the condition of equilibrium:

$$\widehat{p}\text{is}\text{equilibrium}\text{price}\text{vector}⟺S\left(\widehat{p}\right)=D\left(\widehat{p}\right).$$

$2^{\circ }.$ Another point of view.

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

Definition. A set $B\subset I\times J$ is named a structure, if for each $i\in I$ there exists $\left(i,j\right)\in \mathcal{B}$.

Say that a consumption prescribed by $\left\{x^i\right\}$ is consistent with structure $\mathcal{B}$ if

$$\left(i,j\right)\notin \mathcal{B}\Rightarrow x_j^i=0.$$

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

Two sets of the price vectors can be considered for each structure $\mathcal{B}$.

We name them zones:

$$\mathcal{B}\begin{array}{l}\nearrow \text{the}\mathit{\text{preference}}\mathit{\text{zone}}\mathrm{\Xi }\left(B\right)\\ \searrow \text{the}\mathit{\text{balance}}\mathit{\text{zone}}\mathrm{\Omega }\left(B\right).\end{array}$$

$\mathrm{\Xi }\left(B\right)$ is the set of prices by which the consumers prefer the connections of the structure, ignoring the budget conditions and balances of goods. $\mathrm{\Omega }\left(B\right)$ 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

$$p\text{is}\text{an}\text{equlibrium}\text{price}\text{vector}⟺\left(\exists \mathcal{B}\right)p\in \mathrm{\Omega }\left(\mathcal{B}\right)\cap \mathrm{\Xi }\left(\mathcal{B}\right).$$

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 $\mathcal{B}\in \mathfrak{B}$ should be considered and what should be the collection $\mathfrak{B}$?

$3^{\circ }.$ The parametric transportation problem of the model.

Given a price vector $p$ consider the following transportation problem of the model:

$$\sum _{i\in I}\sum _{j\in J}{z}_{\mathit{ij}}ln{c}_j^i\to \text{max}$$

under conditions

$$\left\{z_{\mathit{ij}}\right\}\in Z\left(p\right)\left|\begin{array}{l}\sum _{j\in J}{z}_{\mathit{ij}}=\left(p,w^i\right),i\in I,\\ \sum _{i\in I}{z}_{\mathit{ij}}=p_j,j\in J,\\ z_{\mathit{ij}}⩾0,\left(i,j\right)\in I\times J.\end{array}\right.$$

The equations of this problem represent the financial balances for the consumers and commodities. The variables $z_{\mathit{ij}}$ are introduced by $z_{\mathit{ij}}=p_j{x}_j^i$.

This is the classical transportation problem. The price vector $p$ is a parameter of the problem. Under the assumption about $\left\{w^i\right\}$ this problem is solvable for each $p\in \sigma$.

The answer on the question about $\mathfrak{B}$ reads: $\mathfrak{B}$ is the collection of all dual feasible basic index sets of the transportation problem and of all their subsets being structures.

$4^{\circ }.$ Polyhedral complexes of the model.

For $\mathcal{B}\in \mathfrak{B}$, we obtain the description of zones $\mathrm{\Omega }\left(\mathcal{B}\right)$ and $\mathrm{\Xi }\left(\mathcal{B}\right)$ in the following way.

$$\mathcal{B}\in \mathfrak{B}\Rightarrow \left|\begin{array}{l}a)\mathrm{\Omega }\left(\mathcal{B}\right)\subset \sigma \text{is}\text{the}\text{balance}\text{zone}\text{of}\text{the}\text{structure}:\\ \mathrm{\Omega }\left(\mathcal{B}\right)=\left\{p\in \sigma |\exists z\in Z\left(p\right),z_{\mathit{ij}}=0,\left(i,j\right)\notin \mathcal{B}\right\};\\ b)\mathrm{\Xi }\left(\mathcal{B}\right)\subset {\sigma }^{\circ }\text{is}\text{the}\text{preferance}\text{zone}\text{of}\text{the}\text{structure}:\\ \mathrm{\Xi }\left(\mathcal{B}\right)=\left\{q\in {\sigma }^{\circ }\left|\underset{k}{\text{max}}\frac{c_k^i}{q_k}=\frac{c_j^i}{q_j},\forall \left(i,j\right)\in \mathcal{B}\right.\right\}.\end{array}\right.$$

Here, ${\sigma }^{\circ }$ is the relative interior of $\sigma$.

It is easy to give these descriptions in more detail.

For $q\in \mathrm{\Xi }\left(\mathcal{B}\right)$, we have the linear system

$$\frac{q_k}{c_k^i}=\frac{q_j}{c_j^i}\left(i,k\right)\in \mathcal{B},\left(i,j\right)\in B,$$E1

$$\frac{q_l}{c_l^i}⩾\frac{q_j}{c_j^i}\left(i,l\right)\notin \mathcal{B},\left(i,j\right)\in B.$$E2

Thus, $\mathrm{\Xi }\left(\mathcal{B}\right)$ is the intersection of a polyhedron with ${\sigma }^{\circ }$.

To obtain the description of $\mathrm{\Omega }\left(\mathcal{B}\right)$, we should use the well-known tools of transportation problems theory. Given $B\in \mathfrak{B}$, introduce a graph $\mathrm{\Gamma }\left(\mathcal{B}\right)$ with the set of vertices $V=\left\{1,2,\dots ,m+n\right\}$ and the set of edges $\left\{\left(i,m+j\right)|\left(i,j\right)\in \mathcal{B}\right\}$. Let $\tau$ be the number of components of this graph, let $V_{\nu }$ be the set of vertices of $\nu$ th component, $I_{\nu }=I\cap V_{\nu }$ and $J_{\nu }=\left\{j\in J|\left(m+j\right)\in V_{\nu }\right\}.$. It is not difficult to show that the following system of linear equations must hold for $p\in \mathrm{\Omega }\left(\mathcal{B}\right)$:

$$\sum _{j\in J_{\nu }}{p}_j=\sum _{i\in I_{\nu }}\left(p,w^i\right),\nu =1,\dots ,\tau .$$E3

Under these conditions, the values $z_{\mathit{ij}}$ can be obtained from the conditions $z\in Z\left(p\right)$ and

$$z_{\mathit{ij}}=0,\left(i,j\right)\notin B,$$

presenting linear functions of $p$: $z_{\mathit{ij}}=z_{\mathit{ij}}\left(p\right)$. Now, for $p\in \mathrm{\Omega }\left(\mathcal{B}\right)$, we have in addition the system of linear inequalities

$$z_{\mathit{ij}}\left(p\right)⩾0,\left(i,j\right)\in \mathcal{B}.$$

Thus, $\mathrm{\Omega }\left(\mathcal{B}\right)$ 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 $\mathrm{\Omega }\left(\mathcal{B}\right)$ is also a polyhedron $\mathrm{\Omega }\left({\mathcal{B}}^{\text{'}}\right)$ with ${\mathcal{B}}^{\text{'}}$ $\subset \mathcal{B}$ . Therefore, we have on the simplex $\sigma$ a polyhedral complex $\omega =\left\{\mathrm{\Omega }\left(\mathcal{B}\right)|\mathcal{B}\in \mathfrak{B}\right\}$. The polyhedrons $\mathrm{\Xi }\left(\mathcal{B}\right)$ form on $\sigma$ another polyhedral complex $\xi =\left\{\mathrm{\Xi }\left(\mathcal{B}\right)|\mathcal{B}\in \mathfrak{B}\right\}$. It is clear that

$$\mathrm{\Omega }\left({\mathcal{B}}_1\right)\subset \mathrm{\Omega }\left({\mathcal{B}}_2\right)\Rightarrow \mathrm{\Xi }\left({\mathcal{B}}_1\right)\supset \mathrm{\Xi }\left({\mathcal{B}}_2\right).$$

Thus, the complexes $\omega$, $\xi$ 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:

$$c^1=\left(\mathrm{1,2,3}\right),w^1=\left(1/2,1/2,1/2\right),$$

$$c^2=\left(\mathrm{3,2,1}\right),w^2=\left(1/2,1/2,1/2\right).$$

We need $c^1$ and $c^2$ only up to positive multipliers:

$$c^1\sim \left(1/6,2/6,3/6\right),c^2\sim \left(3/6,2/6,1/6\right).$$

Thus, $c^1$ and $c^2$ can be considered as points of the unit price simplex $\sigma$.

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 $c^{12}$ is its solution: $c^{12}\in {\mathrm{\Omega }}_{12}$. Thus, the corresponding vector $p^{\ast }=\left(3/8,2/8,3/8\right)$ is the equilibrium price vector of the model.

Figure 2.

Polyhedral complexes in exchange model.

Figure 3.

Complementarity problem: $c^{12}$ is the solution.

5. The Fisher’s model

$1^{\circ }.$ 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: $w_j^i={\lambda }_i$ for all $j\in J$, and thus, $\left(p,w^i\right)={\lambda }_i$ for all $p\in \sigma$. 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 ${\mathbb{R}}^n$ that $f\left(p\right)$ for $p\in \sigma$ is the optimal value in the transportation problem of the model, and $f\left(p\right)=-\infty$ for $p\notin \sigma$. This function is piecewise linear and concave. It is natural to define its subdifferential using the subdifferential of convex function $\left(-f\right)$: $\partial f\left(p\right)=-\partial \left(-f\right)\left(p\right)$.

Let $G$ be the mentioned associated mapping.

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

$$\partial f\left(p\right)=\left\{lnq+\mathit{te}|q\in G\left(p\right),t\in \mathbb{R}\right\},$$

where $e=\left(1,\dots ,1\right)$ and $lnq=\left(ln{q}_1,\dots ,ln{q}_n\right)$. (The addend $\mathit{te}$ in this formula arises because it holds $\sum _{j\in J}{p}_j=1$ for $p\in \sigma$.)

Consider the convex function $h$, defining it as follows:

$$h\left(p\right)=\left\{\begin{array}{rr}\left(p,lnp\right),& \text{for}p\in {\sigma }^{\circ },\hfill \\ 0,& \text{for}p\in \partial \sigma ,\hfill \\ -\infty ,& \text{for}p\notin \sigma .\hfill \end{array}\right\}$$

Introduce the function

$$\phi \left(p\right)=h\left(p\right)-f\left(p\right)$$E4

Theorem 2. The fixed point of $G$ coincides with the minimum point of the convex function $\phi \left(p\right)$ on ${\sigma }^{\circ }$.

Another theorem for the problem can be obtained if we take into account that the mapping $G$ and the inverse mapping $G^{-1}$ have the same fixed points. For the introduced concave function $f$, we can consider the conjugate function:

$$f^{\ast }\left(y\right)=\underset{z}{\text{inf}}\left\{\left(y,z\right)-f\left(z\right)\right\}$$

(see [14]) With this function, we associate the function $\psi \left(q\right)=f^{\ast }\left(lnq\right)$, which is defined on ${\sigma }^{\circ }$.

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

$$f^{\ast }\left(lnq\right)=-\sum _{i\in I}{\lambda }_i\underset{j\in J}{\text{max}}ln\frac{c_j^i}{q_j}$$E5

Theorem 3. The fixed point of $G$ is the maximum point of the concave function $\psi \left(q\right)$ on ${\sigma }^{\circ }$.

For the functions $\phi \left(p\right)$ and $\psi \left(q\right)$, there is a duality relation as for dual programs of linear programming:

Proposition 2. For all $p,q\in {\sigma }^{\circ }$ the inequality

$$\phi \left(p\right)\ge \psi \left(q\right)$$

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

Corollary. $\phi \left(r\right)=\psi \left(r\right)$ 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^{\circ }.$ 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 $\omega$ and $\xi$ define the cells structure on ${\sigma }^{\circ }$ similarly to the faces structure of a polyhedron.

For implementation of the algorithms, we need to get the optimum point of the function $\phi \left(p\right)$ or $\psi \left(q\right)$ on the affine hull of the current cell.

Consider a couple of two cells $\mathrm{\Omega }\in \omega$, $\mathrm{\Xi }\in \xi$ corresponding to each other.

Let $L\supset \mathrm{\Omega }$, $M\supset \mathrm{\Xi }$ be their affine hulls. It will be shown that $L\cap M$ is singleton.

Let be $\left\{r\right\}=L\cap M$.

Lemma. The point $r$ is the minimum point of the function $\phi \left(p\right)$ on $L$ and the maximum point of the function $\psi \left(q\right)$ 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 ${\mathcal{B}}_k\in \mathfrak{B}$. We consider the cells ${\mathrm{\Omega }}_k=\mathrm{\Omega }\left({\mathcal{B}}_k\right),{\mathrm{\Xi }}_k=\mathrm{\Xi }\left({\mathcal{B}}_k\right)$ and have the point $q^k\in {\mathrm{\Xi }}_k$. Let $L_k\supset {\mathrm{\Omega }}_k$, $M_k\supset {\mathrm{\Xi }}_k$ be the affine hulls of these cells. We need to obtain the point of their intersection $r^k$.

Return to the transportation problem of the model and to the descriptions of cells. Consider the graph $\mathrm{\Gamma }\left({\mathcal{B}}_k\right)$. This graph can have more than one connected components. Let $\tau$ be number of connected components, and $i\in I_{\nu }$, $\left(m+j\right)$ for $j\in J_{\nu }$ be the vertices of $\nu$-th component. It is easy to verify that the linear system (3) for $L_k$ is going to be equivalent to this one:

$$\sum _{j\in J_{\nu }}{p}_j=\sum _{i\in I_{\nu }}{\lambda }_i,\nu =1,\dots ,\tau .$$E6

The linear system (1) for the cell ${\mathrm{\Xi }}_k$ defines coordinates $q_j$ on each connected component up to a positive multiplier:

$$q_j=t_{\nu }{q}_j^k,j\in J_{\nu }.$$

To obtain the coordinates of the point $r^k$, we need to put $p_j=q_j$ in corresponding Eq. (6), which gives the multiplier $t_{\nu }$.

For the obtained point, $r^k$ can be realized in two cases.

(i) $r^k\notin {\mathrm{\Xi }}_k$. Since $r^k$ is a maximum point on $M_k$ for the strictly concave function $\psi \left(q\right)$, the value of the function will increase for the moving point $q\left(t\right)=\left(1-t\right)q^k+{\mathit{tr}}^k)$ when $t$ increases in [0,1]. In considered case, this point reaches a face of ${\mathrm{\Xi }}_k$ at some $t=t^{\ast }<1$. Some of corresponding inequalities (2) for $p=q\left(t^{\ast }\right)$ is fulfilled as equality. Choose one of them. Corresponding edge $\left(l,m+j\right)$ will be added to graph. It unites two of connected components. We obtain ${\mathcal{B}}_{k+1}={\mathcal{B}}_k\cup \left\{\left(l,j\right)\right\}$, accept $q^{k+1}=q\left(t^{\ast }\right)$ and pass to the next step.

It should be noted that the dimension of the cell $\mathrm{\Xi }$ reduces. It will certainly be $r^k\in {\mathrm{\Xi }}_k$ when the current cell ${\mathrm{\Xi }}_k$ degenerates into a point, and we have $r^k=q^k$. But it can occur earlier.

(ii) $r^k\in {\mathrm{\Xi }}_k$. In this case, we can assume $q^k=r^k$. Otherwise, we can simply replace $q^k$ by $r^k$ with an increase of the function’s $\psi \left(q\right)$ value. We verify $q^k\in {\mathrm{\Omega }}_k$? For this, we obtain from the equations of the transportation problem the variables $z_{\mathit{ij}},\left(i,j\right)\in {\mathcal{B}}_k$, as linear functions $z_{\mathit{ij}}\left(p\right)$ and check $z_{\mathit{ij}}\left(q^k\right)\ge 0$. If it is true, the point $q^k$ is the required fixed point. Otherwise, we have $z_{\mathit{sl}}\left(q^k\right)<0$. We accept ${\mathcal{B}}_{k+1}={\mathcal{B}}_k\text{}\left\{\left(s,l\right)\right\},q^{k+1}=q^k$ 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\in \mathrm{\Xi }$ 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 ${\mathcal{B}}^1\in \mathfrak{B}$ and a point $q^1\in \mathrm{\Xi }\left({\mathcal{B}}^1\right).$ We depict the structures as matrices $m\times n$ with elements from $\left\{\times ,\cdot \right\}$, and $\times$ corresponds to an element of $\mathcal{B}$. For example, the structure ${\mathcal{B}}_{12}=\left\{\left(1,2\right),\left(1,3\right),\left(2,1\right),\left(2,2\right)\right\}$ will be depicted as the matrix

$${\mathcal{B}}_{12}=\left(\begin{array}{lll}\cdot & \times & \times \\ \times & \times & \cdot \end{array}\right)$$

(this is the structure for the cell ${\mathrm{\Omega }}_{12}$). Let us start with the structure

$$\begin{array}{l}{\mathcal{B}}^1=\left(\begin{array}{lll}\times & \cdot & \cdot \\ \times & \cdot & \cdot \end{array}\right)\end{array}$$

It means that both consumers prefer only first good. Let us choose as $q^1$ the price vector $q^1=\left(\mathrm{0.05,0.35,0.6}\right)$. It is easy to verify that ${\mathcal{B}}^1\in \mathfrak{B}$ and $q^1\in \mathrm{\Xi }\left({\mathcal{B}}^1\right)$.

Step 1. The graph $\mathrm{\Gamma }\left({\mathcal{B}}^1\right)$ has three connected components and the system (6) has the form

$$p_1=1,p_2=0,p_3=0.$$

Thus, we have $r^1=\left(\mathrm{1,0,0}\right)$. The cell $\mathrm{\Xi }\left({\mathcal{B}}^1\right)$ is given by the system

$$\frac{q_1}{1}\le \frac{q_2}{2},$$E7

$$\frac{q_1}{1}\le \frac{q_3}{3},$$E8

We have $q^1\in \mathrm{\Xi }\left({\mathcal{B}}^1\right)$ and $r^1\notin \mathrm{\Xi }\left({\mathcal{B}}^1\right)$. It is the case (i) in the description of algorithm. We have to move the point $q^1$ to the point $r^1$. For the moving point $q\left(t\right)$ it will be:

$$q_1\left(t\right)=0.05+0.95t,q_2\left(t\right)=\left(1-t\right)0.35,q_3\left(t\right)=\left(1-t\right)0.6.$$

This point reaches a face of $\mathrm{\Xi }\left({\mathcal{B}}^1\right)$ at $t=t^{\ast }=0.1111$: the inequality (7) for $q=q\left(t^{\ast }\right)$ is fulfilled as equality. We obtain ${\mathcal{B}}^2={\mathcal{B}}^1\cup \left\{\left(1,2\right)\right\}$ and $q^2=q\left(t^{\ast }\right)$.

$$\begin{array}{l}{\mathcal{B}}^2=\left(\begin{array}{lll}\times & \times & \cdot \\ \times & \cdot & \cdot \end{array}\right)\\ q^2=\left(\mathrm{0.1556,0.3111,0.5333}\right).\end{array}$$

Step 2. The graph $\mathrm{\Gamma }\left({\mathcal{B}}^2\right)$ has two connected components and the system (6) has the form

$$p_1+p_2=1,p_3=0.$$

For the point $r^2$, we have to consider this system with the additional equation

$$\frac{p_1}{1}=\frac{p_2}{2},$$

corresponding to (7), this gives $r^2=\left(\mathrm{0.3333,0.6667,0}\right)$. We have $r^2\notin \mathrm{\Xi }\left({\mathcal{B}}^2\right)$ since the inequality (8) is violated. The new moving point $q\left(t\right)=\left(1-t\right)q^2+{\mathit{tr}}^2$ has the coordinates:

$$q_1\left(t\right)=0.1556+0.1777t,q_2\left(t\right)=0.3111+0.3556t,q_3\left(t\right)=0.5333-0.5333t.$$

At $t^{\ast }=0.0625$ this point reaches the boundary of the cell $\mathrm{\Xi }\left({\mathcal{B}}^2\right)$. It is the point $c^1$ in the simplex $\sigma$. The inequality (8) for $q=q\left(t^{\ast }\right)$ is fulfilled as equality. Thus, we obtain:

$$\begin{array}{l}{\mathcal{B}}^3=\left(\begin{array}{lll}\times & \times & \times \\ \times & \cdot & \cdot \end{array}\right)\\ q^3=\left(\mathrm{0.1667,0.3333,0.5}\right).\end{array}$$

Step 3. Now, we have the case (ii) in the description of algorithm: the cell $\mathrm{\Xi }\left({\mathcal{B}}^3\right)$ contains unique point $q^3$ and thus $r^3=q^3$. We have to verify $r^3\in \mathrm{\Omega }\left({\mathcal{B}}^3\right)$? For this, we obtain from the equations of the transportation problem the variables $z_{\mathit{ij}},\left(i,j\right)\in {\mathcal{B}}^3$, and check $z_{\mathit{ij}}\left(q^3\right)\ge 0$. For these variables, we have the system:

$$z_{12}=q_2^3,z_{13}=q_3^3,z_{21}=0.5,z_{11}=q_1^3-0.5$$

We obtain $z_{11}$ = 0.1667–0.5 = −0.3333 < 0. Thus the element $\left(1,1\right)$ should be removed from the structure ${\mathcal{B}}^3$:

$$\begin{array}{l}{\mathcal{B}}^4=\left(\begin{array}{lll}\cdot & \times & \times \\ \times & \cdot & \cdot \end{array}\right)\\ q^4=q^3.\end{array}$$

Step 4. We have to obtain the point $r^4$. The graph $\mathrm{\Gamma }\left({\mathcal{B}}^4\right)$ has two connected components and the system for this point has the form:

$$\begin{array}{l}{p}_1=0.5,p_2+p_3=0.5,\\ \frac{p_2}{2}=\frac{p_3}{3}.\end{array}$$

Hence,

$$r^4=\left(\mathrm{0.5,0.2,0.3}\right).$$

It is easy to see that the description of the cell $\mathrm{\Xi }\left({\mathcal{B}}^4\right)$ has the form:

$$\begin{array}{l}\frac{q_2}{2}=\frac{q_3}{3},\frac{q_1}{1}\ge \frac{q_3}{3},\\ \frac{q_1}{3}\ge \frac{q_2}{2}.\end{array}$$E9

For $q=r^4$, the inequality (9) is violated, so $r^4\notin \mathrm{\Xi }\left({\mathcal{B}}^4\right)$. For the new moving point $q\left(t\right)$ we have:

$$q_1\left(t\right)=0.1667+0.3333t,q_2\left(t\right)=0.3333-0.1333t,q_3=0.5-0.2t.$$

At $t^{\ast }=0.625$ the inequality (9) becomes equality, the point $q\left(t\right)$ attains to the point $c^{12}=\left(\mathrm{0.375,0.25,0.375}\right)$ that is the boundary of $\mathrm{\Xi }\left({\mathcal{B}}^4\right)$. We obtain the new structure:

$$\begin{array}{l}{\mathcal{B}}^5=\left(\begin{array}{lll}\cdot & \times & \times \\ \times & \times & \cdot \end{array}\right)\\ \end{array}$$

and new point $q^5=c^{12}$. It is easy to verify that we obtain the equilibrium of the model.

The equilibrium price vector is

$$\tilde{p}=\left(\mathrm{0.375,0.25,0.375}\right)$$

The optimal solutions of the consumer’s problems are:

$${\tilde{x}}^1=\left(\mathrm{0,0.5,1}\right),{\tilde{x}}^2=\left(\mathrm{1,0.5,0}\right).$$

Figure 5 shows the moving of the point $q\left(t\right)$ 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 ${\mathcal{B}}_k\in \mathfrak{B}$. We consider two cells ${\mathrm{\Omega }}_k=\mathrm{\Omega }\left({\mathcal{B}}_k\right),{\mathrm{\Xi }}_k=\mathrm{\Xi }\left({\mathcal{B}}_k\right)$ and two points $p^k\in {\mathrm{\Omega }}_k,q^k\in {\mathrm{\Xi }}_k$. Let $L_k\supset {\mathrm{\Omega }}_k$, $M_k\supset {\mathrm{\Xi }}_k$ be the affine hulls of these cells. For the points of their intersection $L_k\cap M_k$, we obtain from (1), (3) the common system:

$$\frac{p_k}{c_k^i}=\frac{p_j}{c_j^i}\left(i,k\right),\left(i,j\right)\in B_k,$$E10

$$\sum _{j\in J_{\nu }}{p}_j=\sum _{i\in I_{\nu }}\left(p,w^i\right),\nu =1,\dots ,\tau ,$$E11

where the sets $J_{\nu },J_{\nu }$ correspond to $\nu$-th connected component of the graph $\mathrm{\Gamma }\left({\mathcal{B}}_k\right)$.

Under some assumption about starting structure this system has rank $\left(n-1\right)$ and under additional condition $\sum _{j\in J}{p}_j=1$ the system defines uniquely the solution $r^k=r\left({\mathcal{B}}_k\right)$. This is the intersection point of the affine hulls of the cells $\mathrm{\Omega }\left(\mathcal{B}\right)$ and $\mathrm{\Xi }\left(\mathcal{B}\right).$ It can be shown that $r^k\in \sigma$.

If $r^k\in \mathrm{\Omega }\left({\mathcal{B}}_k\right),r^k\in \mathrm{\Xi }\left({\mathcal{B}}_k\right)$, we have an equilibrium price vector.

Otherwise, we consider for $t\in \left[0,1\right)$ two moving points:

$$p\left(t\right)=p^k+t\left(r^k-p^k\right),q\left(t\right)=q^k+t\left(r^k-q^k\right)$$

It can be shown that in consequence of the assumption $c^i>0$, $\forall i\in I,$ there exists $t^{\ast }=\text{max}t$ under the conditions $p\left(t\right)\in \mathrm{\Omega }\left({\mathcal{B}}_k\right),q\left(t\right)\in \mathrm{\Xi }\left({\mathcal{B}}_k\right).$

It is the case when $t^{\ast }<1$. The two variants may occur:

(i) $t^{\ast }$ is limited by some of the inequalities $z_{\mathit{ij}}\left(p\left(t\right)\right)\ge 0,\left(i,j\right)\in {\mathcal{B}}_k$. Corresponding pair $\left(i,j\right)$ should be removed from ${\mathcal{B}}_k$: ${\mathcal{B}}_{k+1}={\mathcal{B}}_k\backslash \left\{\left(i,j\right)\right\}$. We accept $q^{k+1}=q\left(t^{\ast }\right),p^{k+1}=p\left(t^{\ast }\right)$ and pass to the next step.

(ii) $t^{\ast }$ is limited by some of the inequalities (2) in description of the cell $\mathrm{\Xi }\left({\mathcal{B}}_k\right)$. Corresponding pair $\left(i,l\right)$ should be added to ${\mathcal{B}}_k$: ${\mathcal{B}}_{k+1}={\mathcal{B}}_k\cup \left\{\left(i,l\right)\right\}$. We accept $q^{k+1}=q\left(t^{\ast }\right),p^{k+1}=p\left(t^{\ast }\right)$ and pass to the next step.

We consider the situation when $t^{\ast }$ 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 $p^0,q^0$.

Under this condition, it holds $t^{\ast }>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, $\lambda$ is the corresponding eigenvalue. If for a positive vector $\tilde{x}$ the vector $\tilde{z}=\lambda \tilde{x}-A\tilde{x}$ has all components equal zero except ${\tilde{z}}_{i_1},{\tilde{z}}_{i_2}$, then the following two conditions are equivalent:

$${\tilde{z}}_{i_1}\ge 0⟺\frac{{\tilde{x}}_{i_1}}{{\tilde{x}}_{i_2}}\ge \frac{x_{i_1}}{x_{i_2}}.$$

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 $p\left(t\right)$ reaches the face of its cell earlier than the point $q\left(t\right)$ does. For the next step the cell $\mathrm{\Omega }$ will be reduced, the cell $\mathrm{\Xi }$ 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]): $p_j{x}_j^i\le {\beta }_{\mathit{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=\left\{1,\dots ,n\right\},I=\left\{1,\dots ,m\right\},$ and $K=\left\{m+1,\dots ,m+l\right\}$ be the sets of the numbers of products, consumers, and firms. Thus, $S=I\cup K$ is the set of numbers of all participants.

The consumer $i\in I$ has the initial endowments $w^i\in R_{+}^n$ and also the initial money stock ${\alpha }_i$. His total budget after selling the initial endowments is equal to ${\alpha }_i+\left(p,w^i\right)$. Thus, the $i$ th consumer will choose the purchase vector $x^i$ looking for an optimal solution to the following problem:

$$\left(c^i{x}^i\right)\to \text{max}$$

under the conditions

$$\left(p,x^i\right)\le {\alpha }_i+\left(p,w^i\right),$$

$$x^i\ge 0.$$

The firm $k\in K$ plans to deliver to the market the products to a total sum of at least ${\lambda }_k$. If $x^k=\left(x_1^k,\dots ,x_n^k\right)$ denotes a plan of $k$ th firm then the total cost of such a supply at the prices $p_j$ equals $\left(p,x^k\right)$. The quality of the plan is estimated by the firm in tending to minimize the function $\left(c^k,x^k\right)$ . Here, $c^k=\left(c_1^k,\dots ,c_n^k\right)$ 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:

$$\left(c^k{x}^k\right)\to \text{min}$$

under the conditions

$$\begin{array}{l}\left(p,x^k\right)\ge {\lambda }_k,\\ x^k\ge 0.\end{array}$$

An equilibrium is defined by a price vector $\tilde{p}$ and a collection of vectors ${\tilde{x}}^i$ and ${\tilde{x}}^k$ $i\in I$ and $k\in K$, representing some solutions to optimization problems of the participants for $p=\tilde{p}$ and satisfying the balance of products:

$$\sum _{i\in I}{\tilde{x}}^i=\sum _{k\in K}{\tilde{x}}^k+\sum _{i\in I}{w}^i.$$

From this follows that we have to suppose $\sum _{i\in I}{\alpha }_i=\sum _{k\in K}{\lambda }_k$. As before, we suppose also that $\sum _{j\in J}{p}_j=1$ and $\sum _{i\in I}{w}^i=e$ with $e=\left(1,\dots ,1\right)$. Thus, in the equilibrium, we have

$$\sum _{i\in I}{\tilde{x}}^i=\sum _{k\in K}{\tilde{x}}^k+e.$$E12

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 $B\subset S\times J$ is named a structure, if for each $s\in S$ there exists $\left(s,j\right)\in \mathcal{B}$.

As before, we suppose that all vectors $c^s,s\in S$ are positive. The parametric transportation problem of the model is changed and becomes a net problem:

$$\sum _{i\in I}\sum _{j\in J}{z}_{\mathit{ij}}ln{c}_j^i-\sum _{k\in K}\sum _{j\in J}{z}_{\mathit{kj}}ln{c}_j^k\to \text{max}$$

$$-\sum _{j\in J}{z}_{\mathit{ij}}=-{\alpha }_i-\left(p,w^i\right),i\in I,$$

$$\sum _{i\in I}{z}_{\mathit{ij}}-\sum _{k\in K}{z}_{\mathit{kj}}=p_j,j\in J,$$

$$\sum _{j\in J}{z}_{\mathit{kj}}={\lambda }_k,k\in K,$$

$$z_{\mathit{ij}}\ge 0,z_{\mathit{kj}}\ge 0,i\in I,j\in J,k\in K.$$

It can be shown that this problem is solvable for all $p\in \sigma$.

As mentioned before, we consider the family $\mathfrak{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 $B\in \mathfrak{B}$, we define the balance zone $\mathrm{\Omega }\left(B\right)$ and the preference zone $\mathrm{\Xi }\left(B\right)$. 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 $\tilde{p}\in {\sigma }^{\circ }$ is an equilibrium price vector of generalized linear exchange model if and only if $\tilde{p}\in \mathrm{\Omega }\left(B\right)\cap$ $\mathrm{\Xi }\left(B\right)$ for some $B\in \mathfrak{B}$.

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: $\left(p,x^i\right)\le {\lambda }_i$. But for the ${\lambda }_i,i\in I$ and ${\lambda }_k,k\in K$, we obtain the condition $\sum _{i\in I}{\lambda }_i=1+\sum _{k\in K}{\lambda }_k$.

For this variant of model, we have the reduction to optimization problems as well. To do this, we consider the function $f\left(p\right)$, which gives the optimal value of the transportation problem by given price vector $p$. Having this function, we introduce as before the functions $\phi \left(p\right)=\left(p,lnp\right)-f\left(p\right)$ and $\psi \left(q\right)=f^{\ast }\left(lnq\right)$. For these functions, the main results of classical case remain valid.

Theorem 7. A vector $\tilde{p}$ is an equilibrium price vector if and only if $\tilde{p}$ is a minimum point of the function $\phi$ on ${\sigma }^{\circ }$.

Theorem 8. A vector $\tilde{p}$ is an equilibrium price vector if and only if $\tilde{p}$ is a maximum point of the function $\psi$ on ${\sigma }^{\circ }$.

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:

$$\sum _{j\in J}{p}_j{x}_j^k\to \text{max}$$

$$\sum _{j\in J}{d}_j^k{x}_j^k\le {\zeta }_k,$$

$$x_j^k\ge 0,j\in J.$$

Here, ${\zeta }_k$ is allowable resource and $d_j^k$ indicate the resource cost per unit of product $j$.

Let ${\lambda }_k\left(p\right)$ be the optimal value of this problem. The consumer $i\in I$ has the initial money stock ${\alpha }_i$, $\sum _{i\in I}{\alpha }_i=1$. The revenues of the firms are divided between consumers in some proportions, those are given by ${\theta }_{\mathit{ik}}$. The total budget of $i$ th consumers becomes ${\alpha }_i+\sum _{k\in K}{\theta }_{\mathit{ik}}{\lambda }_k\left(p\right)$. Thus, the $i$ th consumer has the following problem:

$$\left(c^i{x}^i\right)\to \text{max}$$

under the conditions

$$\begin{array}{l}\left(p,x^i\right)\le {\alpha }_i+\sum _{k\in K}{\theta }_{\mathit{ik}}{\lambda }_k\left(p\right),\\ x^i\ge 0.\end{array}$$

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.

Acknowledgments

This chapter was supported by the Russian Foundation for Basic Research, project 16-01-00108 À.