Доминирование

Определение. Пусть дана матрица ; будем говорить, что i -я строка доминирует j -ю строку, если для всех и по крайней мере для одного

Аналогично, будем говорить, что k -й столбец доминирует l -й столбец, если для всех и по крайней мере для одного

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

Теорема. Пусть - платежная матрица игры, и пусть строки матрицы доминируются. Тогда игрок А имеет такую оптимальную стратегию , что ; кроме того, любая оптимальная стратегия для игры, получающейся в результате удаления доминируемых строк, будет так же оптимальной стратегией для исходной игры.

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