Смешанные стратегии и их свойства

Если матричная игра не имеет седловой точки, то решение игры затрудняется. В этих играх . Примене­ние минимаксных стратегий в таких играх приводит к тому, что для каждого из игроков выигрыш не превышает , а проигрыш – не меньше . Для каждого игрока возни­кает вопрос увеличения выигрыша (уменьшения проигры­ша). Решение находят, применяя смешанные стратегии.

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

р = , где ,

q =, где .

Вектор p (q) означает вероятность применения i -й чис­той стратегии первым игроком (j -й чистой стратегии вто­рым игроком).

Поскольку игроки выбирают свои чистые стратегии случайно и независимо друг от друга, игра имеет случай­ный характер и случайной становится величина выигрыша (проигрыша). В таком случае средняя величина выигры­ша (проигрыша) – математическое ожидание – являет­ся функцией от смешанных стратегий р, q:

.

Функция f (p, q) называется платежной функцией игры.

Стратегии р* = , q* =называ­ются оптимальными, если для произвольных стратегий р = , q =выполняется условие:

. (6.3)

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

Совокупность оптимальных стратегий и цены игры со­ставляет решение игры.

Значение платежной функции при оптимальных страте­гиях определяет цену игры, т. е.

Теорема 6.2. В смешанных стратегиях любая конечная матричная игра имеет седловую точку.

Пусть имеем матричную игру и некоторые смешанные оптимальные стратегии р *, q * игроков А и В, обеспечивающие сумму выигрыша v. Вопрос поставим так: как проверить, что набор (р *, q *, v) является решени­ем игры? Для этого нужно проверить справедливость неравенства (6.3) для любых смешанных стратегий, среди которых и будут стратегии р *, q *. Однако различных сме­шанных стратегий, среди которых и оптимальные, имеем бесчисленное множество. И в таком случае проверить справедливость неравенства (6.3) невозможно. Поэтому рассмотрим следующую теорему, которая позволит отве­тить на поставленный выше вопрос.

Теорема 6.3. Для того чтобы смешанные стратегии р*= , q* =были оптимальными для игроков А и В в игре с матрицей и выигры­шем v, необходимо и достаточно выполнения неравенств:

, (6.4)

. (6.5)

Доказательство. Пусть р *, q * – оптимальные смешанные стратегии. Докажем, что для них выполняются соотношения (6.4) и (6.5). Воспользуемся определением оптимальных смешанных стратегий, для которых выпол­няется соотношение (6.3). Неравенство (6.4) получается из соотношения (6.3), если записать его в развернутой форме, а именно:

(6.6)

В правую часть соотношения (6.6) подставим вектор q = (0;...; 0; 1; 0;...; 0). По­лучим

,

т. е. оптимальная стратегия p * удовлетворяет неравен­ству (6.4).

Если вместо произвольного вектора р в левую часть соотношения (6.6) подставить вектор р * = (0;...; 0; 1; 0;...; 0), то аналогично можно показать, что и оптимальная стратегия q * удовлетворяет соотноше­нию (6.5).

Итак, доказано условие необходимости, а именно: если стратегии р * и q * оптимальные, то они должны удовле­творять соотношениям (6.4) и (6.5).

Теперь докажем достаточность этого условия. Пусть выполняются неравенства (6.4), (6.5). Покажем, что р *, q * - оптимальные стратегии. Для этого нужно показать выполнимость соотношения (6.6). С учетом соотношения (6.4) преобразуем правую часть, а с учетом соотношения (6.5) – левую часть соотношения (6.6).

Пусть q =- произвольный вектор, тогда

.

Преобразуя левую часть соотношения (6.6) для произ­вольного вектора р = , получаем

.

Итак, доказано, что если выполняются соотношения (6.4), (6.5), то выполняется и соотношение (6.6), т. е. сме­шанные стратегии р * и q * – оптимальные.

Таким образом, для проверки того, что набор (р *, q *, v) является решением матричной игры, достаточно проверить, удовлетворяют ли р *, q * неравенствам (6.4) и (6.5) и уравнениям

На основании данной теоремы можно сделать вывод: если игрок А применяет оптимальную смешанную страте­гию р*, а игрок В – любую чистую стратегию, то выиг­рыш игрока А будет не меньше цены. игры.

Аналогично: если игрок В использует оптимальную смешанную страте­гию q *, а игрок А – любую чистую стратегию, то про­игрыш игрока В не превысит цены игры.

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

Теорема 6.4. Если один из игроков придерживается своей оптимальной смешанной стратегии, то его выигрыш остается неизменным и равным цене игры независимо от того, какую стратегию применяет другой игрок, если толь­ко тот не выходит за пределы своих активных стратегий.

На основании данной теоремы решение матричной игры можно упростить, выявив при этом доминирование одних стратегий над другими. Так, рассматривая страте­гии игрока А, сравниваем соответствующие элементы строк s и t. Если все элементы s -й строки не меньше элементов
t -й строки, то выигрыш игрока А при стратегии A_s будет больше, чем при стратегии A_t. В этом случае стратегия A_s доминирует над стратегией A_t. Стратегию A_s называют доминирующей, а стратегию A_t – доминируемой.

Аналогично, поскольку игрок В заинтересован в минимизации про­игрыша, доминирующим будет столбец с наименьшими элементами.

Если в матричной игре имеем строки (столбцы) с одними и теми же элементами, то строки (столбцы), а со­ответственно и стратегии игроков А и В, называются дублирующими.

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

Теорема 6.5. Оптимальные смешанные стратегии р* и q* соответственно игроков А и В в матричной игре с ценой v будут оптимальными и в матричной игре ценой v'=bv+c, где b>0.

На основании теоремы 6.5 платежную матрицу, имею­щую отрицательные числа, можно преобразовать в матри­цу с положительными числами.