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

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

т. е. внешние экстремумы у минимакса и максимина достигаются

в точках у* и х* соответственно.

Достаточность. Пусть существуют минимакс и максимин

max inf К{х, у)=inf

K(x*.

у); (3.19)

х у у

min sup K(x. ^) = sup K(x, у*) (3.20)

ух х

и выполняется равенство (3.12). Покажем, что ситуация (х*, у*)

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

К(х*. y*)>iof К(х*. у)=max inf К(х,

у);

(3.21)

у х у

К(х*. >>*)<sup K(x, y*)=min sup Цх, у). (3.22)

х ух

Согласно равенству (3.12) минимакс равен максимину, а из (3.21),

(3.22) следует, что он равен также и величине К(х*. у*), т. е.

неравенства в (3.21), (3.22) выполняются как равенства. Теперь

имеем

К(х*. y*)=inf

K(x*.

у)^К(х*. у),

К(х*.

;F*)=sup K(x, у*)>К(х, у*)

для всех хеХ и j>e

У,

т. е. (х*.

y*)eZ(T).

Заметим, что в ходе доказательства показано, что общее значе-

ние минимакса и максимина равно К(х*.

y*)=v

— значению игры,

при этом любая минимаксная (максиминная) стратегия

у*(х*)

в условиях теоремы является оптимальной, т. е. ситуация (х*. у*)

является равновесной.

Из доказательства теоремы получаем следующее утверждение.

Следствие 1. Если

минимакс

максимин

в (3.11)

существуют

достигаются на~у

и х

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

то

max inf K(x, у)^К(х, у)^тт sup K(x, у). (3.23)

х у ух

Игры, в которых существуют ситуации равновесия, называются

вполне

определенными.

Поэтому данная теорема устанавливает кри-

терий вполне определенной игры и может быть переформулирована

следующим образом. Для того чтобы игра была вполне определена,

необходимо и достаточно, чтобы существовали минимакс и мак-

симин в (3.11) и выполнялось равенство (3.12).

Заметим, что в матричной игре Г

экстремумы в (3.11) всегда

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

Следствие 2. Для

того чтобы матричная

(т х nj-игра Г^

была

вполне

определена,

необходимо

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

mm max а

= max mm a

j-l,

2...,

л i-1,

2...,

т i-l, 2, ...,

J-l, 2, .... я

Например, в игре с матрицей

равновесной. При этом

-2

(3.24)

ситуация (2,1) является

max min a

=min max a

=2.

' J J •

С другой стороны, игра с матрицей

весия, поскольку

1 О

О 1

не имеет ситуации равно-

min max а

>max min

= 0.

l i J

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

— 3 (п. 1.3), не

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

лена и ее значение v=6.

§ 4. СМЕШАННОЕ РАСШИРЕНИЕ ИГРЫ

4.1.

Рассмотрим матричную игру Г^. Если в ней существует

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

но определению ситуации равновесия каждый из игроков может

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

нику и от этого ни один из игроков

не

может получить дополнитель-

ную выгоду. Теперь предположим, что в игре Г^ не существует

ситуации равновесия. Тогда согласно теореме п. 3.4 и лемме п. 2.2

имеем

min max

a,-,—max

min а,

>0.

' 'J

(4.1)

В этом случае максиминная и минимаксная стратегии не являются

оптимальными. Более того, игрокам бывает невыгодно их придер-

живаться, так как они могут получить больший выигрыш. Однако

сообщение о выборе стратегии противнику может привести к еще

большим потерям, чем в случае максиминной или минимаксной

стратегии.

Действительно, пусть матрица А имеет вид

7 3

2 5

Для такой матрицы min max

af/=5,

max min a

=3, т. е. ситуации

j ' t j

равновесия не существует. Обозначим через

г*

максиминную страте-

гию игрока 1

(i*

1),

а минимаксную стратегию игрока 2 через j*

(j*

2).

Пусть игрок 2 придерживается стратегии j*

а игрок

1 выберет стратегию f=2. Тогда последний получит выигрыш 5, т. е.

на 2 единицы больше, чем максимин. Однако если игрок 2 догадает-

ся о выборе игрока 1, то он изменит стратегию на _/=

и тогда

первый получит выигрыш лишь 2 единицы, т. е. на единицу меньше,

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

и для второго игрока. По существу вопрос стоит о том, как раз-

делить между игроками выигрыш (4.1)?

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

случайно, что обеспечивает наибольшую скрытность выбора стра-

тегии. Результат выбора не может стать известным противнику,

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

игроку.

4.2.

Определение. Случайная величина, значениями которой

являются

стратегии

игрока,

называется его смешанной

стратегией.

Так, для матричной игры Г

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

1 является случайная величина, значениями которой являются номе-

ра строк ieM, M={1, 2, ...,

т}

матрицы А. Аналогично определяет-

ся смешанная стратегия игрока 2, значениями которой являются

номера j eN столбцов матрицы А.

Учитывая только что введенное определение смешанных страте-

гий, прежние стратегии будем называть

«чистыми».

Так как случай-

ная величина характеризуется своим распределением, то будем

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

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

разом, смешанная стратегия х игрока

в игре есть m-мерный вектор

*=«!

Л".

I 6=1,

Z,>0,

г'=1 т. (4.2)

(-1

Аналогично, смешанная стратегия у игрока 2 есть л-мерный вектор

у=(гц, ....

Т]„),

£ ty=l, и,>0 (4.3)

у'=1

При этом £,^0 и fy^O—вероятности выбора чистых стратегий

ieM ujeN соответственно при использовании игроками смешан-

ных стратегий хну.

Обозначим через X и Y соответственно

множества смешанных

стратегий первого

второго

игроков.

Нетрудно заметить, что мно-

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

ствующем конечномерном евклидовом пространстве (замкнутое,

ограниченное множество).

Определение. Пусть

х=(£

.... £

)еХ—смешанная

страте-

гия

игрока

Тогда множество индексов

={i\ieM,

{,><)},

где

М={1, 2,

...,

т),

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

х.

Аналогично

для

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

(rj

....

rj„)eY игрока

2 спектр

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

={j\jeN,rij>0},

(4.5)

где iV={l,

2, ...,

и}. Спектр смешанной стратегии состоит

из

таких

чистых стратегий, которые выбираются

положительными вероят-

ностями.

Для любой смешанной стратегии

спектр М

Ф0, поскольку

вектор

имеет неотрицательные компоненты, сумма которых равна

1 [см.

(4.2)].

Рассмотрим смешанную стратегию м

(

=(^

.... &, .... £

)еХ, где

&=1,

^j=0,j^i, 1=1,

2, ...,

т. Такая стратегия предписывает выбор

/-Й

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

А с

вероятностью 1. Естественно отождествлять

смешанную стратегию

щеХ с

выбором

i-й

строки,

т. е. с

чистой

стратегией ie M игрока

Аналогично отождествим смешанную

стратегию w

=(ri

....

г\

}

....

ri„)eY,

где

ц,=

?/,, = 0,

гф],

-, *,

с чистой стратегией j eN игрока

2. Тем

самым

мы

получили,

что

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

его

про-

странства чистых стратегий.

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

Пара

(х,

у)

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

мат-

ричной игре

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

смешанных

стратегиях.

Определим выигрыш игрока

1 в

ситуации

(х, у) в

смешанных

стратегиях для матричной

(т

х л)-игры

как математическое ожи-

дание

его

выигрыша

при

условии,

что

игроки используют смешан-

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

х и у.

Выбор стратегий игроками

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

от

друга, поэтому математическое

ожидание выигрыша К(х,

у)

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

у) в

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

ях

х=(£

, ....

y = {Vv

»..

»?*)

равно

K(x,y)=Y

щ,

т=

(хА)у=х(Ау).

(4.6)

(-1 j-\

При этом функция

К(х, у)

является непрерывной

по хеХ и ye Y.

Заметим,

что

выигрыши

Щ, у),

К(х,

j) при

применении одним

из

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

или j соответственно),

другим — сме-

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

(у

или

х)

имеют

вид

Щ у)=К(ц

y)=Y.

<*u>1j=aiy,

z'=l, ..., т,

K(x,j)=K(x, Wj)=Y a,j&=xa

,j=l, ...,

i-i

где

а„

а' — /-я строка и j-я столбец соответственно

(т

х /^-матри-

цы А.

Таким образом, от матричной игры Т

{М,

N, А) мы пришли

к новой игре Гд = (А", У, К), где X и

У —

множества смешанных

стратегий

игреПГ

а К

—

функция выигрыша в смешанных страте-

гиях. Игру Г^ будем называть

смешанным расширением

игры Г

Игра Г

является подыгрой для Г

, т. е.

с:Г

43.

Определение. Ситуация (х*, у*) в игре Г

образует

ситу-

ацию

равновесия,

число

v=K(x*. у*) является

значением

игры Г

если

для всех хеХ uyeY

К(х,

у*)^К(х*.

у*НК(х*. у). (4.7)

Из теоремы п. 3.2 следует, что стратегии (х*. у*), входящие

в ситуацию равновесия, являются также оптимальными. Более того,

согласно теореме п. 3.4 стратегии х* и у* являются соответственно

максиминнои и минимаксной, поскольку внешние экстремумы

в (З.П) достигаются (функция К(х, у) непрерывна на компактных

множествах X и У).

В п. 3.3 была показана стратегическая эквивалентность двух игр,

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

табом их измерения (лемма о масштабе). Оказывается, что если две

матричные игры Т

и Т

находятся в условиях этой леммы, то их

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

этот факт устанавливается следующим утверждением.

Лемма. Пусть Г^иГ^ —

две матричные (т

п)-игры,

причем

А'

аА +

В,

а>0, a=const,

а В—

матрица

одинаковыми элементами

ft, т. е. P,j=P для всех

i и

Тогда Z(Y

')=*Z(Y

), v

=av

f},

где IV и Г

—

смешанные

расширения

игр IV

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

a v

, v

—

значения

игр

ТлиТ

Доказательство. Обе матрицы А и А' размерности /мхи,

поэтому множества смешанных стратегий в играх Г^ и Г

совпада-

ют. Покажем, что для любой смешанной ситуации (х, у) выполняет-

ся равенство

К'(х,у) = аК(х,у)+р, (4.8)

где К' и К — выигрыши игрока 1 в играх IV и Г^ соответственно.

Действительно, для всех хеХи уе

имеем

К'(х,

у)=хА'у=а(хАу)+хВу =

а.К(х,

у)+0.

Тогда из леммы о масштабе следует, что Z(IV) =

Z(r^),

=olv

+p.

Пример 7. Проверим, что стратегии

(

Ч** Vj»

* =

=( /г>

, V4) оптимальны, a v = 0 — значение игры Г

с матрицей

А =

Упростим матрицу А (с целью получения максимального числа

нулей). Прибавляя ко всем элементам матрицы А единицу, получим

матрицу

[

200

0 0 4

0 4 0

Каждый элемент матрицы А разделим на 2. Новая матрица прини-

мает вид

[

1 о о

о о 2

0 2 0

По лемме значение игр связано равенством v

VA'

= i

l).

Таким образом, требуется проверить, что значение игры

рав-

но

. Действительно, К(х*.

у*)=х*

А"у*

/о.

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

для каждой стратегии yeY, у=(ц

, ц

, г\^) имеем К(х*. у) =

= i

12*1 i

l2П2+

/21з

/2'

/2.

а для всех

х=(£

, СзЛ

хеХ

К(х, у*)= /

€i

/2^2+ /2^з= /г- Следовательно, указанные стра-

тегии х*, у* являются оптимальными, &v

= 0.

В дальнейшем, говоря о матричной игре Г^будем предпола-

гать,

что речь идет о ее смешанном расширении Т

НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ВЫПУКЛЫХ

МНОЖЕСТВ И СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ

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

чтении может быть опущен. Однако для понимания доказательств

последующих утверждений полезно напомнить широко распрост-

раненные понятия и результаты. Большинство из них будет приве-

дено без доказательств, в необходимых случаях даны ссылки на

специальную литературу.

5.1.

Множество А/с

Л™

называется

выпуклым,

если вместе с любыми двумя

точками этого множества х

, х

еМ в нем содержатся все точки отрезка

1 -1 -1

-1 -1 3

_-1 3 -1_

Axj+(1

—A)x

0<A<1.

Понятие выпуклого множества можно сформулировать

и в более общем, но эквивалентном виде.

Множество М<^К" называется выпуклым, если вместе с точками х,..., х* из

М оно содержит и все точки вида

* *

х= £ А,х,, А

(

>0, £ Ai=l,

i-1 i-1

называемые выпуклыми линейными комбинациями точек

....

х*.

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

Рассмотрим систему линейных неравенств

хА^Ь

или

xaJ<Pj,jeN,N={l и}, (5-0

где А=[а>, /еЛП-(|ихл)-матрица, xeR

, Ь=(Р

....

PJelC.

Обозначим

Х={х\хА^Ь}_ьаожество решений системы (S.1). Непосредственно из определения

следует, что X

—

выпуклое множество. Множество X называется

выпуклым

много-

гранным

множеством,

заданным системой ограничений (5.1).

5.2. Точка хеМ, где М

—

выпуклое множество, называется

крайней

точкой,

если

из условия х=Хх

+(\-Х)х

, х

еМ,х

еМяО<Х<1 следует, что х

=х

=х. Содер-

жательно определение означает, что хеМ

—

крайняя точка, если не существует

отрезка, содержащего две точки из М, для которого х является внутренней.

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

обратное неверно.

Пусть X

—

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

(S.1).

Тогда справедливы следующие утверждения.

Теорема.

Множество

имеет крайние

точки тогда и

только

тогда,

когда

таяк.А=[а1,}еЩ=т[\6,

с. 69].

Теорема. Для

того чтобы точка

еХ

была

крайней,

необходимо и

достаточно,

чтобы она была решением системы

Xoa^Pj.jeNt; (5.2)

xjal+fyJsNXN» (5.3)

где Ni^N, rank[e',./eN

]=m [16, с. 65, 66].

Последняя теорема дает алгоритм нахождения крайних точек множества X. Для

этого необходимо рассмотреть столбцовые базисы матрицы А, решить систему

линейных уравнений (5.2) и проверить выполнение неравенств (5.3). Однако такой

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

ки,

поскольку он связан с полным перебором всевозможных столбцовых базисов

матрицы Л.

5.3.

Выпуклой оболочкой множества

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

лых

множеств,

содержащих

Р,

и обозначать conv (P). Данное определение эквивален-

тно следующему. Выпуклая оболочка множества Р состоит из всех выпуклых линей-

ных комбинаций всевозможных точек из Р, т. е.

Л R

convfPj ={*!*= £ fa £

А.=

А,>0,

х,-еР}.

f-i i-1

Выпуклая оболочка конечного числа точек называется

выпуклым

многогранни-

ком,

порожденным этими точками. Выпуклый многогранник порожден своими край-

ними точками. Так, если рассмотреть множество X смешанных стратегий игрока

1 в

(т

л)-игре,

то X=conv{u

,....

щ,},

где

и, = (0

О,

1,0,...,0)

— орты пространства

Я™

или чистые стратегии игрока 1. Множество X является выпуклым многогранни-

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

(т—1)

и называется также

(т—1)-мерным симплексом

(или фун-

даментальным симплексом). При этом все векторы щ (чистые стратегии) являются

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

множества Y смешанных стратегий игрока 2.

Конусом

С называется множество таких точек, что если хеС, Х^О, то ЛхеС

Содержательно конус

С —

это такое подмножество К", которое вместе с точкой

х содержит и всю полупрямую (х), где

Конус С называется

выпуклым

конусом,

если выполняется условие: для всех

х,

уеС справедливо х+уеС. Другими словами, конус

С —

выпуклый, если он замкнут

относительно операции сложения. Можно дать и другое эквивалентное определение.

Конус называется выпуклым, если

он

является выпуклым множеством. Сумма

выпуклых конусов

={с\с=с

+с

, с^еС,, сеС

)

их пересечение

Cif]C

также являются выпуклыми конусами.

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

что

множество

{х\хА^6} решений однородной системы линейных неравенств, соответству-

ющей (5.1),_является выпуклым конусом.

Пусть X

—

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

(5.1),

записанной в эквивалентной форме

I Ьа,^Ь,

(5.4)

где *=(?!, ...,

)eK",

а,-

—

J-Я

строка матрицы Л, /=1 т. Предположим, что

rank А=г^,т, и векторы

,...,

а, образуют строчечный базис матрицы А. Разложим

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

"ь

iJ"

- (

Подставляя (5.5) в (5.4), получим эквивалентную (5.4) систему неравенств

l(ft+

I ijSi)a^b. (5.6)

j-i

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

множество векторов

х=({

—, Z^eR", удовлетворяющих

неравенствам (5.6) и условию £j=0,j=r+l,m. По теореме п. 52 множество Х

имеет

крайние точки. Справедлива следующая теорема {16, с. 70

—

74}.

Теорема о представлении многогранного множества.

Пусть

Xмногогран-

ное

множество,

заданное системой ограничений

(5.4).

Тогда

Х=М+С,

где M+C={x\x=y+z,

уеМ, zeC},

M—выпуклый

многогранник,

порожденный

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

заданного

(5.6), а С={х\хА^0} —

выпуклый

конус.

Из теоремы, в частности, следует, что если множество X решений системы (5.4)

ограничено, то X— выпуклый многогранник.

5.4. Напомним, что задача нахождения min

при ограничениях

хА>Ь,х^0,

(5.7)

где А-(тхп)-матрица, с6К",

хеR

beК

называется

прямой стандартной задачей

линейного

программирования,

задача, заключающаяся

определении тяхЬу при

ограничениях

Ау*с,у>0,

(5.8)

где уеК

—

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

для (5.7).

Вектор хеК", удовлетворяющий системе (5.7), называется допустимым решени-

ем задачи (5.7). Аналогично вводится понятие допустимого решения

еЛ задачи

(5.8).

Допустимое решение х(у) называется оптимальным решением задачи (5.7)

[(5.8)],

если на нем достигается минимум (максимум) функции сх(Ьу) на множестве

всех допустимых решений.

Справедливо следующее утверждение [16].

Теорема двойственности. Если обе

задачи_

(5.7), (5.8) имеют допустимые

решения, то они обе имеют оптимальные решения х, у

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

при этом

сх—Ьу.

5.5. В заключение параграфа приведем одно свойство выпуклых функций. Снача-

ла напомним, что функция

<р:

M-*R

где МаК" — выпуклое множество, называет-

ся выпуклой, если

<р(Хх^

-Х)х

) <hp(xj + (1-Х)<р(х

) (5.9)

для любых Xi, х

е М

А е

[0,1].

Если же в (5.9) выполняется обратное неравенство, то

функция

(р

называется вогнутой.

Пусть щ(х) — выпуклые на М функции i=l я. Тогда верхняя огибающая

ф(х) этого семейства функций

ф(х)= max q>i(x) (5.10)

*-1.

-, »

является выпуклой на М.

Действительно, по определению выпуклой функции для х,, х

еМ и ае[0, 1]

имеем

«p.faXi+O-oOxJ ^oupifxJ+il-eitoifXi) <

<а max p/xj +(1

— а)

max

щ(х

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

ф(ях

+ (\- а)х

) =max 9f(**i + (I -

OL)X

)

что и требовалось доказать.

Аналогично можно показать вогнутость нижней огибающей (в (5.10) берется

минимум по 0 семейства вогнутых функций.

§ 6. СУЩЕСТВОВАНИЕ РЕШЕНИЯ МАТРИЧНОЙ ИГРЫ

В КЛАССЕ СМЕШАННЫХ СТРАТЕГИЙ

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

в классе смешанных стратегий.

6.1.

Теорема. Всякая

матричная игра имеет ситуацию

равнове-

сия в

смешанных

стратегиях.

Доказательство. Пусть Г^—произвольная (/яхи)-игра со

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

{<х

т. е.

для всех i=l, m

У=1,

п. Покажем, что в этом случае теорема справедлива. Для

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

рования

хатхи, xA^w, х^О (6.1)

и двойственную ей задачу (п. 5.4)

maxj>w, Ay^u, y^O, (6.2)

где ы=(1, ... 1)G/P", W=(1, ..., 1)еЛ". Из строгой положительности

матрицы А следует, что существует такой вектор х>

для которого

xA^w, т. е. задача (6.1) имеет допустимое решение. С другой

стороны, вектор у=0 является допустимым решением задачи (6.2)

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

(см.

п. 5.4) обе задачи (6.1) и (6.2) имеют оптимальные решения х,

у соответственно, при этом

xu=yw=d>0. (6.3)

Рассмотрим векторы х*=х/в и

у*=у/в

и покажем, что они

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

в игре Г

, при этом значение игры равно 1/0.

Действительно, из (6.3) имеем

х*и=(хи)/в=(yw)/6=y*w =

а из допустимости х и у для задач (6.1), (6.2) следует, что х*=5с/0>О

и у*=у/в^0, т. е. х* и у* — смешанные стратегии игроков

1 и 2 в игре Г^.

Вычислим выигрыш игрока 1 в ситуации (х*. у*):

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

(хАу)1в

(6.4)

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

(6.1),

(6.2) и равенства (6.3) имеем

e=wy^(xA)y=x(Ay)^xu=6. (6.5)

Таким образом, хАу=в, из (6.4) получаем, что

к(х*,

*)=1/е. (6.6)

Пусть хеХ и yeY—произвольные смешанные стратегии иг-

роков 1 и 2. Тогда выполняются неравенства

К(х*. у)=(х*А)у=(хА)у1в>(м>у)/в=11в; (6.7)

Цх, у*)=х(Ау*)=х(Ау)1в^(хи)1в=\/в. (6.8)

Сравнивая (6.6) — (6.8), получаем, что (х*. у*) — ситуация рав-

новесия, а 1/0 — значение игры Г^ со строго положительной ма-

трицей А.

Теперь рассмотрим (тхл)-игру Г*- с произвольной матрицей

A'—{aij}.

Тогда существует такая константа В>0, что матрица

А=А'

+ В — строго положительна, где В={By}

—

(тхп) -матрица,

Ву=В,

m,j=

п.

игре Г^ существует ситуация равновесия (х*,

У*)

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

l\/9, где

в определяется как в (6.3).