Доминирование стратегий

Говорят, что некоторая стратегия i первого игрока (задаваемая i-й строкой платежной матрицы) доминируется некоторой другой стратегией k первого игрока, если все элементы строки i не больше соответствующих элементов строки k, а именно: .

Аналогичное определение можно привести для стратегий второго игрока, а именно: некоторая стратегия j второго игрока (задаваемая j-м столбцом платежной матрицы) доминируется некоторой другой стратегией k второго игрока, если все элементы столбца j не меньше соответствующих элементов столбца k, а именно: .

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

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

Рассмотрим игру, представленную платежной матрицей:

a ¹ b.

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

.

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

.

Ее решение найдено ранее. Однако оптимальное решение исходной игры будет иметь отличный вид. Оно должно отразить, что первый игрок не будет использовать вторую и четвертую стратегию, а второй игрок не будет использовать первую, вторую и третью стратегии. Поэтому решение имеет вид:

; ;

.

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