Методы построения характеристической функции в сетевой игре
В данной работе рассматривается задача построения характеристической функции в двухступенчатой сетевой игре с возможностью кооперации на обоих этапах только с помощью выбора подходящей сети игроков, а также рассматривается задача построения характеристической функции в данной игре только с помощью выбора подходящих управлений игроков. В статье описывается разработанный и реализованный алгоритм для первой вышеупомянутой задачи, а также описывается разработанная и реализованная серия алгоритмов для второй вышеупомянутой задачи, дающая возможность развитию альтернативному подходу построения характеристической функции только выбором подходящих управлений игроков в рассматриваемой мною сетевой игре.
Introduction 3
Problem statement 4
Literature review 5
Chapter 1 A two-stage network game 6
1.2 The first stage of the game 6
1.3 The second stage of the game 7
1.4 Two problems of maximization 8
Chapter 2 The problem of maximization with the selected controls 9
2.1 Algorithm trying all possible assignments of connections 9
2.2 The idea of the algorithm trying all possible assignments of connections 12
2.3 Results of implementation the algorithm which tries all possible assignments of connections 17
Chapter 3 The problem of maximizing when the network is selected 22
3.1 The method of maximizing the payoff functions of players with unspecified strategies 22
3.2 The applicability of the method of maximizing the payoff functions of players with unspecified strategies 28
3.3 The method of maximizing the payoff functions of players with preset strategies 28
3.4 Implementation of methods of maximizing the payoff functions of players with unspecified and specified strategies 32
3.5 A modification of the methods of maximizing the payoff functions of players with specified and unspecified strategies 34
3.6 Implementation of the modification of methods of maximizing the payoff functions of players with specified and unspecified strategies 36
Summary 38
Conclusion 40
List of references 41
Application 42
Chapter 2 brute force algorithm 42
Chapter 3 brute force algorithm 52
Chapter 3 method of maximizing the payoff functions of players with unspecified strategies 59
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.
Petrosyan L., Sedakov A. One-way flow two-stage network games. Вестник Санкт-Петербургского университета. Серия 10: Прикладная математика, информатика, процессы управления, 2014, № 4, c. 72–81
• Петросян Л.А., Седаков А.А., Бочкарев А.О. Двухступенчатые сетевые игры // Математическая теория игр и ее приложения, 2013. – T. 5. – № 4. – с. 84–104
• Petrosyan L., Sedakov A. The Subgame-Consistent Shapley Value for Dynamic Network Games with Shock // Dynamic Games and Applications, 2015.
• Petrosyan, L., Sedakov, A. The Subgame-Consistent Shapley Value for Dynamic Network Games with Shock // Dynamic Games and Applications, 2016. — Vol. 6, — №4. — p. 520-537
• Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В. Теория игр. СПб: БХВ-Петербург, 2012.
• Goyal S., Vega-Redondo F. Network formation and social coordination // Games and Economic Behavior. 2005. V. 50. P. 178-207.
• Jackson M., Watts A. On the formation of interaction networks in social coordination games // Games and Economic Behavior. 2002. Vol. 41, N 2. P. 265-291.
• Bala V., Goyal S. A., Noncooperative Model of Network Formation. Econometrica, 2000, vol. 68, no. 5. P. 1181-1229.
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
5 (21 отзыв)
4.3 (248 отзывов)
4.2 (6 отзывов)
5 (158 отзывов)
4.5 (330 отзывов)
4.5 (80 отзывов)
4.4 (59 отзывов)
5 (91 отзыв)
4.4 (93 отзыва)
