Volume 26, No 1, 2019, P. 114-134

UDC 519.865.3
V. I. Shmyrev
Polyhedral complementarity on a simplex: Search for fixed points of decreasing regular mappings

Abstract:
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.

Keywords: polyhedral complex, complementarity, monotonicity, potentiality, fixed point, suboptimization, algorithm.

DOI: 10.33048/daio.2019.26.598

Vadim I. Shmyrev ^1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: shvi@math.nsc.ru

Received October 19, 2017
Revised September 19, 2018
Accepted September 26, 2018

References

[1] P. S. Aleksandrov, A General Theory of Homologies, Nauka, Moscow, 1979 [Russian].

[2] L. S. Pontryagin, The Basics of Combinatorial Topology, Nauka, Moscow, 1986 [Russian].

[3] R. T. Rockafellar, Convex Analysis, Princeton Univ. Press, Princeton, 1970. Translated under the title Vypuklyi analiz, Mir, Moscow, 1973 [Russian].

[4] V. I. Shmyrev, On the determination of fixed points of piecewise constant monotone mappings in $R^n$, Dokl. Akad. Nauk SSSR, 259, No. 2, 299–301, 1981 [Russian]. Translated in Sov. Math., Dokl., 24, No. 1, 88–90, 1981.

[5] V. I. Shmyrev, On an approach to the determination of equilibrium in elementary exchange models, Dokl. Akad. Nauk SSSR, 268, No. 5, 1062–1066, 1983 [Russian]. Translated in Sov. Math., Dokl., 27, No. 1, 230–233, 1983.

[6] V. I. Shmyrev, An algorithm for the search of equilibrium in a linear exchange model, Sib. Mat. Zh., 26, No. 2, 162–175, 1985 [Russian]. Translated in Sib. Math. J., 26, No. 2, 288–300, 1985.

[7] V. I. Shmyrev, A problem of polyhedral complementarity, in Optimization, Vol. 44, pp. 82–95, Inst. Mat. SO AN SSSR, Novosibirsk, 1988 [Russian].

[8] V. I. Shmyrev, An algorithm for finding equilibrium in the linear exchange model with fixed budgets, Sib. Zh. Ind. Mat., 11, No. 2, 139–154, 2008 [Russian]. Translated in J. Appl. Ind. Math., 3, No. 4, 505–518, 2009.

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

[10] V. I. Shmyrev, Polyhedral complementarity on a simplex. Potentiality of regular mappings, Sib. Zh. Ind. Mat., 21, No. 1, 118–128, 2018 [Russian]. Translated in J. Appl. Ind. Math., 12, No. 1, 167–176, 2018.

[11] B. Adsul, C. S. Babu, J. Gang, R. Mehta, and M. Sohoni, A simplex-like algorithm for Fisher markets, in Algorithmic Game Theory (Proc. 3rd Int. Symp., Athens, Greece, Oct. 18–20, 2010), pp. 18–29, Springer, Heidelberg, 2010 (Lect. Notes Comput. Sci., Vol. 6386).

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

[13] R. Cole, N. R. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. V. Vazirani, and S. Yazdanbod, Convex program duality, Fisher markets, and Nash social welfare, in Proc. 18th ACM Conf. Econ. Comput., Cambridge, MA, USA, June 26–30, 2017, pp. 459–460, ACM, New York, 2017.

[14] N. R. Devanur, K. Jain, T. Mai, V. V. Vazirani, and S. Yazdanbod, New convex programs for Fisher’s market model and its generalizations, 2016 (Cornell Univ. Libr. e-Print Archive, arXiv:1603.01257).

[15] N. R. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani, Market equilibrium via a primal–dual algorithm for a convex program, J. ACM, 55, No. 5, 22:1–22:18, 2008.

[16] E. Eisenberg and D. Gale, Consensus of subjective probabilities: The parimutuel method, Ann. Math. Stat., 30, No. 1, 165–168, 1959.

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

[18] V. I. Shmyrev, An iterative approach for searching an equilibrium in piece-wise linear exchange model, in Discrete Optimization and Operations Research (Proc. 9th Int. Conf. DOOR, Vladivostok, Russia, Sept. 19–23, 2016), pp. 61–72, Springer, Cham, 2016 (Lect. Notes Comput. Sci., Vol. 9869).

[19] V. I. Shmyrev, Polyhedral complementarity and fixed points problem of decreasing regular mappings on simplex, in Optimization and Applications (Proc. VIII Int. Conf. Optim. Methods Appl., Petrovac, Montenegro, Oct. 2–7, 2017), pp. 511–516, RWTH Aachen Univ., Aachen, 2017 (CEUR Workshop Proc., Vol. 1987). Available at http://ceur-ws.org/Vol-1987 (accessed Nov. 15, 2018).

[20] V. V. Vazirani, Spending constraint utilities with applications to the adwords market, Math. Oper. Res., 35, No. 2, 458–478, 2010.