Introduction

It is known that the problem of finding an equilibrium in a linear exchange model can be reduced to the linear complementarity problem [Eaves, 1976]. The polyhedral complementarity approach [Shmyrev, 1983] 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 the simplex-method of linear programming. It has no analogues and makes it possible to obtain the finite algorithms not only for the linear exchange model [Shmyrev, 1985], but also for some of it's variations [Shmyrev, 2008], (more references one can find in [Shmyrev, 2016]). 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 [Eisenberg & Gale, 1959], is well known . This result has been used by many authors to study computational aspects of the problem. Some review of that can be found in [Devanur et al., 2008]. The polyhedral complementarity approach has given an alternative reduction of the Fisher's problem to a convex program [Shmyrev, 1983], [Shmyrev, 2006]. Only the well known elements of transportation problem algorithms are used in the procedures obtained by this way [Shmyrev, 2009]. These simple procedures can be used for getting iterative methods for more complicate models [Shmyrev, 1996], [Shmyrev, 2016].

Ξ 1 Ξ3 Ξ4 Ξ6 Ω1 Ξ7 Ω2 Ξ2 Ξ3 Ξ4 Ξ 5 Ω1 Ω2 x * ∈ Ω 6 ∩ Ξ 6 Ω4 Ω3 Ω7 x * Ω5 Ω6

x * is the solution By the given approach we try to study a mathematical fundamental principle of the proposed finite algorithms ignoring an original economic model. We consider a class of piecewise constant multivalued mappings on the simplex in R n , which possess some monotonicity property . The potentiality of these mappings is proved [Shmyrev, 2017]. This makes possible to reduce a fixed point problem to two optimization problems which are in duality similarly to dual linear programming problems. Two finite algorithms presented here are based on the ideas of suboptimization [Rubinstein, 1971].

Polyhedral Complementarity Problem

We consider polyhedrons in R n . Let two polyhedral complexes ω and ξ with the same number of cells r be given . Let R ⊂ ω × ξ be a one-to-one correspondence : R = {(Ω i , Ξ i )} r i=1 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 each other:

Ω i ≺ Ω j ⇐⇒ Ξ i ≻ Ξ j .

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

p * is the solution ⇐⇒ p * ∈ Ω i ∩ Ξ i for 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 7 cells. There is a unique solution of the problem -the point x * that belongs to Ω 6 and Ξ 6 .

Polyhedral Complementarity on Simplex

Let σ be the unit simplex in R n :

σ = { p ∈ R n + | n ∑ j=1 p j = 1 } .

We consider on σ two polyhedral complexes in duality ω = {Ω i } and ξ = {Ξ i }.The cell of full dimension of the complex ω is defined by the condition p ∈ σ and a system of linear inequalities of the form :

∑ j∈S h j p j + ∑ k / ∈S h k p k ≥ γ, (1)

where S ̸ = ∅, S ⊂ J = {1, ..., n} and . For the faces points of the cell some of inequalities (1) become equalities. For a face of dimension (n − 2) there is only one equality and so we obtain a subdivision J into S and J \ S.

h j > 0, j ∈ S, h k < 0, k / ∈ S.p 1 p 2 p 3 Ω 1 Ω 12 Ω 2 c 1 c 12 c 2

It is assumed that the cells {Ω i } form a subdivision of the simplex σ and the cells {Ξ i } form a subdivision of it's interior σ • . The cells {Ξ i } of full dimension are defined by the inequalities of the form:

p j /p k ≥ γ jk .

(2)

A vertex of ξ will be given by a collection of (n − 1) linearly independent equations obtained from inequalities (2). With such a collection we can associate a graph with a set of vertexes J and a set of edges (j, k) corresponding to the selected inequalities. It is easy to see, that to obtain an edge of ξ we have to remove one edge of the graph. In this way we obtain two connected components and also a subdivision J into two subsets Q and J \Q.

Concordance condition. The subdivision for an edge of the complex ξ is the same as that for the corresponding cell of the complex ω .

Monotone Regular Mappings1 • . Monotonicity property.

For the problem under consideration it is naturally to introduce piecewise constant point-to-set mapping G, which for every point of the relative interior of a cell Ω ∈ ω assigns the corresponding cell Ξ ∈ ξ: G(p) = Ξ for all p ∈ Ω • . So the polyhedral complementarity problem becomes the fixed point one: we have to find p ∈ G(p). It is clear, that the fixed point of the mapping G will be also the fixed point of it's restriction G • on σ • . A key feature of the considered fixed point problem is a specific monotonicity property of arising mappings.

Definition 1. We say that cells Ω 1 , Ω 2 ∈ ω are adjacent, if they have common (n − 2)-dimensional face.

Let the cells Ω 1 , Ω 2 be adjacent and q 1 , q 2 are the corresponding vertexes of ξ. Let h be a vector, for which the inequality (h, Ω

• 2 − Ω • 1 ) ≥ 0 holds.

Definition 2. The mapping G is locally decreasing, if for each two adjacent Ω 1 , Ω 2 the inequality (h, q 2 − q 1 ) ≤ 0 is valid.

For a positive vector q = (q 1 , ..., q n ) we introduce the vector ln q = (ln q 1 , ..., ln q n ).

Definition 3. The mapping G is locally logarithmically decreasing, if (p 2 − p 1 , ln q 2 − ln q 1 ) ≤ 0,

∀p 1 ∈ Ω 1 , p 2 ∈ Ω 2 .

In what follows we consider a narrower class of regular mappings for which in the inequalities (1) we have:

h j = 1, j ∈ S, h k = −1, k / ∈ S,

and

−1 ≤ γ ≤ 1. So (1) becomes ∑ j∈S p j − ∑ k / ∈S p k ≥ γ.

It can be proofed, that for regular mappings the subclass of locally decreasing mappings coincides with the subclass of locally logarithmically decreasing mappings. The main feature of the considered fixed point problem is the fact that logarithmically decreasing mappings are potential [Shmyrev, 2017]. We have as a corollary that locally logarithmically decreasing mappings are logarithmically decreasing in the large :

(p 2 − p 1 , ln q 2 − ln q 1 ) ≤ 0, ∀p 1 , p 2 ∈ σ, ∀q 1 ∈ G(p 1 ), q 2 ∈ G(p 2 ).

This allows us to reduce the fixed point problem to the optimization one. For p > 0 we introduce the function h(p) = (p, ln p) and consider the function

φ(p) = h(p) − f (p),

where f (p) is the potential function of the mapping G • .

Theorem 1. The fixed point of G • coincides with the minimum point of the convex function φ(p) on σ •

The function φ is very simple and the suboptimization approach [Rubinstein, 1971] can be used to minimize it . In this way we obtain the finite algorithm for the fixed point searching.

Another algorithm 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 * :

f * (y) = inf z {(y, z) − f (z)} Theorem 2. The fixed point of G • is the maximum point of the concave function ψ(q) = f * (ln q) on σ • .

It can be shown that for the functions φ(p) and ψ(q) there is a duality relation as for dual programs of linear programming:

Proposition. For all p, q ∈ σ • the inequality φ(p) ≥ ψ(q) holds . If this inequality turns into equality then p = q .

Corollary. φ(r) = ψ(r) if the point r is the fixed point of the mapping G 3 • . Algorithms.

The mentioned theorems allow us to propose two finite algorithms for searching fixed points. Algorithmically they are based on the ideas of suboptimization [Rubinstein, 1971], 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 one does not need to have function φ(p) and f * (y) explicit. We just need to be able to verify the inequality defining cells Ω ∈ ω and Ξ ∈ ξ.

We now describe the general scheme of the algorithm that is based on the theorem 1. The other one using the theorem 2 is quite similar.

Consider a couple of two cells Ω ∈ ω, Ξ ∈ ξ corresponding each other. Let L, M be their affine hulls respectively. It can be shown that L ∩ M is singleton. Let r be the point of this intersection. Theorem 3. The point r is the minimum point of the function φ(p) on L and the maximum point of the function ψ(q) on M .

On the current k-step of the process there are two cells Ω k ∈ ω, Ξ k ∈ ξ corresponding each other and two points p k ∈ Ω k , q k ∈ Ξ k . We consider affine hulls L k ⊃ Ω k , M k ⊃ Ξ k and obtain the point of their intersection r k . For this we need descriptions of these sets.

As it was mentioned before, with an edge of ξ we associate a graph with two connected components and a subdivision J into two subsets Q and J \ Q. For a cell of higher dimension the associated graph will have more components, that will entail an increase of the sets number in the subdivision of J. Let τ be the number of connected components of the associated graph for the cell Ξ k and J = Q 1 ∪Q 2 , ∪..., Q τ is the obtained subdivision of J. It is easy to verify that the linear system for L k is going to be equivalent to this one : ∑ j∈Qν p j = α ν , ν = 1, ..., τ.

(3)

The conditions for the cell Ξ k define coordinates q j on each connected component up to a positive multiplier:

q j = t ν q k j , j ∈ Q ν .

To obtain the coordinates of the point r k we need to put p j = q j in corresponding equation (3), which gives the multiplier t ν . For the obtained point r k can be realized two cases. (i) r k / ∈ Ω k . Since r k is a minimum point on L k for the strictly convex function φ(p), the value of the function will diminish for the moving point p(t) = (1 − t)p k + tr k ) when t increases in [0,1]. In considered case this point reaches a face of Ω k at t = t * < 1 . This face we take as Ω k+1 , that determines the cell Ξ k+1 . We accept p k+1 = p(t * ), q k+1 = q k and pass to the next step.

It should be noted that the dimension of the cell Ω reduces. It will certainly be r k ∈ Ω k when the current cell Ω k degenerates into a point and we have r k = p k . But it can occur earlier.

(ii) r k ∈ Ω k . In this case we can assume p k = r k . Otherwise, we can simply replace p k by r k with a decrease of the function's φ(p) value. If r k ∈ Ξ k , then r k is the required fixed point. Otherwise, we are looking for the maximum t * , at which point q(t) = (1 − t)q k + tr k is still in the Ξ k . At t = t * the point q(t) reaches a face of the cell Ξ k , which is accepted as Ξ k+1 . The corresponding cell of the complex ω will be Ω k+1 . We accept p k+1 = p k , q k+1 = q(t * ) and pass to the next step.

Nondegeneracy condition. The dimension of the current cells Ω k , Ξ k at each step of the process changes per unit.

Under this condition the value of the difference φ(p k ) − ψ(q k ) decreases at each step of the process and we use this to prove the finiteness of the process.