§2.1.2. Доминирование стратегий. Редукция игры.
Решение игры в доминирующих стратегиях.

В этом параграфе пойдет речь о попарном сравнении между собой стратегий игрока. Иногда в результате такого сравнения делается вывод о превосходстве (т.е. доминировании) одной стратегии над другой. Рассмотрим пример.


Пример. Дана платёжная матрица A:

Первый игрок выбирает строку,
второй выбирает столбец.




Второй игрок может заметить, что элементы 4-го столбца соответствующих элементов 2-го столбца. А как было указано выше второй участник стремиться минимизировать аij Значит, при любых действиях соперника 2-я стратегия оказывается лучше или не хуже, чем 4-я. В таких случаях говорят, что 2-я стратегия доминирует над 4-й. Следовательно, 4-ю стратегию 2-й участник может вычеркнуть, аналогично. продолжая рассуждения и сравнивая 1 и 3 стратегии второго игрока, платёжная матрица примет следующий вид: случаях говорят, что 2-я стратегия доминирует над 4-й. Следовательно, 4-ю стратегию 2-й участник может вычеркнуть, аналогично. продолжая рассуждения и сравнивая 1 и 3 стратегии второго игрока, платёжная матрица примет следующий вид:

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

Дадим общее определение доминирования стратегий.
Говорят, что стратегия l доминирует стратегию k для 1-го участника, если для всех значений j=1,2…,n справедливы неравенства alj≥akj, и хотя бы для одного значения j неравенство является строгим.

Аналогично:
Говорят, что стратегия l доминирует стратегию k для 2-го участника, если для всех значений i=1,2…,m справедливы неравенства ail≤aik, и хотя бы для одного значения i неравенство является строгим.
Вычёркивание доминируемых стратегий называется редукцией (сокращением игры). В результате редукции уменьшается размерность платёжной матрицы.

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

Пример. Кот Базилио и лиса Алиса узнали, где спрятан золотой ключик. Каждый из них может сказать об этом либо Карабасу, либо черепахе Тортилле. Если оба расскажут черепахе, или оба расскажут Карабасу, то оба получат одинаковую награду (для простоты возьмем ее за 0). Если один расскажет черепахе, а другой Карабасу, то Карабас заберет один золотой у того, кто рассказал черепахе, и отдаст золотой тому, кто рассказал Карабасу. Найти рациональные стратегии Алисы и Базилио.

Решение. Составим платежную матрицу:

Базилио
Карабасу Черепахе
Алиса Карабасу 0 1
Черепахе -1 0

Мы видим, что у Алисы 1-я стратегия доминирует 2-ю, т.к. 0>-1, 1>0. Поэтому Алиса выберет 1-ю стратегию. Базилио, как рациональный игрок, поймет это из анализа платежной матрицы, и тоже выберет 1-ю стратегию, т.к. в первой строке 1<0. В результате оба расскажут о ключике Карабасу.