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

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

Подставляя (7.15), (7.16) в функцию выигрыша и используя

предположение о неубывании ценностей объектов, а также (7.14),

получаем

K(X*,J):

Ь-т

;

(1-л>1;=«>(о,

i-/.

и.

Таким образом, для всех i,j=\, ..., и выполняются неравенства

K(i,y*)^(p(l)^K(x*,j).

Тогда по теореме п. 7.1 х* и у* — оптимальные стратегии игроков

и v

= <p(l)

— значение игры. Игра решена.

§ 8. ДОМИНИРОВАНИЕ СТРАТЕГИЙ

Сложность решения матричной игры возрастает с увеличением

размеров матрицы А. Вместе с тем в ряде случаев анализ матрицы

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

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

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

размерности.

8.1.

Определение. Говорят, что стратегия х" игрока 1 до-

минирует

стратегию

х" в (тхп)-игре Т

, если для всех чистых

стратегий je(l, ..., и}

игрока

выполняются неравенства

x'a

>x"a

(8.1)

Аналогично, стратегия у' игрока 2 доминирует его стратегию у",

если для всех чистых стратегий /е{1, ..., т) игрока /

a,/W. (8.2)

Если неравенства (8.1), (8.2) выполняются как строгие, то говорят

строгом

доминировании.

Частным случаем доминирования страте-

гий является их эквивалентность.

Определение. Будем

называть стратегии

х" и х"

игрока

1 эк-

вивалентными

игре

если

для

ecexje{\,

..., л}

x'a

=x"a

и обозначать

х'~х".

Для двух эквивалентных стратегий х" и х" выполняется (для

каждого у

е У)

равенство

К(х',у) =

К(х",у).

Аналогично, стратегии у' и у" игрока 2 эквивалентны

(у'

~у") в игре

, если для всех /е{1, ..., т)

у'а^У'ъ.

Отсюда имеем, что для любой смешанной стратегии хеХ игрока

1 выполняется равенство

К(х,у') =

К(х,у").

Для чистых стратегий введенные определения трансформируют-

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

минирует стратегию i", а чистая стратегия / игрока 2 — стратегию

/' того же игрока, то для всех i'=l, ...,

т;

j=\, ..., и выполняются

неравенства

Это можно записать в векторной форме следующим образом:

аг^щ- и

d<id".

Эквивалентность пар стратегий i\

i"(i'~i")

nj',j"(j'~j") означает

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

(</

</).

Определение. Будем говорить, что стратегия х"(у") игрока

1 (2)

доминируема,

если существует стратегия

х'фх"(у'Фу")

этого

игрока,

которая доминирует

х"(у").

противном

случае

стратегия

х"(у")

недоминируема.

Аналогично стратегия х" (соответственно у") игрока 1 (2) назы-

вается

строго

доминируемой,

если существует стратегия х'00 этого

игрока, которая строго доминирует

х"(у"),

т. е. для всех

У=

n(i=

т) выполняются неравенства

x'd>x"d,

aiy'<а

{

у".

В противном случае говорят, что стратегия х"(у") игрока 1 (2)

недоминируема

строго.

8.2. Покажем, что игроки могут не использовать доминируемые

стратегии. Этот факт устанавливает следующее утверждение.

Теорема. Если в игре Т

стратегия х' одного из игроков до-

минирует

оптимальную

стратегию х*, то стратегия х' также

оптимальна.

Доказательство. Пусть, для определенности, х' я х* — стра-

тегии игрока 1. Тогда в силу доминирования

x'a

^x*a

для всех j=l, п. Откуда в силу оптимальности стратегии х*

(см.

п. 7.3) получаем

w^=min x*a

^min x'a

^min x*a

j j j

для Bcexj=

п. Поэтому согласно теореме п. 7.3 стратегия х' также

оптимальна.

Итак, оптимальная стратегия может быть доминируема лишь

оптимальной стратегией. С другой стороны, никакая оптимальная

стратегия не является строго доминируемой, поэтому игроки не

должны использовать строго доминируемые стратегии.

Теорема. Если в игре Т

стратегия

х* одного из игроков оп-

тимальна,

то х* —

недоминируема

строго.

Доказательство. Пусть, для определенности, х* — оптималь-

ная стратегия игрока 1. Предположим, что х* — строго доминиру-

ема, т. е. существует такая стратегия х'еХ, что

х'а

)

>х*а

)

у=1, 2, ..., и.

Откуда

min xV>min

x*a

i i

Но в силу оптимальности х*еХ выполняется равенство

min x*a

. Поэтому справедливо строгое неравенство

max min xa

x j

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

— значение игры (п. 7.3). Получен-

ное противоречие доказывает теорему.

Понятно, что обратное утверждение, вообще говоря, неверно.

Так, в игре с матрицей

1-я и 2-я чистые стратегии игрока 1 недоминируемы строго, но они

неоптимальны.

С другой стороны, интуитивно понятно, что если 1-я строка

матрицы А (/-й столбец) доминируема, то нет необходимости при-

писывать ей (ему) положительную вероятность. Таким образом, для

нахождения оптимальных стратегий вместо игры Г

достаточно

решить подыгру IV, где А' — матрица, получаемая из матрицы

А вычеркиванием доминируемых строк и столбцов.

Прежде чем перейти к точной формулировке и доказательству

этого результата, введем понятие

расширения смешанной стратегии

на

i-м

месте.

Если

х=(£

.... £

)еХ и l^i^m+l,jo расширени-

ем стратегии х на i-м месте будем называть вектор x

=(£

, .... £,_,,

О, &. —. £

)eR

m+i

. Так, расширением вектора (1/3, 2/3, 1/3) на 2-м

месте является вектор

(1/3,

0, 2/3, 1/3); расширением на 4-м месте —

вектор

(1/3,

2/3, 1/3, 0); расширением на 1-м месте — вектор (0, 1/3,

2/3,

1/3).

8.3.

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

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

Предположим,

что i-я

строка матрицы

доминируема

(т. е.

доминируема чистая

страте-

гия i

первого игрока)

пусть

—

игра

матрицей

А',

получаемой

из

вычеркиванием

i-й

строки.

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

утвер-

ждения.

Всякая

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

у*

игрока

2 в

игре

IV являет-

ся

оптимальной

и в

игре

Если х* —

произвольная

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

1 в игре Г

А'

и х' —расширение стратегии х* на i-м месте, то

х*

—

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

игре

Если i-я

строка матрицы

А строго

доминируема,

то произ-

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

х*

игрока

1 в

игре

может

быть

получена

из

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

х* в игре Г

рас-

ширением

на i-м месте.

Доказательство. Не нарушая общности, можно предполо-

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

х= (£

.... t,

) — смешанная стратегия, которая доминирует строку

т.

Если

£„=0,

то из условия доминирования для всех у

=1,

2, ...,

п получаем

т т—1

/-1 i-1

(8.3)

£ 6=1,

£2*0,

f=l,

...,m-l.

В противном случае (£

>0) рассмотрим вектор

х''=(£,[,

.... С)>

гле

i=m.

г,

(8.4)

Компоненты вектора неотрицательны

(б'^О,

i=\, ..., и)и^ £/=1-

i-1

С другой стороны, для

всеху'=1,

..., и имеем

tn 1

—

!£«<,>оц,-- Y 6

ИЛИ

m — i

m —1

—у

E 60u>flWr-r I &

—

j.i

1 — Cm

(-1

Учитывая (8.4), получаем

7B-1

ffl-1

E Ца-ц^вщ E ^'=a»>J=l

-, n,

i-i

m-l

(8.5)

X «=1, {/>0, i=l m-l.

i-l

Таким образом, всегда из доминирования m-й строки следует,

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

льных

m—

l строк [(8.5)].

Пусть

(х*.

y*)eZ(r

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

х*

= (£,\,

•••> £m-i),

У*

(ч*>

—.

*&•

Для доказательства утверждений 1, 2,

3 теоремы достаточно показать, что К(х'

y*)=v

»&

<^' <

«У«*+0

«ч>

(8.6)

J-\ i-l

для всех 1=1, ...,

т;

j—\,

..., п.

Первое равенство очевидно, а из оптимальности стратегий

(х*,

у*) в игре Г

л-

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

т—\

y4j<

A'** £ «</£'

f=1

•••>

«-

иУ=1, ..., и. (8.7)

;'-1

i-l

Из (8.7) очевидным образом следует правое из неравенств (8.6).

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

Цц/%<*4'-

Из неравенств (8.3), (8.5) получаем

л m—I

m —1

Е «wq/^E

««/&•

ч7< Е

*Zi=vx,

j-l

j-l i-l (-1

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

Для доказательства второй части теоремы (утверждение 4) до-

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

ки неравенства (8.3), (8.5) выполняются как строгие для всех j=

п.

Поэтому

я я т—1

Е °Ч/

< £ £ *» &

< »i«-

Тогда из теоремы п. 7.6 получаем, что у любой оптимальной

стратегии игрока / в игре Г^ /и-я компонента равна нулю. Теорема

доказана.

Сформулируем теорему о доминировании для второго игрока,

доказательство которой опустим.

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

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

Предположим,

что

j-й

сто-

лбец матрицы А доминируем и пусть

игра с матрицей А',

получаемой из А

вычеркиванием

j-го столбца. Тогда

справедливы

следующие

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

Всякая

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

х*

игрока

1 в

игре

' являет-

ся

оптимальной

и в игре Т

Если_у*

—

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

2 в иг-

ре Т'

)>j

—расширение стратегии у* на j-м месте, то у) —

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

2 в

игре

Далее,

если

j-й столбец матрицы А строго

доминируем,

то

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

у*

игрока

2 в игре Г

может

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

расширением

на

j-м

месте.

8.4. Обобщим полученные результаты. Подведем итоги. Теоре-

мы п. 8.3 дают алгоритм понижения размерности матрицы игры.

Так, если строка (столбец) матрицы не больше (не меньше) некото-

рой выпуклой линейной комбинации остальных строк (столбцов)

этой матрицы, то для нахождения решения игры можно эту строку

(столбец) вычеркнуть. При этом расширение оптимальных страте-

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

ной

игры.

Если неравенства выполнялись как строгие, то множество

оптимальных стратегий в первоначальной игре можно получить

расширением множества оптимальных стратегий усеченной игры,

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

можно потерять. Поясним применение данных теорем на примере.

Пример 14. Рассматривается игра с матрицей

"2 110"

А=

2 3 13

3 12 0

0 3 0 6

Так как 3-я строка а

превосходит первую

(а

> a

), то, вычеркивая

первую строку, получаем

[

2 3 1 3~|

3 12 0 1.

0 3 О 6 J

В этой матрице 3-й столбец а

не превосходит 1-й столбец а

Поэтому получаем

п:

U о б J

В последней матрице никакая строка (столбец) не доминируется

другой строкой (столбцом). Вместе с тем 1-й столбец а

превос-

ходит выпуклую линейную комбинацию столбцов а

а а

, так как

^1/2о

1/2в

поскольку 3> 1/2+ 1/23,

= 1/22+1/2.0,

3=0

•

1/2+1/2

•

Исключая 1-й столбец, получаем

В этой матрице 1-я строка эквивалентна смешанной стратегии

х=(0,

1/2, 1/2), поскольку

= 1/2-2+0-1/2,

= 0-1/2 +

6-1/2.

Таким

образом, исключая 1-ю строку, получаем матрицу

[::}

Оптимальные стратегии х* и у* игроков в игре с этой матрицей

равны х*=у*

(3/4;

1/4), при этом значение v игры равно 3/2.

Последняя матрица получена вычеркиванием первых двух строк

и столбцов, поэтому оптимальными стратегиями игроков в исход-

ной игре являются расширения указанных стратегий на 1-ми 2-м

местах, т. е. £

=5»?, =

(0,

0, 3/4, 1/4).

§ 9. ВПОЛНЕ СМЕШАННЫЕ И СИММЕТРИЧНЫЕ ИГРЫ

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

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

лишь существенные чистые стратегии игрока. При этом никакая

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

посредственно следует из теорем

9.1.

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

но для нахождения решения игры.

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

Стратегия

х (у)

игрока 1

(2)

называется вполне

смешанной,

если ее

спектр состоит

из

множества

всех

стратегий

игрока,

т. е. M

=M{N

=N).

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

(х*. у*)

называется вполне

смешанной,

если

стратегии

х* и у* —

вполне

смешанные.

Игра Г

называется вполне

смешанной,

если каждая ситуация равновесия

ней

является

вполне

смешанной.

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

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

Теорема.

Вполне смешанная (т

п)-игра

имеет единственную

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

(х*. у*) и

квадратную

матрицу

(т=п).

Если

фО,

то

матрица

невырожденная

. иА~

**=-—',

(9.1)

иА 'и

„. А~

У*=-^г>

(9-2)

иА *и

^=-^г- (9.3)

иА 'и

Доказательство. Пусть

х*

(£\,

....

Сд

(

l\-

—

...,

У*

— произвольные оптимальные стратегии игроков, a v

—

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

. Поскольку Г^ — вполне смешанная игра, х*

и у* — вполне смешанные стратегии, которые (и только они) явля-

ются решениями систем линейных неравенств п. 7.6:

, xu=l, x>0,j=l, ...,

п;

(9.4)

, yw=

у>0, i= l, ..., m, (9.5)

где и=(1, ..., l)eiT, w=(l, ..., 1)еЛ".

Покажем, что решение вполне смешанной игры (х*, у*) единст-

венно. Множества X*. У*, заданные (9.4) и (9.5), являются непус-

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

ние точки. Согласно второй из теорем п. 5.2 имеем

/n^rangfa

, ..., a",

и]=Т2Л%[А,

u]^m, (9.6)

H^rang^, ..., а

rang[^,

w]^n. (9.7)

Теперь из этой же теоремы следует, что множества X*.

имеют по

одной крайней точке и, следовательно, состоят только из них (как

выпуклые многогранники, содержащие единственную крайнюю точ-

ку).

Единственность решения (х*, у*) доказана.

Пусть

= 0. Тогда однородная система

,j=l, n

имеет ненулевое решение, откуда rang (A)<m. Так как

rang

[А,

]=т, имеем: rang

(Л)=/и—1.

Аналогично, из (9.5) и (9.7)

следует, что

тап$(А)=п —

Отсюда п=т.

Пусть v

^0. Тогда

rang (A)=rang

[A,

i^«] = rang|>4, и]=т,

rang (А)=rang

[A,

w]=rang

[A,

w]=n.

Отсюда имеем H=m=rang(.4), т. е. А — невырожденная матрица.

Система уравнений x*A=v

u имеет решение

x*=v

uA~

Запишем решение системы Ay*—v

y*=v

Так как x*u=l=v

uA~

u, то v.= .

л л

иА~

Теорема доказана.

Справедливо и обратное утверждение, доказательство которого

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

Теорема. Пусть в (тхт)-игре Г

матрица

А является

невыро-

жденной. Тогда, если игрок 2 имеет в Т

вполне

смешанную

оп-

тимальную

стратегию,

то

игрок

1 имеет

единственную

оптималь-

ную

стратегию

х* (9.1).

Если

игре

вполне смешанную

оптималь-

ную

стратегию

имеет игрок 1, то игрок 2 имеет

единственную

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

у* (9.2), при этом

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

равно

(9.3).

Пример 15.

((2

2)-игра.)

Пусть дана

х 2)-игра с матрицей

Га

\_л

1г

Произвольная смешанная стратегия х игрока 1 может быть записа-

на в виде *=(<!;, 1—£)> где

0<£<1.

Аналогично, смешанная страте-

гия игрока 2 имеет вид у=(п,

1—п),

где

0<»J<1.

Выигрыш в ситу-

ации (х, у) равен

K(x,y)=^[a

n + a

(\-n)]+^-0[^2i

l + ^22(

l)l

Предположим теперь, что в игре Г

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

в чистых стратегиях (в противном случае решение просто найти из

равенства минимаксов) и пусть х* = (£*,

—£*),

у*

(ч*,

— п*) —

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

и второго игроков. Ситуация (х*. у*) и игра Г

являются вполне

смешанными (<!;*> О и п*>0). Поэтому по теореме п. 9.1 в игре

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

которые являются решением системы уравнений

i'?* + (

-'?*)

22=^

)

«ц{'

+ (1-{*)«21=^.

12^*

(

-^*)«22

= ^-

Если добиваться, чтобы

фЬ

(например, если все элементы матри-

цы А положительны, то это неравенство вьшолняется), то решение

игры

'-_Ц

=—~—,

x*=v

uA \

y*=v

иА

где u=(l, 1). Так, легко проверить, что у матрицы А=\ ' ~ | нет

седдовой точки. Обратная матрица А~

равна

-4

= • Тогда

1^=1/3,

х*

(2/3,

1/3),

(1/3,

2/3).

9.2. Исследуем частный класс игр с матрицами специального

вида.

Определение. Игра Г

квадратной матрицей

называется

симметричной,

если матрица А —

кососимметричная,

т. е. если

(Х

— ctji

для всех i и

В этом случае все диагональные элементы матрицы А равны О,

т. е.

при всех i. Для кососимметричнои матрицы А всегда

выполняется условие А

= —

А.

Поскольку матрица А квадратная,

множества смешанных стратегий игроков совпадают, т. е. Х= Y.

Докажем теорему о свойствах решения симметричной игры Г^,

которая полезна при отыскании ситуации равновесия.

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

—

симметричная

игра.

Тогда

= 0

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

совпадают,

т. е.

Y*.

Доказательство. Пусть А — матрица игры и

хеХ—

произ-

вольная стратегия. Тогда хАх=хА

х= —хАх. Поэтому хАх=0.

Пусть (х*.

y*)eZ(A)—

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

— значение

игры. Тогда

х*Ау*

х*

Ау,

=x*Ay*^xAy*

для всех хеХ, ye

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

^x*Ax*

^y*Ay* = 0.

Откуда получаем v

= 0.