В теории игр доминирующая стратегия — это стратегия , которая лучше любой другой стратегии для одного игрока, независимо от того, как будет играть его противник. Некоторые очень простые игры можно решить с помощью доминирования.
Игрок может сравнить две стратегии, A и B, чтобы определить, какая из них лучше. Результатом сравнения является один из следующих:
Эту концепцию можно обобщить и дальше сравнения двух стратегий.
Стратегия: Полный контингентный план для игрока в игре. Полный контингентный план — это полная спецификация поведения игрока, описывающая каждое действие, которое игрок предпримет в каждой возможной точке принятия решения. Поскольку наборы информации представляют собой точки в игре, где игрок должен принять решение, стратегия игрока описывает, что этот игрок будет делать в каждом информационном наборе. [2]
Рациональность: предположение, что каждый игрок действует таким образом, который предназначен для достижения того, что он или она больше всего предпочитает, учитывая вероятности различных результатов; фон Нейман и Моргенштерн показали, что если эти предпочтения удовлетворяют определенным условиям, это математически эквивалентно максимизации выигрыша. Простым примером максимизации выигрыша является денежный выигрыш, но для целей анализа теории игр этот выигрыш может принимать любой желаемый результат — денежное вознаграждение, минимизация усилий или дискомфорта или содействие справедливости — все это может быть смоделировано как накопление общей «полезности» для игрока. Предположение о рациональности гласит, что игроки всегда будут действовать таким образом, который наилучшим образом удовлетворяет их упорядочиванию от лучшего к худшему из различных возможных результатов. [2]
Общие знания : предположение, что каждый игрок имеет знания об игре, знает правила и выплаты, связанные с каждым курсом действий, и понимает, что каждый другой игрок имеет такой же уровень понимания. Это предпосылка, которая позволяет игроку выносить оценочное суждение о действиях другого игрока, подкрепленное предположением о рациональности, во внимание при выборе действия. [2]
Если для одного игрока в игре существует строго доминирующая стратегия, этот игрок будет использовать эту стратегию в каждом из равновесий Нэша игры . Если у обоих игроков строго доминирующая стратегия, в игре есть только одно уникальное равновесие Нэша, называемое «равновесием доминирующей стратегии». Однако это равновесие Нэша не обязательно «эффективно», что означает, что могут быть неравновесные результаты игры, которые были бы лучше для обоих игроков. Классическая игра, используемая для иллюстрации этого, — « Дилемма заключенного» .
Строго доминируемые стратегии не могут быть частью равновесия Нэша, и, как таковые, для любого игрока нерационально играть их. С другой стороны, слабо доминируемые стратегии могут быть частью равновесия Нэша. Например, рассмотрим матрицу выплат, изображенную справа.
Стратегия C слабо доминирует над стратегией D. Рассмотрим игру C : если противник играет C, игрок получает 1; если противник играет D, игрок получает 0. Сравните это с D, где игрок получает 0 независимо от этого. Поскольку в одном случае игрок выигрывает, играя C вместо D , и никогда не проигрывает, C слабо доминирует над D. Несмотря на это, является равновесием Нэша. Предположим, что оба игрока выбирают D. Ни один из игроков не добьется большего, отклонившись в одностороннем порядке — если игрок переключается на игру C, он все равно получит 0. Это удовлетворяет требованиям равновесия Нэша. Предположим, что оба игрока выбирают C. Ни один из игроков не добьется большего, отклонившись в одностороннем порядке — если игрок переключается на игру D, он получит 0. Это также удовлетворяет требованиям равновесия Нэша.
Итеративное устранение (или удаление, или удаление) доминируемых стратегий (также называемое IESDS, или IDSDS, или IRSDS) является одним из распространенных методов решения игр, который включает в себя итеративное удаление доминируемых стратегий. На первом этапе все доминируемые стратегии удаляются из пространства стратегий каждого из игроков, поскольку ни один рациональный игрок никогда не будет играть этими стратегиями. Это приводит к новой, меньшей игре. Некоторые стратегии, которые ранее не были доминируемыми, могут быть доминируемыми в меньшей игре. Первый этап повторяется, создавая новую, еще меньшую игру, и так далее.
Этот процесс является допустимым, поскольку предполагается, что рациональность среди игроков является общеизвестным фактом , то есть каждый игрок знает, что остальные игроки рациональны, и каждый игрок знает, что остальные игроки знают, что он знает, что остальные игроки рациональны, и так до бесконечности (см. Aumann, 1976).
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )