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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \forall s_{-i}\in S_{-i}: u_i(s^*,s_{-i})\gt u_i(s^\prime,s_{-i}) }[/math].

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

Основная статья: Равновесие в доминирующих стратегиях

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

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

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

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

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

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

Пример

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

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

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

	b1	b2	b3
a1	6 ; 5	3 ; 6	3 ; 9
a2	7 ; 7	3 ; 0	4 ; 1

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

	b1	b2	b3
a1	6 ; 5	3 ; 6	3 ; 9
a2	7 ; 7	3 ; 0	4 ; 1

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

	b1	b3
a1	6 ; 5	3 ; 9
a2	7 ; 7	4 ; 1

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

	b1	b3
a2	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.