Диссертация (1145356), страница 38
Текст из файла (страница 38)
Можно показать, что верны следующиерезультаты: ({1, 2}, ¯2 ) = 20;1 ({1}, ¯2 ) = 6 ;32 ({2}, ¯2 ) = 6 ;31ℎ21 = 10 ;65ℎ22 = 9 .6(8.10.80)(8.10.81)Глава 8.292Кооперативные многошаговые игры со случайным числом шаговДля игры в последней вершине ¯3 = 3,64 значения характеристической функции уже представлены в формуле (8.9.55) (с поправкой на индексы), следовательно, имеем:(8.10.82) ({1, 2}, ¯3 ) = 12; ({1}, ¯2 ) = 5; ({2}, ¯2 ) = 5;(8.10.83)ℎ31 = 6;ℎ32 = 6.Вычислим значения ПРД , = 1, 2, = 0, 1, 2, 3 по формуле (??).
Тогда10 = −0.375;20 = 0.375;1111 = 5 ; 12 = 6 ; 13 = 6;362521 = 6 ; 22 = 5 ; 23 = 6.36(8.10.84)Поскольку 10 ≤ 0, построенный вектор Шепли {ℎ } (8.10.77) не являетсядинамически устойчивым. Перейдем к его регуляризации (этап 3). Вводимновые выплаты ¯ по формуле (8.4.37):(0=1,2 ℎ∑︀¯ = ℎ ({1, 2}, ¯ ).После вычислений получаем:¯10 = 0;¯20 = 0;13¯11 = 5 ; ¯12 = 6.1; ¯13 = 6;1613¯21 = 6 ; ¯22 = 5.9; 23 = 6.16(8.10.85)Заметим, что сумма новых выплат на каждом шаге равна заработанной()()сумме ℎ1 + ℎ2 . Вычислим регуляризованный вектор Шепли на основе ПРД(8.10.85) по формуле (8.2.16).
Окончательный результат:299;32021ℎ2 = 12.320ℎ1 = 11(8.10.86)(8.10.87)Глава 8.Кооперативные многошаговые игры со случайным числом шагов293Можно убедиться, что построенный РВШ является дележом, т.е. ℎ1 + ℎ2 = ({1, 2}, 0 ) = 24.Глава 9Многошаговые игры на деревьяхсобытий9.1Постановка задачиРассмотрим динамическую игру с другими элементами случайности, а именно,многошаговую кооперативную игру на «деревьях событий» (см. [310]).Пусть = {0, 1, .
. . , } будет обозначать множество дискретных моментоввремени. Обозначим через (() : ∈ ) внешний стохастический процесс, который описывается деревом событий. В качестве корневой вершины дерева событий выбирается состояние 0 , соответствующее нулевому моменту. Соответственно, моменту ∈ соответствует множество = 1 .
. . , . Каждая{︀}︀вершина ∈ представляет собой возможную реализацию истории процесса (·) к моменту времени , которую мы будем обозначать ℎ . Структурадерева событий описывает накопление информации с ходом времени. Обозначим через ( ) ∈ −1 вершину, предшествующую вершине ∈ и через( ) ∈ +1 множество вершин, непосредственно следующих за вершиной ∈ . Путь из корневой вершины 0 в конечную вершину , соответствующую моменту , называется сценарием. Каждый сценарий реализуется с некоторой вероятностью и сумма вероятностей всех сценариев равна 1.294Глава 9.295Многошаговые игры на деревьях событийОбозначим через ( ) вероятность прохождения процесса через вершину ,которая соответствует сумме вероятностей всех сценариев, которые проходятчерез эту вершину.
В частности, (0 ) = 1, а величина ( ) равна вероятности реализации (единственного) сценария, который оканчивается в вершине .Пусть = {1, . . . , } – множество игроков. Для каждого игрока ∈ определим множество управляющих переменных, заданных для каждой вершины графа. Так, ( ) ∈ R обозначает управляющую переменную -го игрока в вершине . Соответственно, множество управляющих переменных всехигроков в вершине обозначается ( ) = (1 ( ), .
. . , ( )). Определиммножество состояний как ⊂ R , где ∈ N ∖ {0}. Для каждой вершины ∈ , = 0, 1, . . . , , зададим ⊂ R — множество допустимых значенийуправления -го игрока (где – некоторая заданная положительная целочисленная величина). Соответственно, множество допустимых значений управлений для всех игроков будем обозначать как = 1 × · · · × × · · · × .Функция перехода (·, ·) : × ↦→ определена для каждой вершины .
Уравнения динамики имеют вид)︀)︀ (︀ (︀ )︀)︀)︀ (︀ (︀ (︀( ) = ( ) , (︀ (︀ )︀)︀∈ ( ) , ∈ , = 1, . . . , . (9.1.1)(9.1.2)В каждой вершине , = 0, . . . , − 1, выигрыш -го игрока зависит оттекущего состояния системы и управлений всех игроков в данный момент времени: (( ), ( )). В конечной вершине выигрыш -го игрока задаетсяфункцией Φ (( )).Мы полагаем, что каждый игрок ∈ максимизирует свой суммарныйвыигрыш, дисконтированный с показателем (0 < < 1). Уравнения состояний и функция выигрыша тем самым определяют многошаговую игру, вГлава 9.296Многошаговые игры на деревьях событийкоторой˜ = {( ) : ∈ , = 0, . .
. , },˜ = {( ) : ∈ , = 0, . . . , − 1},и (˜, ˜ ) – выигрыш -го игрока, ∈ , который задается следующим образом: (˜, ˜) = −1∑︁∑︁( ) (( ), ( ))+ ∈ =0∑︁( )Φ (( )), ∈(9.1.3)где( ) = ( ) ((( )), (( ))),(( )) ∈ ( ) ,(9.1.4) ∈ , = 1, . . . , ,(0 ) = 0 .(9.1.5)Определение 9.1.1. Допустимой S-адаптированной стратегией для -гоигрока называется вектор ˜ = { ( ) : ∈ , = 0, . . . , − 1}, т.е. последовательность действий, определенная с учетом реализации случайногопроцесса, представленного деревом состояний.Обозначим через ˜ = (˜ : ∈ ) вектор S -адаптированных стратегий для игроков. Определим игру в нормальной форме с функциями выигрыша (˜, 0 ) = (˜, ˜ ), ∈ . Состояние ˜ зависит от ˜ и определяется какуникальное решение уравнений состояния для начального состояния 0 .Рассмотрим некооперативный вариант игры.Определение 9.1.2.
Пусть ˜ – S-адаптированная допустимая стратегия. Будем называть ˜ S-адаптированным равновесием по Нэшу, если длякаждого игрока , ∈ выполняется неравенство0 (˜ , 0 ) ≥ ([˜ , ũ− ], ),Глава 9.297Многошаговые игры на деревьях событийгде ũ− – вектор, соответствующий равновесию по Нэшу для всех игроковза исключением -того.Хотя S -адаптированные и программные стратегии кажутся похожими, ониотличаются в определении уравнений состояния и управлений. В информационной структуре, соответствующей программным стратегиям, уравнения состояния и управления определены как функции времени. В информационнойструктуре, соответствующей S -адаптированным стратегиям, уравнения состояния и управления определены на вершинах дерева событий.9.2Кооперативный вариант игрыРассмотрим кооперативный вариант игры. Если игроки договариваются о сотрудничестве, они максимизируют сумму своих совокупных дисконтированных выигрышей:max =˜ ,∈∑︁)︀(︀˜ , 0 .
∈(︀ )︀Обозначим через ˜ * 0 результирующий вектор кооперативных управлений,т.е.∑︁(︀ )︀(︀)︀˜ * 0 = arg max ˜ , 0 .∈Пусть ˜* = {* ( ) : ∈ , = 0, 1, . . . , } — кооперативная траектория,соответствующая управлениям ˜ * 0 .(︀ )︀Для ясности дальнейшего изложения, введем следующие обозначения:˜ (* ( )) : Допустимая стратегия для -го игрока в подыгре, начинающейся в вершине с начальным состоянием * ( ), ∈ , = 1, . . . , и˜ (* ( )) = (˜ (* ( )) : ∈ ).*˜ ( ( )) : S -адаптированная стратегия из равновесия по Нэшу для -го иг-рока в подыгре, начинающейся в вершине с начальным состояниемГлава 9.298Многошаговые игры на деревьях событий** ( ), ∈ , = 1, . .
. , и ˜ (* ( )) = (˜ ( ( )) : ∈ ).(︀ * [︀ ]︀)︀*: Последовательность управлений ˜˜ ( ( )) вдоль пу ( ) , , ти, исходящего из вершины , ∈ , > , и заканчивающегося ввершине ∈ .˜* (* ( )) : Кооперативная стратегия (управление) для игрока в подыгре,начинающейся в вершине с начальным состоянием * ( ), ∈ , =1, . . . , ; ˜ * (* ( )) = (˜* (* ( )) : ∈ ).[︀]︀)︀(︀˜* * ( ) , , : Последовательность управлений ˜* (* ( )) на пути, исходящем из вершины , ∈ , > и заканчивающемся в вершине ∈ . (˜ (* ( ))) : Выигрыш -го игрока при использовании игроками управлений ˜ (* ( )). (˜ (* ( ))) : Выигрыш -го игрока, соответствующий S -адаптированномуравновесию по Нэшу в подыгре, начинающейся в вершине с начальнымусловием * ( ), ∈ , = 1, .
. . , .* (˜ (* ( ))) : Выигрыш -го игрока в кооперативной игре, начинающейсяв вершине с начальным состоянием * ( ), ∈ , = 1, . . . , .Замечание 9.2.1. В дальнейших вычислениях будем полагать что кооперативное решение, равно как и равновесие по Нэшу существуют и единственны.Аналогично непрерывному случаю, единственность кооперативного решенияпредполагает строгую выпуклость функции выигрыша, а также компактностьи выпуклость множества допустимых управлений. В случае S -адаптированногоравновесия по Нэшу имеем многошаговую игру в нормальной форме, условияединственности для которой такие же, как и для классических игр с непрерывными выигрышами (см. [314], а также [232]).Глава 9.299Многошаговые игры на деревьях событий(︀ * [︀ ]︀)︀(︀ * [︀ ]︀)︀),,и˜вЗамечание 9.2.2.
Траектории ˜( ( ) , , общем случае не совпадают. Это следует из того, что первая траектория вычисляется в предположении, что игроки кооперировались только в течении*интервала [0, ], в то время как ˜ ( ) , , (︀[︀]︀)︀вычисляется для коопе-ративной игры на интервале [0, ], где > .9.3Динамически устойчивый вектор ШеплиДля определения кооперативных выигрышей * (˜ (* ( ))) , ∈ мы полагаем, что игроки договариваются использовать вектор Шепли [324] в качествемеханизма распределения совокупного кооперативного выигрыша, которыйопределяется как* =∑︁(︀ (︀ (︀ )︀)︀)︀* ˜* 0 0.∈Пусть Γ(, , ; ) – кооперативная игра, в которой = {1, .
. . , } – множество игроков, ⊆ – коалиция; (; * ( )) – характеристическая функция в подыгре, начинающейся в вершине с начальным состоянием * ( ) иопределенная следующим образом:(︀(︀ )︀)︀ ; * : 2 → R,(9.3.6)так, что (∅; * ( )) = 0, и – множество дележей, т.е.⎧⎫⎨∑︁(︀(︀ )︀)︀(︀(︀ 0 )︀)︀⎬*0 = (1 , . . . , ) | ≥ {}; , ∀ ∈ ; = ; .⎩⎭∈Вектор Шепли для -го игрока, полученный за всю игру, начиная с вершины0 , определяется как∑︁ ( − )!( − 1)! (︀(︀ (︀ )︀)︀(︀ )︀)︀(︀(︀ )︀)︀ℎ 0 0 =[ ; 0 0 − ∖{}; 0 0 ],!⊂∈(9.3.7)Глава 9.Многошаговые игры на деревьях событий300где – число игроков в коалиции и∑︁(︀ (︀ )︀)︀(︀(︀ )︀)︀ℎ 0 0 = ; 0 0 .∈Подобным образом можно определить значение вектора Шепли в произвольной подыгре, начинающейся в вершине с начальным состоянием * ( ) как(︀ (︀ )︀)︀ℎ * =∑︁ ( − )!( − 1)! (︀(︀ )︀)︀(︀(︀ )︀)︀[ ; * − ∖{}; * ], (9.3.8)!⊂∈∑︁(︀ (︀ )︀)︀(︀(︀ )︀)︀ℎ * = ; * .∈Ключевым является вопрос определения характеристической функции (; * ( )) для ⊂ , которая выступает в качестве меры стратегическойсилы или, иначе говоря, мощности коалиции.
Мощность коалиции определяется тем, что коалиция может достичь самостоятельно, не кооперируясь состальными (т.е. не включенными в коалицию) игроками ∖. Как было указано в разделе 5.3, это привело к появлению различных определений характеристической функции, таких как −, −, −, −, − характеристическихфункций (см.
[165, 185, 303, 26, 309, 268]).В данном случае будем использовать определение − характеристическойфункции [185], т.е. будем полагать, что (; * ( )) определяется как выигрыш коалиции в S -адаптированном равновесии по Нэшу в некооперативной игре между коалицией , максимизирующей свой совокупный выигрыш,и остальными игроками, играющими индивидуально, т.е. максимизирующими свои индивидуальные выигрыши.
Таким образом, игроки, не вошедшие вкоалицию , не предпринимают действий, направленных на уменьшение выигрыша коалиции , а используют свои оптимальные стратегии.Пусть в начальный момент времени игроки договариваются действоватьГлава 9.301Многошаговые игры на деревьях событийсовместно оптимально в течение всей игры и распределять совокупный выигрыш с использованием вектора Шепли (9.3.7). В свою очередь, динамическая устойчивость вектора Шепли обеспечивается использованием процедурыраспределения дележа [111], т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
