V.I. Shmyrev. Polyhedral complementarity on a simplex. Method of meeting paths for decreasing quasi-regular mappings ... P. 273-286

The paper explores the mathematical basis of a novel polyhedral complementarity approach proposed by the author for finding an economic equilibrium in a linear exchange model and its variations. The equilibrium problem reduces to finding fixed points of point-to-set mappings of the price simplex to itself. As a result, we obtain a polyhedral complementarity problem generated by a pair of polyhedral complexes in duality. The class of quasi-regular mappings, which is a new class of decreasing mappings having no analogs in $\mathbb{R}^n$, is considered. The procedure of meeting paths, which generalizes the known Lemke method for linear complementarity problems, is studied. It is shown that in the case under consideration the procedure has the property of monotonicity characteristic of linear complementarity problems with positive principal minors of the constraint matrix (P-class). The uniqueness of the desired fixed point is a consequence of monotonicity.

Keywords: simplex, polyhedral complex, complementarity, monotonicity, fixed point, algorithm

Received January 28, 2019

Revised March 15, 2019

Accepted April 15, 2019

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 19-010-00910 A), by Program no. 227 of the Presidium of the Russian Academy of Sciences, and by Interdisciplinary Integration Project no. 7B of the Siberian Branch of the Russian Academy of Sciences.

Vadim Ivanovich Shmyrev, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: shvi@math.nsc.ru

REFERENCES

1.   Shmyrev V.I. On the determinationof fixed pointsof piecewise constant monotone mappings in $\mathbb{R}^n$. Sov. Math. Dokl., 1981, vol. 24, no. 1, pp. 88–90.

2.   Shmyrev V.I. The problem of polyhedral complementarity. Optimizatsiya, 1988, vol. 44 (61), pp. 82–95 (in Russian).

3.   Shmyrev V.I. Polyhedral complementarity on a simplex. Potentiality of regular mappings. J. Appl. Indust. Math., 2018, vol. 12, no. 1, pp. 167–176. doi: 10.1134/S1990478918010155 

4.   Shmyrev V.I. Polyhedral complementarity on a simplex: search for fixed points of decreasing regular mappings. Diskret. Anal. Issled. Oper., 2019, vol. 26, no. 1, pp. 114–134 (in Russian). doi: 10.33048/daio.2019.26.598 

5.   Lemke C.E. Bimatrix equilibrium points and mathematical programming. Management Science, 1965, vol. 11, no. 7, pp. 681–689. doi: 10.1287/mnsc.11.7.681 

6.   Shmyrev V.I. An algorithm for the search of equilibrium in a linear exchange model. Sib. Math. J., 1985, vol. 26, no. 2, pp. 288–300. doi: 10.1007/BF00968776 

7.   Eisenberg E., Gale D. Consensus of subjective probabilities: The pari-mutuel method. Ann. Math. Statist., 1959, vol. 30, no. 1, pp. 165–168.

8.   Devanur N.R., Papadimitriou C.H., Saberi A., Vazirani V.V. Market equilibrium via a primal–dual algorithm for a convex program. JACM, 2008, vol. 55, no. 5, paper 22. doi: 10.1145/1411509.1411512 

9.   Shmyrev V.I. Polyhedral complementarity algorithms for finding equilibrium in linear models of competitive economics. Diskret. Anal. Issled. Oper., 2014, vol. 21, no. 2, pp. 84–101 (in Russian).

10.   Shmyrev V.I. On an approach to the determination of equilibrium in elementary exchange models. Sov. Math. Dokl., 1983, vol. 27, no. 1, pp. 230–233.

11.   Nikhil R. Devanur, Kamal Jain, Tung Mai, Vijay  V. Vazirani, Sadra Yazdanbod. New convex programs for fisher’s market model and its generalizations. arXiv:1603.01257v1 [cs.GT]. 2016. Available at: https://arxiv.org/pdf/1603.01257.pdf. 23 p.

12.   Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay  V. Vazirani, Sadra Yazdanbod. Convex program duality, fisher markets, and nash social welfare. In: Proc. 18th ACM Conf. Economics and Computation, Massachusets Institute of Technology, 2017, pp. 459–460. doi: 10.1145/3033274.3085109 

13.   Shmyrev V.I. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. J. Appl. Industr. Math., 2009, vol. 3, no. 4, pp. 505–518. doi: 10.1134/S1990478909040097 

14.   Pontryagin L.S. Foundations of combinatorial topology. Dover Publ., 2015, 112 p. ISBN: 9780486406855 . Original Russian text published in Pontryagin L.S. Osnovy kombinatornoi topologii. Moscow: Nauka Publ., 1986, 120 p.

15.   Aleksandrov P.S. Obshchaya teoriya gomologii [General homology theory]. Moscow: Nauka Publ., 1979, 416 p.

Cite this article as: V.I.Shmyrev. Polyhedral complementarity on a simplex. Method of meeting paths for decreasing quasi-regular mappings, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 2, pp. 273–286.