МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

7. МАТРИЧНЫЕ ИГРЫ

Матричная игра предполагает наличие двух игроков (конкурентов) Ji, J2 и строится по следующим правилам. Первый игрок выбирает один вариант из т возможных. Пусть это будет вариант і (і = 1,2,... ,т). Второй игрок может выбрать один из п вариантов, например j (j = 1,2,... ,п). Варианты і и j каждый игрок выбирает самостоятельно. Результаты всех возможных ходов обоих игроков заносятся в так называемую платежную матрицу, или матрицу выигрышей (второго игрока) С = {су}. Смысл элементов этой матрицы состоит в том, что су указывает сумму выигрыша второго игрока при выборе вариантов inj игроками соответственно Ji и J2. Если су > 0, то первый игрок платит второму, а при су < 0 наоборот.

Пример 1 (угадывание монет). Каждый из двух игроков выбирает определенную сторону монеты, затем игроки одновременно называют свой выбор. Если выбраны разные стороны, то первый игрок платит второму одну денежную единицу, если же выбраны одинаковые стороны, то второй платит первому одну денежную единицу.

Для этой игры платежная матрица имеет вид С =

Пусть в векторе X = (х\,..., хп) содержатся вероятности выбора первым игроком каждого из т доступных ему вариантов, причем

т

= 1, 0 < X,. < 1, а в векторе у = (у\,... ,уп) — вероятности

г=1

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

п

имеют место соотношения ^ ty = 1, 0 < ty < 1.

i=i

Если для некоторой стратегии х = (х\,..., ж»,..., хт) выполняется Xi = 1, а остальные хи = 0 (к = 1,2,..., т, к ф і), то эта стратегия

82

называется г-й чистой стратегией игрока J\. Аналогично определяется j-я чистая стратегия игрока Ji ■ В остальных случаях стратегии называются смешанными.

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

Рассмотрим матричную игру двух лиц с платежной матрицей С = = {су }; і = 1,2,... ,m; j = 1,2,... ,п с точки зрения второго игрока. Так как второй игрок выбирает j-й вариант, это означает, что все возможные его выигрыши — в j-м столбце матрицы С, т. е. это (cij,... ,cmj). Для того чтобы сделать выигрыш максимальным, он должен выбрать такой вариант j, чтобы максимизировать наименьший элемент в этом столбце. При этом гарантированный выигрыш второго игрока (нижняя цена игры)

V = max    min су.

1<У<п 1<г<т

Эту же игру можно рассмотреть с точки зрения игрока J\. Очевидно, если С является матрицей выигрыша второго игрока, то матрица —С = {—су}, / 1.2.....nr. j 1.2...../( матрицей выигрышей первого игрока. Рассуждая, как и ранее, приходим к выводу, что гарантированный выигрыш первого игрока

max    min (— су) = — min    max су.

При этом второй игрок получит наибольшее

V =  min    max су.

Величина V представляет собой верхнюю цену игры. Итак, игрок Ji может гарантировать по меньшей мере v, а игрок J\ может помешать ему получить больше v. Если окажется, что v = v = v или

и = min max су = max min су, (*)

і       З З і

то игрок Ji должен понять, что он может получить и, а его противник помешает ему получить больше v. Поэтому числа і* и j* такие, что в соотношении (*) выполняется и = (c,*j*); естественно назвать оптимальными решениями игроков соответственно J\ и Ji. В этом

83

случае V — цена игры, а сама игра допускает решение в чистых стратегиях. Векторы

г* 3*

(0,...,0,1,0,...,0), (0,...,0,1,0,...,0)

т п

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

Оказывается, что соотношение (*) выполняется не для каждой игры, определяемой платежной матрицей С. В этой связи не всякая матричная игра разрешима в чистых стратегиях. Например, для игры "угадывание монет" заданной платежной матрицей является п    { -1 1\

G = I     j      1 /' нетРУДн0 видеть, что

V = max min су = — 1,   v = min max су = 1, v^v, з     і і з

и поэтому данная игра неразрешима в чистых стратегиях.

При ответе на вопрос о разрешимости матричной игры в чистых

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

Теорема. Матричная игра двух лиц с платежной матрицей С = {су }, і = 1,2,..., т; j = 1,2,..., п разрешима в чистых стратегиях (выполняется соотношение (*)) тогда и только тогда, когда матрица С имеет седловую точку. При этом если — седловая точка матрицы С, то цена игры v = c,» j*.

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

Напомним, что (i*,j*) — седловая точка матрицы С, если для всех указанных inj

Сі* j ^ Сі*     ^ Cij* .

Пример 2. Матрица С выигрышей игрока Ji имеет такой вид:

max су

з

64 90 18 95

min сц     18    5 12

С =

( 50

27

64 \

50

5

90

18

9

12

\ 25

95

20 )

84

В дополнительной нижней строке вычисляются величины min су, а в

г

дополнительном правом столбце — величины max су соответственно

і

для каждого фиксированного j и г.

Для рассматриваемой игры соотношение (*) выполняется при і* = = 3, j* = 1; при этом цена игры v = 18. Если игрок Ji отступит от своей оптимальной стратегии, соответствующей і* = 3, а игрок Ji будет придерживаться своей оптимальной стратегии j* = 1, то первый игрок проиграет более 18 ед. Аналогично если игрок Ji отступит от своей оптимальной стратегии, а игрок Ji будет придерживаться своей оптимальной стратегии, то второй игрок выиграет менее 18 ед.

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

При отсутствии седловой точки в платежной матрице (например, как в игре "угадывание монет"), очевидно, ни одному из игроков не следует постоянно применять одну и ту же чистую стратегию. Здесь естественно определить понятие оптимальной стратегии в классе смешанных стратегий.

m

Пусть векторы X = (х\,... ,хт), 0 < Х\ < 1, ^ х, = 1; у =

i=i

п

= (yi,... ,уп), 0 < уі < 1, ]Г ty = 1, і = 1, 2,... ,т суть смешанные

і=і

стратегии игроков соответственно первого и второго, а матричная игра определяется платежной матрицей С = {су}, і = 1,2,... ,т; j = 1,2,..., п. Тогда математическое ожидание платежа игрока J\ игроку Ji (средний выигрыш игрока Ji) определяется очевидным образом:

т п

Т{х, у) = хСу -r'-r'JHJ(7Л)

1=1 j=l

Как и для случая чистых стратегий, игрок Ji может обеспечить себе средний проигрыш не более

minG(a;) = min[max J7(x, у)], (7.2)

ш зі у

а игрок Ji может обеспечить себе средний выигрыш не менее

maxff(y) = max[min J7(x, у)]. (7.3)

У У з>

85

Задачи (7.2) и (7.3) представляют собой задачи поиска гарантированных смешанных стратегий игроками соответственно первым и вторым.

Если для некоторых фиксированных смешанных стратегий ж* и у* и для всех остальных смешанных стратегий ж, у выполняется

^{х*,у)<Т{х*,у*)<Т{х,у*),

т. е. (ж*, у*) является седловой точкой функции Т(х, у), то доказано, что

Т{х*,у*) = minmax Т(х,у) = maxmin Т(х,у). (7.4) ж     у у ж

Таким образом, если функция Т{х,у), представляющая собой средний выигрыш второго игрока и определяемая соотношением (7.1), имеет седловую точку, то вводятся следующие определения.

Если существует седловая точка (ж*,у*) функции Т{х, у), то ее компоненты ж* и у* называются соответственно оптимальными стратегиями игроков J\ и Ji, а Т{х*,у*) — ценой игры. При этом также говорят, что матричная игра имеет решение в смешанных стратегиях.

Доказано, что поиск седловой точки (ж*,у*) функции Т{х,у) = = хСу связан с решением двойственных ЗЛП; кроме того, эта точка всегда существует, а это означает, что любая матричная игра разрешима в смешанных стратегиях. Эти результаты сформулируем в виде теорем.

Теорема 1. Задачи (7.2) и (7.3) игроков J\ и Ji эквивалентны следующим ЗЛП:

ticyy~ij—j— ............^ гніті j

m

^ ^ ('ijXі 1 ; j — 1, 2, ... , /I,

i=i (7.5)

m

.r,     1.      .r, > 1.    /    1.2.....in:

i=l

86

Ут+1

Y '''''-'О < Ут+1,

3=1

1,2,...,m, (7.6)

Yvj

3=1

Уз > 1,   j = 1,2,...,п.

Теорема 2 (о минимаксе). Любая матричная игра имеет решение в смешанных стратегиях.

Пример 3. Рассмотрим игру "угадывание монет" с платежной

матрицей С =  ^    j      j ^. Пусть х = (х\,х2); у = (1/1,1/2) —

смешанные стратегии игроков соответственно J\ и J2. Средний выигрыш второго игрока

Т{х,у) = хСу = yi(-жі + х2) + Уі(хі х2).

Задачи (7.2), (7.3) приобретают вид

max[j/i(— Х\ + х2) + у2{х\ — х2)] —¥ min;

У їв

min[j/i(—жі + х2) + У2(хі х2)]

max, у

где

X = (хі,х2), У = (Уі,У2),

X! > О,

Vi >o, ж2 > 0, У2 >0, a*i + x2 = 1; Уі +У2 = 1.

Задачи (7.5), (7.6) записываются в виде

ж3 —mm,

— Жі + Х2 < Хз,

Х\ — Х2 < Хз,

х\ > 0,   х2 > 0;

Уз -*> max, -Уі + У2 > Уз,

Уі У2 > УЗ,

уі>0, у2>0.

Решая эти двойственные ЗЛП (например, с помощью симплекс-метода), получаем оптимальные смешанные стратегии х* = = (1/2; 1/2); у* = (1/2; 1/2) игроков соответственно J\ и J2. При этом цена игры Т(х*,у*) = 0.

87

Как отмечалось в случае чистых стратегий, если один из игроков придерживается своей оптимальной стратегии, а второй отступает от своей оптимальной стратегии, то последний (отступающий) игрок либо выигрывает меньше, либо проигрывает больше. Аналогичные действия игроков в случае смешанных стратегий имеют результат, сформулированный в следующей теореме.

Рассматривается оптимальная смешанная стратегия ж* = (х\,... ...,х*т) игрока J\. Назовем і-ю стратегию игрока активной (существенной), если X* > 0. Аналогично определяются активные стратегии игрока J2.

Теорема (об активных стратегиях). Если игрок J2 придерживается своей оптимальной стратегии у*, то его средний выигрыш

Лх.у') Ну'

остается неизменным и равным цене игры v = J7(x*,y*) независимо от стратегии игрока J\, если только первый (J\) игрок не выходит за пределы своих активных стратегий (пользуется любой из них в чистом виде или смешивает их в любых пропорциях).

Разумеется, теорему можно переформулировать, меняя местами игроков Ji и J2.

( -2     1 \

Пример 4. Игра определяется матрицей С = I     ^      ^   I, не

имеющей седловой точки. Следовательно, ее решение нужно искать в классе смешанных стратегий. Пусть у* = (t/J,t/|) — оптимальная смешанная стратегия игрока J2. В силу сказанного она удовлетворяет системе уравнений

V = —2yJ + J/J,

V =     l/i 2/2, УІ+У2 = 1,

откуда у* = (2/5;3/5),«= -1/5.

Аналогично находим оптимальную смешанную стратегию игрока Л: ж* = (2/5;3/5).

88

 

 ...  10



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх