Транспортная задача. Матричные игры: Методические указания к практическим занятиям, страница 14

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

Теорема о седловой точке.  Пара  стратегий   является решением игры тогда и только тогда, когда эта пара седловая. Конечная игра имеет решение тогда и только тогда, когда платёжная матрица содержит (хотя бы один) седловой элемент.

          Доказательство:Утверждение   « - решение игры» по определению эквивалентно выполнению трёх равенств

                                       (23)

Вторая часть  утверждения теоремы следует из первой. Для доказательства  первой части достаточно проверить,  что каждая из систем равенств (22)  и (23)  является следствием другой.

Из равенств (23) и определений величин      и   следует, что

В этой цепочке крайние числа совпадают (равны  ), поэтому оба неравенства обращаются в равенства и      т.е. выполнены равенства (22).

Наоборот, пусть выполнены равенства (22). Тогда

Здесь, кроме (22), использованы определения чисел   и     и   неравенство (19); как и в предыдущей цепочке, все  неравенства обращаются в равенства и, следовательно,    т.е. выполнены равенства  (23). Из доказательства теоремы следует также, что все  седловые элементы платёжной матрицы совпадают между собой и равны цене игры   (если, конечно, такие элементы существуют).

В качестве упражнения предлагаем читателю проверить справедливость доказанной теоремы в примерах  8 и 9: в первом случае матрицы    и 

не содержат седловых элементов, во втором  решениям игры    и   соответствуют седловые элементы 

Смешанные стратегии. В конечной игре без седловых точек (т.е. при ) у игроков нет оптимальных стратегий, а игрок,  «угадавший» выбор противника, получает   большое  преимущество. Пусть, например, игрок   знает, что   выбрал     Тогда  может применить стратегию  , соответствующую наибольшему элементу  го  столбца платежной  матрицы, и выиграть    этот результат, конечно, вполне устраивает игрока     и невыгоден игроку  . Понятно, что в такой ситуации каждый игрок стремится  скрыть свой окончательный выбор и в то же время разведать намерения противника. Любые рассуждения  игрока, стремящегося засекретить свой  выбор, могут быть  восстановлены  разумным противником, которому известны правила игры. Естественный способ сделать собственный выбор непредсказуемым состоит в том, чтобы сделать его случайным.

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

Смешанной  стратегией  игрока    называется вектор                  

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

  где  

Игра в смешанных стратегиях  заключается в следующем. Игроки    и   выбирают  (независимо друг от друга)  определенные  смешанные стратегии    и   соответственно. Затем игрок  организует лотерею, в которой стратегии    выпадают  с вероятностями   а  игрок  - лотерею, в которой    выпадают с вероятностями    Выигрыш игрока   совпадает с проигрышем игрока   и представляет собой случайную величину, для которой  возможные значения    имеют вероятности 

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

                                    (24)

В теории игр переход к случайному выбору стратегий называется  смешанным расширением игры,  стратегии исходной игры называются чистыми. а сама исходная игра – игрой в чистых стратегиях.

Чистой стратегии    поставим в соответствие смешанную стратегию    где  число 1 стоит  на  ом  месте:  применение    заключается в выборе   с вероятностью 1, т.е. во всех партиях. Аналогично связаны чистая стратегия    и смешанная стратегия  

где число 1 стоит на ом месте. Из формулы (24) следует, что