Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. в-S-P-ядро в играх в развернутой форме с выигрышами в каждой позиции 9
1.1. Игра в развернутой форме с совершенной
информацией 9
1.2. S-P-ядро в игре в развернутой форме с
терминальными выигрышами 11
1.3. Процедура распределения дележа и в-S-P-ядро 14
1.4. Стратегическая поддержка в-S-P-ядра 18
1.5. Сужение в-S-P-ядра 21
1.6. в-S-P-ядро в модели «рыбных войн» в
развернутой форме 24
Глава 2. в-S-P-ядро в многошаговой модели добычи возобновляемых ресурсов 28
2.1. Описание модели. Анализ некооперативного поведения 29
2.2. Кооперативное поведение. в-S-P-ядро 33
2.3. Алгоритм сужения в-S-P-ядра 37
2.4. Численный пример 39
Заключение 43
Список литературы
Основной целью работы является исследование свойств новой схемы кооперативного поведения в многошаговых играх с трансферабельными выигрышами, основанной на введенной в 2020 г. в работе [10] концепции Subgame-Perfect Core. Мы предлагаем обобщение данного решения для класса многошаговых игр в развернутой форме с полной информацией и выигрышами, заданными в каждой позиции игры, а также для одной многошаговой игры с дискретной динамикой, заданной разностным уравнением.
Проблеме обеспечения устойчивого долгосрочного сотрудничества (кооперации) в динамических играх nлиц посвящены сотни работ различных исследователей (см., например, [14, 46, 48]). В качестве инструментов стабилизации кооперативного соглашения используется подход, предложенный Л.А. Петросяном в статье [45]. Он заключается в том, чтобы построить такое распределение кооперативного выигрыша каждого игрока вдоль кооперативной траектории развития динамической игры, чтобы полученное распределение (процедура распределения дележа - ПРД, payoff distribution procedure, payment schedule) удовлетворяло ряду привлекательных свойств, например: поддерживало стимул к кооперации на протяжении всего времени игры, было динамически устойчивым (состоятельным во времени [43]), сильно динамически устойчивым [28, 44, 46, 48], устойчивым против
иррационального поведения игроков [58] и т.д. Развитию данного подхода применительно к различным классам динамических игр посвящены, в частности, работы [12, 18, 21, 22, 25, 26, 28, 33, 41, 42, 44, 49, 50, 52, 55, 57, 60].
В статье [10] была представлена новая концепция решения для игр в развернутой форме с терминальными выигрышами (заданными только в окончательных позициях дерева игры) - так называемое S-P-ядро. Любой вектор из S-P-ядра является таким распределением суммарного кооперативного выигрыша (исключительно в окончательной позиции кооперативной партии), что никакая коалиция не может совершить выгодное для себя отклонение ни в какой подыгре с начальной позицией на кооперативной партии (при условии, что в случае отклонения коалиции Sв подыгре между S и остальными игроками, действующими индивидуально, разыгрывается абсолютное равновесие по Нэшу - subgame-perfect equilibria [56]).
В работе [29] было предложено распространить естественным образом данную концепцию ядра на класс игр в развернутой форме, в котором выигрыши игроков заданы в каждой позиции игры, за счет применения специальной ПРД (процедуры распределения дележа) в - то есть подходящего правила распределения текущих выигрышей в каждой позиции вдоль кооперативной партии [14, 18, 45, 46, 59]. Были изучены свойства предложенного обобщения S-P-ядра, названного в-S-P-ядро.
Постановка задачи
Основными задачами данной работы являются:
1. Изучить предложенную в работе [10] для игр в развернутой форме с терминальными выигрышами концепцию S-P-ядра;
2. Обобщить концепцию S-P-ядра на класс игр в развернутой форме с выигрышами, определенными в каждой позиции игры (с использованием подходящей процедуры распределения дележа);
3. На нескольких примерах сравнить S-P-ядро и в-S-P-ядро;
4. Определить наличие/отсутствие взаимосвязи между сильным равновесием по Нэшу (SNE) и в-S-P-ядром;
5. Предложить методы сужения в-S-P-ядра, если оно представляет собой множество процедур распределения дележа;
6. Продемонстрировать свойства и реализацию e-S-P-ядра в многошаговой игре с дискретной динамикой, моделирующей добычу возобновляемых ресурсов (с симметричными и асимметричными игроками).
В диссертационной работе новая концепция S-P-ядра с применением процедуры распределения дележей распространена на более общий класс игр в развернутой форме (с выигрышами, заданными в каждой позиции игры). Показано, что полученное решение - в-S-P-ядро - является более мощным инструментом стабилизации долгосрочного кооперативного соглашения, чем S-P-ядро. Установлена взаимосвязь между сильным равновесием и e-S-P-ядром для класса игр в развернутой форме с совершенной информацией и выигрышами, определенными в каждой позиции. Предложено несколько методов сужения в-S-P-ядра (некоторые из них требуют решения вспомогательных задач оптимизации, другие подразумевают, что конкретная ПРД должна удовлетворять дополнительным свойствам).
Дополнительно продемонстрирована возможность применения концепции e-S-P-ядра для анализа многошаговой модели добычи возобновляемых ресурсов. А именно: рассмотрен случай симметричных и асимметричных игроков, методом динамического программирования построено абсолютное равновесие и кооперативное решение, установлена непустота в-S-P-ядра в игре двух лиц, предложен алгоритм выбора единственной ПРД из ядра, полученные результаты проиллюстрированы численным примером.
[1] Aumann R. Acceptable points in general cooperative n-person games. // Contributions to the Theory of Games, Vol. IV. Princeton University Press, Princeton, 1959, 287-324.
[2] Breton M., Dahmouni I., Zaccour G. Equilibria in a two-species fishery. // Mathematical Biosciences, 2019, Vol. 309, 78-91.
[3] Breton M.; Keoula M.Y. Farsightedness in a Coalitional Great Fish War. // Environmental and Resource Economics, 2012, Vol. 51, 297-315.
[4] Breton M., Keoula M. A great fish war model with asymmetric players. // Ecological Economics, 2014, Vol. 97, 209-223.
[5] Cabo F.; Tidball M. Cooperation in a Dynamic Setting with Asymmetric Environmental Valuation and Responsibility. // Dynamic Games and Applications, 2021.
[6] Castaner A.; Marin-Solano J.; Ribas C. A time consistent dynamic bargaining procedure in differential games with heterogeneous discounting. // Mathematical Methods of Operations Research, 2021, Vol. 93, 555-584.
[7] Chander P. The gamma-core and coalition formation. // International Journal of Game Theory, 2007, Vol. 35, 539-556.
[8] Chander P. Subgame-perfect cooperative agreements in a dynamic game of climate change. // Journal of Environmental Economics and Management, 2017, Vol. 84, 173-188.
[9] Chander P.; Tulkens H. The core of an economy with multilateral environmental externalities. // International Journal of Game Theory, 1997, Vol. 26, 379-401.
[10] Chander P.; Wooders M. Subgame-perfect cooperation in an extensive game. // Journal of Economic Theory, 2020, Vol. 187, 105017.
[11] Chebotareva A.; Su S.; Tretyakova S.; Gromova E. On the Value of the Preexisting Knowledge in an Optimal Control of Pollution Emissions. // Contributions to Game Theory and Management, Vol. 14. St. Petersburg State University Press, St. Petersburg, 2021, 49-58.
[12] Gromova E.V.; Plekhanova T.M. On the regularization of a cooperative solution in a multistage game with random time horizon. // Discrete Applied Mathematics, 2019, Vol. 255, 40-55.
[13] Crettez B.; Hayek N.; Zaccour G. Do charities spend more on their social programs when they cooperate than when they compete? // European Journal of Operational Research, 2020, Vol. 283, 1055-1063.
[14] Haurie A.; Krawczyk J.B.; Zaccour G. Games and Dynamic Games. // Scientific World: Singapore, 2012.
[15] Hillas J.; Kvasov D. Backward induction in games without perfect recall. // Games and Economic Behavior, 2020, Vol. 124, 207-218.
[16] Kaitala V. T.; Lindroos M. Game Theoretic Applications to Fisheries. // Handbook Of Operations Research In Natural Resources. International Series In Operations Research & Mana, 2007, Vol. 99, 201-215.
[17] Kuhn H. Extensive games and the problem of information. // Contribution to the Theory of Games, 1953, Vol. II, Annals of Mathematics Studies, 28, 193--216, Princeton.
[18] Kuzyutin D.; Gromova E.; Pankratova Ya. Sustainable cooperation in multicriteria multistage games. // Operations Research Letters, 2018, Vol. 46, 557-562.
[19] Kuzyutin D.; Gromova E.; Smirnova N. On the cooperative behavior in multistage multicriteria game with chance moves. // Mathematical Optimization Theory and Operations Research (MOTOR 2020), International Conference Proceedings, LNCS Series, 2020, Vol. 12095, 184-199.
[20] Kuzyutin D.; Lipko I.; Pankratova Y.; Tantlevskij I. (2020). Cooperation Enforcing in Multistage Multicriteria Game: New Algorithm and Its Implementation. // Frontiers of Dynamic Games, Static & Dynamic Game Theory: Foundations & Applications, 2020, 141-159.
[21] Kuzyutin D.; Nikitina M. Time consistent cooperative solutions for multistage games with vector payoffs. // Operations Research Letters, 2017, Vol. 45, 269-274.
[22] Kuzyutin D.; Nikitina M. An irrational behavior proof condition for multistage multicriteria games. // Consrtuctive Nonsmooth Analysis and Related Topics (Dedicated to the Memory of V.F. Demyanov); CNSA 2017; IEEE: New York, NY, USA, 2017, 178-181.
[23] Kuzyutin D.; Pankratova Y.; Svetlov R. A-Subgame Concept and the Solutions Properties for Multistage Games with Vector Payoffs. // Frontiers of Dynamic Games, Static & Dynamic Game Theory: Foundations & Applications, 2019, 85-102.
[24] Kuzyutin D.; Romanenko I. On properties of equilibrium solutions for n- person games in extensive form. Vestnik St. Petersburg Univ. Math., 1998, Vol. 3(15), 17-27.
[25] Kuzyutin D.; Smirnova N. Subgame consistent cooperative behavior in an extensive form game with chance moves. // Mathematics, 2020, Vol. 8, 1061.
[26] Kuzyutin D.; Smirnova N.; Tantlevskij I. Subgame perfect Pareto equilibria for multicriteria game with chance moves. // Submitted to “IV Stability and Control Processes (SCP 2020)” Conference Proceedings, LNCIS series, Springer (2020)
[27] Kuzyutin D., Smirnova N. Subgame-perfect core based on the payoff distribution procedure. // Submitted to Economics Letters, 2021.
[28] Kuzyutin D.; Smirnova N.; Gromova E. Long-term implementation of the cooperative solution in multistage multicriteria game. // Operations Research Perspectives, 2019, Vol. 6, 100107.
[29] Kuzyutin D., Skorodumova Y., Smirnova N. Implementation of subgame-perfect cooperative agreement in an extensive-form game. // Contributions to Game Theory and Management, St. Petersburg State Univ., 2021, Vol. 14, 257-272.
[30] Kuzyutin D., Skorodumova Y., Smirnova N. A cooperation scheme in multistage game of renewable resource extraction with asymmetric players. // Mathematical Optimization Theory and Operations Research (MOTOR 2022), International Conference Proceedings, LNCS Series (to appear).
[31] Levhari D.; Mirman L.J. The Great Fish War: An Example Using a Dynamic Cournot-Nash solution. // The Bell Journal of Economics, 1980, Vol. 11 (1), 322-334.
[32] Masoudi N.; Zaccour G. Adapting to climate change: Is cooperation good for the environment? // Economics Letters, 2017, Vol. 153, 1-5.
[33] Mazalov V.V.; Rettiyeva A.N. The discrete-time bioresource sharing model. // Journal of Applied Mathematics and Mechanics, 2011, Vol. 75, 180-188.
[34] Mazalov, V.V.; Rettieva, A.N. Cooperation maintenance in fishery problems. // Fishery Management. Nova Science Publishers, 2012, 151-198.
[35] Mazalov, V.V.; Rettieva, A.N. Asymmetry in a cooperative bioresource management problem. // Game-Theoretic Models in Mathematical Ecology, Nova Science Publishers, 2015, 113-152.
[36] Mazalov V., Parilina E.; Zhou J. Altruistic-Like Equilibrium in a Differential Game of Renewable Resource Extraction. // Mathematical Optimization Theory and Operations Research, 2021, Lecture Notes in Computer Science, Vol. 12755, 326-339.
[37] Myerson R. Game Theory. Analysis of Conflict // Harvard University Press: Cambridge, MA, USA, 1997.
[38] Moulin H. Axioms of cooperative decision making. // Cambridge University Press: Cambridge, MA, USA, 1988.
[39] Nash J.F. Equilibrium points in n-person games. // Proceedings of the National Academy of Sciences of the United States of America, 1950, Vol. 36, 48-49.
[40] Ougolnitsky G.; Usov A. Spatially distributed differential game theoretic model of fisheries. // Mathematics, 2019, Vol. 7, 732.
[41] Parilina E.; Zaccour G. Node-consistent core for games played over event trees. // Automatica, 2015, Vol. 55, 304-311.
[42] Parilina E.; Zaccour G. Node-consistent Shapley value for games played over event trees with random terminal time. // Journal of Optimization Theory and Applications, 2017, Vol. 175, 236-254.
[43] Petrosyan L. Time-consistency of solutions in multi-player differential games. // Astronomy, 1977, Vol. 4, 46-52.
[44] Petrosyan L.A.; Danilov N.N. Cooperative Differential Games and Their Applications. // Publishing House of Tomsk University: Tomsk, Russia, 1985.
[45] Petrosyan L.A.; Danilov N.N. Stability of solutions in non-zero sum differential games with transferable payoffs. // Astronomy, 1979, Vol. 1, 52-59.
[46] Petrosyan L.; Kuzyutin D. Games in Extensive Form: Optimality and Stability. // Saint Petersburg University Press: St. Petersburg, Russia, 2000.
[47] Petrosyan L.A.; Kuzyutin D.V. On the stability of E-equilibrium in the class of mixed strategies. // Vestnik St.Petersburg Univ. Math., 1995, 3, 54-58.
[48] Petrosyan L.; Zenkevich N. Game Theory. // World Scientific Publisher: Singapure, London, 1996.
[49] Petrosyan L.; Zaccour G. Time-consistent Shapley value allocation of pollution cost reduction. // Journal of Economic Dynamics and Control, 2003, Vol. 27, 381-398.
[50] Petrosyan O.; Zakharov V. IDP-Core: Novel Cooperative Solution for Differential Games. // Mathematics, 2020, Vol. 8, 721.
[51] Pintassilgo P.; Finus M.; Lindroos M.; Munro G.R. Stability and Success of Regional Fisheries Management Organizations // Environmental and Resource Economics, 2010, Vol. 46, 377-402.
[52] Reddy P.; Shevkoplyas E.; Zaccour G. Time-consistent Shapley value for games played over event trees. // Automatica, 2013, Vol. 49, 1521-1527.
[53] Rettieva A. N. A discrete-time bioresource management problem with asymmetric players. // Automation and Remote Control, 2014, Vol. 75, 1665-1676.
[54] Rettieva A. Cooperation in bioresource management problems. // Contributions to Game Theory and Management, 2017, Vol. 10, 245-286.
[55] Sedakov A. On the Strong Time Consistency of the Core. // Automation and Remote Control, 2018, Vol. 79, 757-767.
[56] Selten R. Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games. // International Journal of Game Theory, 1975, Vol. 4, 25-55.
[57] Yeung D.; Petrosyan, L. Subgame consistent solutions for cooperative stochastic dynamic games. // Journal of Optimization Theory and Applications, 2010, Vol. 145, 579-596.
[58] Yeung D. An irrational-behavior-proof condition in cooperative differential games. // International Game Theory Review, 2006, Vol. 8 (4), 739-744.
[59] Yeung D.; Petrosyan L. Subgame Consistent Economic Optimization: An Advanced Cooperative Dynamic Game Analysis. // Static and Dynamic Game Theory: Foundations and Applications, Birkhauser Verlag AG, 2012.
[60] Zakharov V.; Dementieva M. Multistage Cooperative Games and Problem of Time Consistency. // International Game Theory Review, 2004, Vol. 6, 157-170.