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

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

Стратегии Р' — Первого и О' — Второго называются оптимальными, если М(Р, О'} < М(Р', О') ^ М(Р', О) для любых стратегий Р — Первого и 0 — Второго игроков.

Величина М(Р', О'), т.е. средний выигрыш Первого при игре обоих игроков с оптимальными стратегиями, называется ценой игры и обозначается v.

Из определения оптимальных стратегий видно, что они образуют ситуацию равновесия в смысле Нэша в матричной игре — ни одному из игроков невыгодно отходить от своей оптимальной стратегии, если другой будет продолжать придерживаться своей оптимальной стратегии. Напомним, что с ситуацией равновесия по Нэшу мы уже имели дело в лекциях 3.2 и 4.2.

5. Матричная игра имеет решение в смешанных стратегиях.

10. Игра с нулевой суммой

Докажем, что цена игры с матрицей А из п. 1 положительна. Действительно, пусть Первый играет со стратегией Р' из примера 1, тогда, как доказано в примере 1, М(Р', 0^1 для любой стратегии О Второго, следовательно, М(Р', 0') > 1 также. Но, по определению, М(Р', ()') < М(Р', ()') = v, что и требовалось доказать.

Пусть }У(г, 0 — выигрыш Первого при использовании им чистой г-й стратегии, а Вторым — стратегии О, ]у(р,]~) — выигрыш Первого при использовании им стратегии Р, а Вторым — чистой ]-». стратегии, М(1, О), М(Р, ]) — математические ожидания выигрышей Первого при таких стратегиях.

Имеют место следующие легко проверяемые соотношения: М(Р, О) =

⁼ Т.Р.Щ1,0) = е^м(ду) = ЕЕ^о.^ = Е2>,^ •

ЯП

Предложение 1. Пусть Р', О' — оптимальные стратегии Первого и Второго соответственно, v — цена игры. Если р\ > 0, то

М(^, 0') ^ v; аналогично, если ^ > 0, то М(Р\ Г) = v. Доказательство. Из определения оптимальных стратегий имеем

МО, (У) < удля любого I = 1,..., т. Отсюда получаем v = ^р\М(1, О») ^

|

<\р^у+р'1,М(1с, (,))<. У р\у+р'^= v. Значит, все неравенства есть

1^1( <*А

равенства и потому р[М(1^, (,)') = р'^, а поскольку р\ > 0, то

М(1с, д') = v.

Другое утверждение доказывается аналогично.

Решение игр в чистых стратегиях и седловые точки матрицы игры

Элемент а, матрицы А называется седловой точкой, если а,^ ^

< а <= а для любых 7 = 1,..., и и г = 1,..., т.

Пример 4. Построить матрицу с седловой точкой. Решение. Пишем любой элемент а. Затем по горизонтали пишем несколько чисел, не меньших а, а по вертикали — несколько чисел, не больших а. Затем дополняем построенный «крест» любыми числами до прямоугольной таблицы чисел, которая и есть матрица, в которой элемент а есть седловая точка. Вот (2 1-1) -200 6 13' 7-2 0;

Теорема 2. Матричная игра имеет решение в чистых стратегиях если и только если в матрице игры есть седловая точка.

Доказательство. Пусть (г'о, }о) — «^ оптимальных чистых стратегий. Тогда, по определению оптимальных стратегий, М(г, Уо) ^ М'о> Уо) ^$ < М^У) Дл» любых ; = 1,..., т тл] = 1,..., п. Но М(1,]) = Оу, так что имеем а,, < а, , < а, . для любых г= 1, ...,тн}= 1, ..., и, а это и есть ха-

'/0 •О./О О-/

рактеристика того, что <з,^ есть седловая точка.

Доказательство того, что если а^ — седловая точка, то пара чистых стратегий (г'о,7о) ^ть пара оптимальных стратегий, еще проще.