Петросян Л.А. и др. Теория игр

Подождите немного. Документ загружается.

Из леммы п. 4.3 следует, что (х*. y*)eZ(Y

) — ситуация равно-

весия в игре Гл< в смешанных стратегиях, а значение игры равно

—

l/e—p. Теорема доказана.

Неформально факт существования решения в классе смешанных

стратегий означает, что игроки всегда могут снять неопределен-

ность выбора стратегии, с которой они столкнулись перед началом

игры, рандомизируя множество чистых стратегий. Следует отме-

тить,

что не всегда в антагонистических играх существует решение

в смешанных стратегиях. Примеры таких игр с бесконечным числом

стратегий приведены в § 3, 4 гл. И.

Заметим также, что доказательство теоремы конструктивно, по-

скольку сводит решение матричной игры к задаче линейного про-

граммирования, при этом алгоритм решения игры Г

- следующий.

По матрице А строится строго положительная матрица

А =

А'

В,

где В={р

p,j=p>0.

Решаются задачи линейного программирования (6.1), (6.2).

Находятся векторы х, у и число в [см. 6.3)].

Строятся оптимальные стратегии игроков 1 и 2 соответ-

ственно

х*

= х1в,у*=у/в.

Вычисляется значение игры Г^

Пример 8. Рассмотрим матричную игру Г

, определенную мат-

рицей

-Б

Соответствующие ей задачи линейного программирования имеют

следующий вид:

min^ +

^2,

max^+f/2,

4£

+2£

>1,

4ij!<l,

>1,

2»h

+ 3ij

<l,

Заметим, что эти задачи в эквивалентной форме могут быть записа-

ны для ограничений типа равенств:

min^ +

ij,

max ^+7/2,

4£

+2£

-£з =

4^ +

^з

3£

-£4=1> 2^ +

+ ^=1,

£i>0,

^0, Z

>0, £

>0, п^О,

>0,

т]

>0,

Таким образом, любой метод решения задач линейного про-

граммирования может быть приспособлен для решения матричных

игр.

Наиболее распространенным методом решения таких задач

является симплекс-метод, систематическое изложение которого мо-

жно найти в [16, 25, 73].

6.2. Задача линейного программирования в определенном смыс-

ле эквивалентна матричной игре Г

. Действительно, рассмотрим

следующие прямую и двойственную задачи линейного програм-

мирования

minxu

xA^w, (6.9)

х>0;

maxyw

Ау^и, (6.10)

у>0.

Пусть X и Y

—

множества оптимальных решений задач (6.9) и (6.10)

соответственно. _ Обозначим (11в)Х={х/в\хеХ},

(\1в)¥={у1в\уе¥},в>0.

Теорема. Пусть Г

— (тхп)-игра с

положительной матрицей

А (все

элементы положительны)

и даны две

двойственные

задачи

линейного программирования

(6.9) и (6.10).

Тогда имеют

место сле-

дующие

утверждения.

Обе задачи линейного программирования имеют решение

(ХФ0 и УФ0),

при

этом

0=min хм=max yw.

х у

Значение

игры

равно

стратегии

х*

= х16,у*=у1в,

являются

оптимальными,

где хеХ

— оптимальное решение

прямой

задачи

(6.9),

ayef—

двойственной задачи

(6.10).

Любые оптимальные стратегии

х*еХ*

y*eY*

игроков

мо-

гут

быть построены указанным

способом,

т. е.

Х*

(1/в)Х,

Г*

(1/в)?.

Доказательство. Утверждения 1, 2 и включения

(\l&)XczX*,

l/OYczY*

непосредственно следуют из доказательства теоремы

п. 6.1.

Покажем обратное включение. Для этого рассмотрим векторы

х*

(Л*.

•••>

&)еХ*

и х=(^, ....

где х=0х*. Тогда для

всех

jeN

имеем

=Bx*a

> 0(1/0)= 1,

при этом х>0, так как б>0 и х*>0. Поэтому х— допустимое

решение задачи (6.9).

Вычислим значение целевой функции

хи=вх*и

в=min xu,

т. е.

хеХ—

оптимальное решение задачи (6.9).

Аналогично доказывается включение

Y*cz(l/0)Y.

Теорема до-

казана.

§ 7. СВОЙСТВА ОПТИМАЛЬНЫХ СТРАТЕГИЙ И ЗНАЧЕНИЯ ИГРЫ

Рассмотрим свойства оптимальных стратегий, которые в ряде

случаев помогают находить значение игры и ситуацию равновесия.

7.1.

Пусть (х*, у*)еХх Y— ситуация в смешанных стратегиях

в игре Г^. Оказывается, что для проверки ситуации (х*, у*) на

равновесность неравенства (4.7) достаточно проверять не для всех

хеХ и yeY, а лишь для ieM и jeN, поскольку справедливо

следующее утверждение.

Теорема. Для того

чтобы ситуация

(х*, у*)

была равновесной

в игре Т

, а число v=K(x*. у*) —значением игры Т

необходимо

и достаточно выполнение следующих

неравенств

для всех ieM

njeN:

K(i,y*)*ZK(x*,y*)^K(x*,j), (7.1)

Доказательство. Необходимость. Пусть (х*, у*) — ситу-

ация равновесия в игре Г^. Тогда

К(х,у*)^К(х*,у*)*Щх*,у)

для всех

xeX.yeY.

Поэтому, в частности, для щеХл и^е

имеем

K(i,

y*)=K(u

y*)^K(x*,

у*НЦх*.

) = K(x*,j)

для всех ieM

ujeN.

Достаточность. Пусть (х*, у*) — пара смешанных стратегий,

для которой выполняются неравенства (7.1). Пусть также х=(£

...

..., £

)еХя y

(rj

....

q„)e

Y— произвольные смешанные стратегии

игроков

и 2 соответственно. Умножая первое

второе неравенства

(7.1) на

г\

}

соответственно и суммируя, получаем

£ {,Щ у*)^ Цх*. у*)% Ъ = К(х*,

у*);

(7.2)

£ r,jK(x*,j)>K(x*, у*) £

r,j=K(x*,

у*). (7.3)

j-l

У-i

При этом имеем

£ Mi, >*)=*(*,

у»);

(7.4)

/-1

t^^*,;)

^*,j;).

(7.5)

j-i

Подставляя (7.4), (7.5) в неравенства (7.2) и (7.3) соответственно

и учитывая произвольность стратегий хеХя ye Y, получаем равно-

весность ситуации (х*. у*).

Следствие 1. Пусть (f, j*) —

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

в игре Г

Тогда ситуация

(/*, j*)

равновесна

и в

игре

Пример 10. (Решение игры на

уклонение.)

Предполагается, что

игроки выбирают целые числа / и

между

п,

а игрок

выигрыва-

ет величину

а.

1Л

=\1—

j\,

т. е. расстояние между числами / и/

Пусть первый игрок придерживается стратегии х* = (

, 0, ...

..., 0,

). Тогда

K(x*,j)=\l2\\-j\

l/2\n-j\

\l2(j-l)

ll2(n-j)=(n-W

для всех 1</^и.

а) Пусть n=2k+1 — нечетно. Тогда игрок 2 имеет чистую стра-

тегию

(п +1 )/2 = к +1 такую, что

o^ = |i-(n +

l)/2|

= |i-*-l|<b=(n-l)/2

для всех /=1, 2, ..., п.

б) Предположим, что п = 2к — четно. Тогда игрок 2 имеет та-

кую стратегию

у*

(0,

0, ...,

, 0, ..., 0), где

г\

=Ч

>7*

rij =

0,j^k

l,j^k,

что

Щ У*)

1/21i-k|.+1/21i-k-11<1/2*+ l/2(fc-1) = (л-1)/2

для всех 1</<и.

Теперь, используя теорему, нетрудно убедиться, что значение

игры v =

(n—1)/2,

игрок / имеет оптимальную стратегию х*, а оп-

тимальная стратегия игрока 2 равна

j*,

если

и=2£+1,

и у*, если

п =

2к.

7.2. Приведем результаты, являющиеся непосредственным след-

ствием теоремы п. 7.1.

Теорема. Пусть Г

—

(тхп)-игра. Для того чтобы ситуация

смешанных стратегиях

(х*, у*)

была равновесной

в игре Г

, необ-

ходимо и

достаточно выполнение равенства

max K(i, у*) = min K(x*. j). (7.6)

Доказательство. Необходимость. Если (х*. у*) — ситуа-

ция равновесия, то согласно теореме п. 7.1 имеем

K(i,y*)^K(x*,y*HK(x*,j)

для всех /б{1, ..., m},je{l, ...,

и}.

Поэтому

K(i,y*HK(x*,j)

для каждого i и/ Предположим противное, т. е. (7.6) не выполнено.

Тогда

max Щ,

у*)

< min

K(x*.

j).

Следовательно, имеют место неравенства

К(х*. у*)= £ £Щ

y*)*Z

max Щ, у*)< min K(x*,j)^

^£ri;K(x\j) =

K(x*,y*).

j-1

Полученное противоречие и доказывает необходимость утвержде-

ния теоремы.

Достаточность. Пусть пара смешанных стратегий (х, у) тако-

ва, что max K(i, y)=min K(x, j). Покажем, что в этом случае

/ j

(х, у) — ситуация равновесия в игре Г

Справедливы соотношения

min Щ, j)^^fjj

K(x,

J)=К(х, у) =

= £ №• Ж max Щ у).

Поэтому имеем

Щ, JO^max

K(i,

y)=K(x, y)=min K(j, x)^K(x,j)

i J

для всех

1«%

i^m и^.</<и, тогда по теореме п. 7.1 (х, у) — ситуация

равновесия в игре Г^.

Из доказательства следует, что любое из чисел в (7.6) равно

значению игры. _

7.3.

Теорема. Для

матричной

игры Y

справедливы следующие

соотношения:

max min

K(x,

j)=v

=min max K(i, у), (7.7)

x j у i

причем экстремумы по смешанным стратегиям

хиу в (7.7)

достига-

ются

на

оптимальных стратегиях

игроков.

Теорема является следствием теорем п. 3.4, 7.2, и ее доказатель-

ство предоставляем читателю.

7.4. Теорема. В

матричной

игре Г

множества

оптимальных

смешанных стратегий

X* и Y*

игроков

являются

выпуклыми

много-

гранниками.

Доказательство. Согласно теореме п. 7.1 множество X* явля-

ется множеством всех решений системы неравенств

'^v

,jeN,

хи=1,

х>0,

где и=(1, ..., \)eR

, v

—значение игры. Таким образом, X*—

выпуклое многогранное множество (п. 5.1).

другой стороны,

Х*<^Х,

где X

—

выпуклый многогранник (п. 5.3). Поэтому X* —

ограничено. Следовательно, по теореме п. 5.3 множество X* — вы-

пуклый многогранник.

Аналогично доказывается, что

У*

— выпуклый многогранник.

7.5.

6 качестве примера использования теоремы п. 7.3 приведем

геометрическое решение игр

двумя стратегиями

одного

из

игроков

((2

и)-

и (т х

2)-игры).

Такой подход в литературе также

называется

графоаналитическим

методом решения игр. В основе

графоаналитических методов лежит свойство оптимальных страте-

гий х* и у* доставлять внешние экстремумы в равенстве

»4=max min K(x,j)=mm max K(i, у).

J У I

Пример 11.

((2

п)-игра).

Рассмотрим игру,

которой игрок

1 имеет две стратегии, а игрок 2 — и стратегий. Матрица имеет вид

[

«12 -

1»"|

22 "•

2nJ

Пусть игрок 1 выбрал смешанную стратегию х=(£,

—£),

а иг-

рок 2 чистую стратегию jeN. Тогда выигрыш игрока 1 в ситуации

(х,

равен

Kix.j^faMl-Ovy.

(7.8)

Геометрически он представляет собой прямую в координатах (€,

К).

Таким образом, каждой чистой сратегии

соответствует своя

прямая. Графиком функции

H(£)=mmK(.x,j)

является нижняя огибающая семей-

ства прямых (7.8). Эта функция вог-

нута как нижняя огибающая семей-

ства вогнутых (в данном случае ли-

нейных) функций (п. 5.5). Точка £*,

в которой достигается максимум фу-

нкции

Н{£)

по

[0,

1],

и дает требу-

емое оптимальное решение

х*

(£*,

1 —

£*)

и значение игры v

=H(£,*).

Для определенности рассмотрим

игру с матрицей

~ 2 1 4 О

Для каждого j=

2, 3, 4 имеем:

К(х, 1)=-£ +

/фс,

2£+1,

/фс,

3;=-3^+4, Дх, 4J=4£. Нижняя

огибающая #(£) семейства прямых

ис

1 {Щх, j)} и сами прямые К(х, j),

j=\,

2, 3, 4, изображены на рис.

Максимум #(£*) функции //(О находится на пересечении первой

и четвертой прямых. Таким образом, £* — решение уравнения

Откуда получаем оптимальную стратегию

х*

(2/5,

3/5) игрока

1 и значение игры

—

S/5.

Оптимальную стратегию игрока 2 най-

дем из следующих соображений. Заметим, что в рассматриваемом

случае К(х*. 1)=К(х*. 4)=«< =

8/5.

Для оптимальной стратегии

= (tj\, г\

, т/

) должно выпол-

няться равенство

K{x*.

у*)

ц\

К(х*. l)

ri'

К{х*, 2)+т/

К(х*.

+ т,

Цх», 4).

При этом К(х*, 2)>8/5, К(х*, 3)>8/5, следовательно,

7/2

1/3

О,

г\\,

т/4

можно найти из условия (7.1)

ц\ + 4т,;=

8/5,

27,1

= 8/5.

Таким образом,

7/1

= 4/5 и т/4=1/5 и оптимальная стратегия игрока

2 равная* =

(4/5,

0, 0, 1/5).

Пример 12.

((т

Ту-игра.)

В этом примере Две стратегии имеет

игрок 2, а игрок 1 — т стратегий. Тогда матрица А имеет вид

^а

1Х

а,

*21

«•22

т1 0^2

Анализ этой игры проводится аналогично. Действительно, пусть

==(?/,

—

TJ)

— произвольная смешанная стратегия игрока 2. Тогда

выигрыш игрока 1 в ситуации (i, у) равен

K(i, у)=ацГ1 + а

(1-г1) = (ап-а,п)г1 + аа-

График функции K(i, у) — прямая. Рассмотрим верхнюю огиба-

ющую этих прямых, т. е. функцию

H(ri)=max

[(a,,

- а

)п

aj.

Функция

H{r\)

выпуклая (как верхняя огибающая семейства выпук-

лых функций).

Точка минимума п* функции Н(п) дает оптимальную стратегию

у*

(?/*,

l —

ri*)

и значение игры v

=H(n*) = min Н(п).

,, „ „

<J6

[0. 1]

7.6. Приведем результат, полезный при отыскании решения

игры.

Теорема.

Пусть

х*

= (£\,.... О яу* = (п\,...,

п'^

—

оптимальные

стратегии

в игре Г

и v

—

значение

игры.

Тогда для любого i, при

котором

K(i,

y*)<v

имеет

место равенство

£*=0, а для любого

такого,

что

<K(x*,j),

имеет место равенство

п]=0.

Обратно,

если

£*>(), то

K(i,

y*)=v

если

n)>Q,

то K(x*,j)=v

Доказательство. Допустим, что для некоторого /

еД/ выпол-

нено K(i

y*)<v

и при этом £*

#0. Тогда получаем, что

K(i

,y*K<v

Для всех ieM

K(i,

y*)^v

поэтому

K(i,y*)£^v

Следовательно,

К(х*.

y*)<v

что противоречит тому, что v

— зна-

чение игры. Вторая часть теоремы доказывается аналогично.

Этот результат является аналогом теоремы о дополняющей

нежесткости [73] или, как ее еще называют, канонической теоремой

равновесия для задачи линейного программирования [25].

Определение.

Чистая стратегия

ieM(jeN)

игрока

1 (2)

назы-

вается

существенной

или

активной

стратегией,

если существует

оптимальная стратегия

х*

(£,\,

....

\*„)

(у*

(п\,

.... п

)) этого

игрока,

для

которой

£>0 (fy>0).

Из определения и последней теоремы следует, что для каждой

существенной стратегии i игрока 1 и любой оптимальной стратегии

y*eY*

игрока 2 в игре Г^ выполняется равенство

K(i,y*)=ao>*=v

Аналогичное равенство имеет место для любой существенной

стратегии j eN игрока 2 и оптимальной стратегии х* еХ* игрока 1

K(x*,j)

x*=v

Если для чистой стратегии ie M

смешанной стратегии уе У выпол-

няется равенство a{y=v

, то говорят, что стратегия i

уравновешива-

ет смешанную стратегию у в игре Г^.

Таким образом, в данной терминологии теорему можно перефо-

рмулировать следующим образом. Если чистая стратегия игрока

существенна, то она уравновешивает любую оптимальную страте-

гию противника.

Знание спектра оптимальной стратегии упрощает нахождение

решения игры. Действительно, пусть

— спектр оптимальной

стратегии JC* игрока 1. Тогда каждая оптимальная стратегия

у*=

(г\\,

....

г\*„)

игрока 2 и значение игры v удовлетворяют системе

неравенств

aor*=v,

ieM*.,

При этом в спектр М* любой оптимальной стратегии х* могут

входить лишь существенные стратегии.

7.7. В заключение параграфа приведем аналитическое решение

игры «нападение — защита» (см. пример 4 п. 1.3)

Пример 13. Рассмотрим игру с(лхи) матрицей А

7*1*1 Ч ... Tj

чЯ

2^2

А.

Здесь т,>0 — ценность, а 0</?,<1—вероятность поражения

объекта Q, /=1, 2, ..., л, при условии, что он защищен. Пусть

<т

<...<т

. Определим функцию ср от целых чисел 1, 2, ...

..., п следующим образом:

?(*) = [£ (WO^-lj^Ml-u)}-

, (7.9)

и пусть /е{1, 2, ..., л} — целое число, доставляющее максимум

функции

(р(к),

т. е.

(р(1)= max q>(k).

к~\, 2,

(7.10)

Установим свойства функции

(р(к).

Обозначим символом R один

из знаков отношения порядка {>, =, <}. В этом случае

<p(k)R(p(k+\) (7.11)

тогда и только тогда, когда

•z

R(p(k),

k=\, 2, ..., п-1, т

= 0. (7.12)

Действительно, из (7.9) получаем

<№

О-А)"

, ,.

,. ,

1Ч

, (1-АГ

fofl-A)}-

fod-ft)}-

i-Jfc+1 j-Jt-fl

Тогда имеем

И-ll ."-

" +?(*)=.(*+!)• (7.13)

Е Mi-ft»"'

i«*+l

Заметим, что коэффициент в (7.13), стоящий после квадратных

скобок, положительный. Поэтому из (7.13) получаем эквивалент-

ность соотношений (7.11) и (7.12).

Теперь так как

q>(l)^(p(l—l)

или <р(/)>ф(/+1) (в этом случае

т,_1<ф(/—1) или т,>ф(0), то из соотношений (7.10), (7.11) имеем

неравенство

т,_,<ф(0<т

(7.14)

Найдем оптимальные стратегии в игре Г^. Напомним, что мы

предполагаем выполненными неравенства т

<т

^...^т

. Тогда оп-

тимальными смешанными стратегиями

х* = (£,\,

....

£*

)

y* =

(t]\,

.... r\J игроков 1 и 2 соответственно являются следующие:

{

0, «=1, .... /-1,

/" (7 15)

Wi-ft)]"

fed-/»/)]-

'='--.

«;

•

f<W=i

/-1,

^ ЦТ

-Ф((Я/М1-ДЙ, у-/, .... и.

(- J

а значение игры равно

«л

<?(%>•

Действительно, ^'^0, i=

2,...,

п и £ £*=

1 •

Из определения <р(/)

и (7.14) получаем, что rjj^0,j=l, 2, ..., ли^ ^*=1-

Пусть K{x*,j) — выигрыш игрока 1 в ситуации

(x*,j),

аналогич-

но

K(i,

у*) — выигрыш в ситуации (i, у*).