Связь двух подходов к модели Фишера

Связь двух подходов к модели Фишера

Шмырёв В. И.
Дискретный анализ и исследование операций, 30, 2, 91–108 (2023)
Скачать статью

УДК 519.865.3 
DOI: 10.33048/daio.2023.30.759

Аннотация:

Работа продолжает исследования автора по проблеме отыскания равновесия в экономических моделях обмена. Для модели Фишера ранее было известно предложенное Гейлом и Айзенбергом сведéние проблемы равновесия к некоторой оптимизационной задаче. Однако конечных алгоритмов на этом пути получено не было. Автором был предложен оригинальный подход полиэдральной комплементарности, сводящий проблему равновесия к оптимизационной задаче иного типа, что дало возможность разработать простые конечные алгоритмы отыскания равновесных цен. Полученные две оптимизационные задачи принципиально отличны, и не известно сведéния одной к другой. Однако сравнительно недавно с использованием специальной схемы двойственности была показана эквивалентность соответствующих двойственных задач. В данной работе излагается общая схема двойственности для выпуклых задач оптимизации, объясняющая природу двойственности, и на её основе установлена эквивалентность двух упомянутых оптимизационных задач для отыскания равновесия в модели Фишера. 
Ил. 1, библиогр. 17.

Литература:
  1. Gale D. The linear exchange model // J. Math. Econ. 1976. V. 3, No. 2. P. 205–209.
     
  2. Eaves B. C. A finite algorithm for linear exchange model // J. Math. Econ. 1976. V. 3, No. 2. P. 197–203.
     
  3.  Шмырёв В. И. Об одном подходе к отысканию равновесия в простейших моделях обмена // Докл. АН СССР. 1983. Т. 268, № 5. С. 1062–1066.
     
  4. Шмырёв В. И. Алгоритм поиска равновесия в линейной модели обмена // Сиб. мат. журн. 1985. Т. 26, № 2. С. 162–175.
     
  5. Шмырёв В. И. Обобщённая линейная модель обмена // Дискрет. анализ и исслед. операций. Сер. 2. 2006. Т. 13, № 2. С. 74–102.
     
  6. Шмырёв В. И. Об одном алгоритме отыскания равновесия в линейной модели обмена с фиксированными бюджетами // Сиб. журн. индустр. математики. 2008. Т. 11, № 2. С. 139–154.
     
  7. Eisenberg E., Gale D. Consensus of subjective probabilities: The pari-mutuel method // Ann. Math. Stat. 1959. V. 30, No. 1. P. 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 // J. ACM. 2008. V. 55, No. 5, ID 22. 18 p.
     
  9. Shmyrev V. I. An algorithmic approach for searching an equilibrium in fixed budget exchange models // Russian contributions to game theory and equilibrium theory. Heidelberg: Springer, 2006. P. 217–235. (Theory Decis. Libr., Ser. C; V. 39).
     
  10. Birnbaum B., Devanur N. R., Xiao L. Distributed algorithms via gradient descent for Fisher markets // Proc. 12th ACM Conf. Electronic Commerce (San Jose, CA, USA, June 5–9, 2011). New York: ACM, 2011. P. 127–136.
     
  11. Cole R., Devanur N., Gkatzelis V., Faira K. J., Mai T., Vazirani V. V., Yazdanbod S. Convex program duality, Fisher markets, and Nash social welfare // Proc. 2017 ACM Conf. Economics and Computation (Cambridge, MA, USA, June 26–30, 2017). New York: ACM, 2017. P. 459–460.
     
  12. Шмырёв В. И. Двойственность в линейных экономических моделях обмена // Тр. Ин-та математики и механики. 2020. Т. 26, № 3. С. 258–274.
     
  13. Svaiter B. F. A new duality theory for mathematical programming // J. Math. Program. Oper. Res. 2011. V. 60, No. 8–9. P. 1209–1231.
     
  14. Shmyrev V. I. Polyhedral complementarity approach to equilibrium problem in linear exchange models // Optimization algorithms — Examples. London: IntechOpen, 2018. P. 27–46.
     
  15. Деннис Дж. Б. Математическое программирование и электрические цепи. М.: Изд-во иностр. лит., 1961. 215 с.
     
  16. Шмырёв В. И. Введение в математическое программирование. М.: Ин-т компьют. исслед., 2002. 192 с.
     
  17.  Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. 469 с.

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF–2022–0019).

Шмырёв Вадим Иванович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
  2. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: shvi@math.nsc.ru

Статья поступила 15 декабря 2022 г. 
После доработки — 15 февраля 2023 г. 
Принята к публикации 16 февраля 2023 г.

Abstract:

The article continues the author’s research on the problem of finding equilibrium in economic exchange models. For the Fisher model, it was previously known that the equilibrium problem can be reduced to some optimization problem. This result was obtained by Gale and Eisenberg, while the final algorithms on this way were not found. The author proposed the original polyhedral complementarity approach, which generated an optimization problem of a different type. This approach made possible the development of finite algorithms for finding the equilibrium. So far, the equivalence of these two optimization problems has not been shown. However, it turned out that the dual problems obtained in a special way are equivalent. In this paper, avgeneral scheme of duality for convex optimization problems is proposed. This scheme allows us to clarify the nature of duality and the relationship between the Gale–Eisenberg and the polyhedral complementarity approaches. 
Illustr. 1, bibliogr. 17.

References:
  1. D. Gale, The linear exchange model, J. Math. Econ. 3 (2), 205–209 (1976).
     
  2. B. C. Eaves, A finite algorithm for linear exchange model, J. Math. Econ. 3 (2), 197–203 (1976).
     
  3. V. I. Shmyrev, On an approach to the determination of equilibrium in elementary exchange models, Dokl. Akad. Nauk SSSR 268 (5), 1062–1066 (1983) [Russian] [Sov. Math. Dokl. 27 (1), 230–233 (1983)].
     
  4. V. I. Shmyrev, An algorithm for the search of equilibrium in the linear exchange model, Sib. Mat. Zh. 26 (2), 162–175 (1985) [Russian] [Sib. Math. J. 26 (2), 288–300 (1985)].
     
  5. V. I. Shmyrev, A generalized linear exchange model, Diskretn. Anal. Issled. Oper., Ser. 2, 13 (2), 74–102 (2006) [Russian] [J. Appl. Ind. Math. 2 (1), 125–142 (2008)].
     
  6. V. I. Shmyrev, An algorithm for finding equilibrium in the linear exchange model with fixed budgets, Sib. Zh. Ind. Mat. 11 (2), 139–154 (2008) [Russian] [J. Appl. Ind. Math. 3 (4), 505–518 (2009)].
     
  7. E. Eisenberg and D. Gale, Consensus of subjective probabilities: The parimutuel method, Ann. Math. Stat. 30 (1), 165–168 (1959).
     
  8. 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 (5), ID 22, 18 p. (2008).
     
  9. V. I. Shmyrev, An algorithmic approach for searching an equilibrium in fixed budget exchange models, in Russian Contributions to Game Theory and Equilibrium Theory (Springer, Heidelberg, 2006), pp. 217–235 (Theory Decis. Libr., Ser. C, Vol. 39).
     
  10. 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 (ACM, New York, 2011), pp. 127–136. 
     
  11. R. Cole, N. Devanur, V. Gkatzelis, K. J. Faira, T. Mai, V. V. Vazirani, and S. Yazdanbod, Convex program duality, Fisher markets, and Nash social welfare, in Proc. 2017 ACM Conf. Economics and Computation, Cambridge, MA, USA, June 26–30, 2017 (ACM, New York, 2017), pp. 459–460.
     
  12. V. I. Shmyrev, Duality in linear economic models of exchange, Tr. Inst. Mat. Mekh. 26 (3), 258–274 (2020) [Russian].
     
  13. B. F. Svaiter, A new duality theory for mathematical programming, J. Math. Program. Oper. Res. 60 (8–9), 1209–1231 (2011).
     
  14. V. I. Shmyrev, Polyhedral complementarity approach to equilibrium problem in linear exchange models, in Optimization Algorithms — Examples (IntechOpen, London, 2018), pp. 27–46.
     
  15. J. B. Dennis, Mathematical Programming and Electrical Networks (MIT Press, Cambridge, MA, 1959; Izd. Inostr. Lit., Moscow, 1961 [Russian]).
     
  16. V. I. Shmyrev, Introduction to Mathematical Programming (Inst. Kompyut. Issled., Moscow, 2002) [Russian].
     
  17.  R. Rockafellar, Convex Analysis (Princeton Univ. Press, Princeton, 1970; Mir, Moscow, 1973 [Russian]).