KarRC RAS structure

Laboratory for Mathematical Cybernetics

Head: Dr. (DSc) of Phys. and Math., Professor Mazalov, Vladimir V.

Major research trends

  • Game-theoretic models and analysis of communication networks
  • Dynamic resource management problems investigation
  • Game-theoretic models and analysis of the best choice problems, negotiations and opinion dynamics
  • Stability analysis of high-performance systems and multiservice networks
  • Regenerative approach to stability analysis of queueing systems
  • Gaussian models of the communication and computational systems
  • Rare event simulation
  • Main activity results

    The members of Laboratory for Mathematical Cybernetics had obtained results in the following fields:



    Game-theoretic analysis of network structure

    Applications of game theory methods to network analysis are considered [1]. The betweenness centrality is one of the basic concepts in the analysis of the social networks. Initial definition for the betweenness of a node in the graph is based on the fraction of the number of geodesics (shortest paths) between any two nodes that given node lies on, to the total number of the shortest paths connecting these nodes. This method has polynomial complexity. We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory [4, 5]. The characteristic function is determined by special way for different coalitions (subsets of the graph). Two approaches are used to determine the characteristic function. In the first approach the characteristic function is determined via the number of direct and indirect weighted connecting paths in the coalition. In the second approach the coalition is considered as an electric network and the characteristic function is determined as a total current in this network. We use the Kirchhoff’s law. After that the betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks are presented.

    Game-theoretic methods for cluster formation in communicative networks are proposed. The network clustering problem is presented as a coalition game where a Nash-stable coalition partition is constructed. A new clustering method based on the potential games’ methods has been developed [5, 6]. Various types of potentials that lead to the stable coalition partition construction are proposed. It is shown that the presented potential method is equivalent to the maximum likelihood method if the network is modeled by a random graph [7].

    A cooperative game on a network where the nodes represent players and the characteristic function is defined as maximal covering by the pairs of connected nodes has been investigated. Owen value describing the significance of each node in the network is obtained. To construct the maximum covering of a graph and the Owen value a method of generating functions is proposed [8].

    Necessary and sufficient conditions for the core existence in the cooperative game with characteristic function defined as maximum graph covering with the pairs of connected coalitions are presented [9].

    Dynamic games in resource management problems

    The primary aim of rational resource exploitation consists in sustainable development of a renewable resource. A new method of ecological regulation is proposed, where the center determines the optimal share of the exploited territory to maintain the stable resource evolution in the long-term prospect [10]. Cooperation plays an important role in resource management problems as it leads to a sparing mode of exploitation. We presented two methodological schemes to maintain cooperation: incentive equilibrium [11] and time-consistent imputation distribution procedure [12]. Another meaningful applied problem is to determine cooperative behavior in asymmetric models, where players have different discount factors and planning horizons. We apply Nash bargaining schemas to construct cooperative strategies and payoffs in such models [13,14]. Dynamic game models with vector payoff functions are investigated. Noncooperative [15] and cooperative [16] behavior as well as the schemes to maintain cooperation [17] are formalized.

    Best-choice games

    Best-choice games describe selection processes in real life. They naturally arise in various situations as object searching problems, competitions and auctions. Methods for solving game-theoretic best-choice problems with different information about the actions of other participants and the observed objects available for the players are proposed. Equilibrium in the two-sided best-choice problem with complete information is obtained. It is proved that the optimal players' behavior in the problem with arriving flow coincides with the one in the one-sided choice problem [18]. A new competition model is proposed and the solution of a multi-stage best-choice game with incomplete information about the qualities of incoming objects is obtained [19,20]. Game-theoretic models with optimal stopping where the players have different information about the actions of other participants are investigated [21, 22].

    Developing of the stability analysis for the stochastic queues

    Developing of the theoretical foundations for the stability analysis of stochastic queuing systems based on the regenerative method. A wide class of queuing systems is considered, including classical systems, retrial systems, systems with feedback, with an optical buffer, systems in discrete time. The results are presented in the book “Stability Analysis of Regenerative Queueing Models” [23] (https://link.springer.com/book/10.1007/978-3-030-82438-9) written by E.V. Morozov (co-authored with a colleague from the University of Ghent). These authors had also published a chapter Une méthode d’analyse de stabilité des systèmes de files d’attente régénératifs [24] in the french book Théorie des files d’attente 2. The chapter is dedicated to the stability analysis of regenerative mass service systems. Such an analysis, is based on renewal theory methods. This approach allows to obtain simple proofs for stability conditions of the stochastic processes under consideration.

    The motivation of mixing distributions in communication/queueing systems modeling is that some input data (e.g., service time in queueing models) may follow several distinct distributions in a single input flow.In the paper [25, 26], we study the sensitivity of performance measure of a multiserver model of the network node, with Exponential-Pareto mixture distribution of service times.

    In the paper [27] we consider a multi-server queuing system under speed scaling policy, speed regimes are switched at arrival/departure instants according to the corresponding transition probability matrices. We present the regenerative structure of the model and rely on regenerative approach to construct confidence intervals for the steady-state system performance measures.

    In [28, 29] we consider a modified multiserver Erlang loss system with two-priority classes of customers: the first priority customers (class-1) are lost if find all servers busy, while the second priority customers (class-2) join an infinite capacity queue if find all servers busy.

    Queueing-inventory models have many practical applications and have been studied extensively in the literature. Most of the studies focus on models in which the demands occur singly. Only a very few papers analyze models wherein the demands occur in batches. In the paper [30] we consider batch demands in the context of two models, both of which assume that the demands occur according to a versatile Markovian point process.

    Stochastic analysis of retrial queuing models

    We consider a multiclass multiserver retrial queuing system with classical retrial discipline: the customers, meeting server busy, are blocked on the corresponding (virtual) orbit and then retry to occupy server independently. We exploit a regenerative structure of a basic process describing the dynamics of the system to establish stability conditions. In [31] we show that, provided the retrial times belong to the New-Better-Than-Used class, the convenient requirement that the mean load (traffic intensity) is less than the number of servers, is the stability criterion of the model. In the paper [32] we rely on regenerative approach and results from renewal theory to obtain the stability criterion of the system under consideration with general distribution of retrial times.

    In the paper [33], we consider a single-server retrial model with multiple classes of customers. Arrival of customers follow independent Poisson rule. A new customer, facing a busy server upon his arrival, may join the corresponding (class-dependent) orbit queue with a class-dependent probability, or leaves the system forever (balks). A restricted, two-way communication model with exponential service time distributions, is analyzed by matrix-analytic method. Moreover, we combine both methods to efficiently derive explicit solutions for the restricted model.

    In [34] we present a new coupling-based proof of the necessary stability conditions for the multi-class retrial system. The key ingredient of the proof is a coupling of the processes of retrials
    with the corresponding independent Poisson processes.

    In the papers [35—37], a large deviation analysis of the retrial systems is developed. We focus on the (overflow) probability that the orbit size in the single-server system reaches a high level N within a regeneration period. The research was based on the comparison with the corresponding results for the minorant and majorant classical buffered systems.

    Model for the expected project runtime estimation in a distributed computing system of the Desktop Grid type

    The problem of modeling the process of executing a final project (a project with a fnite number of subtasks) in a stationary computer network of the Desktop Grid type with a large number of participants has been studied. The Gaussian approximation of the desired process is based on the well-known limit theorems for the superposition of the so-called on-off sources (which are a variant of the telegraph process). The asymptotic properties of the distribution of the project execution time are investigated. The results are presented in [38–40].

    Variance reduction techniques for estimation some characteristics of the Gaussian systems and degradation processes

    The problems of estimating the characteristics of highly reliable systems described in terms of the so-called degradation process are considered. In particular, algorithms for estimating the failure probability were developed using the variance reduction methods. For the case when the stage durations of degradation are independent and have a distribution with a heavy tail, the Asmussen-Kroese approach was used. In the case when the durations of degradation stages have a light-tailed distribution, several variants of the importance sampling, differing in the choice of the proposal distribution: the cross entropy method and the Laplace approximation of the optimal distribution.
    Several problems of estimating the characteristics of Gaussian communication and computing systems were considered, in particular, estimating the busy period duration probabilities of Gaussian queuing systems and estimating the tail distribution of the hitting time of the Gaussian process with a linear drift. To estimate the desired characteristics, a special version of the conditional Monte Carlo method based on the properties of the Gaussian bridge was used. The results are presented in [41–43].

    References
    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).
    11. Mazalov V.V., Rettieva A.N. Incentive equilibrium in discrete-time bioresource sharing model. Doklady Mathematics, 2008. 78 (3).
    12. Mazalov V.V., Rettieva A.N. Fish wars and cooperation maintenance. Ecological Modelling, 2010. 221.
    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.
    14. Rettieva A.N. A bioresorce management problem with different planning horizons. Automation and Remote Control, 2015. 76 (5).
    15. Rettieva A.N. Equilibria in dynamic multicriteria games. International
    Game Theory Review, 2017. 19(1).
    16. Rettieva A.N. Cooperation in dynamic multicriteria games with random horizons. Journal of Global Optimization, 2020. 76.
    17. Rettieva A. Rational behavior in dynamic multicriteria games. Mathematics, 2020. 8.
    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 E. Morozov. 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.

    Events

  • March 5 - 7, 2024
    International workshop "Networking Games and Management"
  • July 5 - 6, 2016
    International workshop "Networking Games and Management"
  • September 12 - 16, 2010
    International conference "Stochastic Optimal Stopping"(SOS2010)
  • August 22 - 26, 2005
  • July 12 - 15, 2002
  • Staff

    PhD student, Leading Mathematician in the Geoinformation Centre
    Senior Researcher, Cand. (PhD) Phys. and Math.
    PhD student
    Senior Researcher, Cand. (PhD) Phys. and Math.
    Research Probationer
    Chief Researcher, Dr. (DSc) of Phys. and Math., Professor
    Senior Researcher, Cand. (PhD) Phys. and Math.
    Leading Researcher, Cand. (PhD) Phys. and Math., Dr. of Technics, Assistant Professor
    Leading Researcher, Deputy Director for Science of the Institute of Applied Mathematical Research, Dr. (DSc) of Phys. and Math., Assistant Professor
    PhD student
    Research Probationer, PhD student
    Junior Researcher, Cand. (PhD) Phys. and Math.

    Contact information

    Official title: Institute of Applied Mathematical Research of the Karelian Research Centre of the Russian Academy of Sciences
    Address: IAMR KarRC RAS
    11, Pushkinskaya str.
    Petrozavodsk
    Karelia
    185910, Russia
    Contact phone(s): +7 (8142) 77-11-08
    Fax: +7 (8142) 76-33-70
    E-mail: