Доминирование (теория игр)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\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.

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

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

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

Литература

• Васин А. А., Морозов В. В. Теория игр и модели математической экономики. — М., 2005.
• Данилов В.И. Лекции по теории игр. - М.: Российская экономическая школа, 2002.
• Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. — М.: Высшая школа, 1998.
• Печерский, С.Л., Беляева, А.А. Теория игр для экономистов. Вводный курс. (Учебное пособие) — СПб.: Изд-во Европейского университета, 2001.