Методы построения характеристической функции в сетевой игре

Games are strictly defined mathematical objects. The game is formed by players, a set of strategies for each player and instructions of payoffs, or payments, players for each combination of strategies. Network games (games with a network structure) are a section of game theory, which studies both methods of forming relationships between players in conflict-controlled systems, and the rules for determining the payoffs of players taking into account these relationships. In this paper, we consider a cooperative version of the network game, in which the main problem is the choice of the rules of distribution of the total payoffs of the players among themselves at some predetermined or formed by the players network structure (as one of these rules of distribution, we can consider the Shapley value). In cooperative games with the ability to transfer funds from one player to another, is used the so-called characteristic function that determines the payoff of each coalition of players. Since in these games the construction of the characteristic function is necessary for different coalitions of players to be able to distribute the total payoffs of players, the importance of the possibility of rapid successful construction of the characteristic function can not be overestimated.
In this paper, we consider a cooperative two-stage network game in which the first stage players together form a network in which each player is associated with a certain set of other players, and in the second stage choose controls so that the total gain of all players was the maximum. Here we consider two options of constructing the characteristic function: in the first embodiment, the characteristic function is based on finding the maximum of the sum of the payoffs of the players only by selection controls of the players, and in the second embodiment, only by the selection of a suitable network of interaction between players. The paper discusses algorithms and approaches for both options that can be used to construct a characteristic function, as well as to reduce the time of it’s construction.

Problem statement
• Immersion in the theory of network games, the study of their features and properties, including also for a two-stage network game in which players can choose strategies on both stages together.
• Development and implementation of an algorithm by which it is possible to build a characteristic function in a two-stage network game in which players at both stages act together, only by selecting a suitable network .
• Development and implementation of algorithms that enable the development of an alternative more effective approach to the construction of a characteristic function in a two-stage network game compared to the method of searching all possible combinations of player’s controls. At the same time, the construction of the characteristic function is carried out in a two-stage network game in which players at both stages act together, only by choosing the appropriate controls of the players.

Literature review
To dive into the theory of network games are very useful articles [2], [5], [6] which studies the impact of links between players on decision-making about the choice of strategies. A detailed description of the process of modeling a two-stage network game made it possible to get a view of all stages of the game, their features for the case of non-cooperative two-stage network game, for the case of a two-stage game with the possibility of cooperation in the second stage, as well as a cooperative version of a two-stage network game. Articles [1], [7], [8] also proved to be useful because they supplemented articles [2], [5], [6] with various explanations and examples, enabling a deeper understanding of the area under consideration in this work. Paper [3] also provided an opportunity for a deeper study of the material. The article [4] also discusses the theory of cooperative network games, the influence of player’s links with each other.