20. Свойства оптимальных смешанных стратегий в матричной игре.

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

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

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

1 свойство. Если x" = ( x₁, x₂, ... x_m ) и y" = ( y₁, y₂,...y_n ) - оптимальные смешанные стратегии игроков в матричной игре, то для произвольных стратегий x и y справедливо

Н ( А, x", y) = å a_ij x_i" ³ v для всех j=1:n, так как это равносильно использованию вторым игроком чистой j-той стратегии: y = ( 0, 0,...y_j=1,... 0, 0 )

Н ( А, x, y") = å a_ij y_j" £ v для всех i=1:m, так как это равносильно использованию первым игроком чистой i-той стратегии: x = ( 0, 0,...x_i=1,... 0, 0 )

2 свойство. Если в матричной игре с матрицей А и ценой игры v стратегии x" и y" - оптимальные, то

если å a_ij x_i" > v, то y_j" = 0

если å a_ij y_j" < v, то x_i" = 0

если неравенства обращаются в равенства, то соответственно:

xi" ¹ 0, yj" ¹ 0.

На приведенных свойствах основано решение матричных игр в смешанных стратегиях.

21. Графический метод решения матричной игры (2´m).

22. Графический метод решения матричной игры (n´2).

23. Активные (существенные) стратегии игроков. Теоремы об активных стратегиях.

24. Принцип доминирования стратегий двух игроков. Теоремы о доминируемых стратегиях.

Рассмотрим несколько методов упрощения платёжных матриц.

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

Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B.

Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры.

Частный случай доминирования является дублирование стратегий.

Если платёжная матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляем только одну строку, а остальные строки (столбцы) отбрасываем. Отброшенным стратегиям припишем нулевые вероятности.

Упрощение (уменьшение размерности) платёжных матриц за счёт исключения заведомо невыгодных чистых стратегий возможно в силу справедливости следующей Теоремы о доминирующих стратегиях:

Пусть I - игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G - игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда:

4. цена игры I равна цене игры G;

5. оптимальная смешенная стратегия Q^*= (q₁^*,q₂^*,…,q_n^*) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I;

6. если P^*= (p₁^*,p₂^*,…,p_i^*, p*_i+2,…, p_m^*) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P^*= (p₁^*,p₂^*,…,p_i^*, p*_i+2,…, p_m^*) является оптимальной в игре I.

Из выше сказанного следует, что как первому, так и второму нет смысла использовать доминируемую стратегию, поэтому все доминируемые стратегии могут быть отброшены, т.е. фактически отброшены строки и столбцы исходной матрицы A, соответствующие этим строкам. Это преобразование уменьшает размерность исходной платёжной матрицы A, тем самым упрощается поиск оптимального решения.

Рассмотрим ряд примеров с использованием калькулятора Решение матричной игры.

ПРИМЕР 1. Платёжная матрица игры задана в виде: .

Упростим игру (упростим платёжную матрицу).

1-я и 4-я строки равны. Поэтому отбросим 4-ю строку. Вероятность p₄ = 0. Получим матрицу:

.

2-я строка доминирует над 3-й строкой (6 > 3, 5 > 4, 8 = 8, 7 > 6). Поэтому отбросим 3-ю строку. Вероятность p₃ = 0. Получим матрицу:

.

2-й столбец доминирует над 3-м столбцом (9 = 9, 5 < 8). Поэтому отбросим 3-й столбец. Вероятность q₃ = 0. Получим матрицу:

.

Строки между собой не сравнимы (8 > 6, 4 < 7), столбцы тоже (8 < 9, 6 > 5; 8 > 4, 6 < 7; 9 > 4, 5 < 7). Дальнейшее упрощение невозможно. Мы свели игру 4×4 к игре 2×3.