Структура ИПМИ
Лаборатория математической кибернетики
руководитель: д.ф.-м.н., проф. Мазалов Владимир Викторович
Основные направления научных исследований
Научно-исследовательская работа
Основные результаты деятельности
Международное сотрудничество
Публикации
Мероприятия
Сотрудники
Контактная информация
Основные направления научных исследований
Основные результаты деятельности
Сотрудниками лаборатории математической кибернетики были получены результаты в следующих областях:- Теоретико-игровой анализ структуры коммуникационных сетей
- Динамические игры в задачах управления ресурсами
- Игры наилучшего выбора
- Развитие анализа устойчивости высокопроизводительных систем и мультисервисных сетей
- Стохастический анализ систем обслуживания с повторными вызовами
- Модель расчета ожидаемого времени выполнения проекта в системе распределенных вычислений типа Desktop Grid
- Методы понижения дисперсии оценок для различных характеристик гауссовских систем и процессов деградации
Теоретико-игровой анализ структуры коммуникационных сетей
Рассмотрены приложения теоретико-игровых методов к анализу коммуникационных сетей [1]. Мера центральности является одной из важных концепций при анализе социальных сетей. Определение меры центральности вершины графа основывается на отношении числа геодезических (кратчайших путей) между любыми двумя вершинами, которые проходят через данную вершину, к общему числу кратчайших путей, связывающих эти вершины. Данный метод имеет полиномиальную сложность. Был предложен новый подход для определения мер центральности для взвешенных графов, используя методы теории кооперативных игр [4, 5]. Специальным образом определена характеристическая функция для различных коалиций (подмножеств графа). Были использованы два подхода для определения характеристической функции. В первом подходе характеристическая функция определена через число ориентированных и неориентированных взвешенных простых путей в коалиции. Во втором подходе коалиция рассматривается как электрическая сеть и характеристическая функция определена как суммарный ток в этой сети. Следовательно, можно использовать закон Кирхгофа. В этом случае мера центральности определяется вектором Майерсона. Проведено численное моделирование для некоторых примеров сетей.
Предложены теоретико-игровые методы в задаче кластеризации коммуникационных сетей. Задача кластеризации сетей представлена как коалиционная игра, в которой ищется устойчивое по Нэшу коалиционное разбиение. Разработан новый метод кластеризации на основе методов потенциальных игр [5, 6]. Предложены разные типы потенциалов, которые приводят к построению устойчивого коалиционного разбиения. Показано, что данный потенциальный метод эквивалентен методу максимального правдоподобия, если сеть моделируется случайным графом [7].
Исследована кооперативная игра на сети, в которой узлы представляют игроков, а характеристическая функция определяется с помощью максимального покрытия сети парами связанных узлов. Находится решение кооперативной игры в виде значения Оуэна, которое описывает значимость каждого узла в сети. Предложен метод производящих функций для нахождения максимального покрытия графа и для вычисления значения Оуэна [8].
Получены необходимые и достаточные условия существования ядра в кооперативной игре с характеристической функцией, которая определяется с помощью максимального покрытия графа связанными коалициями [9].
Динамические игры в задачах управления ресурсами
Основная цель рационального использования ресурсов состоит в устойчивом развитии возобновляемых ресурсов. Разработан новый метод экологического регулирования, где центр определяет оптимальную долю эксплуатируемой территории для поддержания стабильного развития ресурса в долгосрочной перспективе [10]. Кооперация играет важную роль в задачах управления возобновляемыми ресурсами, поскольку ведет к щадящему режиму эксплуатации. Исследованы методологические схемы для поддержания кооперативного поведения: кооперативное регулируемое равновесие [11] и динамически устойчивая процедура распределения дележа [12]. Другой актуальной задачей является определение кооперативного поведения в асимметричных моделях, где игроки различаются коэффициентами дисконтирования и горизонтами планирования. Для построения кооперативных стратегий и выигрышей в таких моделях были применены арбитражные схемы [13, 14]. Исследованы динамические игры с векторными функциями выигрыша. Формализованы некооперативное [15] и кооперативное [16] равновесие, а также схемы поддержания кооперации [17].
Игры наилучшего выбора
Игры наилучшего выбора описывают реальные процессы выбора, они возникают в различных ситуациях поиска какого-либо объекта, конкурсах и аукционах. Предложены методы решения теоретико-игровых задач наилучшего выбора с различной степенью информированности игроков как о действиях других участников, так и о наблюдаемых объектах. Найдено равновесие в задаче двустороннего наилучшего выбора с полной информацией. Доказано, что в задаче с пополнением групп оптимальное поведение игроков совпадает с поведением игрока в задаче одностороннего выбора [18]. Предложена новая модель конкурса и найдено решение в многошаговой игре наилучшего выбора с неполной информацией о качествах поступающих объектов [19,20]. Рассмотрены теоретико-игровые модели с оптимальной остановкой, в которых игрокам доступна разная информация о действиях других участников игры [21,22].
Развитие анализа устойчивости высокопроизводительных систем и мультисервисных сетей
Развиты теоретические основы анализа стационарности стохастических систем обслуживания на основе регенеративного метода. Рассмотрен широкий класс систем обслуживания, включающий классические системы, системы с повторными вызовами, системы с обратной связью, с оптическим буфером, системы в дискретном времени. Результаты опубликованы в книге “Stability Analysis of Regenerative Queueing Models” (https://link.springer.com/book/10.1007/978-3-030-82438-9) [23], написанной главным научным сотрудником лаборатории математической кибернетики ИПМИ КарНЦ РАН Е.В.Морозовым (в соавторстве с коллегой из Университета Гента). Также данными авторами на французском языке опубликована глава Une méthode d’analyse de stabilité des systèmes de files d’attente régénératifs [24] книге Théorie des files d’attente 2, глава посвящена анализу устойчивости регенеративных систем массового обслуживания, основанному на методах теории восстановления. Такой подход позволяет получить простые доказательства условий устойчивости рассматриваемых случайных процессов.
Смешанные распределения возникают в коммуникационных моделях и моделях систем с очередями в случае, когда входящий поток заявок состоит из нескольких различных потоков. В работах [25, 26] исследованы чувствительность характеристик производительности системы, в которой распределение времени обслуживания представлено смесью экспоненциального распределения и распределения Парето.
Исследована многосерверная система обслуживания с асинхронной политикой управления скоростью обслуживания в моменты прихода/ухода клиентов в соответствии со стохастическими матрицами переключения скоростей. В работе [27] предложена регенеративная структура модели и построены доверительные интервалы для ключевых характеристик производительности системы в стационарном режиме.
В работах [28, 29] рассматривается модифицированная многосерверная эрланговская система с потерями и двумя приоритетами: клиенты первого приоритета теряются, если обнаруживают все сервера занятыми в момент прихода, в то время как клиенты второго приоритета ожидают в неограниченной очереди.
Модели обслуживания-запасания широко применяются в практике. В статье [30] исследованы две модели со множественными запросами, входной поток которых является Марковским точечным процессом.
Стохастический анализ систем обслуживания с повторными вызовами
Рассматривается многоклассовая многосерверная модель системы с повторными вызовами с классической дисциплиной: заявки, поступающие при занятых серверах поступают на соответствующую (виртуальную орбиту) и затем независимо друг от друга вновь пытаются получить обслуживания после случайного интервала времени с заданным распределением, зависящим от класса. При определении условий устойчивости мы опираемся на регенеративную структура базового процесса, описывающего динамику заявок в системе. В работе [31] показано, что в предположении, что распределение интервалов между повторными вызовами принадлежит к классу Новое-Лучше-Старого, условие коэффициент загрузки меньше числа серверов, является критерием стационарности рассматриваемой модели. В работе [32] получен критерий устойчивости модели с произвольным распределением интервалов между повторными вызовами, анализ основывается на регенеративном подходе и результатах из теории восстановления.
В статье [33] рассмотрена односерверная модель системы с повторными вызовами и пуассоновским входным потоком заявок разных классов. Клиент, наблюдающий занятый сервер в момент прихода, отправляется на (соответствующую его классу) орбиту с некоторой вероятностью, либо навсегда покидает систему. Выполнен более детальный анализ системы матрично-аналитическим методом, на начальном этапе которого использованы результаты анализа регенеративным методом.
В работе [34] представлено новое доказательство необходимого условия устойчивости многоклассовой модели с повторными вызовами, основанное на методе каплинга. Ключевой момент доказательства заключается в каплинге (склеивании) процессов повторных попыток с соответствующими независимыми Пуассоновскими процессами.
В статях [35—37] разработан анализ вероятности большого уклонения в системах с повторными вызовами. В качестве вероятности большого уклонения рассматривается вероятность того, что число заявок на орбите достигает достаточно большого значения на периоде регенерации. Для односерверной системы с повторными вызовами и постоянной интенсивностью орбитальных заявок получена оценка логарифмической асимптотики стационарной вероятности переполнения. Изучена логарифмическая асимптотика стационарной вероятности большого размера орбиты для широкого класса систем с повторными вызовами путем анализа минорантной и мажорантной систем с очередью.
Модель расчета ожидаемого времени выполнения проекта в системе распределенных вычислений типа Desktop Grid
Исследована задача моделирования процесса выполнения конечного проекта (проекта с конечным числом подзаданий) в стационарной вычислительной сети типа Desktop Grid с большим числом участников. Гауссовская аппроксимация искомого процесса производится на основе известных предельных теорем для суперпозиции так называемых on-off источников (являющихся вариантом телеграфного процесса). Исследованы асимптотические свойства распределения времени выполнения проекта. Результаты опубликованы в работах [38—40].
Методы понижения дисперсии оценок для различных характеристик гауссовских систем и процессов деградации
Рассмотрены задачи оценивания характеристик высоконадежных систем, которые описываются в терминах так называемого процесса деградации. В частности были разработаны алгоритмы оценивания вероятности отказа с привлечением методов понижения дисперсии оценок. Для случая, когда времена пребывания на стадиях деградации независимы и имеют распределение с тяжелым хвостом был подход Асмуссена-Крёзе. В случае, когда длительности стадий деградации имеют распределение с легким хвостом, для оценивания вероятности отказа предложены различные варианты метода существенной выборки (importance sampling), отличающиеся выбором вспомогательного распределения: метод перекрестной энтропии (cross entropy) и аппроксимация Лапласа оптимального распределения.
Были рассмотрены ряд задач оценивания характеристик гауссовских коммуникационных и вычислительных систем, в частности оценка вероятности занятости гауссовских систем обслуживания и оценка хвоста распределения времени достижения гауссовским процессом с линейным сносом некоторого уровня (hitting time). Для оценки искомых характеристик был использован специальный вариант условного метода Монте-Карло, основанный на свойствах гауссовского моста. Результаты опубликованы в работах [41—43].
Литература
1. Mazalov V., Chirkova J. Networking Games. Network Forming Games and Games on Networks. Academic Press. 2019. 322 p.. DOI: https://doi.org/10.1016/C2017-0-04296-9.
2. Мазалов В.В. Математическая теория игр и приложения (четвертое издание, исправленное
и дополненное). Санкт-Петербург-Москва-Краснодар, Лань. 2021. 500 с.
3. Мазалов В.В., Менчер А.Э., Токарева Ю.С. Переговоры. Математическая теория. Санкт-Петербург-Москва-Краснодар, Лань. 2012. 304 с.
4. Mazalov, V., Trukhina, L. Generating functions and the Myerson vector in communication networks. Disc. Math. Appl., 2014. 24(5).
5. Avrachenkov, K., Kondratev A., Mazalov, V., Rubanov, D. Network partitioning algorithm as cooperative games. Comput. Soc. Net., 2018. 5(11).
6. Gusev V.V., Mazalov V.V. Potential functions for finding stable coalition structures. Operations Research Letters 47. 2019. P. 478–482.
7. Мазалов В.В., Никитина Н.Н. Метод максимального правдоподобия для выделения сообществ в коммуникационных сетях. Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. Т. 14, вып. 3. 2018. C. 200-214.
8. Mazalov V.V., Gusev V.V. Generating functions and Owen value in cooperative network cover game. Performance Evaluation 144, 102135. 2020.
9. Dotsenko S., Mazalov V. A Cooperative Network Packing Game with Simple Paths. Mathematics, 9(14), 1683. 2021.
10. Mazalov V.V., Rettieva A.N. Nash equilibrium in ecological problems. Mathematical Modelling, 2006. 18(5). 73-90
11. Mazalov V.V., Rettieva A.N. Incentive equilibrium in discrete-time bioresource sharing model. Doklady Mathematics, 2008. 78 (3). 953-955
12. Mazalov V.V., Rettieva A.N. Fish wars and cooperation maintenance. Ecological Modelling, 2010. 221. 1545-1553
13. Mazalov V.V., Rettieva A.N. Asymmetry in a cooperative bioresource management problem. Game-Theoretic Models in Mathematical Ecology. NY: Nova Science Publishers. 2015. 113-152
14. Rettieva A.N. A bioresorce management problem with different planning horizons. Automation and Remote Control, 2015. 76 (5). 919-934.
15. Rettieva A.N. Equilibria in dynamic multicriteria games. International
Game Theory Review, 2017. 19(1). 1750002
16. Rettieva A.N. Cooperation in dynamic multicriteria games with random horizons. Journal of Global Optimization, 2020. 76. 455-470
17. Rettieva A. Rational behavior in dynamic multicriteria games. Mathematics, 2020. 12(1). 19-32
18. Mazalov V.V., Falko A.A. Nash equilibrium in two-sided mate choice problem. International Game Theory Review. Vol. 10, N 4. 2008. P. 421-435.
19. E.N. Konovalchikova, V.V. Mazalov. A Game-Theoretic Model of TV Show "The Voice". Automation and Remote Control, Volume 77, Issue 8. 2016. P. 1468-1479. DOI: 10.1134/S0005117916080130.
20. V.V. Mazalov, A. A. Ivashko, E.N. Konovalchikova. Optimal Strategies in Best-Choice Game with Incomplete Information — The Voice Show. International Game Theory Review, 18, no. 2. 2016. DOI: 10.1142/S0219198916400016.
21. Mazalov V.V., Falko A.A. Equilibrium in n-person game of Showcase-Showdown. Probability in the Engineering and Informational Sciences, Cambridge Univ. Press, 24. 2010. P. 397-403.
22. Seregina T.V., Ivashko A.A., Mazalov V.V. Optimal Stopping Strategies in the Game "The Price Is Right". Proceedings of the Steklov Institute of Mathematics, Vol. 307, Suppl. 1. 2019. P. 127–141. DOI: 10.1134/S0081543819070101.
23. Morozov, Evsey, Bart Steyaert. Stability Analysis of Regenerative Queueing Models
Mathematical Methods and Applications. Springer, Cham, 2021.
https://link.springer.com/book/10.1007/978-3-030-82438-9.
24. Morozov, E., Steyaert, B. Une méthode d’analyse de stabilité des systèmes de files d’attente régénératifs. In Théorie des files d’attente 2; Encyclopédie SCIENCES; ISTE Editions Ltd: London, UK, UK, 2021; pp 264–295.
25. Peshkova I., Morozov E., Maltseva M.: On Comparison of Multiserver Systems with Exponential-Pareto Mixture Distribution // Gaj, P., Guminski, W., Kwiecien, A. (eds.) Computer Networks. CN 2020. Communications in Computer and Information Science, vol 1231. Springer, Cham. - [Switzerland], 2020. - P.141-152. https://doi.org/10.1007/978-3- 030-50719-0_11.
26. Morozov, E., Peshkova, I., Pagano, M., Rumyantsev, A. Sensitivity Analysis and Simulation of a Multiserver Queueing System with Mixed Service Time Distribution. Mathematics 2020, 8 (8), 1277. https://doi.org/10.3390/math8081277.
27. Nekrasova, R. Regeneration Analysis of Non-Markovian System with Simultaneous Service and Speed Scaling. In Distributed Computer and Communication Networks: Control, Computation, Communications; Vishnevskiy, V. M., Samouylov, K. E., Kozyrev, D. V., Eds.; Springer International Publishing: Cham, 2020; Vol. 1337, p pp 299-310.
28. Rogozin S., Simulation a modified Erlang loss system with multi-type servers and multi-type customers // Proceedings of The Second International Workshop on Stochastic Modeling and Applied Research of Technology (SMARTY-2020), 2020.
29. Rogozin S.S., Morozov E.V. Stability condition of a modified erlang loss system with different service rates. В сборнике: Information technologies and mathematical modelling (IТММ2020). Материалы XIX Международной конференции имени А.Ф. Терпугова. Томск, 2021. С. 126-130.
30. Maltseva M., Morozov E.: Asymptotic Analysis of the N-Model with Static Priority // Proceedings of the 26th Conference of Open Innovations Association FRUCT. ISSN 2305- 7254, ISBN 978-952-69244-2-7, e-ISSN 2343-0737. - [Finland], 2020. - P.566-571. https://www.fruct.org/publications/acm26/files/Mal.pdf.
31. Morozov, E., Nekrasova, R., Stability Conditions of a Multiclass System with NBU Retrials// Queueing Theory and Network Applications. QTNA 2019. Lecture Notes in Computer Science / V. 11688. - Springer. - 2019. - P. 51-64.
32. Nekrasova, R. Stability Analysis of a Multi-class Retrial Queue with General Retrials and Classical Retrial Policy // 28th Conference of Open Innovations Association (FRUCT). –IEEE. - 2021. - P. 328–333. https://doi.org/10.23919/FRUCT50888.2021.9347627.
33. Morozov, E., Rumyantsev, A., Sweta Dey, Deepak, T.G.,Performance analysis and stability of multiclass orbit queue with constant retrial rates and balking // Performance Evaluation. - 2019. P. 102005.
34. Morozov, E., Morozova., T., A Coupling-Based Analysis of a Multiclass Retrial System with State-Dependent Retrial Rates// Queueing Theory and Network Applications. QTNA 2019. Lecture Notes in Computer Science / V. 11688. - Springer. - 2019. - P. 34-50.
35. Morozov, E., Zhukova, K. A large deviation analysis of retrial models with constant and classic retrial rates. Performance Evaluation, 135. - 2019.
36. Morozov, E.; Zhukova, K. The Overflow Probability Asymptotics in a Multiclass Single-Server Retrial System. In Distributed Computer and Communication Networks: Control, Computation, Communications; Vishnevskiy, V. M., Samouylov, K. E., Kozyrev, D. V., Eds.; Communications in Computer and Information Science; Springer International Publishing: Cham, 2020; Vol. 1337, pp 394–406. https://doi.org/10.1007/978-3-030-66242-4_31.
37. Morozov E., Zhukova K. (2021) The Overflow Probability Asymptotics in a Single-Class Retrial System with General Retrieve Time. In: Vishnevskiy V. M., Samouylov K. E., Kozyrev D.V. (eds) Distributed Computer and Communication Networks: Control, Computation, Communications. DCCN 2021. Lecture Notes in Computer Science, vol 13144. Springer, Cham, pp.55–66.
38. Khokhlov, Y. S., Lukashenko, O. V., Morozov, E. V., On a lower asymptotic bound of the overflow probability in a fluid queue with a heterogeneous fractional input // Journal of Mathematical Sciences. - 2019. - Vol. 237, No 5. - P. 667-672.
39. Lukashenko, O. V., Morozov, E. V., Pagano, M., A Gaussian approximation of the distributed computing process // Informatika i ee Primeneniya. - 2019. - Vol.13, No 2. - P.109-116.
40. Lukashenko, O., Pagano, M. Rare-Event Simulation for the Hitting Time of Gaussian Processes. In Distributed Computer and Communication Networks; Vishnevskiy, V. M., Samouylov, K. E., Kozyrev, D. V., Eds.; Springer International Publishing: Cham, 2020; Vol. 12563, pp 589–603. https://doi.org/10.1007/978-3-030-66471-8_45.
41. Borodina A., Lukashenko O., Morozov E. On Conditional Monte Carlo for the Failure Probability Estimation // Proceedings of 2018 10th International Congress on Ultra Modern Telecommunications and Control Systems (ICUMT 2018), 5-8 November 2018. IEEE, 2018. P. 202–207
42. Borodina A., Lukashenko O. and Morozov E. A rare-event estimation of heterogeneous degradation process. 2019 11th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2019, pp. 1-6
43. Lukashenko, O., Borodina, A. Importance Sampling for the Estimation of the Failure Probability of the Degradation Process. In Proceedings of the Second International Workshop on Stochastic Modeling and Applied Research of Technology (SMARTY 2020); 2020; Vol. 2792, pp 191–202.
Международное сотрудничество
Мероприятия
5 - 7 марта 2024
Международный семинар "Networking Games and Management"
5 - 6 июля 2016
Международный семинар "Networking Games and Management"
12 - 16 сентября 2010
Международная конференция "Stochastic Optimal Stopping"(SOS2010)
22 - 26 августа 2005
Семинар "Optimal stopping and stochastic control"
12 - 15 июля 2002
Семинар "Networking games & resource allocation"
Сотрудники
младший научный сотрудник, аспирант лаб. СМИТС
аспирант, ведущий математик геоинформационного центра
старший научный сотрудник, к.ф.-м.н.
аспирант
младший научный сотрудник, к.ф.-м.н.
старший научный сотрудник, к.ф.-м.н.
стажер-исследователь
главный научный сотрудник, д.ф.-м.н., проф.
старший научный сотрудник, к.ф.-м.н.
ведущий научный сотрудник, к.ф.-м.н., д.т.н., доц.
ведущий научный сотрудник, заместитель директора по научной работе ИПМИ, д.ф.-м.н., доц.
аспирант
стажер-исследователь, аспирант
Контактная информация
Официальное название: Институт прикладных математических исследований — обособленное подразделение Федерального государственного бюджетного учреждения науки Федерального исследовательского центра "Карельский научный центр Российской академии наук"Адрес: 185910, Россия,
Республика Карелия,
г. Петрозаводск,
ул. Пушкинская, 11
ИПМИ КарНЦ РАН
Контактный телефон(ы): +7 (8142) 77-11-08
Факс: +7 (8142) 76-33-70
Электронная почта: vmazalov@krc.karelia.ru