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

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

матрицы

А =

{а

}, где ау=К(х

yj),

(i,j)eMxN,

y)eXxY,ieM,

jeN (отсюда и название игры — матричная). При этом игра Г ре-

ализуется следующим образом. Игрок 1 выбирает строку геМ,

а игрок 2 (одновременно с ним) — столбец j eJV. После этого игрок

1 получает выигрыш а

, а второй — (—а

). Если выигрыш равен

отрицательному числу, то речь идет о фактическом проигрыше

игрока.

Игру Г с матрицей выигрышей А обозначим Г^ и назовем

(тхл)-игрой (по размерности матрицы А). Если из изложения

понятно, об игре с какой матрицей идет речь, то индекс А будем

опускать.

Нумерация стратегий в матричной игре может производиться

различными способами, поэтому каждому отношению порядка,

строго говоря, соответствует своя матрица. Таким образом, конеч-

ная антагонистическая игра может быть описана различными мат-

рицами, отличающимися друг от друга лишь порядком строк и сто-

лбцов.

1.3. Пример 1.

(Оборона города.)

Этот пример известен в литера-

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

«игра полковника Блотто»

[4].

Полковник Блот-

то имеет т полков, а его противник — п полков. Противник защи-

щает две позиции. Позиция будет занята полковником Блотто, если

на ней наступающие полки окажутся в численном превосходстве.

Противоборствующим сторонам требуется распределить полки

между двумя позициями.

Определим выигрыш полковника Блотто (игрока 1) на каждой

позиции. Если у него на позиции полков больше, чем у противника

(игрока 2), то его выигрыш на этой позиции равен числу полков

противника плюс один (занятие позиции равносильно захвату одно-

го полка). Если у игрока 2 полков на позиции больше, чем у игрока

то игрок 1 теряет все свои полки на этой позиции и еще единицу

(за потерю позиции). Если обе стороны имеют одинаковое число

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

не получит. Общий выигрыш игрока 1 равен сумме выигрышей на

обеих позициях.

Игра, очевидно, антагонистическая. Опишем стратегии игроков.

Пусть, для определенности, т>п. Игрок

имеет следующие страте-

гии:

(т,

0) — послать все полки на первую позицию, x

=(m— 1,

1)—(т—

полков послать на первую позицию, а один — на вто-

рую,

(т—2,2),...,

(1, т

—

1),

=(0,

т). Противник (игрок

2) имеет такие стратегии: у

(п,

0), у

(п

—

1), ..., у„

(0,

и).

Пусть игрок 1 выбрал стратегию

а игрок 2 — стратегию у

Вычислим выигрыш а

игрока 1 в этой ситуации. Поскольку т>п,

на первой позиции выигрывает игрок 1. Его выигрыш равен л-И

(единица — за удержание позиции). На второй позиции — ничья.

Поэтому а

= и +

Вычислим а

. Так как т>п—\, то на первой

позиции выигрыш игрока 1 равен

п—1

=и. На второй позиции

выигрывает игрок 2. Поэтому проигрыш игрока 1 на этой позиции

равен единице. Таким образом, а

=л

—1.

Рассуждая аналогично,

получаем

=n—J+1

— 1

=n—j, l^J^n. Далее, если

т—

\>п, то

=я +

+ 1=л +

= и-1 + 1=и, ot

=n-j+\-\-\=n-j-\,

2<у'<и. В общем случае (для любых m и л) элементы

ijt

i=0, m,

;=0,

л матрицы выигрышей вычисляются следующим образом:

я+2,

если

m—i>n—j,

i>j,

п—

j+\, если

m—i>n—j,

i=j,

n—j—i,

если

m—i>n—j,

i<j,

—m+i+j, если

m—i<n—j,

i>j,

j+1,

если

m—i=n—j,

i>j,

—m—2, если

m—i<n—j,

i<j,

—i—

если

m—i=n—j,

i<j,

—m+i—l, если

m—i<n—j,

i=j,

a,j=K(x„

yj)

О если

m—i=n—j,

i—j.

Так, при /я=4, и=3, рассмотрев всевозможные ситуации, полу-

чим матрицу выигрышей А этой игры:

=*1

*э

х*

Уо У1 У г Уъ

"421 0"

13 0-1

-2 2 2-2

-10 3 1

_ 0 1 2 4_

Пример 2.

{«Игра

на уклонение») Игроки 1 и 2 выбирают целые

числа i и

между

и и, при этом игрок

выигрывает величину

\i—j\.

Игра антагонистическая. Матрица выигрышей этой игры квадрат-

ная,

размера

(п

и),

где

ау=

\i—j\.

Так, если л=4, то матрица А игры

принимает вид

А =

"о

Пример 3. (Дискретная игра типа дуэли.) Игроки продвигаются

навстречу друг другу на п шагов. После каждого сделанного шага

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

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

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

шись на k шагов, равна fc/n

(к^п).

Стратегия игрока 1(2) заключается в принятии решения стрелять

на 1-м (/-м) шаге. Пусть i<j и игрок 1 принимает решение стрелять

на /-м шаге, а игрок 2 — на у-м шаге. Тогда выигрыш a

игрока

1 определяется формулой

» Л Л J n(i-j)+ij

Таким образом, выигрыш а^ — это разность вероятностей пораже-

ния противника и собственной гибели в дуэли. В случае i>j первым

стреляет игрок 2 и <х

—

Если же i=j, то полагаем а

=0. Так,

если положить п=5, то матрица этой игры, умноженная на 25,

имеет вид

-3

-1

-7

;

-7

-5

-11

-2

-15

-5

Пример 4. (Игра «нападение — защита».) Пусть игрок 1 намерен

атаковать один из объектов с

, ....

с„,

которые имеют положитель-

ные ценности т

>0,..., т„>0. Игрок 2 защищает один из этих объек-

тов.

Будем считать, что если атакован незащищенный объект с,, то

он с достоверностью уничтожается (игрок 1 выигрывает т,), а защи-

щенный — поражается с вероятностью

>j8/>0 (объект с

(

выдержи-

вает нападение с вероятностью

1 —

/J/>0),

т. е. игрок

выигрывает (в

среднем)

i= l, 2, ..., и.

Тогда задача выбора объекта нападения (для игрока

и объекта

защиты (для игрока 2) сводится к матричной игре с матрицей

выигрышей

'РхЧ

А =

0Л

••Дл

Пример 5. (Игра

дискретного

поиска.) Имеется и ячеек. Игрок

2 прячет предмет в одной из п ячеек, а игрок 1 хочет его найти. При

проверке г'-й ячейки игрок 1 тратит т,>0 усилий, при этом вероят-

ность найти предмет в г'-й ячейке (если там он спрятан) равна

0<Д<1,

г=1, 2, ..., п. Если предмет найден, то игрок 1 получает

доход а. Стратегиями игроков являются номера ячеек, в которых

игроки соответственно прячут и ищут предмет. Выигрыш игрока

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

ными на поиск предмета. Таким образом, задача поиска и прятания

предмета сводится к матричной игре с матрицей выигрышей

А =

•otft-т,

-т,

-т.

<*Pi-ii

-Ч

-т„...

а.Рп—4

Пример 6.

(Поиск «шумного» объекта.)

Предположим, что игрок

1 ведет поиск подвижного объекта (игрок 2) с целью его обнаруже-

ния. Игрок 2 преследует противоположную цель (т. е. стремится

уклониться от обнаружения). Игрок 1 может двигаться со скоростя-

ми а, =

а,—2,

Ъ,

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

= Х

Дальность действия средства обнаружения иг-

рока 1 в зависимости от скоростей движения участников игры

приведена в матрице

Pi Рг Рг

aj |~4 5 6~|

Z>=aJ 3 4 5

2 3J

Стратегиями игроков являются скорости движения, а в качестве

выигрыша игрока 1 в ситуации (а,, Д) примем производительность

поиска ^=0.^, i = l,

3,у=1,

3, где

— элемент матрицы D. Тогда

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

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

Рг Ръ

4 5 6

6 8 10

L3 б 9.

§ 2. МАКСИМИННЫЕ И МИНИМАКСНЫЕ СТРАТЕГИИ

2.1.

Рассмотрим антагонистическую игру Г=(Х, Y, К). Здесь

каждый из игроков выбором стратегии стремится максимизировать

свой выигрыш. Но для игрока 1 он определяется функцией К(х, у),

а для второго —

(—К(х,

у)), т. е. цели игроков прямо противополо-

жны. При этом заметим, что выигрыш игрока 1(2) определен на

ситуациях (х,

y)eXY,

складывающихся в процессе игры. Но каж-

дая ситуация, а следовательно, и выигрыш игрока зависят не только

от его выбора, но и от того, какая стратегия будет выбрана против-

ником. Поэтому, стремясь получить возможно больший выигрыш,

каждый игрок должен учитывать поведение противника.

Поясним сказанное на примере игры «оборона города». Если

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

принять стратегию х

(или х

). В этом случае, если игрок 2 приме-

нит стратегию

(у

то первый получит выигрыш, равный 4 еди-

ницам. Но если игрок 2 применит стратегию у

(соответственно у

то игрок 1 получит выигрыш, равный 0, т. е. потеряет 4 единицы.

Аналогичные рассуждения можно провести и для игрока 2.

В теории игр предполагается, что оба игрока действуют ра-

зумно, т. е. стремятся к получению максимального выигрыша,

считая, что соперник действует наилучшим (для себя) образом.

Что может себе гарантировать игрок 7? Пусть игрок 1 выбрал

стратегию х. Тогда в худшем случае он выиграет min K(x, у).

Поэтому игрок 1 всегда может гарантировать себе выигрыш

max min К(х, у). Если отказаться от предположения достижимости

* у

экстремума, то игрок 1 может всегда получить выигрыш, сколь

угодно близкий к величине

r = supinf K(x, у), (2.1)

- хеХ yeY

которую будем называть

нижним значением

игры.

Если же внешний

экстремум в (2.1) достигается, то величина v называется также

максимином,

принцип построения стратегии х, основанный на мак-

симизации минимального выигрыша,—

принципом

максимина,

а вы-

бираемая в соответствии с этим принципом стратегия х — мак-

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

игрока 1.

Для игрока 2 можно провести аналогичные рассуждения. Пусть

он выбрал стратегию у. Тогда в худшем случае он проиграет

max K(x, у). Поэтому второй игрок всегда может себе гарантиро-

вать проигрыш — min max K(x, у). Число

inf sup K(x, у) (2.2)

yeY xeX

называется верхним

значением

игры Г, а в случае достижения вне-

шнего экстремума в (2.2) и

минимаксом.

При этом принцип постро-

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

терь,

называется

принципом

минимакса,

а выбираемая в соответст-

вии с этим принципом стратегия у —

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

иг-

рока 2. Подчеркнем, что существование минимаксной (максимин-

ной) стратегии определяется достижимостью внешнего экстремума

в (2.2) ((2.1)).

Пусть задана матричная

(т

х и)-игра Г^. Тогда экстремумы

в (2.1) и (2.2) достигаются, а нижнее и верхнее значения игры

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

» = max mm <х

(2.3)

= min max а.

v (2-4)

Минимакс и максимин для игры Г^ могут быть найдены по следу-

ющей схеме:

Г<Хц «и

•Л\п

••«2л

_*ml «m2 —«mnj Ш1П СЦу,

a.\j

min ay

max mm oty=».

' S

maxon max,

...maxa,

\J f ' v

~v —

min max%=v

j '

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

А =

нижнее значение (максимин) v и максиминная стратегия i

первого

игрока равны i> =

=2, а верхнее значение (минимакс) v и мини-

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

второго игрока — V = 3,j

2.2.

Для любой игры Г=(Х, Y, К) справедливо следующее

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

Лемма. В

антагонистической

игре Г

«<« (2.5)

или

sup inf K(x, y) «ginf sup K(x, y). (2.6)

xeX yeY yeY xeX

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

xeX—

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

ка ). Тогда имеем

К(х, у) <sup K(x, у).

хеХ

Отсюда получаем

inf K(x, у) <inf sup K(x, у).

yeY yeY хеХ

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

константа, а значение хеХ выбиралось произвольно. Поэтому вы-

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

sup inf К(х, у) < inf sup K(x, у).

хеХ yeY yeY хеХ

§ 3. СИТУАЦИИ РАВНОВЕСИЯ

3.1.

Рассмотрим вопрос об оптимальном поведении игроков

в антагонистической игре. Естественно считать оптимальной в игре

Г= (X, Y, К) такую ситуацию (х*, у*) еХ- Y, от которой ни одному

из игроков невыгодно отклоняться. Такая ситуация

(JC*.

у*) называ-

ется

равновесной,

а принцип оптимальности, основанный на постро-

ении равновесной ситуации,—

принципом

равновесия.

Для антагони-

стических игр, как это будет показано ниже, принцип равновесия

эквивалентен принципам минимакса и максимина. Конечно, для

этого необходимо существование равновесия (т. е. чтобы принцип

оптимальности был реализуем).

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

антагонистической игре

Г=(Х, Y, К)

ситуация

(х*,

у*)

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

или

седловой

точкой,

если

К{х,у*)<К(х*,у*); (3.1)

К{х*.

у)>К{х*. у*) (3.2)

для всех хеХ и ye Y.

Множество всех ситуаций равновесия в игре Г обозначим через

Z(r),Z(r)cXY.

Для матричной игры Г^ речь идет о

седловых

точках

матрицы

выигрышей А, т. е. таких точках (/*,

/*),

что для всех ieM ujeN

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

а,/ < а^^оц*/.

В седловой точке элемент матрицы а,.^ является одновременно

минимумом в своей строке и максимумом в своем столбце. Напри-

мер,

в игре с матрицей 5 3 8 ситуация (2.2) является равновес-

ной.

3.2. Множество ситуаций равновесия в антагонистической игре

Г обладает свойствами, которые позволяют говорить об оптималь-

ности ситуации равновесия и входящих в нее стратегий.

Теорема. Пусть (xf, yf), (jcf, yf) —

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

равновесия

антагонистической игре

Г. Тогда

1) ВД, yt) =

K(x*

yt); К(Х1, у1)=К{х*

, у\);

2)(x*

,y^Z(D,(xtyt)eZ(T).

Доказательство. Из определения ситуации равновесия для

всех хеХ и у е Y имеем

Щх,

Я)<ед,

УГНЦХЬ

у); (3.3)

К(х, ЯХВД. ЯНВД. у). (3.4)

Подставим в левую часть неравенства (3.3) х\, в правую —

у%,

в левую часть неравенства (3.4) — х* и в правую у\. Тогда получим

ад, яхед,

yiHK(xi,

>>!)<ВД, уп^км,

Откуда следует равенство

K(xl tf )=ВД, yl)=K(xt,

уХ)=К{хХ,

yt). (3.5)

Покажем справедливость второго из утверждений. Рассмотрим си-

туацию (xf, yf). Тогда из (3.3) — (3.5) имеем

К(х, yf)<K(xt, yt) = K(xt, yt)

K(xl y$)^K(xt у) (3.6)

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

Доказательство равновесности ситуации

(х*,

у*)

проводится аналогично.

Из теоремы следует, что функция выигрыша принимает одно

и то же значение во всех ситуациях равновесия. Поэтому разумно

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

Определение. Пусть (х*, у*) —

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

в игре Г.

Тогда

число

« = К(х*. у*) (3.7)

называется значением игры

Г.

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

факт. Обозначим X* и Y* проекции множества Z(T) на X и Y соот-

ветственно, т. е.

{х*\х*

еX,

Зу*

е Y, (х*. у*) eZ(Y)},

у*

{у*\у*

eY,3x*eX,

(х*. у*)

Z(T)}.

Тогда множество Z(T) можно представить в виде

Z(D=PxP. (3.8)

Доказательство (3.8), как следствие второго утверждения теоремы,

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

Определение. Множество

X*(Y*)

называется

множеством,

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

игрока 1(2) в игре Г, а его

элементы

—

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

(2).

Заметим, что равенство (3.S) указывает на взаимозаменяемость

оптимальных стратегий, т. е. любая пара оптимальных стратегий

образует ситуацию равновесия, а выигрыш в ней равен значению

игры.

33.

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

множества стратегий остаются прежними, а функция выигрыша

умножается на положительную константу (или к ней прибавляется

постоянное число).

Лемма (о масштабе). Пусть Т=(Х, Y, К) и Г' = (Х, Y, К

) две

антагонистические

игры,

причем

К = РК+ а, р >

О,

а=const, р=const. (3.9)

Тогда

Z(T')=Z(r), v

=Pv

+a. (3.10)

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

(х*.

у*) — ситуация равновесия в игре

Г. Тогда имеем

К'(х*.

у*)=РЦх*. у*)+а^рК(х*, у)+а=К'(х*, у),

К'(х,

у*)=рК(х,

у*)

<х*крК{х*,

у*)

+ а=К'(х*, у*)

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

Поэтому (х*,

y*)eZ$"),

Z(T)cZ(r').

Обратно, пусть (х, y)eZ(J"). Тогда

К(х,у)=(11Р)К'(х,у)-а1Р

и, рассуждая аналогично, получаем, что (х, y)eZ(T). Поэтому

Z(t)=Z(J"),

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

=K'(x*, у*)=рК(х*.

y*)

+ a=Pv

+u.

Содержательно данная лемма говорит о стратегической эквива-

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

шей, а также масштабом их измерения.

3.4. Теперь установим связь между принципом равновесия и при-

нципами минимакса и максимина в антагонистической игре.

Теорема. Для того чтобы в игре Г=(Х, Y, К)

существовала

ситуация

равновесия,

необходимо

достаточно,

чтобы

существова-

ли

минимакс

максимин

min sup К(х, у), max inf K(x, у) (3.11)

ух х у

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

v=max inf К(х, у)=min sup K(x, у)=V. (3.12)

~ х у ух

Доказательство. Необходимость. Пусть {x*,y*)eZ(T). То-

гда для всех хеХ и ye Y выполняются неравенства

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

отсюда

supK(x,y*)^K(x*,y*). (3.14)

Вместе с тем имеем

inf sup K(x, у) < sup K(x, у*). (3.15)

ух х

Сравнивая (3.14) и (3.15), получаем

inf sup Цк. y)<sup K(x,

y*)^K{x*.

у*). (3.16)

ух х

Рассуждая аналогично, приходим к неравенствам

Цх*.

у*НМ

К(х*.

yHsap inf K(x, у). (3.17)

у х у

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

inf sup K(x, j>)<sup inf K(x, у).

ух х у

С другой стороны, всегда вьшолняется обратное неравенство (2.6).

Итак, получаем

sup inf К(х, у)=inf sup K(x, у), (3.18)

х у ух

при этом неравенства (3.16), (3.17) выполняются как равенства

inf sup K(x, j>) = sup K(x, y*)=K(x*. у*),

ух х

sup inf K(x, >0=inf

К(х*.

у)=К(х*. у*),

х у у