Динамическая устойчивость принципов оптимальности в кооперативных многошаговых играх с остовным деревом

Approaches of dynamic game theory are increasingly used in solving various applied problems in the modeling and optimization of complex socioeconomic and ecological systems. A characteristic feature of such systems is the presence of several players, whose actions affect the system when the players make decisions in their interests. Stochastic games with uncertainty are also of great importance in modeling real conflict processes since they consider random factors.
In cost allocation game theory, a spanning tree game is closely related to the network structure defining the game. Networks play an important role in economics, so the study of spanning tree games associated with dynamic networks is crucial for solving economic problems, especially when allocating cost. The research presented in this thesis is the first to associate dynamic games with spanning tree games, taking into account changes in networks. The research aims to study cooperative solutions in dynamics and changes in the network structure in dynamics generating these solutions, consider methods for implementing cooperative solutions in dynamics, and analyze their properties.
A feature of the main model considered below is that all one-stage – player games are spanning tree games. Players build a network by their joint actions. The structure of the minimum cost tree, which links all players in this network, affects the network structure at the next stage of the game. In real life, this process can be illustrated with a simple example. Suppose that there are logistics companies, each with a different geographic location.
They plan to create a common transport and logistics network. Whatever joint actions the companies take, they must get a transport and logistics network connecting all geographic points (vertices). Obviously, this must be a connected graph. According to the results of graph theory, a connected graph containing all the vertices on a given graph and having the minimum number of edges is the minimum spanning tree on this graph. However, after some time, the companies need to rebuild the overall transport and logistics network again: there are various factors that can lead to changes in the original transport and logistics network structure. For example, some routes within the transport and logistics network may be used with high load and require repair or modernization (become unavailable). On the other hand, low additional load or repaired and modernized routes can reduce transport logistics cost. Therefore, when building a common transport and logistics network, all companies must agree on a cost allocation scheme, thinking rationally. In this difficult situation, some companies can no longer fully determine the result of the dynamic game. Therefore, it is crucial for all players to reach commonly acceptable solutions in advance.
After formalizing this complex conflict process based on game theory, an important condition for obtaining a commonly acceptable solution is the choice of an optimality criterion. Unfortunately, not surprisingly, there is no universal principle of optimality that would correspond to all conflict processes. Therefore, game theory has a rich family of optimality principles that satisfy various axiomatic systems. One of the most common optimality principles in the theory of noncooperative games is the Nash equilibrium, proposed in 1950 by John Nash [1, 2]. In cooperative games, Donald B. Gillies introduced in 1959 the concept of the core [3], and Reinhard Selten
5

introduced the concept of Nash equilibrium into dynamic analysis and proposed the concept of subgame perfect equilibrium [4]. In 1953, Shapley introduced the concept of the Shapley value using an axiomatization [5]. Subsequently, the Shapley value and the core became two important solutions in the class of cooperative games.
In this thesis, the network structure of a one-stage game changes randomly, and the probability of such a change depends on the joint actions of the players. Therefore, the game combines both the stochastic game model and the spanning tree game model. We present new results in the field of combining stochastic and spanning tree games.
In the work [6] L.A. Petrosyan pioneered a method for constructing cooperative stochastic games realized on finite trees. For this class of games, he formulated the problem of the time consistency of the Shapley value and solved the problem of regularizing the time-inconsistent Shapley value. Parilina and Petrosyan [7] applied this method for cooperative stochastic games of infinite duration. In the paper [8] Petrosyan presented the property of dynamic stability (time consistency) of cooperative solutions for differential games. Petrosyan and Danilov [9] proposed a method for determining payments to players when regularizing a time-inconsistent cooperative solution using the imputation distribution procedure.
Provided that all players adhere to the cooperation agreement, the Shapley value is called time-consistent if the Shapley value component of any player in the original game is equal to the sum of its Shapley value component in the subgame in which he begins to participate and the payoffs accumulated in all previous stages. The notion of time consistency was introduced by Petrosyan [6] for cooperative stochastic games. In several dynamic game-
6

theoretic models with one-stage spanning tree games presented in this thesis, various cooperative solutions are constructed according to the Imputation Distribution Procedure (IDP) first proposed by Petrosyan and Danilov [9]. These cooperative solutions are time-consistent under the given conditions, and the players follow the terms of the cooperative agreement throughout the game.
In the paper [10], Petrosyan and Sedakov proposed a class of solutions possessing the property of time consistency in network games (for example, the Shapley value [5]), in which the player’s strategy is defined like in Kuhn’s approach [11]. Bala and Goyal, Galeotti et al., Haller [12, 13, 14] studied other network formation methods, where the noncooperative solution is based on Nash equilibrium, and the cooperative solution can be found using the Bellman equation [15]. A particular player leaving the game with a given probability at various stages of the game loses the opportunity to obtain any payoff. This effect is called “shock.”
The shock effect was investigated by Li Yin [16] for a two-stage spanning tree game. In this model, a particular player leaves the game with a probability depending on the previous behavior of all players. Such a minimum spanning tree game changes the network structure, which is also random. The cited paper was devoted to the implementability of cooperative agreements, namely, their time consistency. This thesis assumes that the cooperative solution (the dynamic Shapley value) in a two-stage spanning tree game is time-inconsistent. This model describes various economic and social processes (logistics and transport networks, communication networks, etc.).