Диссертация (1145356), страница 33
Текст из файла (страница 33)
. . , максимизировала математическое ожидание суммарноговыигрыша всей коалиции , в то время как игроки, входящие в антикоалицию ∖ , минимизируют эту сумму. Введем функцию (, 0 ), ⊂ следующимобразом: (∅, 0 ) = 0, (, 0 ) = Val , ∖ (0 ), где Val , ∖ (0 ) — значение антагонистической игры , ∖ (0 ) (если оно существует). В том случае,когда значения антагонистической игры не существует, в качестве (, 0 )Глава 8.251Кооперативные многошаговые игры со случайным числом шаговбудем использовать "максимин": (, 0 ) =maxmin(︃ ∑︁ ∑︁∑︁ 0 , 1 ,..., ,..., 0 , 1 ,..., ∖ ∖ ∖ ={ }, ∈ , ∈ ={ }, ∈ , ∈ ∖ ∖∈ =0)︃ℎ ( ) .=0(8.1.5)Использование – характеристической функции (см.
ранее § 5.3.1) обусловлено построением супераддитивной характеристической функции. Если значение антагонистической игры , ∖ (0 ) существует, справедливо равенство:Val , ∖ (0 ) = max min ∖∑︁∈ (. . .) = min max ∖∑︁ (. . .).∈Значение характеристической функции (·) в случае общей кооперацииигроков (коалиция ) в игре (0 ), определяется по формуле (8.1.6), т.е.
(, 0 ) =∑︁max0 ,..., ,... ={ }, ∈ , ∈=1 (1 ,..., ,... ) =(︃ ∞ ∑︁∑︁∑︁=1 =0)︃ℎ (¯ ) .=0(8.1.6)Либо, используя формулу (8.1.3) для каждого игрока , получаем другой видзаписи (8.1.4): (, 0 ) =∑︁ℎ 0 (¯0 ) +∑︁=1ℎ 1 (¯1 ) (1 − 0 ) + . . . +=1∑︁(︃ℎ (¯ ) 1 −=1−1∑︁)︃ .=0(8.1.7)Построенная указанным выше способом характеристическая функция (, 0 )обладает свойством супераддитивности (5.1.2). Доказательство этого фактааналогично проведенному в работе [101]. Таким образом, согласно выражениям (8.1.6) и (8.1.5), мы определили кооперативную игру (0 ) как кооперативную игру лиц в форме характеристической функции .Обозначим через (0 ) множество всех дележей в игре (0 ), т.е.(0 ) = { = { } :∑︁=1 = (, 0 ), ≥ ({}, 0 ), = 1, .
. . , },Глава 8.252Кооперативные многошаговые игры со случайным числом шаговгде ({}, 0 ) — значение характеристической функции (, 0 ) для коалиции , состоящей из одного -го игрока (гарантированное математическое ожидание выигрыша игрока , действующего самостоятельно). Принципом оптимальности (или решением игры) в игре (0 ) будем называть любое фиксированное подмножество (0 ) множества дележей (0 ): (0 ) ⊂ (0 ).Предположим, что игра (0 ) развивалась вдоль оптимальной траектории¯ до определенной вершины ¯ .
В вершине ¯ , = 1, 2, . . . , игроки попадаютв подыгру (¯ ) на некотором подграфе графа с начальной вершиной¯ .Математическое ожидание выигрыша для игрока в подыгре (¯ ) имеетвид: ( , +1 , . . . , ) =1−1−1∑︀∑︁(︃ ∑︁ ==)︃ℎ ( ) .(8.1.8)=0Соответственно, математическое ожидание суммарного выигрыша всех игроков в подыгре (¯ ) вычисляется по формуле:∑︁ ( , +1 , . . . , ) =1−=1,...,1−1∑︀∑︁ ∑︁ =1,...,=(︃∑︁)︃ℎ ( ) .==0(8.1.9)Преобразовав (8.1.9), получим эквивалентное выражение для вычисления математического ожидания суммарного выигрыша в подыгре (¯ ):∑︁+1 ( , =1,...,,..., ) =∑︁ℎ ( )+(8.1.10)=1,...,−1∑︀∑︀1−1−∑︁ ∑︁=0=0+ℎ +1 (+1 )+ ... +ℎ (+ ).−1−1∑︀∑︀=1,...,=1,...,1−1−=0=0Таким образом, значение кооперативной подыгры (¯ ) (если все игрокиГлава 8.Кооперативные многошаговые игры со случайным числом шагов253действуют совместно оптимально), определяется по формуле: (, ¯ ) =∑︁max ,..., + ,...,+++={}, ∈ + , ∈, =0,−=1−1−1∑︀ ∑︁∑︁(︃ ∑︁=1 ==1 ( , .
. . , ) =(8.1.11)=1)︃ℎ (¯ ) ==0∑︀1−∑︁∑︁ =0=ℎ (¯ ) +ℎ +1 (¯+ ...++1 )−1∑︀=1,...,=1,...,1−=0−1∑︀1−∑︁=0.+ℎ (¯ )−1∑︀=1,...,1−=0Важно заметить, что для выражения (8.1.6) выполняется принцип оптимальности (уравнение) Беллмана (, 0 ) =∑︁ℎ 0 (¯0 )(︃+ 1−ℎ 1 (¯1 ) (1 − 0 ) + . . . +(8.1.12)=1=1++∑︁∑︁=1−1∑︁(︃ℎ −1 (¯−1 ) 1 −−2∑︁)︃(8.1.13) +=0)︃ (, ¯ ),∀ = 1, 2, . .
. , .=0Следовательно, если движение и дальше (после вершины ) развиваетсявдоль оптимальной траектории ¯, то на ее усечении ¯ , ¯+1 , . . . , ¯ выражение(8.1.9) достигает своего максимума, т.е. усечение оптимальной траектории ¯игры (0 ) является оптимальной траекторией в подыгре (¯ ).Характеристическая функция (, ¯ ), ⊆ в подыгре (¯ ) вводитсяаналогичнымуказанномудляигры(0 )способом:полагаем (∅, ¯ ) = 0 , а для вычисления (, ¯ ), ⊂ рассматриваем вспомогательную антагонистическую игру , ∖ (¯ ) между коалицией ⊂ , какГлава 8.254Кооперативные многошаговые игры со случайным числом шаговмаксимизирующим игроком, и коалицией ∖ , как минимизирующим игроком.
Следовательно, функциональное уравнение для вычисления значений характеристической функции (, ¯ ) имеет вид: (, ¯ ) =1−1−1∑︀maxmin¯ ,...,¯ ,...,∖∑︁ ∑︁∈ =(︃∑︁)︃ℎ ( ) .(8.1.14)=1=0Здесь для уменьшения громоздкости используются обозначения¯ ,...,¯= ∖∖ , . . . , ∖ ,¯ ,..., = ¯ , . . . , Значение (, ¯ ) вычисляется по формуле (8.1.11).Множества дележей (¯ ) в кооперативной подыгре (¯ ) определим следующим образом:(¯ ) = { = { } :∑︁ = (, ¯ ), ≥ ({}, ¯ ), = 1, . . . , },=1где — номер шага, с которого начинается подыгра. Принципом оптимальности (или решением игры) в подыгре ( ) будем называть любое фиксированное подмножество ( ) множества дележей ( ): ( ) ⊂ ( ).8.2Принцип динамической устойчивостив игре (0)Выполнение принципа оптимальности Беллмана (8.1.12) в многошаговой игре (0 ) не обеспечивает сохранение кооперации игроков на всех шагах игры.Допустим, что игроки перед началом игры договорились о реализации некоторого принципа оптимальности (0 ).
Пошаговому развитию игры соответствует «дискретное движение» вдоль оптимальной траектории ¯ (т.е. переходиз одной вершины графа в другую соответственно с уравнением (8.1.1)), наГлава 8.255Кооперативные многошаговые игры со случайным числом шаговкоторой по определению игроки получают наибольший ожидаемый выигрыш (, 0 ). Игроки рассчитывают, что после окончания игры заработанная ихсовместными усилиями сумма (, 0 ) будет разделена между всеми игроками таким образом, что дележ = { } будет принадлежать принципу оптимальности (0 ), о реализации которого они договаривались заранее.
Однакопри движении вдоль ¯ игроки попадают в подыгры (¯ ) с текущими начальными состояниями ¯ , = 1, 2, . . . , , в которых один и тот же игрок имеетразличные возможности.Определение 8.2.1. Пусть = { } ∈ (0 ), т.е. — оптимальный в смысле(ПО) (0 ) дележ. Если компоненты дележа представимы в виде = ∑︁∑︁ , = 1, . . . , ,(8.2.15)=0 =0 ≥0, = 0, 1, . . . , ,=0,...
то вектор-функцию = { }=1,..., называют процедурой распределения дележа (ПРД) в игре (0 ).В случае игры на конечном графе, ПРД представляет собой матрицу размерности × .Для наглядности распишем формулу (8.2.15) в эквивалентном ей виде: = 0 + 1 (1 − 0 ) +(︃)︃(︃)︃−1−1∑︁∑︁+ . . . + 1 − + . . . + 1 − ,=0(8.2.16)(8.2.17)=0() = 1, . . . , , ≥0.Более корректной была бы запись (¯ ), обозначающая выплату -му игроку в вершине ¯ графа при развитии игры вдоль оптимальной траектории¯ = (¯0 , ¯1 , . . . , ¯ , . . .), однако для уменьшения громоздкости будем использовать обозначение — выплата -му игроку на -ом шаге.
Таким образом, ПРДГлава 8.Кооперативные многошаговые игры со случайным числом шагов256определяет правило выплат на каждом шаге игры, согласно которому компоненты ожидаемого дележа = { }=1,..., распределяются вдоль оптимальнойтраектории ¯.Математическое ожидание суммы, полученной -ым игроком на первых (−1) шагах игры в соответствие с выплатами , = 0, 1, 2, . . . , − 1 обозначим ( − 1): ( − 1) =−1∑︁ (1=0−−1∑︁(8.2.18) ); (0) = 0 .=0Таким образом, игрок заработал величину (−1) до попадания в подыгру (¯ ). Попадая в подыгру (¯ ) (с вероятностью 1 −−1∑︀ ) игрок по-=лучит некоторый дележ .
Очень важным является вопрос, принадлежит ли ) тому же принципу оптимальности, чтоновый вектор = { } в игре (¯и вектор в игре (0 ). Если это не так, это будет означать, что игроки вподыгре (¯ ) не будут ориентироваться на выбранный изначально принципоптимальности (0 ), что поставит под угрозу сохранение кооперации. Следовательно, дележ станет не реализуемым или, другими словами, принципоптимальности (0 ) окажется несостоятельным во времени (динамическинеустойчивым). Дадим формальное определение динамической устойчивостирешения игры.¯ )̸=∅ во всех подыграх (¯Предположим, что (¯ ) (в противном случаеигроки не могут следовать данному принипу на всех шагах игры).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
