Polyhedral Complementarity and Fixed Points Problem of Decreasing Regular Mappings on Simplex Vadim I. Shmyrev Sobolev Institute of Mathematics, Russian Academy of Sciences 4 Acad. Koptyug avenue, 630090 Novosibirsk, Russia. Novosibirsk State University, 2 Pirogova street, 630090 Novosibirsk, Russia. shmyrev.vadim@mail.ru Abstract A new development of polyhedral complementarity investigation is pre- sented. This consideration extends the author’s original approach to the equilibrium problem in a linear exchange model and its variations. Two polyhedral complexes in duality and a cells correspondence are given. The problem is to find a point of intersection of the cells corre- sponding each other . This is a natural generalization of linear comple- mentarity problem. Now we study arising point-to-set mappings with- out the original exchange model. The potentiality for a special class of regular mappings is proved. As a result the fixed point problem of mapping reduces to an optimization problem . Two finite algorithms for this problem are considered. 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 [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]. Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org 511 Ω1 Ξ6 Ω5 Ω7 x∗ is the solution Ω4 x∗ ∈ Ω6 ∩ Ξ6 Ω3 x∗ Ξ2 Ω6 Ξ7 Ξ3 Ω2 Ξ4 Ξ1 Ξ5 Figure 1: Polyhedral complementarity 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 Rn , 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]. 2 Polyhedral Complementarity Problem 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 , Ξi )}ri=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 . 3 Polyhedral Complementarity on Simplex Let σ be the unit simplex in Rn : { ∑ n } σ = p ∈ R+ | n pj = 1 . 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 : ∑ ∑ hj pj + hk pk ≥ γ, (1) j∈S k∈S / where S ̸= ∅, S ⊂ J = {1, ..., n} and hj > 0, j ∈ S, hk < 0, k ∈ / S. 512 p3 p3 G Ω2 1 c c12 Ω12 c2 Ω1 p1 p2 p1 p2 Complex ξ Complex ω Figure 2: Polyhedral complexes in exchange model Fig.2 illustrate the polyhedral complexes for a model with 3 commodities and 2 consumers. Each of both complexes has 17 cells. Fig.3 illustrate the arising complementarity problem. The point c12 ∈ Ω12 is it’s solution: . p3 Ω2 c1 c12 Ω12 Ω1 c2 p1 p2 Figure 3: Complementarity problem: c12 is the solution. 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. 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: pj /pk ≥ γ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) corre- sponding 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 ω . 4 Monotone Regular Mappings ◦ 1 . 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. 513 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 = (q1 , ..., qn ) we introduce the vector ln q = (ln q1 , ..., ln qn ). Definition 3. The mapping G is locally logarithmically decreasing, if (p2 − p1 , ln q 2 − ln q 1 ) ≤ 0, ∀p1 ∈ Ω1 , p2 ∈ Ω2 . In what follows we consider a narrower class of regular mappings for which in the inequalities (1) we have: hj = 1, j ∈ S, hk = −1, k∈ / S, and −1 ≤ γ ≤ 1. So (1) becomes ∑ ∑ pj − pk ≥ γ. j∈S k∈S / It can be proofed, that for regular mappings the subclass of locally decreasing mappings coincides with the subclass of locally logarithmically decreasing mappings. 2◦ . Reduction to the optimization problem. Definition 4. A mapping G is named potential if there exists piecewise linear concave function f on σ such that ∀p ∈ σ ∂f (p) = {ln q + tθ|q ∈ G(p), t ∈ R1 , } where θ = (1, ..., 1) and ∂f (p) is the subdifferential of the function f at the point p. 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 : (p2 − p1 , ln q 2 − ln q 1 ) ≤ 0, ∀p1 , p2 ∈ σ, ∀q 1 ∈ G(p1 ), q 2 ∈ G(p2 ). 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 {(y, z) − f (z)} z Theorem 2. The fixed point of G is the maximum point of the concave function ψ(q) = f ∗ (ln q) on σ ◦ . ◦ 514 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 mini- mization 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 pk ∈ Ωk , q k ∈ Ξk . We consider affine hulls Lk ⊃ Ωk , Mk ⊃ Ξk and obtain the point of their intersection rk . 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 = Q1 ∪Q2 , ∪..., Qτ is the obtained subdivision of J. It is easy to verify that the linear system for Lk is going to be equivalent to this one : ∑ pj = αν , ν = 1, ..., τ. (3) j∈Qν The conditions for the cell Ξk define coordinates qj on each connected component up to a positive multiplier: qj = tν qjk , j ∈ Qν . To obtain the coordinates of the point rk we need to put pj = qj in corresponding equation (3), which gives the multiplier tν . For the obtained point rk can be realized two cases. (i) rk ∈ / Ωk . Since rk is a minimum point on Lk for the strictly convex function φ(p), the value of the function will diminish for the moving point p(t) = (1 − t)pk + trk ) 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 pk+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 rk ∈ Ωk when the current cell Ωk degenerates into a point and we have rk = pk . But it can occur earlier. (ii) rk ∈ Ωk . In this case we can assume pk = rk . Otherwise, we can simply replace pk by rk with a decrease of the function’s φ(p) value. If rk ∈ Ξk , then rk is the required fixed point. Otherwise, we are looking for the maximum t∗ , at which point q(t) = (1 − t)q k + trk 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 pk+1 = pk , 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 φ(pk ) − ψ(q k ) decreases at each step of the process and we use this to prove the finiteness of the process. 515 Acknowledgments. This work was supported by the Russian Foundation for Basic Research, project 16-01-00108 . References [Rubinstein, 1971] Rubinstein G.Sh., Shmyrev V. I. Methods for minimization quasiconvex function on poly- hadron (in Russian). Optimization 1(18). 82–117 [Shmyrev, 2017] Shmyrev V. I. Polyhedral complementarity on simplex. Potentiality of regular mappings (in Russian).J. Appl. Indust. Math. . to appear. [Shmyrev, 1996] Shmyrev V. I., Shmyreva N. V. An iterative algorithm for searching an equilibrium in the linear exchange model. Sib.Adv.Math. 6, 1. 87–104 [Shmyrev, 2009] Shmyrev V. I. An algorithm for finding equilibrium in the linear exchange model with fixed budgets.Journal of Applied and Industrial Mathematics 3(4). 505–518 [Shmyrev, 2006] Shmyrev V. I. An algorithmic approach for searching an equilibrium in fixed budget exchange models. In Driessen, T. S., van der Laan, G. , Vasil’ev, V. A., Yanovskaya, E. B. (eds.) Russian Contributions to Game Theory and Equilibrium Theory. (pp. 217–235). Berlin, Germany: Springer. [Shmyrev, 2016] Shmyrev Vadim I. (2016) An Iterative Approach for Searching an Equilibrium in Piecewise Linear Exchange Model. In Kochetov, Yu. et al. (Eds.) DOOR-2016. LNCS (Lecture Notes in Computer Sciences). ( vol. 9869, pp. 61-72). Heidelberg, Germany : Springer. [Shmyrev, 2008] Shmyrev V. I. A generalized linear exchange model. J. Appl. Indust. Math. 2, 1. 125–142 [Shmyrev, 1985] Shmyrev V. I. An algorithm for the search of equilibrium in the linear exchange model. Sibirian Math. J. 26. 288–300 [Shmyrev, 1983] Shmyrev V. I. On an approach to the determination of equilibrium in elementary exchange models, Sov. Math. Dokl. 27, 1, 230–233 [Eaves, 1976] Eaves, B. C. A finite algorithm for linear exchange model. J. Math. Econom. 3(2), 197–204 . [Eisenberg & Gale, 1959] E. Eisenberg and D. Gale.: Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics 30(1). 165–168 [Devanur et al., 2008] Devanur, N. R., Papadimitriou, C. H., Saberi, A., Vazirani, V. V. Market equilibrium via a primal–dual algorithm for a convex program.Journal of the ACM (JACM), 55(5). Article 22 516