Диссертация (1145356), страница 37
Текст из файла (страница 37)
Введем промежуточноеобозначение ^ ({2}, ) для максимального гарантированного по ветке (проходящей через ) значения, когда мы рассматриваем игру в обратном порядке,Глава 8.282Кооперативные многошаговые игры со случайным числом шаговт.е. с последней позиции. Тогда(0 , 1,1 , 2,1 ) :5 + 0.75 * 0 + 0.25 * 2 = 5.5;(0 , 1,1 , 2,2 ) :5 + 0.75 * 4 + 0.25 * 3 = 8.75;(0 , 1,1 , 2,3 ) :5 + 0.75 * 6 + 0.25 * 2 = 10;(0 , 1,1 , 2,4 ) :5 + 0.75 * 2 + 0.25 * 5 = 7.75;^ ({2}, 1,1 ) = 7.75;(0 , 1,2 , 2,5 ) :8 + 0.75 * 11 + 0.25 * 2 = 16.75;(0 , 1,2 , 2,6 ) :8 + 0.75 * 2 + 0.25 * 3 = 10.25;(0 , 1,2 , 2,7 ) :8 + 0.75 * 3 + 0.25 * 2 = 10.75;(0 , 1,2 , 2,8 ) :8 + 0.75 * 1 + 0.25 * 5 = 10;^ ({2}, 1,2 ) = 10.75;Далее аналогичным образом получаем:(0 , 1,3 , 2,9 ) :1.25;(0 , 1,4 , 2,13 ) :5.25;(0 , 1,3 , 2,10 ) :2.25;(0 , 1,4 , 2,14 ) :2.5;(0 , 1,3 , 2,11 ) :0.5;(0 , 1,4 , 2,15 ) :6;(0 , 1,3 , 2,12 ) :2.75;(0 , 1,4 , 2,16 ) :6.75;^ ({2}, 1,4 ) = 5.25;.^ ({2}, 1,3 ) = 2.25;Из величин ^ ({2}, 1, ), = 1, 2, 3, 4 составляет новую матрицу игры:⎛⎝7.75 10.752.25 5.25⎞⎠Второй игрок является максимизирующим игроком, который выбирает столбец.
Следовательно, выбором 2-го столбца в данной игре он может гарантировать себе выигрыш, равный 5.25. Следовательно, ({2}, 0 ) = 5.25.(8.9.59)Глава 8.283Кооперативные многошаговые игры со случайным числом шагов¯ 0 ) по форТеперь мы можем вычислить значение вектора Шепли в игре (муле (8.9.56):ℎ1 = 10.375;(8.9.60)ℎ2 = 10.125.Этап 0 закончен.Этап 1. Вычислим вектор Шепли для всех подыгр, происходящих вдоль оптимальной траектории ¯ = (¯0 , ¯1 , ¯2 ), где ¯1 = 1,1 , ¯2 = 2,2 . Заметим, что¯ 2 ), начинающейся на последнем, 2-м шаге, мы имеем вседля подыгры (¯необходимое для вычисления компонент вектора Шепли. Исходя из значений ({1, 2}, 2,2 ), ({1}, 2,2 ), ({2}, 2,2 ), полученных в формуле (8.9.55), получаем:ℎ21 = 5;(8.9.61)ℎ22 = 7.¯ 1 ) содержит в себе четыре возможных варианта ихСемейство подыгр (¯развития из позиции ¯1 = 1,1 : 1,1 , 2,1 , 1,1 , 2,2 , 1,1 , 2,3 , 1,1 , 2,4 .
Поскольку принцип оптимальности Беллмана выполняется (и это можно проверитьнепосредственным вычислением суммы ожидаемых выигрышей на всех возможных путях — максимум будет достигаться на усечении оптимальной траектории ¯), то для вычисления ({1, 2}, ¯1 ) достаточно вычислить значениесуммы ожидаемых выигрышей по формуле∑︁ (¯1 ) =(︁(1)ℎ1+(1)ℎ2=1,2)︁)︁1 (︁ (2)(2)ℎ + ℎ2 ;+3 1(8.9.62)вдоль части оптимальной траектории 1,1 , 2,2 . В формуле (8.9.62) коэффициент13появляется в силу пересчета вероятности окончания игры на шаге 2 (2 )¯ 1 )). Слепри условии, что игра не закончилась на нулевом (дошла до игры (¯довательно, значению 2 соответствует21−0=13.Сумму(︁(1)ℎ1+(1)ℎ2)︁игрокиГлава 8.Кооперативные многошаговые игры со случайным числом шагов284получат с вероятностью 1 − 0 (что эквивалентно тому, что игра закончится¯ 1 ), т.е.
сна 1-м или 2-м шаге) при условии, что игра дойдет до подыгры (¯вероятностью1−01−0= 1. Таким образом, ({1, 2}, ¯1 ) = 14.(8.9.63)Для нахождения ({1}, ¯1 ), ({2}, ¯1 ) рассматриваем вспомогательные антагонистические игры с началом в вершине ¯1 = 1,1 и выигрышем следующеговида:1 (2)(1) (¯1 ) = ℎ + ℎ .3(8.9.64) (¯1 )— выигрыш максимизирующего игрока во вспомогательной антагонистической игре. Пусть {1} — максимизирующий игрок. Тогда вычисляя еговозможные выигрыши для всех возможных из позции ¯1 траекторий, получимследующую матрицу антагонистической игры:⎛⎝46 135 313 23⎞⎠.Таким образом, на траектории 1,1 , 2,1 (т.е.
выбирая первую строку в одновременной игре Γ(1 1) с матрицей 1 ) первый игрок может гарантировать себевыигрыш ({1}, ¯1 ) = 4.(8.9.65)Аналогично поступим в том случае, когда максимизирующим является второйигрок {2}. Его задачей является такой выбор столбца в матрице 1 в позиции¯1 , чтобы гарантировать себе лучший (против ответа минимизирующего игрока) ожидаемый выигрыш на оставшейся траектории. Матрица выигрышейимеет вид:⎛⎝2356 233 23⎞⎠.Глава 8.285Кооперативные многошаговые игры со случайным числом шаговТаким образом, на траектории 1,1 , 2,4 (т.е.
выбирая второй столбец в одновременной игре Γ(1 1) с матрицей 1 ) игрок {2} может гарантировать себевыигрыш2 ({2}, ¯1 ) = 3 .3(8.9.66)¯ 1 ), используя полученВычислим значение вектора Шепли для подыгры (¯ные результаты (8.9.63),(8.9.65),(8.9.66):1ℎ11 = 7 ;65ℎ12 = 6 .6(8.9.67)Поскольку значения ℎ21 , ℎ22 были получены выше, этап 1 закончен.Этап 2. Проверка динамической устойчивости.Заметим, что для вектора Шепли динамическая и сильно динамическая устойчивость эквивалентны.
Вычислим пошаговые выплаты игрокам по формуле(8.2.30), используя полученные значения компонент вектора Шепли (8.9.60),¯ 0 ), (¯¯ 1 ), (¯¯ 2 ) . Получаем:(8.9.61), (8.9.67) в играх (10 = 5;11 = 5.5;12 = 5;20 = 5;21 = 4.5;22 = 7.(8.9.68)Заметим, что на каждом шаге = 0, 1, 2 между игроками посредством выплат распределяется ровно столько, сколько они заработали на этом шаге:(0)(0)10 + 20 = 5 + 5 = 10 = 5 + 5 = ℎ1 + ℎ2 ;(1)(1)11 + 21 = 5.5 + 4.5 = 10 = 6 + 4 = ℎ1 + ℎ2 ;(2)(2)12 + 22 = 5 + 7 = 12 = 1 + 11 = ℎ1 + ℎ2 .Таким образом, все выплаты на каждом шаге неотрицательные и являются осуществимыми, следовательно, построенный вектор Шепли ℎ1 = 10.375¯ 0 ). Итак, еслиℎ2 = 10.125 является динамически устойчивым в игре (¯Глава 8.Кооперативные многошаговые игры со случайным числом шагов286игроку выплачивать на каждом шаге величину согласно (8.9.68), то в результате игроки получат ℎ1 = 10 +(1−0 )11 +(1−0 −1 )12 = 10.375; ℎ2 =20 + (1 − 0 )21 + (1 − 0 − 1 )22 = 10.125;.8.10Пример регуляризации вектора Шепли в кооперативной многошаговой игре двух лицВ приведенном выше примере построенный вектор Шепли оказался динамически устойчивым.
Данный пример показывает, что бывают и противоположные случаи, когда вектор Шепли не является динамически устойчивым итребуется провести его регуляризацию согласно этапу 3 предложенного алгоритма.¯ 0 ) двух лиц, заданнуюРассмотрим кооперативную многошаговую игру (на следующем графе :3,13,23,33,43,613,623,633,640QAQ A Q A QQAQQAQAQQAQAQQAQAQQAQAQQAQAQQ+ 1,2AU 3s 41 21,11,31,4BBBJJJBJ BJ BJ BJ BJ BJ BJ BJ BJB JB JB JB JB JB JB JB JB JB JB JB JBBBBJJJJBBBBJJJJBBBBJJJJBBBB1JJJJ2222????BN 3BN 3BN 3 BN 3^J4 1^J4 1^J4 1^J42,32,42,52,62,72,82,92,102,112,122,132,142,15B 2,16BJ 2,1 2,2 B BJ.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B BJ B JB B JB B JBJBBBJBJBBJBB....................................23 2 1BN 3^J4BN4?? 10Глава 8.Кооперативные многошаговые игры со случайным числом шагов287Глава 8.Кооперативные многошаговые игры со случайным числом шагов288Здесь максимальное количество шагов игры = 3. Заданы вероятностиокончания игры на каждом шаге = 0, 1, 2, 3:0 = 0.25;(8.10.69)1 = 0;(8.10.70)2 = 0.25;(8.10.71)3 = 0.5.(8.10.72)В вершине 0 игроки участвуют в одновременной игре Γ(0 ), заданной биматрицей⎛0 = ⎝(0; 0) (0, 1)(1; 0) (0, 0)⎞⎠.Также, как и в приведенном выше примере § 8.10 в каждой вершине , еслиигра дойдет до соответствующего шага, в зависимости от реализованной напредыдущем шаге ситуации, разыгрывается одна из четырех одновременныхигр Γ(1 ), Γ(2 ), Γ(3 ), Γ(4 ), заданных следующими матрицами 1 , 2 , 3 , 4примера § 8.10.
Таким образом, мы используем те же матрицы 1 , 2 , 3 , 4 ,что и в примере § 8.10, однако изменили матрицу 0 и увеличили максимальную длину игры до 3. Переход из вершины в вершину подчинен тем жеправилам: при выборе ситуации (1,1) игроки попадают в вершину, где будетразыгрываться игра с матрицей 1 ; (1,2)– 2 ; (2,1)– 3 ;(2,2)– 4 . Значенияв данных одновременных играх, совпадающие со значениями подыгр, начинающимися на последнем шаге 3, представлены формулой (8.9.55) с поправкой на то, что конечные вершины в данном случае имеют другие индексы:3,1 , . . . , 3,64 .
Соответственно, в вершинах 3,1 , 3,5 , 3,9 ,. . . , 3,61 разыгрывается игра Γ(1 ) и значение характеристической функции равно ({1, 2}, 3,1 = ({1, 2}, 3,5 ) = ({1, 2}, 3,9 ) = . . . = 11. Далее действуем согласно алгоритму. Перебором всех возможных 64 вариантов развития игры, для игрыГлава 8.289Кооперативные многошаговые игры со случайным числом шагов¯ 0 ) вычисляем максимальный ожидаемый суммарный выигрыш. Вычисле(ния проводятся аналогично сделанным в примере § 8.10. В итоге получаем,что максимум выражения∑︁ (0 ) =(︁()ℎ1+(0)ℎ2)︁+ 0.75(︁(1)ℎ1+(1)ℎ2)︁+=1,2+ 0.75(︁(2)ℎ1+(2)ℎ2)︁+ 0.5(︁(3)ℎ1+(3)ℎ2)︁(8.10.73)достигается на траектории ¯ = (¯0 , ¯1,4 , ¯2,16 , ¯3,64 ) и равен ({1, 2}, 0 ) = 24.(8.10.74)Таким образом, для получения максимального ожидаемого выигрыша в кооперативном варианте игры, игрокам следует каждый раз выбирать ситуацию(2,2).
Соответственно, матрицы одновременных игр в каждой вершине оптимальной траектории ¯ будут следующие: 0 , 4 , 4 , 4 .Для нахождения значений вспомогательных антагонистических игр (игро-¯ 0 ), сначала вычисляем всека {1} против игрока {2} и наоборот) на основе (64*2 варианта получения выигрышей на каждой из возможных траекторий игры, а затем решаем игру «снизу». В частности, если {1} — максимизирующийигрок, имеем для него следующие результаты:(0 , 1,1 , 2,1 , 3,1 ) :0 + 0.75 * 3 + 0.75 * 3 + 0.5 * 3 = 6;(0 , 1,1 , 2,1 , 3,2 ) :0 + 0.75 * 3 + 0.75 * 6 + 0.5 * 1 = 7.25;(0 , 1,1 , 2,1 , 3,3 ) :0 + 0.75 * 3 + 0.75 * 5 + 0.5 * 1 = 6.5;(0 , 1,1 , 2,1 , 3,4 ) :0 + 0.75 * 3 + 0.75 * 2 + 0.5 * 5 = 6.25;^ ({1}, 2,1 ) = 6.25;.Таким же образом получаем оставшиеся гарантированные до вершины 2, ,Глава 8.290Кооперативные многошаговые игры со случайным числом шагов = 1, .
. . , 16 значения ожидаемого выигрыша для игрока {1}:^ ({1}, 2,1 ) = 6.25;^ ({1}, 2,9 ) = 5.75;^ ({1}, 2,2 ) = 6.75;^ ({1}, 2,10 ) = 3.25;^ ({1}, 2,3 ) = 5.75;^ ({1}, 2,11 ) = 4.5;^ ({1}, 2,4 ) = 6.5;^ ({1}, 2,12 ) = 6.75;^ ({1}, 2,5 ) = 4.75;^ ({1}, 2,13 ) = 7.75;^ ({1}, 2,6 ) = 5.25;^ ({1}, 2,14 ) = 6.75;^ ({1}, 2,7 ) = 2.75;^ ({1}, 2,15 ) = 2.75;^ ({1}, 2,8 ) = 5.75;^ ({1}, 2,16 ) = 9.5.Далее поднимаемся еще на один уровень вверх, учитывая то, что первый игрокявляется максимизирующим, а второй - минимизирующим.
Имеем:^ ({1}, 1,1 ) = 6.25;^ ({1}, 1,2 ) = 4.75;^ ({1}, 1,3 ) = 4.5;^ ({1}, 1,4 ) = 6.75.Таким образом, матрица антагонистической игры фактически имеет следующий вид:⎛⎝Следовательно,мыполучили6.25 4.754.5 6.75⎞⎠.значениехарактеристическойфункции ({1}, 0 ) на «оптимальной» траектории 0 , 1,2 , 2,5 , 3,12 (матрицы одновременных игр —0 , 2 , 1 , 4 ) в антагонистической игре: ({1}, 0 ) = 4.75.(8.10.75)Аналогичным образом получаем значение характеристической функцииГлава 8.Кооперативные многошаговые игры со случайным числом шагов291 ({2}, 0 ) как значение антагонистической игры второго игрока против пер¯ 0 ):вого (игрок {2} — максимизирующий игрок) на основе игры ( ({2}, 0 ) = 6.25.(8.10.76)Подставляя значения (8.10.74),(8.10.75),(8.10.76) в формулу (8.9.56), получаем¯ 0 ):значение вектора Шепли для игры (¯ℎ1 = 11.25;(8.10.77)ℎ2 = 12.75.Далее переходим в семейство в подыгр, начинающихся из вершины ¯1 = 1,4 .Аналогичным способом вычисляем значения характеристической функции: ({1, 2}, ¯1 ) = 32;(8.10.78) ({1}, ¯1 ) = 9; ({2}, ¯1 ) = 10.Соответственно, вектор Шепли имеет вид:ℎ11 = 15.5;(8.10.79)ℎ12 = 16.5.При развитии игры вдоль оптимальной траектории игроки на втором шагеоказываются в вершине ¯2 = 2,16 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
