Диссертация (1145356), страница 35
Текст из файла (страница 35)
Множество (¯чивый принцип оптимальности (ДУПО) в регуляризованной игре ¯ (¯0 ).Заметим, что введенная по формуле (8.4.37) ПРД обладает важным свойством осуществимости таких выплат — суммарные выплаты игрокам на каждом шаге в точности равны заработанной ими сумме:∑︁¯==1=∑︁=1∑︁ℎ (¯ )ℎ (¯ ),=∑︁=1∑︀ )=1 ℎ (¯ (, ¯ )∀ = 0, 1, 2, . . . , .=(8.4.41)=1Таким образом, при использовании выплат игрокам на каждом шаге по формуле (8.4.37), мы обеспечиваем динамическую устойчивость принципа опти-¯ 0 ) и при этом не требуются дополнительные инвестиции.мальности (¯8.5Регуляризация вектора Шепли и C-ядра в игре (0)Предположим, что в качестве принципа оптимальности (¯0 ) игроки выбраливектор Шепли (5.1.7).
В том случае, когда компоненты вектора Шепли не могут быть представлены в виде (8.2.21) при помощи неотрицательных выплатна каждом шаге (т.е. ПРД { }), требуется провести улучшение или регу-ляризацию вектора Шепли. Говоря другими словами, необходимо построитьнекоторый другой принцип оптимальности — регуляризованный вектор Шепли (РВШ), применяя который игроки не имели бы оснований для отклоненийот оптимальной траектории в течение всей игры. Справедлива следующаятеорема.Теорема 8.5.1. Вектор Шепли, вычисленный для характеристической функции ¯ (, ¯0 ), ⊆ (8.3.34), всегда динамически устойчив в игре ¯ (¯0 ).Глава 8.266Кооперативные многошаговые игры со случайным числом шаговДоказательство.
Доказательство данной теоремы аналогично доказательствуТеоремы 6.5.3 части II. Поскольку вектор Шепли вычисляется по формуле(5.1.7), то компоненты вектора Шепли в игре ¯ (¯0 ) с характеристическойфункцией ¯ (, ¯0 ) имеют вид:ℎ (¯0 ) =∑︁ ( − )!( − 1)!!⊂∈[¯ (, ¯0 ) − ¯ (∖{}, ¯0 )].(8.5.42)Из формул (8.3.34) и (8.5.42) получаем выражение для компонент регуляризованного вектора Шепли ℎ (¯0 ):¯ (0 ) =ℎ ∑︁∑︁( − )!( − 1)! ∑︁=0 =0!∑︀− (∖{}, ¯ )][ (, ¯ )−⊂ )=1 ℎ (¯ = (, ¯ )∑︀ ∑︁∑︁ℎ (¯ )ℎ (¯ ) =1 = .(,¯)=0=0Таким образом, РВШ имеет вид (8.4.35), который, согласно доказанной Теореме 8.4.1 означает динамическую устойчивость регуляризованного вектораШепли {ℎ (¯0 }.
Таким образом, вектор Шепли ℎ (¯0 ), вычисленный для характеристической функции ¯ (, ¯0 ), является динамически устойчивым.Согласно доказанной теореме, регуляризованный вектор Шепли может бытьпостроен как при помощи непосредственных вычислений нового вида ПРД(8.4.37), так и вычислен для новой характеристической функции ¯ (, ¯0 ) (8.3.34).Если игроки выбрали C-ядро в качестве принципа оптимальности, в соответствии с которым они собираются разделить ожидаемый выигрыш (, 0 ),справедлива следующая теорема. Везде далее предполагается, что (¯ ) ̸= ∅вдоль всей кооперативной траектории.^ 0 ) — C-ядро игры ¯ (0 ), построенное для хаТеорема 8.5.2. Пусть (рактеристической функции ¯ (, 0 ). Если изначально выбранный принципГлава 8.267Кооперативные многошаговые игры со случайным числом шаговоптимальности (0 ) является C-ядром (что означает, что∈ ∑︀≥¯ 0) (, ¯ ), ∀ ), то построенный на его основе принцип оптимальности (^ 0 ):будет принадлежать (¯ 0 ) ⊂ (^ 0 ).(Доказательство.
Доказательство аналогично доказательству Теоремы 6.5.2.^ 0 ) тогда и только тогда, когда выполненоДележ ¯ принадлежит С-ядру (следующее условие :∑︁¯ ≥ ¯ ( , ),∀ ⊂ .∈¯ 0 ) имеемВ то же время, для любого дележа ¯ ∈ (∑︁¯ = ∑︁∑︁ ∑︁∈ =0 =0∈∑︀=1 ℎ (·) (, ¯ ) .Т.к. (0 ) является C-ядром, должно выполняться неравенство∑︁ ≥ (, ¯ ),∀ ⊂ .∈Тогда ∑︁∑︁ ∑︁∑︀ ∑︁∑︁ℎ(·)ℎ (·)=1 ≥ (, ¯ ) =1 . (, ¯ )(,¯)=0∑︀∈ =0 =0=0Поскольку характеристическая функция ¯ (, 0 ) вычисляется по формуле(8.3.34)), получаем, что∑︁¯ ≥ ¯ (, 0 ),∈¯ 0 ) ⊂ (^ 0 ).Таким образом, (∀ ⊂ .Глава 8.8.6Кооперативные многошаговые игры со случайным числом шагов268Алгоритм регуляризации вектора Шеплив игре (0)Рассмотрим игру на конечном графе длины . Предположим, игроками былвыбран вектор Шепли в качестве решения игры. На основании представленнойвыше теории, приведем алгоритм регуляризации вектора Шепли.
Алгоритмможет быть использован для регуляризации любого классического ПО с соответствующими изменениями при вычислениях дележей.Этап 0. Вычисление вектора Шепли {ℎ } в игре (¯0 ).(1) Находим оптимальную траекторию ¯ как последовательность вершин¯0 , ¯1 , . . . , ¯ , которая соответствует набору стратегий ¯ = ({¯ 0 }, {¯ 1 }, .
. . ,{¯ }), максимизирующему совокупный ожидаемый выигрыш (8.1.4). Вдальнейшем для уменьшения громоздкости будем обозначать выбраннуюстратегию на шаге (в вершине ) как .(2) Вычисляем значение (, ¯0 ) по формуле (8.1.7).(3) Для вычисления (, ¯0 ) рассматриваются вспомогательные антагонистические игры на основе игры (0 ), где — первый, т.е. максимизи ,...,рующий игрок (применяет стратегию 0)а ∖ — минимизирующий ,...,игрок (стратегия 0 ∖ ). Соответственно, значения (, ¯0 ) для всевозможных ⊂ находятся по формулам (8.1.5).(4) Находим компоненты вектора Шепли по формуле (5.1.7) в игре (0 ).В общем случае дележ является некоторым распределением значения (, 0 ).Этап 1. Вычисление компонент вектора Шепли {ℎ } = 1, .
. . , во всехподыграх (¯ ), = 1, 2, . . . , .Глава 8.Кооперативные многошаговые игры со случайным числом шагов269(1) Рассмотрим семейство подыгр, в которое могут попасть игроки при сдвигена 1 шаг по оптимальной траектории ¯, т.е. подыгру (¯1 ), начинающуюся из вершины ¯1 . Тогда, поскольку для выражения (8.1.6) выполняетсяпринцип оптимальности Беллмана (8.1.12), усечение оптимальной траектории ¯1 , . . . , ¯ (а точнее, соответствующие им стратегии) будет обеспечивать максимизацию суммы ожидаемых выигрышей в подыгре (¯1 ): (, ¯1 ) =11 − 0(︃ ∑︁∑︁∑︁=1 =1)︃ℎ (¯ ) .(8.6.43)=1Также имеем следующий вид функциональных уравнений для нахождения (, ¯1 ), ⊂ :(︃ )︃∑︁ ∑︁∑︁1ℎ ( ) .minmax (, ¯1 ) =¯,...,¯,...,1 − 0 1 1∖ =1∈(8.6.44)=1Далее находим вектор Шепли ℎ1 (1 ) в подыгре (¯1 ) по формуле (5.1.7).(k) На шаге находим значения (, ¯ ), (, ¯ ), ⊂ по следующимформулам (8.1.11), (8.1.14).
Вектор Шепли вычисляется по формуле (5.1.7).(l) На последнем шаге находим значения (, ¯ ), (, ¯ ), ⊂ какзначения одновременной игры Γ(¯ ) и соответствующей ей одновременнойантагонистической игры. Вычисляем вектор Шепли.Этап 2. Проверка динамической устойчивости.Вычисление компонент ПРД по формулам (8.2.30).
В том случае, когда все являются неотрицательными величинами, построенный вектор Шепли ℎ (¯0 )является динамически устойчивым. Если это не так, переходим к следующемуэтапу.Этап 3. Построение регуляризованного вектора Шепли.(1) Вычисляем новые выплаты игрокам на каждом шаге ¯ по формуле (8.4.37),где соответствует -й компоненте вектора Шепли ℎ в подыгре (¯ ).Глава 8.270Кооперативные многошаговые игры со случайным числом шагов(2) Используя полученный результат для новой ПРД, вычисляем РВШ ℎпо формуле (8.2.15) (или (8.2.16). Таким образом,{︃¯ = {ℎ } =ℎ¯0 + ¯1 (1 − 0 ) + .
. . + ¯(︃1−−1∑︁)︃}︃=0,=1,...,(8.6.45)является динамически устойчивым принципом оптимальности.8.7Сильно динамически устойчивые принципы оптимальности.Согласно предложенному выше определению, динамическая устойчивость ПО¯ 0 ) в игре (¯(¯0 ) означает, что для каждого дележа ¯ ∈ ¯(¯0 ) существуеттакая ПРД { ≥ 0}, что если выплаты в каждой вершине ¯ оптимальной траектории ¯ = ¯0 , ¯1 , . . .
, ¯ , . . . , ¯ (для бесконечного графа 2 ¯ =¯0 , ¯1 , . . . , ¯ , . . .) производятся в соответствии с ПРД { }, то игроки будутожидать, что в каждой подыгре (если игра не закончится раньше) (¯ ) ониполучат величину {¯ }, которая является оптимальной в смысле изначаль-¯ 0 ) в игре (¯но выбранного принципа оптимальности (¯0 ). В прикладномаспекте более важным являлось бы следующее, более сильное свойство: приосуществлении выплат согласно ПРД { ≥ 0}, игроки, заработав сумму ()¯ ), оптимальдо некоторого шага , могли бы выбирать любой дележ ¯ ∈ (¯¯ 0 ), и при этом всеный в том же смысле, что и изначально выбранный (¯равно получать в игре (¯0 ) выплаты (не равные {¯ } в общем случае) в¯ 0 ).соответствии с некоторым дележом ′ , принадлежащим (¯¯ 0 ) назовем сильно динамическиОпределение 8.7.1.
Принцип оптимальности (¯¯ 0 ) существует такая (ПРД)устойчивым (СДУПО), если для любого ¯ ∈ (¯Глава 8.Кооперативные многошаговые игры со случайным числом шагов271,..., = { }=1,..., ≥0, что=1,...,{′= ∑︁∑︁ + (1 −−1∑︁=0 =0¯ (0) ), )¯ } ⊂ ((8.7.46)=0¯ ).для любого дележа ¯ ∈ (¯Используя обозначение ⊕ : [ ⊕ = ( + , ∈ )], имеем эквивалентноеопределение:{−1 ∑︁∑︁ ⊕ (1 −=0 =0−1∑︁¯ )} ⊂ (¯¯ 0 ), )(¯(8.7.47)=0{∞ ∑︁∑︁¯ 0 ). = ¯ } ∈ (¯(8.7.48)=0 =0Данное определение СДУПО означает, что любое продолжение выплат после шага (при условии, что игра продолжилась после него) в соответствии¯ ) также приведет к некоторым выплатамс некоторым вектором ¯ ∈ (¯в игре (¯0 ), удовлетворяющим первоначально выбранному принципу оп-¯ 0 ).
Вопрос о «быстрой» проверке динамически устойчивоготимальности (¯принципа оптимальности на предмет сильно динамической устойчивости остается открытым, поскольку равенство (8.7.46) должно выполняться для любойподыгры, начинающейся с шага = 1, 2, . . . , (а для бесконечного графа 2 = 1, 2, . . .) и любого дележа ¯ ∈ (¯ ). Здесь мы не можем вывести аналитического выражения, подобного (8.2.28). Тем не менее, для рассмотреннойдискретной задачи может быть сформулировано утверждение, аналогичноеТеореме 6.6.2 и Следствию 6.6.2 для случая абсолютно непрерывной случайной величины, позволяющее значительно сузить круг поисков ПРД, обеспечивающих сильную динамическую устойчивость.
Рассмотрение всех возможныхвариантов даже при условии конечности игры является очень трудоемким.Однако, если выбранный игроками принцип оптимальности не является даже динамически устойчивым, имеет смысл сразу ориентироваться на регу-Глава 8.272Кооперативные многошаговые игры со случайным числом шаговляризацию этого принципа, приводящую к его сильной динамической устойчивости.8.8Регуляризованные сильно динамически устойчивыепринципы оптимальности¯ 0 ) на основе некоторого (ПО) (¯Построим СДУПО (¯0 ). Пусть (¯ ) ̸= ∅для всех подыгр вдоль оптимальной траектории ¯.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
