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

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

игру в случае, когда множество S совпадает с отрезком [—1, 1].

Теорема.

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

v* игрока 2 за-

ключается

равновероятном выборе

двух

наборов

из т

точек:

2/И-1

, 1=0, 1, ..., т-\>,

— 1

о, 1, .., т-\

Ъп-\

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

ц*

игрока

состоит

выборе точек

Ъп-\

-, /=0, 1, ...,2т-1

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

1/(2/и).

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

1/(2/и—

1).

Доказательство. Пусть р* и v* — смешанные стратегии иг-

роков 1 и 2 соответственно, оптимальность которых нужно до-

казать. Введем следующие обозначения:

, Г2т-2.-1 2m-2i+l"| . , „

li=\———,——— , i=l, 2, ..., 2m-1.

Покажем вначале, что К{х, v*)<l/(2m—1) для всех хе[—

1].

Действительно, при xel, имеем

К(х, v*)=- min

2m—4J—l

2m-l

+-mm

-2m+4i+l

2m-l

1 /

2m-2j-l\

/2m-2/+l

\ 1

=-[x — +- x = . (6.8)

2m-\ / 2\ 2w-l / 2/w-l

Пусть теперь игрок 1 выбирает смешанную стратегию ц*, а иг-

рок 2 — произвольную чистую стратегию у={у

, .., у

Обозначим

2т—2/—1

х,=-

2т-1

У=0,

1, ...,Ьп-\.

Тогда

2т-1

К{ц*,

3>)= Е min p(x

)~ =

= Г" S

т1П

(*»->' ^)

+ miQ

P(*V-2. У|) >

1 2 1

>—

•

= .

2т 2т-1 2т-1

Из неравенств (6.8), (6.9) вытекает утверждение теоремы.

(6.9)

100

§ 7. ОДИН КЛАСС ИГР С РАЗРЫВНОЙ ФУНКЦИЕЙ ВЫИГРЫША

Для игр, у которых функции выигрыша разрывны, нельзя гаран-

тировать существование значения игры в смешанных стратегиях

(см.

пример п. 4.12). Однако часто именно разрывность функции

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

ры.

Нахождению решения помогают также эмпирические предполо-

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

7.1.

В данном параграфе будут исследованы игры с выбором

момента времени или игры типа дуэли (см. примеры 4.5 п. 1.2).

Основной особенностью этого класса игр на квадрате является

разрывность функции выигрыша Н(х, у) вдоль диагонали х=у.

Рассмотрим игру на единичном квадрате с функцией выигрыша

{

\1/(х,

у), если х<у,

ср(х),

если х=у,

в(х, у), если х>у,

где ф(х, у) — определена и непрерывна на множестве

0<х<^<1,

функция

(р

непрерывна на [0, 1], а в(х, у) определена и непрерывна

на множестве 0<j><;c<

Предположим, что игра Г=(Х, Y, Н), где

=У=[0, 1], Н—задана (7.1), имеет оптимальные смешанные

стратегии ц*, v* игроков 1 и 2 соответственно. Более того, пред-

положим, что оптимальные смешанные стратегии /х*, v* являются

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

ности

(х)

(x)

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

Далее в этом параграфе будем обозначать искомую стратегию

/ (соответственно g), понимая под этим плотность распределения.

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

Пусть/— стратегия игрока 1. Для уе[0, 1] имеем

K(f, у) = ]

(х,

У(х)сЬс+\в(х, yV(x)dx. (7.2)

Предположим, что / и g — оптимальные стратегии игроков

1т 2. Тогда для любой точки у

, в которой

g(y

)>0 (7.3)

(точки спектра стратегии g), выполняется

Ktf,

)=v,

(7.4)

где v — значение игры. Но равенство (7.3) строгое, поэтому суще-

ствует <5>0 такое, что для всех у: \у—у

\<5, неравенство (7.3)

сохраняется. Таким образом, для этих у сохраняется и неравенство

(7.4),

т. е. выполняется равенство K(f, y)=v. Это означает, что

dK(f, у)/ду=0. (7.5)

101

Уравнение (7.5) перепишем в виде

[в(У,

У)-Ф(У,

У)¥(у) = ]

ФЛ*>

y¥(*)dx+

+R(*, y)f(x)dx, yeS(y

, 8). (7.6)

Следовательно, получено интегральное уравнение (7.6) относите-

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

7.2.

Пример 16. Рассмотрим бесшумную дуэль, сформулирован-

ную в примере

п. 1.2. Функция выигрыша Н(х, у) в игре имеет вид

(7.1),

где

ij/(x,y)=x-y+xy; (7.7)

в(х,у)=х-у-ху; (7.8)

р(х) = 0. (7.9)

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

Н (х, у)=—Н(у,х) (кососимметричная функция выигрыша). Поэто-

му анализ, аналогичный проведенному в п. 9.2 гл.

показывает, что

значение v игры, если оно существует, равно нулю, а оптимальные

стратегии игроков (если они также существуют) должны быть оди-

наковыми.

Имеем:

ф,(зс,у)=

-1 +х; в

(х, у)= -1 -х; в(у,у)-ф(у,у)=-2у

и интегральное уравнение (7.6) принимает вид

-2у

№

= ]

(х-l)f(x)dx-\ (x+ l)f(x)dx. (7.10)

О у

Будем искать стратегию /

классе дифференцируемых плотностей

распределения, принимающих положительные значения в интервале

(а, /?) с:

[0,

1] (интервал (а, /?) — спектр стратегии J). Тогда (7.10)

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

у Д

-2у

= [

(x-\)f(x)dx-l (x+ l)f(x)dx. (7.11)

« У

Дифференцируя обе части (7.11) по у, получим дифференциальное

уравнение вида

-4yf-2y

f = (y-l)f+(y+l)f

или

J*r=-3/Xy*0). (7.12)

Интегрируя уравнение (7.12), имеем

f<y)

yy-\ (7.13)

где

у —

некоторая

константа.

102

Теперь осталось найти а, /? и у. Напомним, что оптимальные

стратегии игроков в рассматриваемой игре одинаковы. Из нашего

предположения о спектре стратегии/следует, что

Wy) = Q (7.14)

для всех у е (a, /?).

Пусть /?<

Поскольку функция K(f, у) непрерывна по у, из (7.14)

имеем K(f, /0=0. Следовательно,

J (x-p+Px)f(x)dx=0. (7.15)

Однако в случае /?<

из (7.15) следует

K(f, 1) = J (х-1 +x)f(x)dx<0,

что противоречит оптимальности стратегии/ Таким образом, fi= 1

и K(f, 1)=0. Тогда, подставляя (7.13) в (7.15) при /?=1, получаем

f2x-l ,

—

<ь=о,

7^0.

Откуда вытекает

За

-4а+1=0. (7.16)

Решая уравнение (7.16), найдем два корня а=1 и а

=1/3,

первый из

которых посторонний. Следовательно, а=

1/3.

Коэффициент у нахо-

дится из условия нормировки/(у)

\ f(y)dy=y J r

efy=l,

1/3 1/3

откуда у = 1/4.

Таким образом, получено решение игры примера 5 п. 1.2: значе-

ние игры равно v

оптимальные стратегии/и g обоих игроков

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

П }

0, если х<1

ПХ)

(1/(4х

), если х>1

•1/3.

7.3.

Пример 17. Найдем решение игры «шумная дуэль» (см.

пример 4 п. 1.2) для функций меткости p

(х)=х

(у)=у. Функция

выигрыша Н(х, у) в игре имеет вид (7.1), где

ф(х,у)=2х-1;

(7.17)

9(х,у) = 1~2у; (7.18)

<р(х) =

(7.19)

юз

Игра является симметричной, поэтому v

оптимальные

стратегии игроков совпадают. Здесь

оба

игрока имеют чистую

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

;с*=>>*

1/2. Действительно,

#(1/2,

у)=6

(1/2,

у) =

-2у> О, если у <

1/2,

Я(1/2,

у)=ср

(1/2) =

если

у= 1/2,

Я(1/2,

у)=ф(112,

у)=0,

если у>1/2.

С точки зрения интерпретации игры решение предписывает дуэлян-

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

нции

до

барьера.

В заключение следует отметить, что класс игр с выбором момен-

та времени хорошо изучен (см.

[6,

3, 23]).

РЕШЕНИЕ БЕСКОНЕЧНЫХ ОДНОВРЕМЕННЫХ

ИГР

ПОИСКА

В этом параграфе будет приведено решение

игр

поиска

бес-

конечным числом стратегий, сформулированных

п.

1.2.

Первая

из

рассматриваемых

игр

интересна

тем,

что в ней оба

игрока имеют

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

конечным спектром.

8.1.

Пример 18.

(Поиск на

отрезке).

Рассмотрим задачу поиска

на

отрезке

(см.

пример

2 п. 1.1),

которая моделируется игрой

на

единичном квадрате

функцией выигрыша

Н(х, у)

вида

я(

jl,

если

|*-,|</,

/е(0, 1),

(О

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

Заметим,

что при />

1/2

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

стратегия

х*

1/2

значение игры равно единице, поскольку

этом

случае

Н(х*,

у)=Н(1/2,

у)=1,

так

как \у-1/2|^

1/2^/_для

всех

уе[0,

1].

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

что

1/2. Заметим, что стратегия х=1 доминиру-

ет

все

чистые стратегии

х<1, а

стратегия

x=l

— I — все стратегии

х>

1—1.

Действительно,

Щх,у)=Н(1,у)=\

ПрЯуе[

°>

(О

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

и если

х<1, то

Щх,у)=\

ПрЯуе[

°>

1+Х]

(О

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

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

при

х<1:

Н(х,

у)^Н(1,

у)

для

всех

уе[0,

1].

Анало-

гично имеем

при

уе[\-21,

1],

)=Н(\-1,у)=!}

Н(х,у)-.

„

. .,„

1П

[О

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

104

и если хе[1

—I,

1], то

\\ при

уе[х—1,

1],

H(x,y)=

О в противном случае.

Таким образом, при хе[1

— /, 1]

Н(х, у)^Н(1

—/,

у) для всех>>е[0, 1].

Рассмотрим следующую смешанную стратегию ц* игрока ).

Пусть l=x

<...<x

— I

— точки, для которых расстояние

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

21.

Стратегия ц*

выбирает каждую из этих точек с равными вероятностями \\т.

Очевидно, что при этом любая точка уе[0, 1] попадает в /-окре-

стность хотя бы одной точки х

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

К(ц*,у)>11т. (8.2)

Пусть теперь v* — стратегия игрока 2, которая состоит в равнове-

роятном выборе точек 0=у

<у

<-.<у

=1, причем расстояние

между парой соседних точек больше

21.

Тогда, очевидно, существует

не более одной точки у

, в /-окрестности которой содержится точка

х.

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

К(х, v*)<l/«. (8.3)

Если бы удалось построить стратегии ц*, v* так, чтобы т=п, то

величина 1/и была бы значением игры, а стратегии ц*, v* — оп-

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

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

Для этого достаточно взять

1/(2/),

если

1/(2/)

— целое,

(Jl/(2/)]+l в противном случае.

Здесь

[а]

— целая часть числа а. Точки

=l+~

(i-1), i=\, 2, ..., и, (8.5)

л—1

отстоят друг от друга не более чем на 21, а расстояние между

соседними точками

yj=—:» 7=1,2, ...,R, (8.6)

п—

строго больше

21.

Таким образом, 1/и — значение игры, а опти-

мальные стратегии ц*, v* являются равновероятными смесями чис-

тых стратегий, определяемых формулами (8.5), (8.6).

8.2. Пример 19. Рассмотрим обобщение предыдущей задачи

в том случае, когда игрок 1 (ищущий) выбирает систему из s точек

*!, .., x

, х,е[0, 1], i=l, ..., s, а игрок 2 (прячущийся) выбирает

105

независимо и одновременно с игроком / точку уеГО, 1]. Игрок

2 считается обнаруженным, если находится такое je{\, ..., s), что

\у —

Xj\^l,

/>0. В соответствии с этим функция выигрыша (выигрыш

игрока 1) определяется следующим образом:

{

если min

\у—х^1,

(8.7)

О в противном случае.

Предположим, что игрок 1 располагает точки х

1г

...,

х„

в точках

Xi=l+{\—2l)(i—\)l{n

—

\), 1</^и, являющихся точками спектра

стратегии fi* из предыдущего примера. Очевидно, что располагать

две точки х

, х

]г

в одной точке отрезка [0, 1] (т. е. выбирать

совпадающие точки) невыгодно. Пусть ц, — стратегия игрока 1,

выбирающая равновероятно любые 5-наборы не равных друг другу

точек

{3CJ}.

Если s^n, то, расположив в каждой из точек х\ по точке

Xj,

игрок 1 полностью покроет отрезок [0, 1] интервалами длины 2/

с центрами в точках

Зс,

и тем самым обеспечит, что для любой точки

уе[0,1] будет иметь место min

\xj—j>|</,

т. е. в этом случае значение

игры равно единице. Поэтому будем считать, что s<n. Число

всевозможных различных выборов ^-наборов точек из множества

{х,} равно Q. Имеем

К(ц*,

y)=-LH(x

...,

у)

(±\>Щ =

*-.

Действительно, точка у обнаруживается, если она попадает_ в

/-окрестность хотя бы одной из выбранных стратегией (if точек

{Зс,}.

Для того чтобы это произошло, необходимо игроку 1 выбрать

точку x

из

/-окрестности точки у. Число наборов, удовлетворяющих

этому требованию, не менее

C„Z\.

Предположим теперь, что игрок 2 использует стратегию v* из

предыдущего примера, а игрок ] — произвольную чистую страте-

гию x=(x

..., x

). Тогда

" 1 s

K(x

..., x

; v*)= £ H(x

..., x

;

yj)~^-.

Таким образом, значение игры равно sin и ц*, v* — оптимальные

стратегии игроков. Значение игры линейно зависит от количества

выбираемых ищущим игроком точек.

106

8.3.

Пример

20.

(Поиск

на

сфере).

Рассмотрим игру поиска на сфере (см. пример

3 п. 1.2). Функция выигрыша Н(х, у) имеет вид

{

если

уеМ

(8.8)

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

где х={х

1У

..., х, — набор s точек на сфере С и M

= \J S(xj, г); S(XJ, r) — г-

сферическая окрестность точки

Xj.

Множество смешанных стратегий игрока 1 пред-

ставляет собой семейство вероятностных мер {М}, определенных на декартовом

произведении s сфер Сх Сх... х

C—Q,

т. е. на fl=C.

Множество смешанных стратегий игрока 2 определим как семейство вероятност-

ных мер

{v},

определенных на сфере С.

Рассмотрим конкретную пару стратегий

(p.*,

v*).

качестве стратегии

выберем

равномерную меру на сфере С, т. е. потребуем, чтобы

L(a)

Л*=—-, (8.9)

4nR

где L(a) — лебегова мера (площадь) множества А.

Будем предполагать, что параметры игры 5, г и Л таковы, что можно выбрать

систему точек х=(х

,...,

), удовлетворяющих условию

L{M

)=Y.L(S{xj,r)), (8.10)

J-i

(сферические сегменты S(xp r) не пересекаются).

Зафиксируем фигуру М, на некоторой сфере С. Тогда смешанная стратегия ц*

порождается случайным бросанием этой фигуры М

на сферу С. Для этого в фигуре

фиксируется некоторая внутренняя точка z, с которой жестко связываются два

неколлинеарвых вектора

а,

(с углом

tp>0

между

ними),

расположенных в касатель-

ной плоскости к М

в точке z.

Точка z «бросается» на сферу С в соответствии с равномерным распределением,

т. е. плотностью

1/(4яА

Пусть в результате реализуется точка /еС. Фигура

с фиксированными на ней векторами параллельно переносится на сферу С так,

чтобы точки

совпали. Таким образом, векторы

а,

будут лежать в касательной

плоскости к сфере С в точке

т!.

Затем на промежутке [0, 2п] выбирают в соответствии с равномерным рас-

пределением угол

<р\

и вектор b в касательной плоскости поворачивают вместе со

связанной с ним фигурой М

на угол

ц>

по часовой стрелке. В результате фигура

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

множества М

на сфере в соответствии с описанной двухэтапнои процедурой и поро-

ждает случайный выбор точек x!

...,

соответствующих смешанной стратегии

ц*,

именно:

игрок / выбирает точки У,,...,

еС,

которых оказались центры х

...,

х~,

сферических окрестностей S(xj,

г),

составляющих множество М

Мера ц*, построенная таким образом, оказывается инвариантной, т. е. вероят-

ность покрытия множеством М

любой точки уе

не зависит от

у*.

Действительно,

107

найдем вероятность этого события. Пусть П={со} —пространство всевозможных

размещений

на

сфере

С.

Тогда средняя площадь, покрываемая

на

сфере

С при

бросании

на

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

(математическое ожидание площади), равна

L (М

то же

время

L{M

)=HJ(y,io)dydy*, (8.11)

ас

где J (у,

со)

— характеристическая функция множества

на

сфере

С,

покрываемого

областью

. По

теореме Фубини имеем

J(y,

co)dydii*=

J J(y,

co)dy*dy. (8.12)

с с а

Однако

силу инвариантности меры ц* интеграл

J [у, о>)ф*, совпадающий

веро-

ятностью покрытия

(8.11),

(8.12) имеем

ятностью покрытия точки

множеством

, от у не

зависит

равен р. Тогда

из

L{M

)

*•№(*>'))

Р= —J- °

~' .

•

(8.13)

4nR

Обозначим через

K(ji, v)

математическое ожидание выигрыша

при

использовании

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

{д}

ve{v}.

Если один

из

игроков использует

чистую стратегию,

то

К(х,

v)=J Н(х,

y)<h=

Л=Рг(у

Л/

С Их

KQi,

у)=

Н(х, у№=[

ЦХ,

№'Ъ(уеМ

а о

этом случае математические ожидания соответственно имеют смысл вероят-

ностей попадания случайной точки

фиксированную область

накрытия случайной

областью фиксированной точки.

Для

всех

у и

х=(х

..., х,) в

силу условий

(8.9)

и (8.13) имеем

L(M

) lL(S(xj,r))

К{х, v*) <*=* |1- /1-(- ) ),

4яЛ

2 \ V W )

£ L(S(xj, r))

KQi*,y) = i~

AnR

и-ш

так

как

L{S{xj, г))=2яЛ(Л-^Л

-г

Из определения седловой точки

полученного неравенства K(ji*, у)~^К{х,

v*)

•См.,

например: Саитало

Л. А.

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

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

вероятности.

М., 1983.

108

^'\{Ч

-$)

—

значение рассмотренной игры поиска.

8.4. Рассмотрим вариант предыдущей игры, полагая, что игрок 2 выбирает

некоторое односвязное множество Ус

и целью игрока 1 является максимизация

площади пересечения

МГО^^^П U

,r)\

j-i

Цель игрока

противоположна.

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

игрой,

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

в начале параграфа. Стратегия

ц*

игрока 1 совпадает с таковой в предыдущей игре.

Смешанная стратегия v* игрока 2 строится аналогично стратегии р* и заключается

в случайном бросании множества

У на

сферу (в предыдущем случае игрок

случайно

выбирал точки yeQ. Таким образом, v* строится как инвариантная мера, которая

состоит из случайного (в соответствии

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

С)

выбора

одной из фиксированных точек множества

на С и далее поворота

вокруг этой

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

[0,

2л]).

Пусть К(х,

v),

К(ц,у) соответствуют математическим ожиданиям площади пересече-

ния L(Y\)M

). Тогда

L{Y)L{MJ

КОЛ у)=К{х, v*)=K0i», v*) —г—.

2яЛ

Если У— г-окрестность точки у, то значение игры равно

K(fl*,

V*) = *5 (R-y/tf-t

Упражнения • задачи

Игра нападения —

защиты.

Игрок

силами А единиц намерен атаковать один

из объектов C

С„,

ценность которых определяется числами t

>О,

>О,....

т„>0,

причем т

>т

>...>т

. Чистой стратегией х игрока 1 является вектор

Jc=(f

(

ii=A,

где

£i —

часть сил, выделенных для атаки объекта Q. Суммарные силы

обороняющейся стороны (игрок

равны В. Чистой стратегией у игрока 2 является

выбор набора неотрицательных чисел y=(Vi, —> >ы)> удовлетворяющих условию

t\i=B,

где

щ —

часть сил, предназначенных для защиты объекта Cj. Результат

£таки

на объект С, пропорционален разности

£/

—

щ,

если силы атакующих превос-

ходят силы защищающихся, а в остальных случаях он равен нулю. Построить

функцию выигрыша.

Игра на единичном квадрате имеет функцию выигрыша

Н(х,у)=ху-1/Зх-\12у.

Показать, что (1/2, 1/3) — ситуация равновесия в этой игре.

Показать, что игра на единичном квадрате с функцией выигрыша

H(x,y)=siga(x-y)

имеет седловую точку.

4 Показать, что игра на единичном квадрате типа дуэли с функцией выигрыша

109