Решение игр в смешанных стратегиях

Как мы отмечали выше, если матричная игра содержит седловую точку, то ее решение находится по принципу минимакса. Если же платежная матрица не имеет седловой точки, то применение минимаксных стратегий каждым из игроков показывает, что игрок I обеспечит себе выигрыш не меньше а, а игрок II обеспечит себе проигрыш не больше р. Так как, а < р, то игрок I стремится увеличить выигрыш, а игрок II — уменьшить проигрыш. Если информация о действиях противной стороны будет отсутствовать, то игроки будут многократно применять чистые стратегии случайным образом с определенной вероятностью. Такая стратегия в теории игр называется смешанной стратегией. Из сказанного следует, что смешанная стратегия игрока — это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Для применения смешанных стратегий требуются следующие условия:

• 1) в игре отсутствует седловая точка;
• 2) игроками используется случайная смесь чистых стратегий с соответствующими вероятностями;
• 3) игра многократно повторяется в одних и тех же условиях;
• 4) при каждом из ходов один игрок не информирован о выборе стратегии другим игроком.

Основная теорема теории игр Дж. фон Неймана: каждая конечная игра имеет по крайней мере одно оптимальное решение в смешанных стратегиях. Следствие: каждая конечная игра имеет цену, являющуюся математическим ожиданием выигрыша игрока I и проигрыша игрока II, причем выигрыш, соответствующий оптимальному решению, называется ценой игры у и удовлетворяет условию, а < у < р. Каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат. Оптимальное решение игры в смешанных стратегиях обладает следующим свойством: каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет оптимальную смешанную стратегию, так как это ему невыгодно.

Чистые стратегии игроков в их оптимальных смешанных стратегиях называются активными. В теории игр доказывается следующая теорема об активных стратегиях.

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

Смешанные стратегии игроков I и II, применяющих соответственно стратегии А, А₂, А_т и В_{, В_ъ …, B_w обозначим через.

где> 0, q; > 0, XPi = 1, = 1;РьРъ —, р_т ~ вероятности ис;

i-i г 1.

пользования игроком I стратегий А_ь А₂, А_т q_h q₂,…, q_n — вероятности использования игроком II стратегий В, В_2у…, В_п.

Смешанную стратегию игрока I — S можно записать как.

Соответственно для игрока II.

Зная платежную матрицу Л, можно определить средний выигрыш (математическое ожидание) М (А, р, q)

где р и q — векторы с компонентами p_h р₂,…, р_т и q_h q₂,…, q_n соответственно.

Игрок I, применяя свои смешанные стратегии, стремится увеличить свой средний выигрыш, достигая

Игрок II добивается.

Обозначим через р и q*_B векторы, соответствующие оптимальным смешанным стратегиям игроков I и II, при которых выполняется равенство.

При этом выполняется условие.

Решить игру — это означает найти цену игры и оптимальные стратегии.

Рассмотрим наиболее простой случай конечных игр 2×2 без седловой точки с матрицами.

т.е. имеется платежная матрица.

Требуется найти оптимальные смешанные стратегии игроков 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), находим.

Следовательно, оптимальные смешанные стратегии игроков имеют вид.