Стратегическое доминирование

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

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

Игрок может сравнить две стратегии, A и B, чтобы определить, какая из них лучше. Результатом сравнения является один из следующих:

• B строго доминирует (>) A: выбор B всегда дает лучший результат, чем выбор A, независимо от того, что делают другие игроки.
• B слабо доминирует (≥) A: выбор B всегда дает по крайней мере такой же хороший результат, как выбор A, независимо от того, что делают другие игроки, и существует по крайней мере один набор действий оппонентов, для которого B дает лучший результат, чем A. (Обратите внимание, что если B строго доминирует A, то B слабо доминирует над A. Поэтому мы можем сказать «B доминирует A» как синоним «B слабо доминирует A».) ^[1]
• B слабо доминирует над A: существует по крайней мере один набор действий оппонентов, для которого B дает худший результат, чем A, в то время как все другие наборы действий оппонентов дают A такой же выигрыш, как B. (Стратегия A слабо доминирует над B).
• B строго доминирует над A: выбор B всегда дает худший результат, чем выбор A, независимо от действий других игроков. (Стратегия A строго доминирует над B).
• Ни A, ни B не доминируют друг над другом: B и A не эквивалентны, и B не доминирует и не доминируется A. Выбор A лучше в некоторых случаях, в то время как выбор B лучше в других случаях, в зависимости от того, как именно противник выбирает играть. Например, B — это «бросить камень», а A — «бросить ножницы» в игре « Камень, ножницы, бумага » .

Эту концепцию можно обобщить и дальше сравнения двух стратегий.

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

Стратегия: Полный контингентный план для игрока в игре. Полный контингентный план — это полная спецификация поведения игрока, описывающая каждое действие, которое игрок предпримет в каждой возможной точке принятия решения. Поскольку наборы информации представляют собой точки в игре, где игрок должен принять решение, стратегия игрока описывает, что этот игрок будет делать в каждом информационном наборе. ^[2]

Рациональность: предположение, что каждый игрок действует таким образом, который предназначен для достижения того, что он или она больше всего предпочитает, учитывая вероятности различных результатов; фон Нейман и Моргенштерн показали, что если эти предпочтения удовлетворяют определенным условиям, это математически эквивалентно максимизации выигрыша. Простым примером максимизации выигрыша является денежный выигрыш, но для целей анализа теории игр этот выигрыш может принимать любой желаемый результат — денежное вознаграждение, минимизация усилий или дискомфорта или содействие справедливости — все это может быть смоделировано как накопление общей «полезности» для игрока. Предположение о рациональности гласит, что игроки всегда будут действовать таким образом, который наилучшим образом удовлетворяет их упорядочиванию от лучшего к худшему из различных возможных результатов. ^[2]

Общие знания : предположение, что каждый игрок имеет знания об игре, знает правила и выплаты, связанные с каждым курсом действий, и понимает, что каждый другой игрок имеет такой же уровень понимания. Это предпосылка, которая позволяет игроку выносить оценочное суждение о действиях другого игрока, подкрепленное предположением о рациональности, во внимание при выборе действия. ^[2]

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

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

Стратегия C слабо доминирует над стратегией D. Рассмотрим игру C : если противник играет C, игрок получает 1; если противник играет D, игрок получает 0. Сравните это с D, где игрок получает 0 независимо от этого. Поскольку в одном случае игрок выигрывает, играя C вместо D , и никогда не проигрывает, C слабо доминирует над D. Несмотря на это, ⁠ ⁠${\displaystyle (D,D)}$ является равновесием Нэша. Предположим, что оба игрока выбирают D. Ни один из игроков не добьется большего, отклонившись в одностороннем порядке — если игрок переключается на игру C, он все равно получит 0. Это удовлетворяет требованиям равновесия Нэша. Предположим, что оба игрока выбирают C. Ни один из игроков не добьется большего, отклонившись в одностороннем порядке — если игрок переключается на игру D, он получит 0. Это также удовлетворяет требованиям равновесия Нэша.

Итеративное устранение (или удаление, или удаление) доминируемых стратегий (также называемое IESDS, или IDSDS, или IRSDS) является одним из распространенных методов решения игр, который включает в себя итеративное удаление доминируемых стратегий. На первом этапе все доминируемые стратегии удаляются из пространства стратегий каждого из игроков, поскольку ни один рациональный игрок никогда не будет играть этими стратегиями. Это приводит к новой, меньшей игре. Некоторые стратегии, которые ранее не были доминируемыми, могут быть доминируемыми в меньшей игре. Первый этап повторяется, создавая новую, еще меньшую игру, и так далее.

Этот процесс является допустимым, поскольку предполагается, что рациональность среди игроков является общеизвестным фактом , то есть каждый игрок знает, что остальные игроки рациональны, и каждый игрок знает, что остальные игроки знают, что он знает, что остальные игроки рациональны, и так до бесконечности (см. Aumann, 1976).

• Стратегия с доминированием по максимуму
• Доминирование риска
• Выигрышная стратегия

• Фуденберг, Дрю; Тироль, Жан (1993). Теория игр . MIT Press.
• Гиббонс, Роберт (1992). Теория игр для прикладных экономистов . Princeton University Press. ISBN 0-691-00395-5.
• Гинтис, Герберт (2000). Развитие теории игр . Princeton University Press. ISBN 0-691-00943-0.
• Лейтон-Браун, Кевин; Шохам, Йоав (2008). Основы теории игр: краткое, междисциплинарное введение. Сан-Рафаэль, Калифорния: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1.. 88-страничное математическое введение; см. раздел 3.3. Бесплатно онлайн во многих университетах.
• Рапопорт, А. (1966). Теория игр двух лиц: основные идеи . Издательство Мичиганского университета.
• Курс теории игр Джима Рэтлиффа: стратегическое доминирование
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Многоагентные системы: алгоритмические, игровые и логические основы. Нью-Йорк: Cambridge University Press . ISBN 978-0-521-89943-7.Полный справочник с точки зрения вычислений; см. разделы 3.4.3, 4.5. Можно бесплатно загрузить онлайн.
• «Строгое доминирование в смешанных стратегиях – Теория игр 101». gametheory101.com. Получено 17.12.2021.
• Уотсон Джоэл. Стратегия: Введение в теорию игр . Третье издание. WW Norton & Company 2013.

В данной статье использованы материалы из Dominant strategy на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .