Диссертация (1145356), страница 36
Текст из файла (страница 36)
Определим для селектора = 1, . . . , вектор ¯ по формуле:∑︀ ∑︁∑︁ )ℎ (¯¯ = . =1 (,¯)=0{ } ∈ (¯ ), = 1, . . . , ,(8.8.49)=0Нетрудно заметить, что {¯ } — дележ в игре (¯0 ) (см. построение (ДУПО)).=0,...,−1Зафиксируем и введем ¯ = {¯ }=1,..., :()¯ = ∑︀ )=1 ℎ (¯ (, ¯ )(8.8.50), = 0, . . . , − 1.=1,...,Заметим, что все компоненты ¯ = {¯ }=1,..., – неотрицательные числа.Предположим, что принципу оптимальности (0 ) соответствует не единственный дележ { } ∈ (¯ ), поскольку тогда определение динамической и сильнодинамической устойчивости являются эквивалентными.
Выберем другой произвольный дележ ̂︀{ } ∈ (¯ ), = , . . . , и определим дележ в каждойподыгре по формуле:¯=1−1∑︀−1 ∑︁∑︁=0 = =̂︀∑︀ )=1 ℎ (¯ (, ¯ ).(8.8.51)Рассмотрим̂︀ = ̂︀∑︀ )=1 ℎ (¯ (, ¯ ), = , . . . , ,()̂︀ ≥ 0.(8.8.52)Глава 8.273Кооперативные многошаговые игры со случайным числом шаговПусть =⎧⎪⎨¯ , = 0, . . . , − 1,(8.8.53)⎪⎩̂︀ , = , . . .
, .Сформируемдлявсехмножество¯ 0 ) = { :(¯′′=(соответствующих ∑︁∑︁различным̂︀ ) , = 1, . . . , }.=0 =0¯ 0 ) является сильно динамически устойчиТеорема 8.8.1. Множество (¯вым принципом оптимальности.Доказательство Теоремы 8.8.1 проводится по построению.8.9Пример динамически устойчивого решения в кооперативной многошаговой игре двух лиц¯ 0 ) двух лиц, заданную наРассмотрим кооперативную многошаговую игру (следующем графе :0Q A Q A Q A QQAQQAQAQQAQAQQAQAQQAQAQQAQAQQAQQAQAQ+s 41 2 1,21,11,3 AU 31,4 QSSSSCCCC CS CS CS CS C S C S C S C S C SC SC SC SCCCCSSSSCCCCSSSSCCCCSSSS C C C CSSSS1 2 341 2 341 2 341 2 34////CWCWCWCWwSwSwSwS2,12,22,32,42,52,62,72,82,92,102,112,122,132,142,152,160Глава 8.Кооперативные многошаговые игры со случайным числом шагов274Глава 8.275Кооперативные многошаговые игры со случайным числом шаговМножество вершин (21 вершина) графа сформировано следующимобразом:0 ; (0 ) = {1,1 , 1,2 , 1,3 , 1,4 }; (1,1 ) = {2,1 , 2,2 , 2,3 , 2,4 }; (1,2 ) = {2,5 , 2,6 , 2,7 , 2,8 }; (1,3 ) = {2,9 , 2,10 , 2,11 , 2,12 }; (1,4 ) = {2,13 , 2,14 , 2,15 , 2,16 }.Игра происходит следующим образом: на нулевом шаге игроки участвуют водновременной игре Γ(0 ), заданной биматрицей⎛0 = ⎝(5; 5) (0, 8)(8; 0) (1, 1)⎞⎠.¯ 0 ) либо заканчивается с вероятностью 0 = 0.25, либоПосле этого игра (переходит в следующую из возможных четырех0 = {1,1 , 1,2 , 1,3 , 1,4 }(8.9.54)вершину 1 , причем этот переход зависит от реализовавшейся ситуации в вершине 0 .
Если в игре Γ(0 ) реализуется ситуация (1,1), то из вершины 0 играпереходит в вершину 1 = 1,1 , если реализуется ситуация (1,2), то из вершины0 игра переходит в вершину 1 = 1,2 ; ситуации (2,1) соответствует переход ввершину 1 = 1,3 ; ситуации (2,2) соответствует переход в 1 = 1,4 .В вершине 1 игроки играют в игру Γ(1 ) двух лиц, которая, в зависимостиот реализованной на предыдущем шаге ситуации, задается одной из следующих биматриц:⎛1 = ⎝⎛3 = ⎝(3; 0) (6, 4)(5; 6) (2, 2)(1; 1) (0, 2)(2; 0) (1, 2)⎞⎠;⎞⎠;⎛2 = ⎝(1; 11) (4, 2)⎞⎠;(1; 3) (1, 1)⎞(5; 5) (6, 1)⎠.4 = ⎝(1; 6) (6, 6)⎛Глава 8.Кооперативные многошаговые игры со случайным числом шагов276На этом шаге игра может закончиться с вероятностью 1 = 0.5 или перейтив следующую вершину 2 .
Правила перехода в вершину 2 (одну из четырехвозможных из позиции 1 ) такие же: в случае реализации ситуации (1,1) играпереходит в последнюю вершину 2 , в которой осуществляется игра Γ(2 ) cматрицей 1 ; ситуации (1,2) соответствует переход в такую вершину 2 , в которой осуществляется игра Γ(2 ) c матрицей 2 ; ситуации (2,1) соответствуетпереход в 2 , в которой осуществляется игра Γ(2 ) c матрицей 3 ; выбору ситуации (2,2) соответствует переход в вершину, в которой разыгрывается играс матрицей 4 . Вероятность окончания игры на втором шаге равна 2 = 0.25.Для начала решим одновременные игры Γ1 , .
. ., Γ4 . Тогда в подыграх, начинающихся на последнем шаге, будут следующие 4 вида значений характеристических функций: ({1, 2}, 2,1 ) = ({1, 2}, 2,5 ) = ({1, 2}, 2,9 ) == ({1, 2}, 2,13 ) = 5 + 6 = 11; ({1}, 2,1 ) = ({1}, 2,5 ) = ({1}, 2,9 ) = ({1}, 2,13 ) = 3; ({2}, 2,1 ) = ({2}, 2,5 ) = ({2}, 2,9 ) = ({2}, 2,13 ) = 2; ({1, 2}, 2,2 ) = ({1, 2}, 2,6 ) = ({1, 2}, 2,10 ) == ({1, 2}, 2,14 ) = 1 + 11 = 12; ({1}, 2,2 ) = ({1}, 2,6 ) = ({1}, 2,10 ) = ({1}, 2,14 ) = 1; ({2}, 2,2 ) = ({2}, 2,6 ) = ({2}, 2,10 ) = ({2}, 2,14 ) = 3;(8.9.55)Глава 8.277Кооперативные многошаговые игры со случайным числом шагов ({1, 2}, 2,3 ) = ({1, 2}, 2,7 ) = ({1, 2}, 2,11 ) == ({1, 2}, 2,15 ) = 1 + 2 = 3; ({1}, 2,3 ) = ({1}, 2,7 ) = ({1}, 2,11 ) = ({1}, 2,15 ) = 1; ({2}, 2,3 ) = ({2}, 2,7 ) = ({2}, 2,11 ) = ({2}, 2,15 ) = 2; ({1, 2}, 2,4 ) = ({1, 2}, 2,8 ) = ({1, 2}, 2,12 ) == ({1, 2}, 2,16 ) = 6 + 6 = 12; ({1}, 2,4 ) = ({1}, 2,8 ) = ({1}, 2,12 ) = ({1}, 2,16 ) = 5; ({2}, 2,4 ) = ({2}, 2,8 ) = ({2}, 2,12 ) = ({2}, 2,16 ) = 5; .Предположим, что игроки {1, 2} договорились разделить заработанную совместными усилиями сумму, используя вектор Шепли.
Для случая игры двухлиц формула для вычисления компонент вектора Шепли имеет вид: ({1, 2} , ) − (2, )1,ℎ1 () = (1, ) +221 ({1, 2} , ) − (1, )ℎ2 () = (2, ) +.22(8.9.56)Дальше действуем согласно указанному выше алгоритму.¯ 0 ) вычислим максимальное значение суммарного ожиЭтап 0. Для игры (даемого выигрыша (8.1.7) на одном из 16 возможных путей. Для распределения 0 = 0.25, 1 = 0.5, 2 = 0.25, имеем следующий вид суммарного ожидаемого выигрыша:∑︁ (0 ) =(︁()ℎ1+(0)ℎ2)︁+ 0.75(︁(1)ℎ1+(1)ℎ2)︁+ 0.25(︁(2)ℎ1+(2)ℎ2)︁,(8.9.57)=1,2()()где ℎ1 , ℎ2— выигрыши игроков в одновременной игре на шаге (т.е.
эле-менты матрицы, соответствующие выбранной стратегии). Соответственно, на(2)(2)последнем шаге ℎ1 +ℎ2 = ({1, 2}, 2 ) , т.е. вычисляется по формуле (8.9.55),где 2 — одна из возможных 16 вершин 2,1 , . . . , 2, 16 .Глава 8.Кооперативные многошаговые игры со случайным числом шагов278Запишем все получившиеся значения суммарного ожидаемого выигрыша∑︀ на каждой возможной траектории:(0 , 1,1 , 2,1 ) :∑︁ (0 ) = (5 + 5) + 0.75 * (3 + 0) + 0.25 * 11 = 15;=1,2(0 , 1,1 , 2,2 ) :∑︁ (0 ) = 10 + 0.75 * (6 + 4) + 0.25 * 12 = 20.5;=1,2(0 , 1,1 , 2,3 ) :∑︁ (0 ) = 10 + 0.75 * (5 + 6) + 0.25 * 3 = 19;=1,2(0 , 1,1 , 2,4 ) :∑︁ (0 ) = 10 + 0.75 * (2 + 2) + 0.25 * 12 = 16;=1,2(0 , 1,2 , 2,5 ) :∑︁ (0 ) = (0 + 8) + 0.75 * (1 + 11) + 0.25 * 11 = 19.75;=1,2(0 , 1,2 , 2,6 ) :∑︁ (0 ) = 8 + 0.75 * (4 + 2) + 0.25 * 12 = 15.5;=1,2(0 , 1,2 , 2,7 ) :∑︁ (0 ) = 8 + 0.75 * (1 + 3) + 0.25 * 3 = 11.75;=1,2(0 , 1,2 , 2,8 ) :∑︁=1,2 (0 ) = 8 + 0.75 * (1 + 1) + 0.25 * 12 = 12.5;Глава 8.Кооперативные многошаговые игры со случайным числом шагов∑︁(0 , 1,3 , 2,9 ) :279 (0 ) = 8 + 0.75 * 2 + 0.25 * 11 = 12.25;=1,2(0 , 1,3 , 2,10 ) :∑︁ (0 ) = 8 + 0.75 * 2 + 0.25 * 12 = 12.5;=1,2(0 , 1,3 , 2,11 ) :∑︁ (0 ) = 8 + 0.75 * 2 + 0.25 * 3 = 10.25;=1,2(0 , 1,3 , 2,12 ) :∑︁ (0 ) = 8 + 0.75 * 3 + 0.25 * 12 = 13.25;=1,2(0 , 1,4 , 2,13 ) :∑︁ (0 ) = 2 + 0.75 * 10 + 0.25 * 11 = 12.25;=1,2(0 , 1,4 , 2,14 ) :∑︁ (0 ) = 2 + 0.75 * 7 + 0.25 * 12 = 10.25;=1,2(0 , 1,4 , 2,15 ) :∑︁ (0 ) = 2 + 0.75 * 7 + 0.25 * 3 = 8;=1,2(0 , 1,4 , 2,16 ) :∑︁ (0 ) = 2 + 0.75 * 12 + 0.25 * 12 = 14.=1,2Таким образом, оптимальной траекторией является ¯ = 0 , 1,1 , 2,2 = ¯0 , ¯1 , ¯2 ,на которой игроки получают максимальное математической ожидание суммарного выигрыша, т.е.
({1, 2}, ¯0 ) = 20.5 (здесь мы применяем обозначение¯0 , что соответствует тому, что на нулевом шаге игроки совместно выбираютситуацию (1,1), чтобы перейти в вершину ¯1 = 1,1 ).Для нахождения значений ({1}, 0 ), ({2}, 0 ) рассмотрим вспомогательные антагонистические одновременные игры, где матрицы выигрышей получаются из биматриц 1 , 2 , 3 , 4 следующим образом: для антагонистическойигры первого игрока {1} в качестве максимизирующего игрока, берутся «первые» значения в биматрицах, для антагонистической игры второго игрока {2}в качестве максимизирующего игрока, берутся «вторые» значения в биматрицах. Вычислим значения ожидаемого выигрыша для первого игрока для однойГлава 8.Кооперативные многошаговые игры со случайным числом шагов280ветви игры:(0 , 1,1 , 2,1 ) :5 + 0.75 * 3 + 0.25 * 3 = 8;(0 , 1,1 , 2,2 ) :5 + 0.75 * 6 + 0.25 * 1 = 9.75;(0 , 1,1 , 2,3 ) :5 + 0.75 * 5 + 0.25 * 1 = 9;(0 , 1,1 , 2,4 ) :5 + 0.75 * 2 + 0.25 * 5 = 7.75.Понятно, что второй, минимизирующий игрок, также знает эти значения, поэтому далее игру нужно рассматривать «снизу», т.е.
от последнего шага 2.Фактически, на первом шаге 1-й и 2-й игрок играют в антагонистическуюигру с матрицей:⎛⎝8 9.759 7.75⎞⎠.Тогда первый игрок выбором стратегии 1 (строки 1) в позиции 1,1 может гарантировать себе выигрыш (на этой ветке игры), равный 8. Для оставшихсятрех веток игры также посчитаем математическое ожидание выигрыша первого игрока:(0 , 1,2 , 2,5 ) :0 + 0.75 * 4 + 0.25 * 3 = 1.5;(0 , 1,2 , 2,6 ) :0 + 0.75 * 1 + 0.25 * 1 = 3.25;(0 , 1,2 , 2,7 ) :0 + 0.75 * 1 + 0.25 * 1 = 1;(0 , 1,2 , 2,8 ) :0 + 0.75 * 1 + 0.25 * 5 = 2.Выбором стратегии (1,1) в вершине 1,2 1-й игрок может гарантировать себевыигрыш, равный 1.5.(0 , 1,3 , 2,9 ) :8 + 0.75 * 1 + 0.25 * 3 = 9.5;(0 , 1,3 , 2,10 ) :8 + 0.75 * 0 + 0.25 * 1 = 8.25;(0 , 1,3 , 2,11 ) :8 + 0.75 * 2 + 0.25 * 1 = 9.75;(0 , 1,3 , 2,12 ) :8 + 0.75 * 1 + 0.25 * 5 = 10.Глава 8.281Кооперативные многошаговые игры со случайным числом шаговВыбором стратегии (2,1) в вершине 1,3 1-й игрок может гарантировать себевыигрыш, равный 9.75.(0 , 1,4 , 2,13 ) :1 + 0.75 * 5 + 0.25 * 3 = 5.5;(0 , 1,4 , 2,14 ) :1 + 0.75 * 6 + 0.25 * 1 = 5.75;(0 , 1,3 , 2,15 ) :1 + 0.75 * 1 + 0.25 * 1 = 2;(0 , 1,3 , 2,16 ) :1 + 0.75 * 6 + 0.25 * 5 = 6.75.Выбором стратегии (1,1) в вершине 1,4 1-й игрок может гарантировать себевыигрыш, равный 5.5.
Теперь, для того, чтобы выбрать из возможных ветвейигры (т.е. чтобы подняться еще на одну позицию), игроки фактически имеютновую матрицу (как результаты максимизации на предыдущем уровне):⎛⎝81.59.75 5.5⎞⎠.Выбором (2,2) игрок {1} может гарантировать себе выигрыш, равный 5.5.Таким образом, в антагонистической игре, начинающейся в 0 1-й (максимизирующий игрок) выберет траекторию 0 , 1 4, 2,13 (соответствующие матрицыодновременных игр – 0 , 4 , 1 ), на которой может гарантировать себе выигрыш, равный 5.5. Следовательно, ({1}, 0 ) = 5.5.(8.9.58)Аналогичным образом находится значение ({2}, 0 ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
