Geodesic
Polyhedral complementarity on a simplex: search for fixed points of~decreasing regular~mappings
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 1, pp. 114-134.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the problem of finding a fixed point for a special class of piecewise-constant mappings of a simplex into itself which arise in connection with the search for equilibrium prices in the classical exchange model and its various versions. The consideration is based on the polyhedral complementarity which is a natural generalization of linear complementarity. Here we study the mappings arising from models with fixed budgets. Mappings of this class possess a special property of monotonicity (logarithmic monotonicity), which makes it possible to prove that they are potential. We show that the problem of finding fixed points of these mappings is reducible to optimization problems for which it is possible to propose finite suboptimization algorithms. We give description of two algorithms. Illustr. 3, bibliogr. 20.
Mots-clés : polyhedral complex, complementarity, monotonicity, potentiality, fixed point, suboptimization, algorithm. 
@article{DA_2019_26_1_a6,
     author = {V. I. Shmyrev},
     title = {Polyhedral complementarity on a simplex: search for fixed points of~decreasing regular~mappings},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {114--134},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2019},
     language = {ru},
     url = {https://geodesic-test.mathdoc.fr/item/DA_2019_26_1_a6/}
}
TY  - JOUR
AU  - V. I. Shmyrev
TI  - Polyhedral complementarity on a simplex: search for fixed points of~decreasing regular~mappings
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 114
EP  - 134
VL  - 26
IS  - 1
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DA_2019_26_1_a6/
LA  - ru
ID  - DA_2019_26_1_a6
ER  - 
%0 Journal Article
%A V. I. Shmyrev
%T Polyhedral complementarity on a simplex: search for fixed points of~decreasing regular~mappings
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 114-134
%V 26
%N 1
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DA_2019_26_1_a6/
%G ru
%F DA_2019_26_1_a6
V. I. Shmyrev. Polyhedral complementarity on a simplex: search for fixed points of~decreasing regular~mappings. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 1, pp. 114-134. https://geodesic-test.mathdoc.fr/item/DA_2019_26_1_a6/

[1] P. S. Aleksandrov, A General Theory of Homologies, Nauka, M., 1979 (Russian) | MR

[2] L. S. Pontryagin, The Basics of Combinatorial Topology, Nauka, M., 1986 (Russian) | MR

[3] R. T. Rockafellar, Convex Analysis, Princeton, 1970 | MR

[4] V. I. Shmyrev, “On the determination of fixed points of piecewise constant monotone mappings in $R^n$”, Sov. Math., Dokl., 24:1 (1981), 88–90 | MR | Zbl

[5] V. I. Shmyrev, “On an approach to the determination of equilibrium in elementary exchange models”, Sov. Math., Dokl., 27:1 (1983), 230–233 | MR | Zbl

[6] V. I. Shmyrev An algorithm for the search of equilibrium in a linear exchange model, Sib. Math. J., 26:2 (1985), 288–300 | DOI | MR | Zbl | Zbl

[7] V. I. Shmyrev, “A problem of polyhedral complementarity”, Optimization, 44, Inst. Mat. SO AN SSSR, Novosibirsk, 1988, 82–95 (Russian) | MR | Zbl

[8] V. I. Shmyrev, “An algorithm for finding equilibrium in the linear exchange model with fixed budgets”, J. Appl. Ind. Math., 3:4 (2009), 505–518 | DOI | MR | Zbl

[9] V. I. Shmyrev, “Polyhedral complementarity algorithms for searching an equilibrium in linear models of competitive economy”, Diskretn. Anal. Issled. Oper., 21:2 (2014), 84–101 (Russian) | Zbl

[10] V. I. Shmyrev, “Polyhedral complementarity on a simplex. Potentiality of regular mappings”, J. Appl. Ind. Math., 12:1 (2018), 167–176 | DOI | MR | Zbl

[11] Adsul B., Babu C. S., Gang J., Mehta R., Sohoni M., “A simplex-like algorithm for Fisher markets”, Algorithmic game theory, SAGT 2010, Lect. Notes Comput. Sci., 6386, Springer, Berlin–Heidelberg, 2010, 18–29 | DOI | MR | Zbl

[12] Birnbaum B., Devanur N. R., Xiao L., “Distributed algorithms via gradient descent for Fisher markets”, Proc. 12th ACM Conf. Electronic Commerce (San Jose, CA, June 5–9, 2011), ACM, New York, 2011, 127–136

[13] Cole R., Devanur N., Gkatzelis V., Jain K., Mai T., Vazirani V. V., Yazdanbod S., “Convex program duality, Fisher markets, and Nash social welfare”, Proc. 18th ACM Conf. Economics and Computation (Cambridge, MA, June 26–30, 2017), ACM, New York, 2017, 459–460

[14] Devanur N. R., Jain K., Mai T., Vazirani V. V., Yazdanbod S., New convex programs for Fisher's market model and its generalizations, 2016, arXiv: 1603.01257

[15] Devanur N. R., Papadimitriou C. H., Saberi A., Vazirani V. V., “Market equilibrium via a primal-dual algorithm for a convex program”, J. ACM, 55:5 (2008), 22:1–22:18 | DOI | MR

[16] Eisenberg E., Gale D., “Consensus of subjective probabilities: The pari-mutuel method”, Ann. Math. Stat., 30:1 (1959), 165–168 | DOI | MR | Zbl

[17] Gang J., Mehta R., Sohoni M., Vishnoi N. K., “Towards polynomial simplex-like algorithms for market equilibria”, Proc. 24th Annu. ACM-SIAM Symp. Discrete Algorithms (New Orleans, LA, Jan. 6–8, 2013), SIAM, Philadelphia, PA, 2013, 1226–1242

[18] Shmyrev V. I., “An iterative approach for searching an equilibrium in Piecewise linear exchange model”, Discrete Optimization and Operations Research, Proc. 9th Int. Conf. DOOR (Vladivostok, Russia, Sept. 19–23, 2019), Lect. Notes Comput. Sci., 9869, Springer, Cham, 61–72 | DOI | MR

[19] Shmyrev V. I., “Polyhedral complementarity and fixed points problem of decreasing regular mappings on simplex”, Optimization and Applications, Proc. 8th Int. Conf. Optim. Methods Appl. (Petrovac, Montenegro, Oct. 2–7, 2017), CEUR Workshop Proc., 1987, RWTH Aachen Univ., Aachen, 2017, 511–516

[20] Vazirani V. V., “Spending constraint utilities, with applications to the adwords market”, Math. Oper. Res., 35:2 (2010), 458–478 | DOI | MR | Zbl