УДК 519.865.3
MSC: 90С33, 90С46
DOI: 10.21538/0134-4889-2020-26-3-258-274
Полный текст статьи (Full text)
Работа выполнена при поддержке РФФИ (проект № 19-010-00910 А) и при поддержке программы фундаментальных научных исследований СО РАН № I.5.1, проект № 0314-2019-0018.
Работа посвящена дальнейшему развитию оригинального подхода к поиску равновесных состояний в линейных экономических моделях обмена. Концептуальной основой подхода является полиэдральная комплементарность, обобщающая известную схему линейной комплементарности. Исходная проблема сводится к отысканию неподвижных точек кусочно-постоянных многозначных отображений на симплексе цен, порождаемых парой полиэдральных комплексов в двойственности. Для модели с фиксированными бюджетами (модель Фишера) возникающие отображения потенциальны, что позволяет свести проблему равновесия к паре оптимизационных задач, находящихся в двойственности подобно задачам линейного программирования. Полученное сведение отлично от широко известного результата Гейла — Айзенберг и позволяет предложить конечные алгоритмы отыскания равновесных цен. В статье представлена концептуально завершенная версия подхода. Дана точная формулировка двойственного варианта предложенного сведения как для модели Фишера, так и для ее обобщений. Получено сведение и для общей модели с переменными бюджетами.
Ключевые слова: модель обмена, экономическое равновесие, неподвижная точка, полиэдральная комплементарность, оптимизационная задача, сопряженная функция, алгоритм
СПИСОК ЛИТЕРАТУРЫ
1. Шмырев В.И. Об одном подходе к отысканию равновесия в простейших моделях обмена // Докл. АН СССР. 1983. Т. 268, № 5. С. 1062–1066.
2. Шмырев В. И. Задача полиэдральной комплементарности. Оптимизация // Сб. науч. тр. / Ин-т математики СО АН СССР. Новосибирск, 1988. Вып. 44(61). С. 82–95.
3. Eaves B.C. A finite algorithm for linear exchange model // J. Math. Econom. 1976. Vol 3, no. 2. P. 197–203. doi: 10.1016/0304-4068(76)90028-8
4. Gale D. The linear exchange model // J. Math. Econom. 1976. Vol 3, no. 2. P. 205–209. doi: 10.1016/0304-4068(76)90029-X
5. Shmyrev Vadim I. Polyhedral complementarity approach to equilibrium problem in linear exchange models // Optimization Algorithms. Examples / ed. Jan Valdman. London: IntechOpen, 2018. P. 27–46. doi: 10.5772/intechopen.77206
6. Шмырев В. И. Алгоритмы полиэдральной комплементарности для отыскания равновесия в линейных моделях конкурентной экономики // Дискрет. анализ и исследование операций. 2014. Vol. 21, no. 2. P. 84–101.
7. Шмырев В. И. Полиэдральная комплементарность на симплексе. Потенциальность регулярных отображений // Сиб. журн. индустр. математики. 2018. Т. 21., № 1(73). С. 118–128. doi: 10.17377/SIBJIM.2018.21.111
8. Eisenberg E., Gale D. Consensus of subjective probabilities: The pari-mutuel method // Annals Math. Stat. 1959. Vol. 30, no. 1. P. 165–168. doi: 10.1214/aoms/1177706369
9. 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, art.-no. 22. 18 p. doi: 10.1145/1411509.1411512
10. Birnbaum B., Devanur N.R., Xiao L. Distributed algorithms via gradient descent for Fisher markets // Proc. 12th ACM Conf. on Electronic Commerce. N Y: ACM, 2011. P. 127–136. doi: 10.1145/1993574.1993594
11. Lemke C. E. Bimatrix equilibrium points and mathematical programming // Managment Sience. 1965. Vol. 11, no. 7. P. 681–689. doi: 10.1287/mnsc.11.7.681
12. Adsul B., Babu C. S., Gang J., Mehta R., Sohoni M. A simplex-like algorithm for Fisher markets // Algorithmic Game Theory (SAGT 2010) / eds. S. Kontogiannis, E. Koutsoupias, P.G. Spirakis. Berlin; Heidelberg: Springer, 2010. P. 18–29. (Lecture Notes in Computer Science; vol 6386.) doi: 10.1007/978-3-642-16170-4_3
13. Garg J., Mehta R., Sohoni M., Vishnoi N. K. Towards polynomial simplex-like algorithms for market equilibria // Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: SIAM, 2013. P. 1226–1242. doi: 10.1137/1.9781611973105.89
14. Devanur N. R., Jain K., Mai T., Vazirani V. V., Yazdanbod S. New convex programs for Fisher’s market model and its generalizations [e-resource]. 2016. 23 p. URL: https://arxiv.org/pdf/1603.01257.pdf
15. Cole Richard, Devanur Nikhil, Gkatzelis Vasilis, Jain Kamal, Mai Tung, Vazirani Vijay V., Yazdanbod Sadra. Convex program duality, Fisher markets, and Nash social welfare // Proc. 18th ACM Conf. on Economics and Computation / Massachusets Institute of Technology. 2017. P. 459–460. doi: 10.1145/3033274.3085109
16. Shmyrev Vadim I. Polyhedral complementarity and fixed points problem of decreasing regular mappings on simplex // Proc. VIII Inter. Conf. on Optimization Methods and Applications (OPTIMA-2017) / eds. Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V. U. Malkova, M. A. Posypkin. Petrovac, 2017. Vol. 1987. P. 511–516.
17. Шмырев В. И. Введение в математическое программирование. Москва: Изд-во Ин-та компьютерных исследований, 2002. 192 с.
18. Понтрягин Л. С. Основы комбинаторной топологии. Москва: Наука. Гл. ред. физ. -мат. лит., 1986. 120 с.
19. Рокафеллар Р. Выпуклый анализ. Москва: Мир, 1973. 469 с.
20. Vazirani V. V. Spending constraint utilities, with applications to the adwords market // Math. Oper. Res. 2010. Vol. 35, no. 2.
Поступила 18.10.2019
После доработки 12.04.2020
Принята к публикации 27.07.2020
Шмырев Вадим Иванович
д-р физ.-мат. наук, вед. научный сотрудник
Институт математики им. С.Л. Соболева СО РАН;
Новосибирский государственный университет
г. Новосибирск
e-mail: shvi@math.nsc.ru
Ссылка на статью: В.И. Шмырев. Двойственность в линейных экономических моделях обмена // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 3. С. 258-274
English
V.I. Shmyrev. Duality in linear economic models of exchange
A further development of an original approach to the equilibrium problem in a linear exchange model and its variations is presented. The conceptual basis of the approach is polyhedral complementarity. The original problem is reduced to a fixed point problem for a piecewise constant point-to-set mapping on the price simplex. For the model with fixed budgets (Fisher model), the emerging mapping is potential, and this provides a new reduction of the equilibrium problem to a pair of optimization problems. The problems are in duality similarly to linear programming problems. This reduction of the Fisher model differs from the well-known reduction of E. Eisenberg and D. Gale and allows a development of two finite algorithms for searching equilibrium prices. In this paper we present a new conceptually complete version of the approach. We give an explicit formulation of the dual variant of the obtained reduction for the Fisher model and its generalizations. The reduction of the equilibrium problem to an optimization problem is also obtained for the general exchange model with variable budgets.
Keywords: exchange model, economic equilibrium, fixed point, polyhedral complementarity, optimization problem, conjugate function, algorithm
Received October 18, 2019
Revised April 12, 2020
Accepted July 27, 2020
Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no.~19-010-00910~А) and by the Programme for Fundamental Scientific Research of SB RAS No.~I.5.1 (project 0314-2019-0018)
Vadim Ivanovich Shmyrev, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: shvi@math.nsc.ru
Cite this article as: V.I. Shmyrev. Duality in linear economic models of exchange, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 258–274.
[References -> on the "English" button bottom right]
