Том 26, номер 1, 2019 г., Стр. 114-134

УДК 519.865.3
Шмырёв В. И.
Полиэдральная комплементарность на симплексе: отыскание неподвижных точек убывающих регулярных отображений

Аннотация:
Исследуется проблема отыскания неподвижной точки для специального класса кусочно-постоянных отображений симплекса в себя, возникающих в связи с отысканием равновесных цен в классической модели обмена и различных её вариациях. Основой рассмотрений является схема полиэдральной комплементарности, являющаяся естественным обобщением линейной комплементарности. В данной работе изучаются отображения, возникающие из рассмотрений моделей с фиксированными бюджетами. Отображения этого класса обладают особым свойством монотонности (логарифмическая монотонность), что позволяет доказать их потенциальность. Показано, что задача отыскания неподвижных точек таких отображений может быть сведена к оптимизационным задачам, для которых удаётся предложить конечные алгоритмы субоптимизации. Приводится описание двух алгоритмов.
Ил. 3, библиогр. 20.

Ключевые слова: полиэдральный комплекс, комплементарность, монотонность, потенциальность отображения, неподвижная точка, субоптимизация, алгоритм.

DOI: 10.33048/daio.2019.26.598

Шмырёв Вадим Иванович ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: shvi@math.nsc.ru

Статья поступила 19 октября 2017 г.
После доработки — 19 сентября 2018 г.
Принята к публикации 26 сентября 2018 г.

Литература

[1] Александров П. С. Общая теория гомологий. М.: Наука, 1979. 416 с.

[2] Понтрягин Л. С. Основы комбинаторной топологии. М.: Наука, 1986. 120 с.

[3] Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. 469 с.

[4] Шмырёв В. И. Об отыскании неподвижных точек кусочно-постоянных монотонных отображений в $R^n$ // Докл. АН СССР. 1981. Т. 259, № 2. С. 299–301.

[5] Шмырёв В. И. Об одном подходе к отысканию равновесия в простейших моделях обмена // Докл. АН СССР. 1983. Т. 268, № 5. С. 1062–1066.

[6] Шмырёв В. И. Алгоритм поиска равновесия в линейной модели обмена // Сиб. мат. журн. 1985. Т. 26, № 2. С. 162–175.

[7] Шмырёв В. И. Задача полиэдральной комплементарности // Оптимизация. Новосибирск: Ин-т математики СО АН СССР, 1988. Вып. 44. С. 82–95.

[8] Шмырёв В. И. Об одном алгоритме отыскания равновесия в линейной модели обмена с фиксированными бюджетами // Сиб. журн. индустр. математики. 2008. Т. 11, № 2. С. 139–154.

[9] Шмырёв В. И. Алгоритмы полиэдральной комплементарности для отыскания равновесия в линейных моделях конкурентной экономики // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 2. С. 84–101.

[10] Шмырёв В. И. Полиэдральная комплементарность на симплексе. Потенциальность регулярных отображений // Сиб. журн. индустр. математики. 2018. Т. 21, № 1. С. 118–128.

[11] Adsul B., Babu C. S., Gang J., Mehta R., Sohoni M. A simplex-like algorithm for Fisher markets // Algorithmic game theory (SAGT 2010). Berlin; Heidelberg: Springer, 2010. P. 18–29. (Lect. Notes Comput. Sci.; Vol. 6386).

[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). P. 127–136. New York: ACM, 2011.

[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). P. 459–460. New York: ACM, 2017.

[14] Devanur N. R., Jain K., Mai T., Vazirani V. V., Yazdanbod S. Newconvex 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. 2008. Vol. 55, No. 5. P. 22:1–22:18.

[16] Eisenberg E., Gale D. Consensus of subjective probabilities: The pari-mutuel method // Ann. Math. Stat. 1959. Vol. 30, No. 1. P. 165–168.

[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). P. 1226–1242. Philadelphia, PA: SIAM, 2013.

[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). Cham: Springer. P. 61–72. (Lect. Notes Comput. Sci.; Vol. 9869).

[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) P. 511–516. Aachen: RWTH Aachen Univ., 2017. (CEUR Workshop Proc.; Vol. 1987).

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