Решение игр в смешанных стратегиях
Как мы отмечали выше, если матричная игра содержит седловую точку, то ее решение находится по принципу мини- макса. Если же платежная матрица не имеет седловой точки, то применение минимаксных стратегий каждым из игроков показывает, что игрок I обеспечит себе выигрыш не меньше а, а игрок II обеспечит себе проигрыш не больше р. Так как а < р, то игрок I стремится увеличить выигрыш, а игрок II — уменьшить проигрыш. Если информация о действиях противной стороны будет отсутствовать, то игроки будут многократно применять чистые стратегии случайным образом с определенной вероятностью. Такая стратегия в теории игр называется смешанной стратегией. Из сказанного следует, что смешанная стратегия игрока — это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Для применения смешанных стратегий требуются следующие условия:
- 1) в игре отсутствует седловая точка;
- 2) игроками используется случайная смесь чистых стратегий с соответствующими вероятностями;
- 3) игра многократно повторяется в одних и тех же условиях;
- 4) при каждом из ходов один игрок не информирован о выборе стратегии другим игроком.
Основная теорема теории игр Дж. фон Неймана: каждая конечная игра имеет по крайней мере одно оптимальное решение в смешанных стратегиях. Следствие: каждая конечная игра имеет цену, являющуюся математическим ожиданием выигрыша игрока I и проигрыша игрока II, причем выигрыш, соответствующий оптимальному решению, называется ценой игры у и удовлетворяет условию а < у < р. Каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат. Оптимальное решение игры в смешанных стратегиях обладает следующим свойством: каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет оптимальную смешанную стратегию, так как это ему невыгодно.
Чистые стратегии игроков в их оптимальных смешанных стратегиях называются активными. В теории игр доказывается следующая теорема об активных стратегиях.
Теорема. Применение оптимальной смешанной стратегии обеспечивает игроку максимальный средний выигрыш (или минимальный средний проигрыш), равный цене игры у, независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий.
Смешанные стратегии игроков I и II, применяющих соответственно стратегии А, А2,Ат и В{, Въ ..., Bw обозначим через
т п
где> 0, q; > 0, XPi = 1, = 1;РьРъ -,рт ~ вероятности ис-
i-i г 1
пользования игроком I стратегий Аь А2,Ат qh q2,..., qn — вероятности использования игроком II стратегий В, В2у..., Вп.
Смешанную стратегию игрока I — S можно записать как
Соответственно для игрока II
Зная платежную матрицу Л, можно определить средний выигрыш (математическое ожидание) М(А,р, q)
где р и q — векторы с компонентами ph р2,..., рт и qh q2,..., qn соответственно.
Игрок I, применяя свои смешанные стратегии, стремится увеличить свой средний выигрыш, достигая
Игрок II добивается
Обозначим через р и q*B векторы, соответствующие оптимальным смешанным стратегиям игроков I и II, при которых выполняется равенство
При этом выполняется условие
Решить игру — это означает найти цену игры и оптимальные стратегии.
Рассмотрим наиболее простой случай конечных игр 2x2 без седловой точки с матрицами
т.е. имеется платежная матрица
Требуется найти оптимальные смешанные стратегии иг- роков S[ = (p*,pl) (Р +Р2= 1). = (?1*>
ну игры у.
Каковы бы ни были действия противника, выигрыш будет равен цене игры у. Это означает, что если игрок I придерживается своей оптимальной стратегии S{(р>Р2)> то игроку II нет смысла отступать от своей оптимальной стратегии S*u ql).
В игре 2X2, не имеющей седловой точки, обе стратегии являются активными.
Для игрока I имеем систему уравнений
Для игрока II аналогично:
Если у ^ 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы не равен нулю, следовательно, системы (3.17) и (3.18) имеют единственное решение.
Решая системы уравнений (3.17) и (3.18), находим оптимальные решения S = (рьРг), Sц = (q, г/2) и у
Пример 3.6. Дана платежная матрица
Найдите решение.
Решение. Так как а = 3, р = 5, то а ^ (3, следовательно, игра не имеет седловой точки, цена игры находится в пределах 3 < у < 5, решение можно найти в смешанных стратегиях. Запишем систему уравнений:
• для игрока I
• для игрока II
Решая системы (3.21) и (3.22), находим
Следовательно, оптимальные смешанные стратегии игроков имеют вид
