Диссертация (1149192), страница 11
Текст из файла (страница 11)
Чтобы обойти эту проблему, используем процедуру распределения выигрыша, вычисленную по формуле в (3.2.11)0.537 0.078−0.107 xα (k),+ xαT (k) β1 (k) =k(k + 1)0.078 0.163831.06 0.144−0.216 xα (k).β2 (k) =+ xαT (k) k(k + 1)0.144 0.357(3.3.1)Заметим, что ηi(k) < 0, в силу того, что рассматривается проблема минимизации.Для выполнения устойчивости против иррационального поведения игроковдостаточно, чтобы выполнялось0.537 0.078 xα (k) ≤ 0,β1(k) − xαT (k) 0.078 0.1631.06 0.144 xα (k) ≤ 0.β2(k) − xαT (k) 0.144 0.357Эти неравенства выполнены для процедуры распределения выигрыша, β(k),вычисленной по формуле (3.3.1).84Глава 4Сетевые линейно-квадратичныедискретные игры c управляющей коалициейВ работе [52] рассматривается иерархическая линейно-квадратичная играс одним лидером.
Предполагается, что лидер может влиять на игру, выбираянекоторые параметры выигрышей других игроков - последователей, для достижения своих целей. Последователи объедены общей динамикой игры.В данной главе рассматривается аналог этой задачи, но лидером здесь является не один игрок, а коалиция. Игроки являются узлами некоторой ориентированной сети. Сеть отражает структуру влияния в некоторой организации,т.е.
наличие дуги от игрока i к игроку j означает что игрок i может влиятьна игрока j. Находится равновесие по Нэшу в этой игре, и рассматриваетсякооперативный вариант игры.4.1Постановка задачиРассмотрим линейно-квадратичную игру на сети G = (N, U ), где N – конечноемножество узлов сети, N = {1, 2 . . . , n}, U – множество пар (i, j), называемыхдугами, i ∈ N , j ∈ N . Узлами сети считаем игроков. Предполагаем, что сеть Gпредставляет структуру руководства или влияния некоторой организации.Перед началом игры определятся управляющая коалиция P .
В качестветакой коалиции, например, можно взять базу, т.е. коалицию включающую наименьшее число лиц, влияющих на каждого члена организации.Определение 17 ([11]). База B графа есть множество вершин, из которыхдостижима любая вершина графа и которое является минимальным, в томсмысле, что не существует собственного подмножества в B, обладающеготаким свойством достижимости.85Если в графе существует несколько баз, то в качестве управляющей коалиции можно взять их объединение.Для игроков, не входящих в управляющую коалицию, задается динамика,характеризующая состояние системы в каждый момент времени:x(k + 1) = Ax(k) +XBi ui(k),(4.1.1)i∈N \Pk0 ≤ k ≤ K < ∞,k0, K ∈ T+ ,x(k0) = x0 ,где x ∈ Rm – вектор-столбец, ui ∈ R – управление игрока i, i ∈ N \P ; A, Bi– матрицы размерности (m × m) и (m × 1) соответственно, x(k0) = x0 – начальное состояние. Пусть N \P = {i1 , .
. . , in−p}, Si = {j ∈ N \P : (i, j) ∈ U }– множество игроков из N \P , для которых существует ребро (i, j). Выигрышигрока i ∈ N \P обозначим через Ji(k0, x0, u), где u = (ui1 , . . . , uin−p ). Будемпредполагать, что выигрыш игрока i имеет вид:Ji(k0, x0, u, W ) =K−1XxT (k)Pix(k) + u2i (k)ri +u2j (k)wij −j∈Sik=k0−XXj:i∈Sju2j (k)wji +xT (K)Pix(K),∀i ∈ N \P, (4.1.2)где Pi – симметричные матрицы размерности (m×m), ri ∈ R, wij ∈ R. Здесь Pi ,ri – фиксированные параметры заданные в начале игры, wij – вес ребра (i, j),который задаётся управляющей коалицией на первом шаге игры, W – матрицавесов wij .
При этом wij ∈ M, где M – конечное множество значений весов. Каждый игрок стремится максимизировать свой выигрыш. Предполагается, что игроки выбирают только стратегии вида ui (k, x) = Mi (k)x, k0 ≤ k ≤ K, i ∈ N \P .Обозначим через GN \P игру между игроками, не вошедшими в коалицию, сдинамикой (4.1.1) и выигрышами (4.1.2).Влияние управляющей коалиции на ход игры заключается только в выборе весов {wij }i∈N \P,j∈N \P , характеризующих меру взаимодействия соответству-86ющих игроков.Тогда множество стратегий управляющей коалиции ΓP задаётся следующим образом:ΓP = {{wij }i∈N \P,j∈N \P :wij ∈ M,i ∈ N \P, j ∈ N \P }.Целью управляющей коалиции является максимизация суммарного выигрыша игроков, не вошедших в коалицию P .4.2Некооперативная играСчитаем, что игроки, не вошедшие в управляющую коалицию, играют индивидуально.
Игра протекает следующим образом:1. Управляющая коалиция выбирает стратегию γ ∗ ∈ ΓP , максимизирующуюсуммарный выигрыш игроков, не вошедших в коалицию в ситуации равноPEвесия по НэшуJi (k0, x0, uN E (W ), W ). Здесь uN E (W ) = (uNi1 (W ), . . . ,i∈N \PEuNin−p (W ))– ситуация равновесия по Нэшу в игре GN \P . Предполагается,что управляющей коалиции известно, что оставшиеся игроки выберут равновесные по Нэшу стратегии, и γ ∗ выбирается, учитывая это знание.2. Игроки, не вошедшие в управляющую коалицию, выбирают стратегии, соответствующие равновесию по Нэшу в игре GN \P , и получают выигрышиlJi(k0, x0, uN E , W ∗). Здесь W ∗ – матрица весов, задающаяся стратегией γ ∗,l ∈ (0, 1) – фиксированный параметр, характеризующий долю выигрыша,которую игроки оставляют себе, доля (1 − l) отдаётся управляющей коалиции.Для нахождения ситуации равновесия по Нэшу в игре GN \P переформулируем теорему о равновесии по Нэшу в линейно-квадратичной дискретнойигре, приведенную в [39].87Теорема 14.
Для того чтобы в игре GN \P существовало единственное вклассе допустимых равновесие по Нэшу необходимо и достаточно, чтобысистема матричных уравненийX(A+BiMiN E (k))T Θi (k + 1)(A+i∈N \PXBi MiN E (k)) − Pi − (MiN E )T riMiN E (k)−i∈N \PXXNET ∗NE∗−Mj (k) wij Mj (k) +MjN E (k)T wjiMjN E (k) = Θi (k),j∈Sij:i∈SjMiN E (k) = −(−ri + BiT Θi (k + 1)Bi)−1BiT ×X×Θ(k+1)(A+Bj MjN E (k)), k = k0, .
. . , K − 1,ij6=i,j∈N \P Θ (K) = −P , i ∈ N \Pii(4.2.1)имела единственное решение {MiN E (k), Θi (k)}, в виде вещественных матриц размерности 1 × m и m × m соответственно, где Θi (k) – симметричны для любого i ∈ N \P , для которого (−ri + BiT Θi(k + 1)Bi) > 0,i ∈ N \P.Тогда набор стратегийE{uN= MiN E (k)x,ii ∈ N \P }будет являться равновесием по Нэшу в игре GN \P , при этомJi(k0, x0, uN E , W ∗) = −xT0 Θi(k0 )x0,Значит, выигрыши игроков i ∈ N \P имеют вид:−lxT0 Θi (k0)x0.3. Управляющая коалиция получает выигрышi ∈ N \P.(4.2.2)88(1 − l)XJi(k0 , x0, uN E , W ∗) =i∈N \PX(l − 1)xT0 Θi (k0)x0.i∈N \P4. Для каждого игрока i ∈ P определим величину bi равную числу дуг (i, j),где j ∈ N \P .
Тогда выигрыш игрока i задаётся по следующему правилу:ϕ∗iXbi= P (1 − l)Jj (k0, x0, uN E , W ∗) =bij∈N \Pi∈PbPi (l − 1)xT0 Θj (k0)x0.bii∈P4.3Кооперативная играПредположим теперь, что игроки, не вошедшие в управляющую коалицию, могут объединяться с целью максимизации суммарного выигрыша.Опишем ход игры в этом случае:1. Управляющая коалиция выбирает стратегию γ̂ ∈ ΓP , максимизирующуюсуммарный выигрыш игроков, не вошедших в коалицию, при условии, чтоониPтожемаксимизируютсвойсуммарныйвыигрышJi (k0, x0, û(W ), W ).
Здесь û(W ) = (ûi1 (W ), . . . , ûin−p (W )) – набор стра-i∈N \Pтегий в игре GN \P , максимизирующий суммарный выигрыш. Предполагается, что управляющей коалиции известно, как будут вести себя другиеигроки, и γ̂ выбирается, учитывая это знание.2. Игроки, не вошедшие в управляющую коалицию, выбирают стратегии,Pмаксимизирующие суммарный выигрышJi (k0, x0, u, Ŵ ). Коалицияi∈N \P89N \P получает выигрыш V (N \P ) = lPJi (k0, x0, û, Ŵ ). Здесь Ŵ – мат-i∈N \Pрица весов, задаваемая стратегией γ̂, û – набор стратегий, на котором достигается максимум, l ∈ (0, 1) – фиксированный параметр, характеризующий долю выигрыша, которую игроки оставляют себе, доля (1−l) отдаётсяуправляющей коалиции.Пусть B = (B1, . . .
, Bn ), P =PPi ,i∈N \PM̂ (k) i1M̂ (k) = . . . ,M̂in−p (k)XXwji −wij = wi,j,i∈SjR=ri 1 + w i 1Oj∈SiO...ri 2 + w i 2 . . .OO............OO. . . rin−p + win−p.Для нахождения в игре GN \P набора стратегий, максимизирующего суммарный выигрыш, сформулируем теорему:Теорема 15. Для того чтобы в игре GN \P существовал единственныйPнабор стратегий, максимизирующийJi (k0, x0, u, Ŵ ), необходимо иi∈N \Pдостаточно, чтобы:(a) Cистема матричных уравнений(A + B M̂ (k))T Θ̂(k + 1)(A+B M̂(k)) − P − M̂(k)T RM̂(k) = Θ̂(k),M̂(k) = −(−R + B T Θ̂(k + 1)B)−1B T ×× Θ̂(k + 1)A, k = k0, . .
. , K − 1, Θ̂(K) = −P,90имела решение {M̂(k), Θ̂(k)}, в виде вещественных матриц размерности (n−p)×m и m×m соответственно, где Θ̂(k) – симметричны.(b) (−R + B T Θ̂(k + 1)B) – положительно определенные матрицы, k =k0 , . . . , K − 1.Тогда набор стратегий{ûi = M̂i (k)x,доставляет максимумPi ∈ N \P }(4.3.1)Ji(k0, x0, u, Ŵ ), при этомi∈N \PXJi (k0, x0, u, Ŵ ) = −xT0 Θ̂(k0)x0,i ∈ N \P.i∈N \PЗначит,V (N \P ) = −lxT0 Θ̂(k0)x0.3. Как и в главе 2, в качестве решения кооперативной игры будем рассматривать ES-вектор [45]. Тогда игроки, не вошедшие в управляющую коалициюполучают выигрыш:ξi (k0, x0) =Pv(N \P ) −Ji(k0, x0, uN E , W ∗) i∈N \Pl Ji (k0, x0, uN E , W ∗) +. (4.3.2)n−pСогласно теоремам 14 и 15 в рассматриваемом классе игр ES-вектор можетбыть вычислен по формуле:ξi (k0, x0) =− l xT0 Θi (k0)x0 +xT0 Θ̂(k0)x0 −Pi∈N \Pn−pxT0 Θi (k0)x0 .
(4.3.3)914. Управляющая коалиция получает выигрыш(1 − l)XJi(k0, x0, û, Ŵ ) = (l − 1)xT0 Θ̂(k0)x0.i∈N \P5. Для каждого игрока i ∈ P определим величину bi равную числу дуг (i, j),где j ∈ N \P . Тогда выигрыш игрока i задаётся по следующему правилу:XbiPϕ̂i =(1 − l)Ji(k0, x0, û, Ŵ ) =bii∈N \Pi∈PbPi (l − 1)xT0 Θ̂(k0)x0.bii∈P4.4ПримерРассмотрим игру на сети G = (N, U ) (рисунок 4.1):Рис. 4.1: G=(N, U).Можно показать, что для данного графа существует три базы: {x3, x11},92{x3, x12}, {x3, x13}. Тогда в качестве управляющей коалиции возьмем объединение баз P = {x3, x11, x12, x13}.Для остальных игроков задаётся динамика игры:x(k + 1) = x(k) +Xui(k),0 ≤ k ≤ 2.i∈N \PM = {1, 2}, т.е.
веса дуг могут принимать только значения 1 или 2.Будем предполагать, что выигрыши игроков имеют вид:J1(k0, x0, u, W ) =K−1X0, 1x2(k) − u21(k) + u22(k)w12 + u26(k)w16 + u25 (k)w15−k=k0− u22(k)w21 − u25(k)w51 +0, 001x2(K),J2(k0, x0, u, W ) =K−1X0, 1x2(k) − 2u22(k) + u21 (k)w21 − u21(k)w12 +k=k0+ 0, 001x2(K),J4(k0, x0, u, W ) =K−1X20, 1x (k) −5u24(k)+u29 (k)w49−u27(k)w74k=k0++ 0, 001x2(K),J5(k0, x0, u, W ) =K−1X0, 1x2(k) − u25(k) + u21(k)w51 + u27(k)w57 − u21 (k)w15−k=k0− u26(k)w65 +0, 001x2(K),J6(k0, x0, u, W ) =K−1X0, 1x2(k) − 3u26(k) + u210(k)w6,10 + u28(k)w68 + u25 (k)w65−k=k0− u21(k)w16 +0, 001x2(K),93J7(k0, x0, u, W ) =K−1X0, 1x2(k) − 2u27(k) + u24 (k)w74 − u29(k)w97 − u25(k)w57−k=k0− u28(k)w87 +0, 001x2(K),J8(k0, x0, u, W ) =K−1X0, 1x2(k) − 4u28(k) + u27(k)w87 + u210(k)w8,10 − u26 (k)w68−k=k0− u210(k)w10,8 +0, 001x2(K),J9(k0, x0, u, W ) =K−1X0, 1x2(k) − u29(k) + u27(k)w97 − u24(k)w49 +k=k0+ 0, 001x2(K),J10(k0 , x0, u, W ) =K−1X0, 1x2(k) − 2u210(k) + u28 (k)w10,8 − u28 (k)w8,10 −k=k0− u26(k)w6,10 + 0, 001x2(K),Тогда решая систему (4.2.1) и максимизируя суммарный выигрыш игроковпо параметрам wij , получаем, что оптимальная стратегия управляющей коали∗∗∗∗∗∗∗∗ции: w12= 1, w21= 2, w15= 2, w51= 2, w16= 1, w6,10= 2, w68= 1, w65= 2,∗∗∗∗∗∗∗w57= 1, w74= 1, w49= 2, w97= 2, w8,10= 2, w10,8= 1, w87= 1.Значения MiN E , соответствующие оптимальным стратегиям, на каждомшаге представлены в таблице 4.1:94Таблица 4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
