Диссертация (1145356), страница 34

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 34)

Вопросо непустоте принципа оптимальности в каждой подыгре вдоль оптимальнойтраектории является нетривиальным .¯ 0 ) назовем динамически устойОпределение 8.2.2. Принцип оптимальности (¯чивым (ДУПО) или состоятельным во времени, если для любого дележа ¯ ∈¯ 0 ) существует процедура распределения дележа { } > 0, ∈ {0, 1, . . .

, },(¯Глава 8.257Кооперативные многошаговые игры со случайным числом шагов ) по формулетакая, что вектор ¯ = ¯ , вычисленный для подыгры (¯{︀ }︀¯ =1−1−1∑︀(︃ ∑︁∑︁)︃ ,(8.2.19) = 1, . . . , ,===0принадлежиттомужепринципу¯ )(¯оптимальностивподыгре (¯ ).Напомним, что для игры на бесконечном графе 2 мы полагаем = ∞.¯ 0 )Определение ДУПО означает, что для каждого дележа ¯ из ДУПО (¯возможно определить такие пошаговые выплаты игрокам, равные { }, =0, 1, 2, . .

. , , что в любой подыгре (¯ ) усечение тех же самых выплат (т.е.выплаты { }, = , + 1, . . . , ) будет обеспечивать принадлежность де-¯ ), к которому принадлежитлежа к тому же принципу оптимальности (¯дележ ¯ в игре (0 ).¯ 0 ). Имеет место равенствоПусть ¯ ∈ (¯¯ =−1∑︁[︃(︃=0=∑︁ +=0[︃(︃ −1∑︁∑︁=0=[︃(︃ −1∑︁∑︁=0]︃)︃=0∑︁[︃(︃=)︃]︃ +=0)︃]︃ +(︃∑︁ =0[︃(︃ −1∑︁∑︁=−1∑︁1−]︃)︃)︃(︃ +=0)︃ (︃ −1∑︁=0)︃+=0∑︁ =[︃(︃ ∑︁∑︁=]︃)︃)︃]︃ .=(8.2.20)Учитывая определение динамической устойчивости (8.2.19) и обозначение (8.2.18),данное выше, путем несложных преобразований получаем¯ = ( − 1) + (1 −−1∑︁ )¯ .(8.2.21)=0Второе слагаемое представляет собой математическое ожидание выигрыша-го игрока в подыгре (¯ ) при условии, что игра не закончилась до шагаГлава 8.Кооперативные многошаговые игры со случайным числом шагов258¯ 0 ) для любого де.

Таким образом, в случае динамической устойчивости (¯лежа ¯ из него существует такая ПРД { } ≥ 0, что дележ ¯ может бытьпредставлен в виде (8.2.21).Понятно, что в общем случае для произвольного принципа оптимальностимы можем представить любой дележ из него в виде (8.2.21), если не накладывать требование о неотрицательности ПРД { }. Если на каком-то шаге игроку будет предписываться «выплата» = −^ , т.е. игрок должен будет не получить, а отдать величину ^ , сложно ожидать от данного игрокасохранение кооперации с остальными игроками.Для того, чтобы иметь удобный механизм проверки ПО на динамическуюустойчивость, необходимо получить аналитическое выражение для ПРД.

Последовательно рассмотрим формулу (8.2.21) для = 1, 2, . . . , , + 1, . . . , .Имеем:(︀)︀¯ = 0 0 + (1 − 0 ) 0 + ¯1 = 0 + (1 − 0 ) ¯1 ;(8.2.22)(︀)︀¯ = 0 0 + 0 + 1 1 +(8.2.23)(︀)︀+ (1 − (0 + 1 )) 0 + 1 + ¯2 = 0 + (1 − 0 ) 1 + (1 − (0 + 1 )) ¯2 ;...(︃¯ = 0 + (1 − 0 ) 1 + . . . +1−−2∑︁)︃(︃ −1 +1−=0−1∑︁)︃ ¯ ; (8.2.24)=0...(︃¯ = 0 + (1 − 0 ) 1 + . . . +1−−1∑︁)︃ ¯ .(8.2.25)=0Таким образом, согласно формулам (8.2.22), компоненты ПРД могут быть вычислены рекуррентно (используя вычисленные на предыдущих шагах выплаты):0 = ¯ − (1 − 0 ) ¯1 ;(8.2.26)Глава 8.Кооперативные многошаговые игры со случайным числом шагов1 =2591 ¯ 1 − (0 + 1 ) ¯21 − −0 ;1 − 01 − 01 − 0...−1=1−1−2∑︀1−−1∑︀1−=0−2∑︀¯ −=0¯ −1−=01−2∑︀0 −(8.2.27)=01−−3∑︀1 − 0=01−2−−...−;−2−2∑︀∑︀1−1−=0=1−1−1∑︀=01−∑︀1−=0−1∑︀¯ −=0¯+1 −1−=01−1∑︀0 −(8.2.28)=0−2∑︀1−1 − 0=01− − .

. . −−1 ;−1−1∑︀∑︀1−1−=0=0... =1−1−1∑︀1−∑︀1−=0−1∑︀¯ −=0¯+1 −1−=01−1∑︀0 −(8.2.29)=01−−2∑︀1 − 0=0−1 − . . . −−1 .−1−1∑︀∑︀1−1−=0=0В том случае, когда все полученные являются неотрицательными, принцип оптимальности (¯0 ) является динамически устойчивым. Поскольку вобщем случае гарантировать неотрицательность ПРД в указанных формулахнельзя, требуется произвести некоторое перераспределение пошаговых выплатГлава 8.Кооперативные многошаговые игры со случайным числом шагов260согласно указанному ниже алгоритму. Используя формулы (8.2.27) и (8.2.28),получаем аналитическое выражение для вычисления ПРД:−1∑︀ = ¯ − ¯+1 +1−¯+1 .=0Либо, в другой форме:=¯1−∑︀1−=0−1∑︀−¯+1 .=0На нулевом шаге ПРД вычисляется по следующей формуле:0 = ¯ − (1 − 0 ) ¯1 .На последнем шаге выплаты игроку , = 1, .

. . , имеют вид: = ¯ .Заметим, что на последнем шаге игрок получает дележ, вычисленный в одновременной игре Γ( ) (аналог терминального выигрыша).Таким образом, доказана следующая теорема.Теорема 8.2.1. Пусть (¯0 ) = {{ }=1 }. Пусть для каждого ¯ ∈ (0 ) ПРД = { }=1 , = 1, .

. . , вычисляется следующим образом:=¯1−∑︀1−=0−1∑︀−¯+1 ,(8.2.30)=00 = ¯ − (1 − 0 ) ¯1 ,(8.2.31) = ¯ .(8.2.32)Если ≥ 0, ∀ ∈ , ∈ {0, . . . , }, {¯ } ∈ (0 ), {¯ } ∈ (¯ ), то в игре (0 ) принцип оптимальности (0 ) является динамически устойчивым.Глава 8.Кооперативные многошаговые игры со случайным числом шагов261Заметим, что многошаговой игре с детерминированным числом шагов [99]соответствует распределение вероятностей 0 = 0, 1 = 0, . . .

, −1 = 0, = 1.Тогда формулы (8.2.26)-(8.2.29) представимы в виде0 = ¯ − ¯1 ;... = ¯ − ¯+1 ,(8.2.33)...−1 = ¯−1 − ¯ , = ¯ .Здесь наглядно можно убедиться, что условие неотрицательности ПРД не выполнено в общем случае: например, если игроки имеют только терминальныевыигрыши ℎ (·) ≥ 0 в последней вершине , а во всех предыдущих вершинахграфа получают ℎ (·) = 0, ∀ = 0, 1, 2, . . .

, − 1, гарантировать неотрицательность ПРД в формуле (8.2.33) нельзя.Таким образом, для проверки принципа оптимальности на динамическуюустойчивость нужно последовательно вычислить пошаговые выплаты однимиз указанных выше способов, согласно формулам (8.2.26)-(8.2.29) или (8.2.30),а затем проверить неотрицательность полученных . В том случае, когда всекомпоненты ПРД являются неотрицательными, выбранный игроками принципоптимальности является динамически устойчивым. В том случае, когда этоне так, необходимо провести регуляризацию по указанному ниже алгоритму,чтобы на каждом шаге игры (0 ) игрок получал такие выплаты ¯ , которые«обезопасили» бы его от отклонения от оптимальной траектории ¯.Глава 8.8.3Кооперативные многошаговые игры со случайным числом шагов262Введение новой характеристической функцииВ данном разделе предлагается к рассмотрению функция, которая удовлетворяет классическим свойствам характеристической функции (для непрерывных моделей см.

§ 6. 5). В дальнейшем она будет использоваться в качествехарактеристической функции регуляризованной игры.Аналогично § 6. 5 рассмотрим функцию ¯ (, 0 ), определяемую по формуле¯ (, ¯0 ) = ∑︁∑︁∑︀ (, ¯ ) )=1 ℎ (¯=0 =0 (, ¯ ).(8.3.34)Заметим, что¯ (∅, ¯0 ) = 0,¯ (, ¯0 ) = (, ¯0 ),¯ (1 ∪2 , ¯0 )≥¯ (1 , ¯0 ) + ¯ (2 , ¯0 ).Первые два свойства проверяется непосредственно, для доказательства последнего используется супераддитивность функции (, ¯0 ) (аналогично доказательству леммы 6.5.1 § 6.5). Следовательно, ¯ (, ¯0 ), ⊆ являетсяфункцией, обладающей классическими свойствами характеристической функции. Таким образом, верна следующая лемма.Лемма 8.3.1.

¯ (, ¯0 ), определенная по формуле (8.3.34), является характеристической функцией в кооперативном варианте игры (¯0 ).Аналогичным образом можно показать, что функция¯ (, ¯ ) =1−1∑︀−1=0 ∑︁∑︁= =∑︀ (, ¯ ) )=1 ℎ (¯ (, ¯ )является характеристической функцией в подыгре (¯ ).Глава 8.8.4Кооперативные многошаговые игры со случайным числом шагов263Регуляризованные динамически устойчивыепринципы оптимальностиПринцип оптимальности не обязательно является динамически устойчивым,поскольку в (8.2.30) нельзя гарантировать существование (ПРД) ≥ 0.

Перейдем к построению улучшенного (регуляризованного) принципа оптималь-¯ 0 ) на основе некоторого классического принципа оптимальности (¯ности (¯0 ),который будет обладать свойством динамической устойчивости. Предположим, что (¯ ) ̸=∅ во всех подыграх (¯ ). Определим для { } ∈ (¯ ), =1, . . . , , = 0, 1, 2, .

. . , вектор {¯ } по формуле (см. [112] для детермини-рованных моделей):¯ = ∑︁∑︁=0 =0∑︀ )=0 ℎ (¯ (, ¯ ) .(8.4.35)Нетрудно заметить, что {¯ } является распределением общего выигрыша (, ¯0 )в игре (0 ). Действительно,∑︁¯ ==1 ∑︁ ∑︁∑︁ℎ (¯ ) = (, ¯0 )=1 =0 =0Более того, справедливо следующее утверждение:Предложение 8.4.1.

Для ¯ , построенного по формуле (8.4.35), выполняется свойство индивидуальной рациональности: ¯ ≥ ¯ ({}, ¯0 ).Доказательство. Согласно Лемме 8.3.1, характеристическая функция регуляризованной игры имеет вид (8.3.34). Отметим, что поскольку являетсядележом в подыгре (¯ ), то ≥ ({}, ¯ ). Следовательно,¯ = ∑︁∑︁=0 =0∑︀ )=0 ℎ (¯ (, ¯ ) ≥≥ ∑︁∑︁=0 =0∑︀ ({}, ¯ ) )=1 ℎ (¯ (, ¯ )= ¯ ({}, ¯0 ).Глава 8.264Кооперативные многошаговые игры со случайным числом шаговТаким образом, вектор {¯ }, построенный по формуле (8.4.35), являетсядележом в игре ¯ (¯0 ), где ¯ (¯0 ) – некоторое расширение игры (¯0 ).Определим¯ 0 ) = {¯ : ¯ =(¯ ∑︁∑︁∑︀=0 =0 )=1 ℎ (¯ (, ¯ ) , = 1, .

. . , ,(8.4.36)∀ ∈ (¯0 )}.=0,1,...,Фактически, мы вводим новую (ПРД) = { }=1,..., , ≥0, обеспечивающую динамическую устойчивость:¯ = ∑︀ )=1 ℎ (¯ (, ¯ )(8.4.37).На последнем шаге , в случае игры на конечном графе , выплаты игрокамназначаются прежние:¯ = ,(8.4.38)∀ = 1, . . . , .Для того, чтобы показать это, рассмотрим подыгры (¯ ) и определим¯ =Очевидно, что¯ =−1 ∑︁∑︁=0 =0∑︀¯=1 1−1∑︀−1=0 ∑︁∑︁∑︀= = )=1 ℎ (¯ (, ¯ ).(8.4.39)= (, ¯ ). Кроме того, мы имеем:∑︀ −1−1 ∑︁∑︁ℎ(¯)ℎ (¯ )=1 + (1 − ) =1 + (, ¯ )(,¯)=0=0∑︀ ∑︁∑︁ℎ (¯ )+ =1 . (8.4.40)(,¯)=∑︀=Учитывая (8.2.18),(8.4.37) и (8.4.39), получаем¯ = ( − 1) + (1 −−1∑︁ )¯ .=0Таким образом, мы доказали следующую теорему.Глава 8.265Кооперативные многошаговые игры со случайным числом шагов¯ 0 ) представляет собой динамически устойТеорема 8.4.1.

Характеристики

Список файлов диссертации