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

Понятие доминирования используется при решении или упрощении некоторых типов некооперативных игр .

Терминология

При выборе своей стратегии из множества допустимых игрок сравнивает по предпочтительности исходы от их применения. Может возникать три типа результатов:

• Стратегия В доминирует стратегию A, если при любом поведении остальных игроков использование стратегии В приводит к не худшему исходу, нежели использование А. Различают строгое доминирование , когда В дает больший выигрыш, чем А, в любых условиях, и слабое доминирование , если при некоторых действиях других игроков В обеспечивает больший выигрыш, чем А, а при других — одинаковый с ней.
• Стратегия В доминируется стратегией A, если при любом поведении остальных игроков стратегия В приводит к не лучшему исходу, нежели стратегия А. Аналогично предыдущему случаю, стратегия может доминироваться строго и слабо.
• Стратегии А и В называются нетранзитивными , если В не доминирует А и А не доминирует В. Это оначает, что в зависимости от выбора стратегий другими игроками, большие выигрыши игроку может обеспечивать как выбор стратегии А, так и В.

Это понятие обобщается на сравнение более чем двух стратегий:

• Стратегия B называется строго доминирующей , если она строго доминирует любую другую допустимую стратегию игрока.
• Стратегия B называется слабо доминирующей , если она доминирует любую другую допустимую стратегию игрока, при этом некоторые из них доминируются слабо.
• Стратегия B называется строго доминируемой , если существует другая стратегия, которая строго её доминирует.
• Стратегия B называется слабо доминируемой , если существует другая стратегия, которая слабо её доминирует.

Формальные определения

Говорят, что стратегия ${\displaystyle s^{*}\in S_{i}}$ игрока ${\displaystyle i}$ слабо доминирует стратегию ${\displaystyle s^{\prime }\in S_{i}}$ , если

${\displaystyle \forall s_{-i}\in S_{-i}:u_{i}(s^{*},s_{-i})\geq u_{i}(s^{\prime },s_{-i})}$ , причем хотя бы одно неравенство выполнено строго.

Здесь ${\displaystyle S_{-i}}$ представляет собой прямое произведение стратегических множеств всех игроков, кроме ${\displaystyle i}$ -го.

Стратегия ${\displaystyle s^{*}}$ строго доминирует ${\displaystyle s^{\prime }}$ , если

${\displaystyle \forall s_{-i}\in S_{-i}:u_{i}(s^{*},s_{-i})>u_{i}(s^{\prime },s_{-i})}$ .

Доминирование и равновесия Нэша

	C	D
C	1, 1	0, 0
D	0, 0	0, 0
Слабое доминирование

Если для одного из игроков существует строго доминирующая стратегия, он будет её использовать в любом из равновесий Нэша в игре. Если все игроки имеют строго доминирующие стратегии, игра имеет единственное равновесие Нэша. Однако, это равновесие не обязательно будет эффективным по Парето , т.е. неравновесные исходы могут обеспечить всем игрокам больший выигрыш. Классическим примером этой ситуации является игра « Дилемма заключенного ».

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

Здесь стратегии D обоих игроков слабо доминируются их стратегиями C . Однако, ситуации ( D , D ) является равновесием Нэша в этой игре. Действительно, ни один из игроков, отклоняясь от использования D , не сможет получить большего выигрыша, если другой игрок придерживается D .

Последовательное исключение доминируемых стратегий

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

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

Пример

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

Пусть в игре участвуют игроки A и B. Для игрока A доступны стратегии a ₁ и a ₂ , для игрока B — стратегии b ₁ , b ₂ , b ₃ . Игроки выбирают стратегии одновременно и независимо друг от друга. В таблице приведены платежи, которые получают игроки, сыграв свою стратегию, в зависимости от выбранной стратегии другого игрока. Первая цифра в ячейке — платёж первого игрока, цифра после точки с запятой — платёж, получаемый вторым игроком.

Исходная таблица. Например, из таблицы видно, что если игрок A сыграет стратегию a ₂ , а игрок B сыграет стратегию b ₃ , то игрок A получит 4 очка, а игрок B — 1 очко.

	b 1	b 2	b 3
a 1	6 ; 5	3 ; 6	3 ; 9
a 2	7 ; 7	3 ; 0	4 ; 1

Можно заметить, что вне зависимости от выбора игрока A, для второго игрока стратегия b ₂ уступает по своим характеристикам стратегии b ₃ (6 < 9 и 0 < 1).

	b 1	b 2	b 3
a 1	6 ; 5	3 ; 6	3 ; 9
a 2	7 ; 7	3 ; 0	4 ; 1

Поэтому столбец со стратегией b ₂ можно не учитывать в дальнейшем рассмотрении, вычёркиваем его. С точки зрения игрока A, среди оставшихся стратегий, a ₁ явно уступает a ₂ (6 < 7 и 3 < 4)

	b 1	b 3
a 1	6 ; 5	3 ; 9
a 2	7 ; 7	4 ; 1

Вычёркиваем строку со стратегией a ₁ . В таблице платежей остаётся всего две ячейки, и для второго игрока стратегия b ₁ явно предпочтительнее стратегии b ₃ (1 < 7).

	b 1	b 3
a 2	7 ; 7	4 ; 1

Таким образом, исключением строго доминируемых стратегий мы решили игру: рациональные игроки сыграют стратегии b ₁ и a ₂ , каждый игрок получит платёж равный 7.

Примечания

Литература

• Васин А. А. , Морозов В. В. Теория игр и модели математической экономики. — М. : Макс-пресс, 2005. — 272 с. — ISBN 5-317-01388-7 .
• Васин А.А. Некооперативные игры в природе и обществе. М.: Макс Пресс, 2005, 412 с. ISBN 5-317-01306-2 .
• Данилов В. И. . — М.: РЭШ, 2002. — 140 с. : ил. ISBN 5-8211-0193-X
• Петросян Л. А. , Зенкевич Н.А., Семина Е.А. Теория игр: Учеб. пособие для ун-тов. — М. : Высш. шк., Книжный дом «Университет», 1998. — С. 304. — ISBN 5-06-001005-8 , 5-8013-0007-4.
• Печерский, С.Л., Беляева, А.А. Теория игр для экономистов. Вводный курс. (Учебное пособие) — СПб.: Изд-во Европейского университета, 2001.