Доминирующие и доминируемые стратегии

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

Это можно сделать, если в ней имеются доминирующие и доминируемые строки и столбцы.

Если в матрице игры Все элементы строки А_i = (a_i1, a_i2, …, a_in) не меньше соответствующих элементов строки А_k = (a_k1, a_k2, …, a_kn) и, по крайней мере, один элемент строго больше, то строка А_i (и соответствующая стратегия) называется доминирующей, а строка А_k (и соответствующая стратегия) – доминируемой.

Аналогичны понятия доминирующий столбец (и соответствующая стратегия) и доминируемый столбец (и соответствующая стратегия).

Игроку А не целесообразно применять стратегии, которым соответствуют доминируемые строки, а игроку В – стратегии, которым соответствуют доминирующие столбцы. Поэтому при решении игры можно уменьшить размерность платежной матрицы путем удаления из нее доминирующих столбцов и доминируемых строк.

Пример 2. Платежная матрица игры имеет вид

Н =

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

Решение. В матрице Н строка 3 доминирует над строкой 2 (6> 4; -1> -2; 4> 3), поэтому строку 2 можно удалить из платежной матрицы. В результате удаления матрица примет вид

Н₁ = .

В матрице Н₁ первый и третий столбцы доминируют над вторым (2> -3; 6> -1 и 5> -3; 4> -1), следовательно, их можно удалить из матрицы Н₁. В результате платежная матрица преобразуется в вектор столбец

Н₂ = .

В матрице Н₂ вторая строка доминирует над первой, следовательно платежная матрица вырождается в один элемент

Н₃ = (-1).

Из анализа матрицы Н следует, что игрок А должен выбрать стратегию А₃, а игрок В – стратегию В₂. Эти стратегии будут чистыми оптимальными, а цена игры V = -1.

Для проверки решим игру, не проводя упрощений:

α ₁ = -3, α ₂ = -2, α ₃ = -1, тогда α = -1;

β ₁ = 6, β ₂ = -1, β ₃ = 5, тогда β = -1;

Таким образом, α = β = -1, т.е. задача имеет седловую точку, V = -1 и оптимальными являются чистые стратегии А₃ и В₂, что и подтверждает правильность первого варианта решения задачи.

Задание 1. В соответствии с номером фамилии в журнале решить игру с заданной платежной матрицей. Дать интерпретацию полученных результатов.

Вариант 1. Н = . Вариант 2. Н = .

Вариант 3. Н = . Вариант 4. Н = .

Вариант 5. Н = . Вариант 6. Н = .

Вариант 7. Н = . Вариант 8. Н =

Вариант 9. Н = . Вариант 10. Н = .

. Вариант 11. Н= . Вариант 12. Н = .

Вариант 13. Н = . Вариант 14. Н = .

Вариант 15. Н = . Вариант 16. Н = .

Вариант 17. Н = Вариант 18. Н =

Вариант 19. Н = Вариант 20. Н =

Вариант 21. Н = Вариант 22. Н =

Вариант 23. Н = Вариант 24. Н =

Вариант 25 Н = Вариант 26 Н =

Вариант 27 Н = Вариант 28 Н =

Вариант 29 Н = Вариант 30 Н =

Вариант 31 Н = Вариант 32 Н =