Коэффициентные критерии при выборе концепций равновесия (на примере линейно-квадратичной игры двух лиц)

Те, кто занимался теорией устойчивости по Ляпунову, помнят коэффициентные условия устойчивости. Суть в том, что по знакам коэффициентов дифференциального уравнения, соотношениям между ними иногда можно судить об устойчивости невозмущенного движения. В предлагаемой читателю статье такая же идея осуществлена для линейно-квадратичной бескоалиционной игры двух лиц. Именно по свойствам коэффициентов функций выигрыша решаются два вопроса: а) существует или отсутствует равновесие по Бержу или по Нэшу; б) если существует, то каков его явный вид.

Постановка задачи и вспомогательные сведения

Рассматриваем бескоалиционную линейно-квадратичную игру

Г = /{ 1,2 } , { X_t = R” ' }     , { f_t ( x i ,x 2) }^ A

= 1,2                   ' ^1,2

Особенность Г2 в том, что отсутствуют ограничения на множества стратегий Xi , именно стратегиями i-го игрока могут быть любые ni -векторы-столбцы xi (из ni -мерного евклидова про- странства Rni с обычной евклидовой нормой ||·|| и скалярным произведением); функция выигрыша игрока i пусть имеет вид f (x1, x 2) = x1 AjX1 + 2 x1 Btx 2 + x 2 Ctx 2 + 2 atxx + 2 ctx2, (i = 1,2),              (1)

где постоянные симметричные матрицы A_i , C_i , прямоугольная B_i и постоянные вектора a_i , c_i соответствующих размерностей; штрих сверху означает операцию транспонирования; det A означает определитель матрицы A ; далее A <0 (>,≤) означает, что квадратичная форма z ₁ ^' Az определенно отрицательна (соответственно положительна, неположительна); будем использовать следующие операции дифференцирования билинейных форм по векторному аргументу [1, с.13–16]:

А Гx1 Bx2 ] = Bx2    f А" Гx1 Bix21 = Bix1 Л Гx1 A-x1 ^ Оx1                 у ^ Оx 2                    Оx1 d2 x’Aixi = 2 A■; dx 2 = 2 Aix1 л    Г 2 a1 x11 = 2 a1 |, dx. Г      1 J 1                 У (2) для скалярной функции V(x) и векторного к-мерного аргумента x достаточными условиями реализации max V(x) = V(x*) будут xE Rk Жуковский В.И., Бельских Ю.А., Самсонов С.П. Коэффициентные критерии при выборе концепций равновесия (на примере линейно-квадратичной игры двух лиц) 1) ^^(x)    = grad Т( x )|,_ ^= 0 k, xx ux x=x * (3) 2) d2^

Для бескоалиционных игр вида Г2 в последние годы получили распространение два вида равновесий по Нэшу и по Бержу.

Игра Г2 происходит следующим образом: каждый i-ый игрок, не объединяясь с другим в коалицию, выбирает свою стратегию xi е Rn (i = 1,2), в результате образуется ситуация x = (x1,x2)е Rn (n = n1 + n2). На множестве таких ситуаций определены функции выигрыша fi(x) для i-го игрока, значение которой определяет выигрыш i-го игрока.

Определение.Ситуация x = (xB, xB) называется равновесной по Бержу в игре Г₂, если max   f(x||x^B) = f (xB)(i = 1,2),

(xx⁵ )eR^{n —}n      "

а ситуация x = (xe, x2) - равновесна по Нэшу, если max f(xe L) = f(xe)(i = 1,2);

xi е Rn¹

здесь f1(x ||z1) = f1(z1,x₂), f2(x ||z₂) = f2(x1, z₂). Каждое из двух равновесий имеет свои позитивные и негативные свойства [2–4]. Зная коэффициенты в функциях выигрыша (1), выясним какое из равновесий существует, а какое отсутствует, и, если существует, найдем его явный вид.

Равновесная по Бержу ситуация

С учетом (1) и с помощью (3) приходим к следующему достаточному условию существованию равновесной по Бержу ситуации в игре Г2.

Утверждение 1.Пусть в игре Г₂

A2 < 0, C1 < 0(4)

и det [ C - B1 A-1 B2 ] * 0.(5)

Тогда равновесная по Бержу ситуация x = (xB, xB) примет вид x1 = — A2 B2 ГC1 — B1A2 B21 (B1A2 a2 — c1) — A2 a2,

L 1      ]

xB = [ C1 — B1 A— B 2 ] (B1 A— a 2 — C1).

Доказательство.Согласно определению, ситуация x = (xB, xB) равновесия по Бержу игры

Г2, формализуется двумя равенствами max f1(xB, x2) = f,(xB ), x2eRn г

df^(x1 , x 2)

dx 2

В x 2 = x 2

= 2 B1 x^ + 2 C1 x 2 + 2 C1 = 0 n 2,

d f1^(x1 ,x2)

dx 2²

= 2 C1.

в x₂=x₂

Аналогично для второго равенства из (7)

df 2( x1 ,x 2 ) dxj = 2 A2 xB + 2 B2 xB + 2 a 2 = 0 ni, =B xi = xi

Математика

d2f2(x1 ,x2 )      = 2A dx2     х BxB

Х1= Х1

Так как согласно (4), матрицы C₁< 0 и A2< 0 , то ситуация равновесия по Бержу (xB, xB) игры

Г2 найдется из матричной системы неоднородных линейных уравнений

A2 xi + B2 x2 = ^-a 2,

• _ B1 xB + C₁ x 2B = - c₁.

Согласно импликации [ A2 < 0] ^ [det A2 * 0] ^ I 3A- I. Умножим первое из (8) слева на A-, от- куда сразу получим xB = -A-B2xB - A-1 a2.(9)

Подставляя его во второе уравнение из (8), приходим к

[ Ci - Bi A- B 2 ] xB = - ci + Bi A 21 a 2

или xB = [ Ci - Bi A 21 B2 ]-1( Bi A 21 a 2 - Ci).(11)

Здесь учтено, что, согласно (5), будет (det I C1 - B1 A-B 2 I * 0) ^ (3(C1 - B1 A-x B 2) 1), и поэтому, умножая обе части (10) слева на |C1 - B1A21 B2 J , приходим к справедливости (11). Подставляя найденные x2B в (9), получим первые равенства из (6). ■

Аналогично, решая систему (8) умножением второго уравнения слева на C-¹, получаем

Утверждение 2. Пусть в игре Г2 выполнены требования (4) и det | A2 - B2 C-1 Bi J * 0.                                  (12)

Тогда равновесная по Бержу ситуация xB = (xB , xB) имеет вид xB = |A2 - B2Ci-1 Bi ]-1 (B2Ci-1 ci - a2), xB = - Ci-1 Bi IA2 - B2 Ci-1 Bi ]-1 (B 2 Ci-1 Ci - a 2) - CT1 Ф

Замечание 1. Система (8) имеет единственное решение при A2 < 0 и C1 < 0. Авторам уда- лось привести вид одного из них к другому.

Равновесная по Нэшу ситуация

Приведем аналогичные результаты для равновесия по Нэшу. Здесь уже для игры Г2 вместо

• (7)    следует использовать равновесную по Нэшу ситуацию xe = (x^, x2), которая определяется

двумя условиями max fi(xi,xe) = fi(xe), max f2(xe,x2) = f2(xe).

xieR^Я1                               x₂e r”²

Достаточными условиями реализации (13) будут gradxfxi,x 2 )L _= =dfi( x1 , x2)     = 2 A1 xe + 2 Bix e + 2 ai = 0 nx,

• ¹               ixi=xi         dx₁         _ _e                                          ¹

xi=xi gradx f2(x1e,x2)     e

2                x₂= x₂

^df2^(xe,^x2) dx -2

= 2 B 2 xee + 2 C2 x 2e + 2 c 2 = 0 n 2, e x2 = x2

Жуковский В.И., Бельских Ю.А., Коэффициентные критерии при выборе концепций равновесия Самсонов С.П.                              (на примере линейно-квадратичной игры двух лиц)

М^ - 2А₁< 0, дX]

д f2(X1 ,x2) _ дX 22

< 0.

Из первых двух условий получаем матричную систему линейных алгебраических неоднородных уравнений с постоянными коэффициентами

A] xe + B] x2 _ — a],

_ B2 ^x2⁺C2 ^x 2^_ - c 2^.

С учетом A₁< 0 и C₂< 0, как и в случае утверждений 1 и 2, приходим к справедливости следующих двух утверждений.

Утверждение 3.Пусть в игре Г₂

А₁< 0, C₂< 0                                       (14)

и det [C2 - B2 А— В1 ] Ф 0.                                (15)

Тогда ситуация равновесия по Нэшу x² = (x2, x2) имеет вид

• ^X1 ^{_ — А}1 B1 [ C2 ^—B 2 ^А1 B1 ] ⁽B2 ^А1 a1 ^—c 2^{) — А}1 ^а1,

X2 _ [C2 — B2А—¹ B1 ] ^—1(в2А—¹ a1 — c2).

Утверждение 4. Пусть в игре Г2 выполняются ограничения (14) и det [ А1 — B1 C21 B2 ] Ф 0.                                  (16)

Тогда равновесная по Нэшу ситуация x2 = (xf, x2) имеет вид x2e _ [А1 — B1C21 в2 J1 (B1C21c2 — a1), x2 _ — C21 в2 [А1 — B1C2—1 в2]—1 (B1C21 c2 — aj — C21 c2.

Критерии отсутствия равновесия

Приведем довольно любопытное утверждение, которое позволяет отсекать игры, в которых не существует равновесия по Бержу или (и) по Нэшу.

Лемма 1. Если в игре Г2 матрица А1 > 0, то не существует x1, такого, что при каждом фиксированном x2 имело место бы равенство max f(x1,x 2) _ f1(x1,x 2),                                   (17)

• x1E R^B1

т.е. в этом случае максимума по x₁е Rn¹ функции f _(x₁,x₂) не существует.

Доказательство. «Заморозим» какую-либо стратегию x2 е Rn2 второго игрока. Тогда функцию выигрыша первого игрока можно представить в виде f1(x1, x 2) _ x1 А1 x1 + 2 x^( x 2) + ^( x 2), где ni-вектор-столбец ^(x2) и скалярная величина ^(x2) зависят только от «замороженного» x2.

По условию леммы матрица А1 > 0 (определенно положительна). Тогда характеристическое уравнение det ^А1 — ЕП1^] = 0 (ЕП1 - единичная n 1хn 1-матрица) имеет n 1 вещественных положительных корней (A1 симметрична) и, кроме того, x1 А1 x1 > 1* ||x11|2 Vx1 е Rn1,                                      (18)

Математика

где Л > 0 наименьший из указанных корней. Максимума в (17) не существует, если, каким бы большим ни было число m > 0, существует стратегия x1(m, x₂) е Rn¹, такая, что f,(x1(m, x₂), x₂) > m . В силу (18) последнее неравенство имеет место, если

Л*|| x1( m, x₂)||²+ 2 x1( m, x₂)^( x₂) + ^( x₂) > m.                            (19)

Будем искать решение x1(m, x2) неравенства (19) в виде x1(m,x 2) = Pen^                                      (20)

где число в > 0 построим ниже, а en - вектор размерности n1, все компоненты которого равны единице.

Подставляя (20) в (19), получаем для нахождения в неравенство

^Л^n + 2^в(en ^⁽x2))+ ^⁽x2) - m > 0.

Поэтому при любых постоянных

в > в+

I en.^ ^x 2)| ⁺ V ⁽en^^{( x} 2⁾⁾²

Л П1

+ Л n11^( x₂) - m|

и стратегиях первого игрока x1(m, x₂) = ве_П1 выполнено f1(x1(m, x₂), x₂) > m и поэтому максимума в (17) не существует.

Замечание 2.Тогда, с учетом (17) в игре Г₂ при A1 > 0 не существует равновесной по Нэшу ситуации. Отсюда и из утверждения 1 получаем

• 1.    Если в игре Г₂ матрицы A1 > 0 или (и) C₂> 0, а также А₂< 0 , C1 < 0 и выполнено (5), то в игре Г2 не существует равновесие по Нэшу, но существует равновесие по Бержу, причем ситуация равновесия по Бержу имеет вид (6).

• 2.    Если A₂< 0 , C₁< 0 , имеет место требование (5) или (12) и A₁> 0 или (и) C₂> 0 , то существует равновесие по Бержу, но отсутствует равновесие по Нэшу.

• 3.    Если A1 < 0, C₂< 0, имеет место требование (15) или (16) и A₂> 0 или (и) C1 > 0 , то существует равновесие по Нэшу, но отсутствует равновесие по Бержу.

• 4.    Если A1 > 0 или (и) C₂> 0 и A₂> 0 или (и) C1 > 0 , то в Г₂ не существует как равновесия по Нэшу, так и по Бержу.

• 5.    Если A₂< 0 , C₁< 0 , A₁< 0 , C₂< 0 и требования (5) или (12), а также (15) или (16), то в Г2 существует как равновесие по Нэшу, так и по Бержу.

Аналогично,

Заключение

Итак, рассмотрели линейно-квадратичную бескоалиционную игру двух лиц без ограничений

(Xi е Rn1 (i = 1,2)) и функциями выигрыша f_ (x1, x2) = x1 A1 x1 + 2 x1 B1 x 2 + x 2 C1 x 2 + 2 ax x1 + 2 c1 x 2, f,(x1, x 2) = x1 A2 x1 + 2 x1 B 2 x 2 + x 2 C2 x 2 + 2 a 2 x1 + 2 c 2 x2;

штрих сверху означает операцию транспонирования, A_i - симметричная постоянная порядка n1 х n1 матрица, C_i - симметричная постоянная порядка n₂х n₂ -матрица, B_i - постоянная прямоугольная n1 х n₂ матрица, a_i (c_i) - постоянные n1 (соответственно, n₂)-вектора (i = 1,2); A > 0 (<) означает, что квадратичная форма x1 Ax определенно положительна (соответственно, отрицательна); кванторы: Я - существование, V - общности, — - отрицание.

С помощью утверждений 1-4 можно также сформулировать коэффициентные условия существования равновесий в игре Г2 (см. таблицу).

Как пользоваться таблицей?

Шаг 1. Прежде всего, проверить знакоопределенность матриц A1, A2, C1 и C2; пусть, напри- мер, матрицы A1 < 0 , C2 < 0 (определенно отрицательны), а A2 > 0 (определенно положительна).

Жуковский В.И., Бельских Ю.А., Коэффициентные критерии при выборе концепций равновесия Самсонов С.П. (на примере линейно-квадратичной игры двух лиц)

Шаг 2. Найти соответствующую строку в таблице (условия A1< 0, C₂< 0 и A2 > 0 занимают третью строку) и проверить невырожденность соответствующей в 5-ом столбце матрицы (15), т.е. det [C2 - B2 A-B1 ] Ф 0.

Шаг 3. Сразу из столбцов 6 и 7 таблицы следует, что в такой игре Г₂ не существует равновесия по Бержу, но имеется равновесие по Нэшу при любых матрицах C₁, B_i соответствующих размерностей и векторах a_i , с_i .

Явный вид такого равновесия по Нэшу приведен в утверждении 3 (см. дополнительный столбец впереди таблицы).

Коэффициентные условия существования равновесий

Утверждение	Существует одно из равновесий					РБ	РН
1	A1 > 0	A2 < 0	C1 < 0		(5)	3	-3	V C2, Bi, ai, ci
2		A2 < 0	C1 < 0	C2> 0	(12)	3	-3	VA1, Bi, ai, ci
3	A1 < 0	A2 > 0		C2< 0	(15)	-3	3	V Ci, B-, ai-, ci
4	A1 < 0		C1 > 0	C2< 0	(16)	-3	3	VA2, В,, ai, с,
	Не существуют равновесия
	A1 > 0	A2 > 0				-3	-3	V Ci, Bi, ai, ci
	A1 > 0		C1 > 0			-3	-3	VA2, C2, Bi, ai, ci
		A2 > 0		C2> 0		-3	-3	VAi, Ci, Bi, ai, ci
			C1 > 0	C2> 0		-3	-3	VA1, A2, Bi, ai, ci
	Существуют оба равновесия
	A1 < 0	A2 < 0	C1 < 0	C2< 0	(5) и (15)	3	3	VBi-, ai-, c,
	A1 < 0	A2 < 0	C1 < 0	C2< 0	(12) и (16)	3	3	VBi, ai, ci